論文メモ The Ubiquitous B-Tree

March 19, 2021

ファイルインデックスのためのデータ構造B木とB木を改良したデータ構造のサーベイであり、とくにB+木に重点がおかれている。 B+木は、全てのキーを葉に置き、キーを隣接リストに入れて、B木が不得手なシーケンシャルなアクセスを改善する。 これにより、定数オーダーの時間と空間の計算量で次の要素へのアクセスにできる。 ランダムな検索、挿入、削除にかかる時間、空間計算量はB木と変わらない。 以降はB木のデータ構造を前提としてB+木の概要を説明する。B木について知りたい場合は、B木のオリジナル論文の解説記事を参照してほしい。

B木とくらべたB+木の特徴は、全てのキーが葉にあり、キーが隣接リストをなす点にある。 以下のFigure 13が示すように、葉より上の構造は、インデックスのみがあることをのぞけばB木と同じ。 btreep

葉にのみキーがあることで、B木の削除が単純になる。 まず、ルート以外のページがもてるキー数の範囲が\(k\)以上\(2k\)以下であり、キーを削除しても範囲に収まるのであれば、キーの置換がおきず、単にキーを削除するだけでよくなる。 キー数が範囲を下回れば、B木同様にunderflow, catenationが必要になる。

挿入と検索はB木とほとんど変わらない。 葉を2分割するときは、B木のように真ん中のキーを昇格させず、キーの複製を昇格し、複製元のキーを右側の葉に置いたままにする。 検索するときは、クエリの値に最も近い右側のポインタを選んで葉に到達するまで木をたどる。

論文をこちらからダウンロードできます。 図は論文から引用されています。