データ構造におけるB+ツリーの削除操作を徹底解説

本記事では、B+ツリーからノード（キー）を削除する方法について詳しく解説します。以下のようなB+ツリーを例に、削除処理の流れを見ていきましょう。

B+ツリーの例：

削除処理の基本ルール

B+ツリーの削除処理は、大きく分けて2つの段階で構成されます。

第一段階は、削除対象の要素を検索することです。この検索戦略は、通常のクエリ（参照）操作と同じ要領で行います。

第二段階では、削除後にツリーの構造を維持するための調整を行います。B+ツリーでは、各ノードは最低でも m/2 個の要素を持つ必要があるというルールがあります。そのため、要素を1つ削除した結果、残りの要素数が規定値を下回る（アンダーフローが発生する）場合には、ノード自身が構造を調整しなければなりません。

さらに、ノード全体が削除された場合には、その子ノード同士が統合されます。統合後のサイズが m と等しくなった場合には、再び2つの部分に分割し、中央値にあたるキーを親ノードへ繰り上げます。

具体例：キー78の削除

例として、キー「78」を削除するケースを考えます。このとき、注目するノードには [75, 77] と [78, 85] という2つの子（葉）が存在します。削除手順は以下の通りです。

1. まず、葉ノードからキー78を削除します。
2. 次に、残ったキー85のコピーを作成します。
3. 作成したキー85を、該当する部分木の新しい区切りキー（親ノードのキー）として設定します。

削除アルゴリズム：BPlusTreeDelete(x, key)

入力： ツリーのルートノード x、および削除するキー key

以下に、B+ツリー削除の擬似コードを示します。

キーはリスト内に存在すると仮定する
ルートノードから開始し、葉ノードに到達するまでキー 'key' との完全一致検索を行う。
探索経路を x1, x2, …, xh とする。
x1 は最初のノード（ルート）、xh は葉ノードである。
各ノード xi は xi+1 の親ノードに相当する。

xh からキー 'key' を持つオブジェクトを削除する。

if h = 1 の場合：
    ノードはルートのみなので、そのまま終了する。

i := h
while xi がアンダーフローしている間、以下を繰り返す：
    if 直近の兄弟ノード s が m/2 + 1 個以上の要素を持っている場合：
        // 再分配（Redistribution）
        s と xi の間でエントリを均等に再分配する。
        再分配に伴い、親ノード xi-1 内のキー k が変更される。
        if xi が非葉ノードの場合：
            k を xi へ引き下ろし、s 内のキーを1つ繰り上げて k の位置を埋める。
        else（葉ノードの場合）：
            k を s 内のキーで単純に置き換える。
        処理を終了する。
    else：
        // 統合（Merge）
        xi を兄弟ノード s と統合し、xi-1 内の対応する子ポインタを削除する。
        if xi が内部ノードの場合：
            以前 xi と s を分割していた xi-1 内のキーを、
            新しく統合されたノードへ引き下ろす。
        else：
            xi-1 内のそのキーを削除する。
        i := i - 1
    end if
done

まとめ

B+ツリーの削除処理では、単にキーを取り除くだけでなく、アンダーフローの検出と、それに対する再分配（Redistribution）または統合（Merge）による木の高さ維持が重要なポイントとなります。兄弟ノードに余裕がある場合は再分配で済ませ、余裕がない場合は親のキーも巻き込んで統合を行う――この判断を繰り返すことで、B+ツリーは常に平衡状態を保ち、効率的な検索性能を維持できるのです。