多分岐探索木の完全ガイド：B木・B+木・B*木の定義・特徴・操作・性能とデータベース・ファイルシステムでの活用
エバープレイ編集部導入 — 「多分岐探索木」とは何か
多分岐探索木（たぶんきたんさくぼく、multi-way search tree）は、各ノードが複数のキーと複数の子ポインタを持つ探索木の総称です。二分探索木（BST）が各ノードで最大2分岐であるのに対し、多分岐探索木は「ファンアウト」（分岐数）が大きく取れるため、特にディスクや大容量ストレージ上のデータ構造として効率的に働きます。代表的な実装にB木（B-tree）、B+木（B+tree）、B*木などがあり、データベースやファイルシステムのインデックスで広く使われています。
基本的な定義と性質
- ノード構造：各ノードは複数のキー（sorted）と、それに対応する子ポインタ（キー数＋1が一般）を持つ。キーは区間分割の役割を果たす。
- 順序性：ノード内のキーは昇順に保たれ、各子ポインタが指す部分木のキーは親ノードの境界キーの範囲に収まる。
- 平衡性（バランス）：B木など多くの多分岐探索木は高さ平衡を保ち、葉ノードはすべて同じ深さにある（または同等の制約がある）。これにより探索経路が制限され、最悪でも対数オーダーの時間で探索できる。
- ノードの許容量：多分岐木の「次数（order, m）」により、各ノードの子ポインタ数は最大m、最小は概ね⌈m/2⌉（根は例外）といった制約がある。
探索アルゴリズム（検索）
検索は根から始め、各ノード内でキーの範囲を線形探索または二分探索で判定して、適切な子ポインタへ進む。内部ノードのキー数が多い場合は二分探索やバイナリサーチを使うことでノード内コストを抑えられる。ディスク志向の実装では、1ノードがディスクブロックに対応するためノードアクセス回数（IO回数）が最重要であり、高いファンアウトにより高さが低くなるためIO回数を減らせる。
挿入（Insert）と分割（Split）
典型的な手順は以下の通りです：
- 挿入位置の葉ノードを探索で特定する。
- 葉に余裕があればキーを挿入して完了。
- オーバーフロー（最大キー数を超える）した場合、ノードを中央で分割し、分割した中央のキーを親ノードへ昇格（promote）させる。
- 親もオーバーフローすれば再帰的に分割し、最終的に根が分割されると木の高さが1増える。
この「分割と昇格」により木の平衡性が保たれ、各操作の平均・最悪時間は木の高さに比例します（平衡B木ならO(log n)）。
削除（Delete）と再分配／結合
削除は挿入よりも複雑です。基本的には削除対象を見つけて削除し、ノードが最小許容量を下回った場合に調整を行います。調整の方法は主に次の二つ：
- 再分配（borrow / rotation）：隣接する兄弟ノードが十分なキーを持っている場合、キーを借りて親の境界キーを適切に入れ替える。
- 結合（merge）：隣接兄弟も最小の場合、兄弟と現在のノードを結合して親の境界キーを下ろし、親のキー数が減ることで伝播的な調整が必要になる場合がある。
最終的に根のキー数が0になれば、根を削除して高さが1減ることもあります。
主な派生とその特徴
- B木（B-tree）：最も基本的な多分岐探索木。ノードの子数は最大m、最小は⌈m/2⌉（根は例外）。すべての葉は同じ深さ。データベースやファイルシステムで広く採用。
- B+木（B+tree）：内部ノードは検索キーのみを持ち、実際のレコード（またはポインタ）は葉にのみ置く。葉ノードは通常双方向リストで連結され、範囲検索が高速。多くのDBMSで採用。
- B*木（B*tree）：分割の代わりに隣接ノードとの再分配を優先し、ノードの平均充填率を高める（例えば最低2/3の充填）。ページ使用効率を改善するための変種。
- 2-3木、2-3-4木：B木の特別なケースで、ノードあたりのキー数が限定される。これらは自己平衡の二分木に対応する理論的モデルとして使われる。
性能解析（時間・空間）
- 時間計算量：平衡な多分岐探索木（B木系）では探索・挿入・削除ともにO(h + node_search_cost)で、hは木の高さ。高さは概ねO(log_{fanout} n)＝O(log n / log fanout)なので、ファンアウトが大きいほど高さは小さくなる。
- ディスクIO最適化：1ノードをディスクブロックと合わせることで1回のディスク読み込みで多数のキーを参照でき、IO回数が減る。これがB木をDBやファイルシステムで使う最大の理由。
- 空間効率：ノードの最小・最大キー数の制約により内部断片化（空き空間）が生じる。B*木のような変種はこれを改善する工夫をしている。
実用上の設計上のポイント
- オーダー（m）の決定：ディスクブロックサイズ、キャッシュライン、レコードサイズに合わせてノードあたりのキー数を決める。通常はディスクページ/ブロックごとに1ノードで、ファンアウトは大きくなる。
- ノード内検索：キー数が多い場合は線形探索より二分探索やSIMD/検索テーブルを使うことが多い。メモリ内部の高性能実装ではキャッシュフレンドリーなレイアウト（例えばEytzingerやB+木の配列表現）も検討される。
- トランザクション／並行処理：DB用途ではロック粒度（ページ単位、ノード単位）やロックフリー手法、コピーオンライト（COW）といった実装上の工夫が重要。並列挿入・削除時の競合回避には複雑な扱いが必要。
- 耐障害性：クラッシュリカバリやログ（WAL）との連携、原子的なページ更新の扱いなど、運用面での設計も重要。
用途と比較
多分岐探索木は次の用途で有用です：
- データベースの二次インデックス、クラスタ化インデックス
- ファイルシステムのディレクトリエントリやメタデータ
- ディスク／SSD上のキー・値ストアや組込みDB
- 範囲検索や順次走査が多いワークロード（B+木が特に有利）
比較対象として、二分探索木（BST）はメモリ内で簡単に実装できるが、データが大きくなると高さが増えやすく（平衡化をしないBSTは最悪O(n)）、ディスクアクセスが増える点で不利です。トライ（Trie）は文字列やプレフィックス検索に強いが、メモリ消費が大きくなる場合があるため用途に応じて選択します。
実装例（概念的疑似コードの要点）
挿入の主要な要点をまとめると：
- 葉へ到達するために内部ノードを降りる。途中で子が満杯なら事前に分割しておく（下に降りる前分割方式）と実装が単純かつ効率的。
- 葉で挿入 → オーバーフロー時は分割 → 親へ中央値を上げる → 必要なら親も分割。
まとめ
多分岐探索木は高いファンアウトとバランス性を利用して、ディスクや大容量メモリ上での探索を効率化する重要なデータ構造です。B木系（B木、B+木、B*木）は実運用における代表的な実装で、データベースやファイルシステムの根幹を支えています。設計ではノードサイズ、キャッシュやディスクブロックとの整合性、並行制御・耐障害性など実装上の工夫が成功の鍵となります。
参考文献
- B木 - Wikipedia（日本語）
- B+ tree - Wikipedia（英語）
- B* tree - Wikipedia（英語）
- 2-3 tree - Wikipedia（英語）
- Database index - Wikipedia（英語）
- GeeksforGeeks: B-Tree (Introduction)（英語）
投稿者プロフィール
