B木（B-Tree）への要素の挿入方法をわかりやすく解説

この記事では、B木（B-Tree）データ構造への要素の挿入方法について詳しく解説します。まず、次のようなB木を例に考えてみましょう。

B木の例

挿入の基本ルール

要素を挿入する際の基本的な考え方は二分探索木（BST）と似ていますが、B木ではいくつかのルールに従う必要があります。各ノードは最大 m 個の子と m−1 個のキーを持つことができます。ノードに新しい要素を挿入する場合、状況は次の2つに分けられます。

• ノード内のキー数が m−1 個未満の場合：新しい要素をそのまま該当ノードに挿入します。
• ノード内のキー数がすでに m−1 個（満杯）の場合：既存のすべてのキーと挿入対象の要素を合わせた集合の中央値（メディアン）を求めます。その中央値を親ノードへ送り上げ、残りのキーを中央値を基準に「左半分」と「右半分」の2つのノードに分割します。親ノードも満杯の場合は、同じ手順を再帰的に繰り返します。

挿入の具体例：79 を挿入する

ここでは、値 79 を上図のB木に挿入する例を見てみましょう。

1. まず79を根（ルート）のキー 56 と比較します。79 の方が大きいため、右端の部分木へ移動します。
2. 次にキー 81 と比較すると、79 の方が小さいため、左側の部分木へ進みます。
3. 到達したノードに 79 を挿入すると、ノード内のキーは [66, 78, 79] の3つになります。
4. このとき中央値は 78 なので、78 が親ノードへ押し上げられます。その結果、根のノードは [78, 81] となり、元のノードのキーは2つのノードに分割されます。一方は 66 を、もう一方は 79 を保持します。

以上の手順により、79 を挿入した後のB木は次のようになります。

アルゴリズム

BTreeInsert(root, key)

入力：木の根（root）と挿入するキー（key）。なお、挿入するキーはまだ木の中に存在しないものと仮定します。

x := 根を読み込む
if x が満杯ならば
    y := 新しいノード
    z := 新しいノード
    x 内の中央のオブジェクト oi を特定し、
    oi より左側のオブジェクトをノード y へ移動する
    oi より右側のオブジェクトをノード z へ移動する
    x がインデックスノード（内部ノード）であれば、
    子ポインタも適切に振り直す
    x->child[1] := y のアドレス
    x->child[2] := z のアドレス
end if

このように、B木の挿入操作は常に木の高さ方向にバランスを保ちながら行われるため、検索・挿入・削除のいずれも O(log n) の時間計算量で実行できるのが大きな特徴です。データベースやファイルシステムのインデックス構造として広く採用されているのも、この性質によるものです。