B木 【B tree】 Bツリー
木構造は単一の根ノードを起点に「親ノードは複数の子ノードを持つことができる」という規則に従ってノードを連結したデータ構造で、根から末端の葉に至るまでに通過する階層の数を「深さ」という。
B木は親が3つ以上の任意の数の子を持つことができる「多分木」で、どの葉の深さもなるべく均等になる「平衡木」としての性質も兼ね備えている。二分木とは異なり、一つのノードに複数の値（キー）が登録される。
各ノードはn個の子ノード（C1～Cn）と、n-1個のキー（K1～Kn-1）を持っている。nの数はノードごとに異なってよいが、最大値は決まっている。キーは昇順（小さい順）に整列（ソート）されており、子ノードへのリンクは各キーの中間にあるとみなされる。C1はK1の左、C2はK1とK2の中間、…CnはKn-1の右といった具合である。
例えば、キーとして自然数を格納できるB木で、根ノードが3つのキー（5,10,15）と4つの子ノード（C1,C2,C3,C4）を持つとき、キー1～4はC1（およびその子孫）に、6～9はC2に、11～14はC3に、16以上はC4にそれぞれ格納される。
この木から「13」を探索したい場合、まず根ノードのキーを探索する。存在しないので、最も近い10と15の間にある子ノードC3をたどってそのキーを調べる。この操作を繰り返し子孫ノードに適用し、途中でキーが見つかれば探索終了となり、葉ノードまで探しても無ければ存在しないことがわかる。
値を挿入するには、探索によって値が存在すべきノードを確定し、キーに空きがあれば登録する。空きが無ければノードを中央のキーで2つに分割する。中央のキーを親ノードに移し、その左右に分割したノードへのリンクを登録する。親のキーもいっぱいの場合は再帰的に上位のノードへ分割処理を繰り返していく。
多数の値を効率よく管理できるため、記憶装置の領域（ブロック）の管理などで広く応用されている。B+木やB*木などの派生構造が考案されており、リレーショナルデータベース（RDBMS）のインデックス管理やファイルシステムのブロック管理などに用いられている。
共有ボタンをタップ