B 木

ウィキペディア

B*木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/28 03:57 UTC 版)

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

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

IEEEカンファレンスICCI '93 (Anestis A. Toptsis 1993)においては B**木の定義も見られた。

参考文献

• Anestis A. Toptsis; Chang, Carl K.; Koczkodaj, Waldemar W.; et.c. (27 May 1993). "B**-tree: a data organization method for high storage utilization". Computing and Information, 1993. Proceedings ICCI '93. Sudbury, Ontaro, Canada: IEEE Computer Society Press. pp. 277–281. ISBN 0-8186-4212-2. OCLC 30738554. 2007年2月17日閲覧。

脚注

[脚注の使い方]

関連項目

• B木
• B+木

外部リンク

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

表 話 編 歴 データ構造
その他	コレクション コンテナ 代数的データ型 素集合データ構造 永続データ構造 並行データ構造
配列構造	配列 可変長配列 ビット配列 接尾辞配列 スタック キュー 両端キュー リングバッファ 疎行列
リンク構造	連結リスト スキップリスト 展開リスト XOR連結リスト 優先度付きキュー
検索構造	連想配列 ハッシュテーブル ハッシュ配列木 ハッシュ関数 コンシステントハッシュ法 分散ハッシュテーブル 連想リスト
木構造	二分木 二分探索木 二重連鎖木 デカルト木 トップ木 T木 平衡二分木 AA木 AVL木 赤黒木 スプレー木 スケープゴート木 ツリープ 2-3木 2-3-4木 フィンガーツリー B木 B+木 B*木 Bx木 UB木 ダンス木 H木 X木 M木 トライ木 基数木 接尾辞木 三分探索木 Cトライ X-fastトライ Y-fastトライ ハッシュ木 BSP木 四分木 八分木 インターバル木 レンジ木 セグメント木 カバー木 メトリック木 BK木 kd木 暗黙k-d木 vp木 R木 R+木 R*木 ヒルベルトR木 優先R木 多重木 多分木 三分木 スパゲッティスタック フェニック木 リンクカット木 フュージョン木 ヴァンエムデボアス木 指数木 SPQR木 PQ木 (a,b)木 ヒープ 二分ヒープ 三分ヒープ D分ヒープ 二項ヒープ 2-3ヒープ Beap フィボナッチヒープ 左翼ヒープ ペアリングヒープ 傾斜ヒープ ソフトヒープ ウィークヒープ
グラフ構造	有向グラフ 有向非巡回グラフ 二分決定グラフ ハイパーグラフ 有向非巡回ワードグラフ
抽象データ型	リスト キュー スタック セット マップ マルチセット マルチマップ クラス
カテゴリ

この項目は、ソフトウェアに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

• 表示
• 編集

B+木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/28 00:30 UTC 版)

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つとして、ブロックをサブブロックに分け、サブブロック単位で圧縮することが考えられる。この場合、要素の挿入や削除ではブロック全体ではなくサブブロックだけを解凍し再圧縮すればよい。また、圧縮率がブロックによって異なると、格納できる要素数も大きく異なってくるという問題もある。

関連項目

• 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)

実装

• Interactive B+ Tree Implementation in C
• Memory based B+ tree implementation as C++ template library
• Stream based B+ tree implementation as C++ template library
• Open Source JavaScript B+ Tree Implementation
• Perl implementation of B+ trees
• Java/C#/Python implementations of B+ trees
• File based B+Tree in C# with threading and MVCC support
• JavaScript B+ Tree, MIT License
• JavaScript B+ Tree, Interactive and Open Source

B木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/05 03:42 UTC 版)

B木
種類	木構造
発表時期	1970
発明者	Rudolf Bayer, Edward M. McCreight
ビッグオー記法による計算量 (en)
アルゴリズム 平均 最悪の場合 空間 O(n) O(n) 探索 O(log n) O(log n) 挿入 O(log n) O(log n) 削除 O(log n) O(log n)

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

実システムでも多用されており、データベース管理システムの多くは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個だけ持っている。

参考文献

• 奥村, 晴彦 『C言語による最新アルゴリズム事典』技術評論社〈ソフトウェアテクノロジー13〉、1991年、316-323頁。ISBN 4-87408-414-1。 NCID BN06103373。 

• Donald E. Knuth 『The Art of Computer Programming』Volume 3 Sorting and Searching Second Edition 日本語版、有澤誠・和田英一監訳、石井裕一郎ほか訳、株式会社アスキー、2006年、ISBN 4-7561-4614-7。

関連項目

• B+木
• B*木
• kd木
• R木
• スプレー木
• 基数木
• 2-3 フィンガーツリー

外部リンク

• Ｂ木の普遍性について（英語）(2012年12月15日にアーカイブ)