論文メモ The Ubiquitous B-Tree
March 19, 2021B木とその派生データ構造のサーベイ論文で、とくにB+木に重点がおかれている。 B+木は、全てのキーを葉におき、葉を隣接リストでつなぐことで、B木が不得手なシーケンシャルなアクセスを改善する。 これにより、定数オーダーの時間と空間計算量で逐次的にキーにアクセスにできる。 ランダムな検索、挿入、削除にかかる時間、空間計算量はB木と変わらない。 以降はB木のデータ構造を前提としてB+木の概要を説明する。B木について知りたい場合は、B木のオリジナル論文の解説記事を見てほしい。
B木とくらべたB+木の特徴は、全てのキーが葉にあり、葉が隣接リストでつながれている。
以下のFIGURE 13が示すように、葉より上の構造は、インデックスのみがあることを以外はB木にひとしい。
葉だけにキーをおくことで、計算量が減るだけでなく、B木の削除を単純にできる。 まず、ルート以外のページがもてるキー数の範囲がB木の制約である\(k\)以上\(2k\)以下であり、キーを削除しても範囲に収まるのであれば、キーの置換がおきず、単にキーを削除するだけでよくなる。 キー数が範囲を下回れば、B木同様にunderflow, catenationが必要になる。
挿入と検索はB木とほぼ変わらない。 葉を2分割するときは、B木のように真ん中のキーを昇格させず、キーの複製を昇格し、複製元のキーを右側の葉に置いたままにする。 検索のときは、クエリの値に最も近い右側のポインタを選んで葉に到達するまで木をたどる。
論文をこちらからダウンロードできます。 図は論文から引用されています。