B木の削除操作を漫画で解説：葉ノード・内部ノード・マージのパターン

約 8 分で読めます

以前の記事「B木とは？DBインデックスに使われる理由を図解で解説」では、B木がどのように木の高さを低く抑えているかを解説しました。挿入時のノード分割はイメージしやすい一方、B木の削除操作は「削除するキーが葉ノードにあるか、内部ノードにあるか」で手順が変わり、最初は戸惑いやすいポイントです。今回は、若手メンバーとのやり取りを漫画形式で再現しながら、削除のパターンを整理していきます。

B木の削除、パターンはいくつある？

生徒がB木のキー25の削除方法を先生に質問する漫画。次数のB木の図とともに、削除操作の選択肢として前すくい・後ろすくい・マージ・単に削除するの4択が示されている

キー「25」を削除する問題を例に、削除操作の選択肢として次の4つが挙がっています。

  • A. 前すくい: 前の兄弟ノードからキーを借りてくる
  • B. 後ろすくい: 後ろの兄弟ノードからキーを借りてくる
  • C. マージ: 兄弟ノードと統合する
  • D. 単に削除する: そのままキーを取り除く

図の25は葉ノード [20, 25, 28, 30] に含まれており、削除してもキー数が最小値を下回らないため、正解は D. 単に削除する です。ただし、これは「たまたま単純なケースだった」だけで、削除対象のキーがどこにあるか・削除後にキー数が最小値を下回るかによって、適切な操作は変わります。

削除の3パターンを整理する

B木の削除操作を3パターンに分けて解説する漫画。葉ノードの単純削除、内部ノードを後続値または前の値で置き換える方法、兄弟が少ない場合のマージ操作をそれぞれ図解している

漫画の中で整理されている通り、B木の削除は大きく3つのパターンに分類できます。

① 葉ノードのキーを削除する場合

削除したいキーが葉ノードにあり、削除後もそのノードのキー数が最小値（⌈m/2⌉ - 1個など、木の次数による）を満たしていれば、単純にそのキーを取り除くだけで済みます。図の例では、キー「25」を葉ノード [20, 25, 28, 30] から取り除いても3個のキーが残るため、これだけで完了です。

② 内部ノードのキーを削除する場合

削除したいキーが内部ノード（子を持つノード）にある場合、そのキーを単純に取り除くと木の構造が崩れてしまいます。そこで、次のどちらかの値で置き換えます。

  • 後続の値（successor）: 削除するキーの右部分木の中で最小のキー
  • 前の値（predecessor）: 削除するキーの左部分木の中で最大のキー

漫画の例では、内部ノードのキー「30」を削除する際に、後続の値と前の値のどちらでも置き換えが成立することが示されています。後続・前値のどちらを使っても木の順序（大小関係）は保たれるため、実装によってどちらを採用するかが決まります。

置き換えた後は、置き換え元のキー（後続値または前値）自体を、それが元々あった葉ノードから改めて削除する必要があります。つまり内部ノードの削除は、「値の置き換え」＋「葉ノードでの削除」の2段階になる点がポイントです。

③ 兄弟が少ない場合のマージ

葉ノードや内部ノードからキーを削除した結果、そのノードのキー数が最小値を下回ってしまう場合があります。このとき、まず隣接する兄弟ノードから借用（前すくい・後ろすくい）を試み、それも難しい場合は兄弟ノードとマージします。

漫画の例では、あるノードのキー数が最小値を下回った結果、隣接ノードとキーがマージされる様子が描かれています。マージによってノードが1つ減るため、親ノードのキーも巻き込んで再調整が必要になることがあり、最悪の場合はルートまで調整が伝播します。

なぜこんなに複雑な手順になるのか

B木の削除が複雑なのは、「すべての葉ノードが同じ深さを保つ」というB木の性質を、削除後も維持し続ける必要があるためです。単純に削除するだけでは、この性質が崩れて木のバランスが失われ、以前の記事で説明した「木の高さを低く保つ」というB木の最大のメリットが失われてしまいます。

漫画の重要ポイントをまとめると、次のようになります。

  • B木の削除は「葉ノード」「内部ノード」で手順が異なる
  • 内部ノードは「後続値」または「前の値」で置き換える
  • 兄弟が少ない場合は「マージ」が発生する
  • 削除後は、B木の性質（各ノードのキー数の範囲）を必ず満たすように調整する

実務・試験対策での活かし方

実務でB木の削除アルゴリズムを自分で実装する機会は多くありませんが、DBのインデックスメンテナンスやストレージエンジンの内部動作を理解するうえで、この削除ロジックを知っておくと役立ちます。例えば、大量データの削除処理の後にインデックスの再構成（REINDEXなど）が推奨される場面がありますが、これは削除によってノード（ページ）内のキー利用率が下がり、ディスク上のページ利用効率が落ちていくことが主な理由です。B木自体はマージ・借用によって常にバランス条件（各ノードのキー数の範囲）を満たすよう調整されますが、それでも削除が繰り返された領域はページの詰まり方が疎になりやすい、という点は押さえておくとよいでしょう。

応用情報技術者試験では、擬似言語やトレース問題として「あるB木からキーを削除した後の木構造を選べ」という出題が定番です。今回のように、①葉ノードか内部ノードか、②削除後にキー数が最小値を満たすか、の2段階で判断する流れを押さえておくと、初見の木構造でも落ち着いて手順を追えるようになります。自分もB木の削除を初めて学んだときは手順の多さに戸惑いましたが、「性質を保つための調整」という目的から逆算して考えると、各操作の必然性が見えてきます。

まとめ

B木の削除操作は、削除対象が葉ノードか内部ノードかで手順が分岐し、さらに削除後のキー数が最小値を下回る場合はマージによる調整が必要になる、という複数パターンを持つ操作です。一見複雑に見えますが、「すべての葉ノードの深さを揃える」というB木の性質を保つための調整だと理解すれば、手順を丸暗記しなくても対応できるようになります。挿入時のノード分割とあわせて、削除時のマージ・借用のロジックも押さえておくと、試験対策はもちろん、DBインデックスの内部動作を説明する際の説得力も増すはずです。

関連記事