IT用語辞典バイナリ

B木

読み方：ビーき
【英】B tree

B木とは、データ構造を枝分かれした図で表したツリー構造のモデルのひとつで、データの分岐（枝分かれした「葉」）の先がすべて同一の階層に属しているような構造モデルのことである。

B木では、葉を除いた全ての節が一定数以下の分岐（枝）をもち、その先が分岐した元の枝よりも少ない分岐を持っている。B木はBerkeley DBなどのデータベースシステムにおいてデータ構造の形式に採用されている。

情報処理のほかの用語一覧

アルゴリズム：

エイトクイーン問題  枝  親  B木  FIFO  バックトラック法  ハッシュ法

>>アルゴリズムカテゴリの他の用語

ウィキペディア

B木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/01/26 04:50 UTC 版)

B木（びーき）は、コンピュータサイエンスにおけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。

実システムでも多用されており、データベースマネージメントシステムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木やB*木を使うことが多い）。

構造

B木の例

多分岐の平衡木(バランス木)である。1 ノードから最大 m 個の枝が出るとき、これをオーダー m のB木という。後述する手順に従って操作すると、根と葉を除く「内部ノード」は最低でも m /2 の枝を持つことを保証できる。

各ノードは、枝の数 - 1 のキーを持つ。枝₁ ～ 枝_m と キー₁ ～ キー_{m -1} を持つとき、枝_i には キー_{i -1} より大きく キー_i より小さいキーだけを保持する（キーの重複を許す場合はどちらかに等号をつける）。

葉ノードの定義は文献によって違いが見られる。木の終端をヌルポインタのような特殊な値で表す場合、枝がすべて終端記号となっているノードを葉とする。これに対して一部の文献では、終端を表すためにキーが0個のノードを連結し、このノードを葉と定義している。すなわち、後者の定義における葉ノードの親が、前者の定義における葉ノードとなる。後者の定義をとる文献では「葉ノードはキーを持たない」ということになる。以下の記述では、前者の定義に従うものとする。

ノードはページと呼ばれることもある。特にハードディスクドライブなどの外部記憶装置を使ってB木を実現する場合によく見られる。この場合、各ノード（ページ）のサイズが、外部記憶装置のブロックサイズの整数倍になるようにオーダーを調整することが多い。

B木の中でも特に、オーダー3のものを2-3木、オーダー4のものを2-3-4木と呼ぶ。

操作

検索

実装例を以下に示す。ここでは簡単のため、ノードの中を探索するのに線形探索を使っているが、ノードに含まれるキーの数が多い場合には二分探索を使うことで高速化できる可能性がある。

1. 根を対象ノードとして検索を開始する
2. 対象ノードが存在しない場合は検索値が木に登録されていないものとして終了
3. i = 1
4. キー_i が存在しないか、検索値 < キー_i の場合、枝_i が指すノードを対象として2へ
5. 検索値 = キー_i の場合、検索成功として終了
6. i = i + 1 として4へ

挿入

B木におけるノードの分割

検索の処理を行うことで、挿入しようとする値が木のどこに位置するべきかがわかる。まだ登録されていない値を検索した場合、処理は必ず葉ノードまで達する。すなわち、挿入処理は常に葉ノードを対象として開始される。ノードにまだ新たなキーを登録する余地がある場合、キーを追加して挿入処理は終了する。

問題は、対象となるノードが既に許容できる最大数のキーを持っている場合である。この場合、ノードの分割処理を行う。分割が必要なノードからキーをひとつ選択し（通常、大小順で中央の値を選択する）、このキーより小さいキーだけを含むノードと、より大きいキーだけを含むノードに分割する。分割の基準となったキーは、親のノードに移動する。

ここで、親ノードに対してキーを追加している。親ノードでキーの最大数を越えた場合は、根に向かって順に分割処理を適用していく。根まで到達して根が分割された場合は、木の高さが1段増加することになる。分割直後の新しい根は、キーを1個と枝を2個だけ持っている。

関連項目

• B+木
• B*木
• kd木
• R木
• スプレー木
• 基数木

参考文献

• R. Bayer and E. McCreight. "Organization and Maintenance of Large Ordered Indexes," Acta Informatica, 1, 1972.
• Donald E. Knuth 『The Art of Computer Programming』Volume 3 Sorting and Searching Second Edition 日本語版、有澤誠・和田英一監訳、石井裕一郎ほか訳、株式会社アスキー、2006年、ISBN 4-7561-4614-7。
• 奥村晴彦 『C言語による最新アルゴリズム事典』 技術評論社<ソフトウェアテクノロジー13>、平成3年（1991年）、ISBN 4-87408-414-1。

外部リンク

• Ｂトリーの普遍性について（英語）

---

B*木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2011/10/10 05:56 UTC 版)

B*木（英: B*-tree）は、B木から派生した木構造の一種で、HFS や Reiser4 ファイルシステムで使われている。根ノード以外のノードは、B木のように1/2ではなく、2/3まで埋まった状態になる。このため、ノードがいっぱいになったとき即座に分割するのではなく、キーを次のノードと共有する。連続する2つのノードがいっぱいになると、それを3つのノードに分割する。また、常に左端のキーは使わずに残しておく。一般に総称して「B木」と呼ばれることが多く、「B*木」と呼ばれることは滅多にない。

B*木とB+木は異なる。後者は、葉ノードが連結されて連結リストを構成するようになっているものである。B+木は、挿入のコストを増大させて、検索を効率化したものである。

IEEE 0-8186-4212-2 1993 には B**木の定義も見られた。

関連項目

• B木
• B+木

外部リンク

• Dictionary of Algorithms and Data Structures entry for B*-tree

---

B+木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2011/11/26 15:20 UTC 版)

簡単なB+木の例。1から7のキーとデータ値 d₁-d₇ がリンクされている。赤で示された連結リストによって順序通りの素早い走査が可能

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 _bn)
• 1つのレコードを探すのに要する操作回数は最悪で O(log _bn)
• 位置がわかっているレコードの削除に要する操作回数は最悪で O(log _bn)
• 範囲クエリで k 個の要素が見つかる場合、要する操作回数は最悪で O(log _bn + 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つとして、ブロックをサブブロックに分け、サブブロック単位で圧縮することが考えられる。この場合、要素の挿入や削除ではブロック全体ではなくサブブロックだけを解凍し再圧縮すればよい。また、圧縮率がブロックによって異なると、格納できる要素数も大きく異なってくるという問題もある。

歴史

B+木が初めて記述されたのは、Rudolf Bayer と Edward M. McCreight の論文 Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972) である。

関連項目

• B木
• B*木
• NTFS
• データベース
• 2分探索木
• JFS
• ReiserFS

外部リンク

• Study notes for B+ Trees - Insertion and Deletion
• Dr. Monge's B+ Tree index notes
• Link to how BTrees work
• Evaluating the performance of CSB+-trees on Mutithreaded Architectures
• Effect of node size on the performance of cache conscious B+-trees
• Fractal Prefetching B+-trees
• Towards pB+-trees in the field: implementations Choices and performance
• Cache-Conscious Index Structures for Main-Memory Databases (PDF)

実装

• Open Source C++ B+ Tree Implementation
• B+ tree implementation as C++ template library
• Perl implementation of B+ trees
• java/C#/python implementations of B+ trees
• B+Tree Java SortedMap Implementation