B+木

B+木（英: B+ tree）は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント（「ブロック」などと呼ばれる。木構造におけるノードに相当）にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層（葉ノード）に格納され、内部ノードにはキーのみが格納される。

B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ $b$ の記憶装置があるとき、 $b$ の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い（2分探索木はブロック型でない記憶装置に適している）。

ReiserFS（UNIX、Linux）、XFS（IRIX、Linux）、JFS2（AIX、OS/2、Linux）、HammerFS（DragonFly BSD）、NTFSといったファイルシステムはいずれもB+木に類する構造をブロックのインデックス付けに使っている。関係データベースでも表のインデックスにこの種の木構造を使っていることが多い。

詳細

B+木の次数は木構造内のノードの容量の尺度である。次数を d としたとき、d <= m <= 2 d となるような m が各ノードのエントリ数となる。例えば、次数7のB+木があるとき、根ノード以外の内部ノードは7個から14個のキーを格納する。根ノードは1個から14個のキーを格納する。

さらに各内部ノードは、最低でも d+1 個、最高でも 2d+1 個の子ノードを持つ。

探索

レコード r を探索するアルゴリズムは、葉ノードに到達するまで正しい子ノードへのポインタを辿っていく。そして、その葉ノード内を調べて、求めているレコードを探す（見つからない場合は失敗となる）。

 function search(record r)
   u := 根ノード
   while (u は葉でない) do
     そのノード内の正しいポインタを選択
     ポインタを辿った先の最初のノードに移動
     u := 現在のノード
   scan u for r

この擬似コードは反復がないと仮定している。

特徴

次数 b、高さ h のB+木には以下の特徴がある。

格納できる最大レコード数は $n=b^{h}$
最小キー数は $2(b/2)^{h-1}$
この木構造を格納するのに要する領域は $O(n)$
1つのレコードの挿入に要する操作回数は最悪で $O(\log _{b}n)$
1つのレコードを探すのに要する操作回数は最悪で $O(\log _{b}n)$
位置がわかっているレコードの削除に要する操作回数は最悪で $O(\log _{b}n)$
範囲クエリで k 個の要素が見つかる場合、要する操作回数は最悪で $O(\log _{b}n+k)$

他のデータ構造との関係

B+木（および他のB木やその派生）は(a,b)-木を特殊化したものである（(a,b)-木は最大と最小を a と b というように明示的に指定した木構造）。

B+木はB木から派生したもので、B木は内部ノードにもキーとレコードを格納できる。また、ある意味ではB木がB+木を特殊化したものと見ることもできる。

B#木はB+木にさらに制限を加えたものである。

実装

B+木の葉ノードは連結リストで相互にリンクされていることが多い。これにより範囲クエリが簡単かつ効率的に行える（上述の上限は連結リストがなくとも実現できる）。これによって領域消費量が大幅に増えたり、手間が大幅に増えるということはない。

記憶装置のブロックサイズが B バイトの場合、格納されるキーのサイズを k バイトとすると、最も効率的なB+木では $b=(B/k)-1$ となる。理論的には1を引く必要はないが、実際にはインデックスブロックには何らかの余分な空間が必要になることが多い（例えば、葉ブロックでの連結リスト用参照）。インデックスブロックがその記憶装置の実際のブロックより若干大きい場合、性能は大幅に低下する。

B+木のノードが配列として構成される場合、挿入や削除で配列の要素をずらす必要が生じ、性能が悪くなる。そのため、ノード内の要素は2分木やB+木で構成するのが望ましい。

B+木はメモリ上のデータ格納にも使われる。その場合、ブロックサイズはプロセッサのキャッシュラインに合わせるのがよい。ただし、キャッシュのプリフェッチ機能がある場合、キャッシュラインの何倍かをブロックサイズとした方が性能がよいことが研究で証明されている^[要出典]。

B+木の空間効率は、ある種の圧縮技法を使うことで改善できる。例えば、各ブロックに格納するキーに差分符号化を施すことが考えられる。内部ブロックの場合、領域を節約するにはキーかポインタを圧縮すればよい。文字列キーの場合、領域を節約するには次のようにする。通常、内部ブロックの i 番目のエントリには i+1 番のブロックの最初のキーが格納されている。キー全体を格納する代わりに、直前のｉ番目のブロックの最後のキーよりも確実に大きいとわかる、i+1 番のブロックの最初のキーの最短のプレフィックスを格納する。ポインタにも簡単な圧縮方法がある。いくつかのブロックが連続する位置に順に配置されている場合、先頭ブロックへのポインタと連続するブロック数を格納すればよい。

上述の圧縮技法にはいずれも何らかの問題が存在する。まず、1つの要素を取り出すにはブロック全体を解凍する必要がある。この問題への対処の1つとして、ブロックをサブブロックに分け、サブブロック単位で圧縮することが考えられる。この場合、要素の挿入や削除ではブロック全体ではなくサブブロックだけを解凍し再圧縮すればよい。また、圧縮率がブロックによって異なると、格納できる要素数も大きく異なってくるという問題もある。

歴史

外部リンク

実装

詳細

探索

特徴

他のデータ構造との関係

実装

歴史

関連項目

外部リンク

実装