B木（B-tree）とは？データベースインデックスの仕組み・B+木／B*木の違いと実装ポイント
エバープレイ編集部B木とは — 概要
B木（B-tree）は、ディスクやその他の二次記憶装置上で大量のデータを効率よく検索・挿入・削除するために設計された平衡木（平衡探索木）の一種です。1970年代に登場して以来、データベース管理システム（RDBMS）やファイルシステムなどで事実上の標準として広く使われています。B木は「ノードの高さが小さく、各ノードが多数の子を持てる」点が特徴で、これによりディスクI/O回数を減らして高速化を図ります。
基本的な定義と性質
B木はさまざまな表現がありますが、ここでは一般的な「次数 m（order m）」での定義を示します。
- 各内部ノードは最大で m 個の子（children）を持ち、最小で ceil(m/2) 個の子を持つ（根を除く）。
- 各ノードは子の数 − 1 個のキー（keys）を保持する。したがって、最大のキー数は m−1、最小は ceil(m/2) − 1 となる。
- すべての葉（external nodes）は同じ深さ（高さ）にあり、木は常に平衡である。
- ノードは一つの単位（通常はディスクページやメモリページ）として読み書きされることを前提に設計されることが多い。
別の表現として CLRS（導入アルゴリズム）で用いる最小次数 t（minimum degree）というパラメータがあります。ここでは各ノードは少なくとも t−1 個、多くとも 2t−1 個のキーを持つという定義になります（t ≥ 2）。どちらの定義も本質は同じで、ノードの最大・最小のキー数で木の分岐と高さを制御します。
なぜ B木が高速なのか（ディスク指向設計）
主な利点はノードの高い分岐率（branching factor）により木の高さが非常に低く保たれることです。ディスクI/Oは高コストなので、1回のノード読み出しに多くのキー／子ポインタを詰め込めれば、必要なディスクアクセス回数（＝ノード訪問回数）を減らせます。実際の実装では「1ノード＝ディスクブロックサイズ（ページサイズ）」となるようにノードサイズを調整するのが一般的です。
探索（検索）
探索は通常の多分岐探索木の手続きに似ています。あるノードに対して保持しているキー列を二分探索（または線形探索）で位置を決め、該当する子ポインタに進みます。高さ h の木では、ディスクI/O回数は O(h)、計算量は O(h · log k)（k はノード内のキー数、二分探索を使うと log k）になります。一般に h = O(log_{⟨branching⟩} n) なので探索は O(log n) 時間です。
挿入（Insert）
挿入は次の手順で行われます（CLRS に準じた典型的な方法）：
- 挿入位置の葉ノードを探索する。
- 葉ノードに空きがあればキーを挿入して終了。
- もしそのノードが満杯（最大キー数）なら、ノードを分割（split）する。分割では中央値のキーを親に昇格させ、左右にノードを分ける。
- 親が満杯であれば再帰的に分割を行い、最終的に根が分割されると木の高さが1増える。
分割は局所的な操作で、木全体の再編成を必要としないため、挿入の平均的／振る舞い上のコストは効率的です。ディスクベースでは分割時に2ページの書き出し＋親の更新が必要になり、I/Oを最小化するために遅延書き込みやバッファリングが使われます。
削除（Delete）
削除は挿入よりやや複雑です。キーが内部ノードにある場合、前駆（predecessor）または後継（successor）のキーと交換して実際には葉から削除することが多いです。削除後にノードのキー数が最小を下回ると、次の2つの手段を用います。
- 隣接兄弟ノードからキーを借りる（rotating / borrowing） — 兄弟に余裕がある場合。
- 借りられない場合は兄弟と合併（merge）して親からキーを下降させ、木を短くする。
合併は親のキーを消費するため、親が最小を下回れば再帰的に上へ処理が及び、最悪では根が1つの子だけになることで木の高さが1減ります。
B+木、B*木などの派生
実運用では B木 の派生形が多用されます。代表的なものを挙げます。
- B+木：内部ノードは索引（キーと子ポインタ）だけを持ち、実際のレコードはすべて葉ノードにのみ格納されます。葉ノード同士は連結リストでつながっており、レンジ検索が非常に効率的です。多くのDBMSやファイルシステムは B+木を採用しています。
- B*木：分割時の扱いを工夫してノードの充填率を高めるバリエーション。分割の前に兄弟との再分配（redistribution）を試み、それでも駄目なら分割する（通常は更に隣接要素を巻き込んで 2 分割ではなく 3-way-ish の再配置を行う）。これにより平均充填率が向上します。
- その他：CSB+-tree、LSM-tree（用途が異なる）など、要件に応じた多くの変種があります。
時間計算量とディスクI/O
B木に関する代表的な計算量は次の通りです（n を木中のキー数、m をノードの最大子数とする）：
- 探索（search）：O(h) のノード訪問、すなわち O(log_m n)。各ノード内のキー探索は二分探索で O(log m) なので合計 O(log n)。
- 挿入／削除：探索に加えて局所的な分割・合併を行う。分割や合併はノード単位で行われるため、ディスクI/Oコストは O(h) に近いが、平均的な追加コストは定数時間に抑えられる（振る舞い上の解析で amortized O(1) の分割/合併回数とされることが多い）。
重要なのは「ノードあたり多くのキーを入れることで h が小さくなり、結果としてディスクアクセス回数が劇的に減る」点です。実装ではノードサイズをページサイズ（例：4KB、8KB）に合わせることが一般的です。
実装上の考慮点
- ノードレイアウト：キー配列と子ポインタ配列の配置、サイズ、アライメントを慎重に設計する。可変長キー（文字列など）はオフセットテーブルを用いる場合が多い。
- ページサイズ選定：1ページにできるだけ多くのキーを詰めることが性能に直結するが、ページ内操作（挿入・削除時のデータ移動）とのトレードオフがある。
- キャッシュとバッファプール：頻繁に使う内側のノードはメモリに常駐させ、I/Oを抑制する。DBMSではバッファプール管理が重要。
- 並行制御：複数スレッド／トランザクションからの同時アクセスに対してはラッチ（軽量ロック）やロックカップリング（crabbing）、さらに細粒度ロックやMVCCと組み合わせた手法が使われる。
- クラッシュ回復：ノード分割や更新時に中途半端な状態でクラッシュすると一貫性が壊れるため、WAL（Write-Ahead Logging）やジャーナリングを組み合わせる。
- 一括ロード（bulk loading）：大量データを一度に作る場合、順序付き挿入を使った高速な構築アルゴリズムを用いることで効率化できる。
適用例と実際の利用
B木・B+木は次のような用途で広く採用されています：
- データベースのインデックス（B+木が多数派）。範囲検索や順序取得が効率的。
- ファイルシステム（ディレクトリやinodeの索引など）。例：HFS+、NTFS、Btrfs など（実装により変種を利用）。
- 組み込みデータベースやキー・バリュー・ストアの内部構造（SQLite の B-tree 実装など）。
実装例として SQLite の B-tree ドキュメントや、MySQL / InnoDB のインデックス構造、PostgreSQL の B-tree 実装ドキュメントを参照すると、現実的な実装上の工夫（ページ分割の閾値、再平衡の手法、遅延書き込み戦略など）が学べます。
よくある誤解
- 「B木は必ず B+木 と同じ」：B木とB+木は異なる構造です。B+木は葉にデータを集約し、範囲検索に有利です。
- 「B木は常に最適」：ワークロードによっては LSM-tree のような書き込み重視の構造の方が有利な場合があります（例：大量のランダム書き込みや高頻度の小さな更新）。
- 「ノードサイズを大きくすればよい」：確かにノードを大きくするほど高さは低くなるが、ノード内操作の費用やキャッシュ効率、分割コストなどのトレードオフがある。
まとめ（運用の勘所）
B木はディスク志向の平衡木として、低い高さと局所的な再構成により大規模データの検索・更新を高速化します。実装ではノードサイズの決定、キャッシュ戦略、並行制御、クラッシュ回復との統合が性能と信頼性を左右します。用途や負荷特性（読み込み中心か書き込み中心か、レンジ検索の頻度など）を見極めて、B木（あるいはB+木／B*木／別アプローチ）を選択することが重要です。
参考文献
- B木 — Wikipedia（日本語）
- SQLite: The B-Tree Storage Engine — sqlite.org
- MySQL Internals: Storage Engine and Indexes（MySQL ドキュメント）
- Douglas Comer, "The Ubiquitous B-Tree"（論文・解説、参考資料）
投稿者プロフィール
