B+木への挿入操作をわかりやすく解説｜ノード分割とアルゴリズムの手順

この記事では、B+木（B+ツリー）への挿入操作の方法について、具体例を交えながら解説します。

B+木の例

まず、次のようなB+木を例として考えます。

挿入の基本ルール

要素を挿入する際の基本的な考え方は、B木と非常によく似ています。最大のポイントは以下の通りです。

• 新しく挿入される要素は、必ず葉ノードに格納される
• もし同じキーが内部ノード（索引ノード）に既に存在する場合でも、そのキーは葉ノードにも自分自身の右側として重複して存在する

挿入例：65 を追加する場合

ここでは、値「65」をこの木に挿入するケースを見てみましょう。

65 は 60 より大きく、75 より小さいため、中央の部分木に挿入されることになります。まず、キー 63 の直後に 65 が挿入されますが、これにより該当ノードが許容上限を超えるため、ノードは 2つに分割されます。

分割の結果、65 は親レベルへ送られる（プッシュアップ／コピーアップ）と同時に、葉ノード側にもコピーして残ります。これがB木との大きな違いです。

以下が、65 を挿入した後のB+木の状態です。

挿入アルゴリズム

ここからは、B+木への挿入を擬似コードの形で整理します。

BPlusTreeInsert(root, key)

入力： 木の根ノード root と、挿入するキー key

前提：挿入するキーはリスト内にまだ存在しないものと仮定する

1. 根ノードから開始し、葉ノードに到達するまで
   キー 'key' との完全一致探索を行う。
   探索経路を x₁, x₂, …, x_h とする。
   （x₁ は根ノード、x_h は葉ノード。
     各ノード xᵢ は xᵢ₊₁ の親にあたる）

2. キーが 'key'、値が v である新しいオブジェクトを
   葉ノード x_h に挿入する。

3. i := h とし、以降はオーバーフローの解消処理：

   while xᵢ がオーバーフローしている間、繰り返す：

     a. xᵢ を 2つのノードに分割する。
        大きい方半分のキーを新しいノード p へ移動する。

     b. xᵢ が葉ノードの場合、
        p を葉ノード間の連結リストにリンクする。

     c. 親レベルに挿入すべきキー k と、
        p を指す子ポインタを決定する。

        ・xᵢ が葉ノードの場合 → 「コピーアップ」
          p 内の最小のキーを k として親にコピーする。

        ・xᵢ が非葉ノードの場合 → 「プッシュアップ」
          p 内の最小のキーを k として親ノードへ移動する。

     d. if i = 0 then
          新しいインデックスノードを作成して新しい根とし、
          そこにキー k と 2つの子 xᵢ および p を格納する。
          return
        else
          キー k と p を指す子ポインタを
          ノード xᵢ₋₁ に挿入する。
          i := i − 1
        end if

   done

まとめ

B+木への挿入では、「常に葉ノードに挿入する」「オーバーフロー時にノードを分割する」「葉か内部ノードかでコピーアップ／プッシュアップを使い分ける」という3つのポイントが重要です。特に、葉ノードでは最小キーのコピーを親に残す一方、内部ノードではキーを移動させる点が、検索効率の高いB+木の構造を支えています。