B 木

2025年10月21日

B 木

英語表記: B-Tree

概要

B木は、主にデータベース管理システム（DBMS）やファイルシステムにおいて、ハードディスクなどの外部記憶装置に格納された大量のデータを効率的に検索・管理するために設計された、特殊なツリー構造です。データ構造（リスト, スタック, キュー, ツリー）という大きな分類の中で、このB木は一つのノードが多数の子ノードを持つことを許容する「多分木」の一種として位置づけられます。そして、常に木のバランスを保ち、深さを最小限に抑える「平衡木」の特性を持つことが、他の一般的なツリー構造との決定的な違いであり、この点が「特殊木」として分類される所以なのですね。

詳細解説

1. 存在意義と多分木の役割

B木が誕生した最大の目的は、ディスクI/O（入出力）の回数を最小限に抑えることです。CPUの処理速度に比べ、ディスクへのアクセスは非常に時間がかかります。もしデータがディスク上のあちこちに散らばっていると、検索のたびにディスクを何度も読み込まなければならず、パフォーマンスが著しく低下してしまいます。

そこでB木では、ノードのサイズをディスクが一度に読み込むことができるブロックサイズ（通常、数KB程度）に合わせて設計します。これが「多分木」であることの核心です。一般的な二分探索木（Binary Search Tree）では、ノード一つが保持できるキーは一つですが、B木ではノード一つに多数のキーとポインタを格納できます。これにより、木全体の高さ（深さ）が極端に浅くなります。

2. 主要コンポーネントと動作原理

B木のノードは、以下の要素で構成されています。

キー（Key）: 実際に検索対象となるデータやインデックス値です。ノード内では昇順に並べられます。
ポインタ（Pointer）: 子ノードを指し示すアドレス情報です。キーの数よりも一つ多く存在します。
次数（Order, M）: B木の構造を決定する重要なパラメータで、ノードが持つことができる最大の子ノード数（または最大キー数）を定義します。この次数が大きいほど、木はより広く、より浅くなります。

検索（探索）の仕組み

B木での検索は、ルートノードから目的のキーを見つけるまで階層を降りていきます。ノード内では線形探索や二分探索が行われますが、重要なのは「ノードを一つ読み込む＝ディスクアクセス一回」とみなせる点です。木が浅ければ浅いほど、検索に必要なディスクアクセス回数が少なくなり、結果として高速なデータ取得が可能になるわけです。これは本当に効率的で、データベースの性能を支える土台となっています。

挿入と平衡化（特殊木の特性）

B木が「特殊木」として機能するのは、データの挿入や削除が行われた際に、自動的にバランスを維持する仕組みがあるからです。

挿入: 新しいキーを適切なリーフノード（末端ノード）に挿入します。
ノードの分割（Split）: もしノードが許容される最大キー数を超えてしまった場合、そのノードは中央のキーを親ノードに移動させ、残りのキーを二つの新しいノードに分割します。これをノードの分割と呼びます。

この分割操作により、木は常にルートからリーフまでのパス長がほぼ等しく保たれます（平衡性の維持）。データがどれだけ増えても、木の深さが急激に増すことがないため、大規模なデータセットに対しても安定したパフォーマンスを提供できるのです。この頑丈さがB木の魅力ですね。

3. データ構造における位置づけ

B木がデータ構造 → ツリー構造 → 多分木と特殊木のパスに位置づけられるのは理にかなっています。

ツリー構造であること: 階層的な構造を持ち、探索が効率的であるため、基本的なツリーのメリットを享受しています。
多分木であること: ディスクブロックサイズに対応するため、一つのノードに多くのキーとポインタを持ちます。
特殊木であること: ディスクI/Oの最適化という特定の目的のために、自動平衡化のロジックが組み込まれています。これはメモリ効率を追求するAVL木や赤黒木とは異なり、外部記憶装置の効率を追求した結果であり、まさに「特殊」な設計と言えるでしょう。

具体例・活用シーン

巨大図書館の蔵書インデックス（メタファー）

B木を理解するための最も分かりやすいメタファーは、「巨大な図書館の蔵書インデックスカード」です。

二分探索木（BST）の場合: 従来の図書館では、インデックスカードが非常に小さく、一枚のカードには「次はこのカードを見てください」という情報が左右二つしか書かれていません。目的の書籍を探すには、何百枚、何千枚ものカードを順番にたどらなければなりません。
B木の場合: B木は、巨大で分厚い索引台帳だと考えてください。この台帳（ノード）は非常に大きく、図書館のフロア全体に対応するほどの情報（キーとポインタ）が詰まっています。あなたは、まずルート台帳（ルートノード）を開きます。そこには「A～Fを探すなら1階へ」「G～Mを探すなら2階へ」といった広範囲の指示が数百件記載されています。つまり、たった数冊の台帳をめくるだけで、目的の書籍がある棚（データ）の場所までたどり着けるのです。

この「索引台帳をめくる回数」がディスクアクセス回数に相当します。B木は、台帳（ノード）を大きくすることで、めくる回数（I/O回数）を最小限に抑え、素早く目的の情報を引き出すことを可能にしているわけです。

活用シーン（箇条書き）

データベースインデックス: 最も典型的な利用例です。特にリレーショナルデータベース（RDB）のインデックス構造として広く採用されています。高速な検索を実現するために、テーブルの主キーや外部キーにB木ベースのインデックスが作成されます。
ファイルシステム: NTFSやext4といった現代的なファイルシステムの一部では、ディレクトリ構造やファイル割り当て情報を管理するためにB木、またはその派生形（B+木）が用いられています。
大規模辞書検索システム: 非常に巨大なキーセット（単語など）を扱う検索エンジンや辞書サービスにおいて、ディスク上のデータの検索効率を上げるために利用されます。

資格試験向けチェックポイント

IT系の資格試験、特に応用情報技術者試験や基本情報技術者試験では、B木はその重要性から頻出のテーマとなります。

最重要キーワードの確認:
- 「多分木」であり、「平衡木」であること。
- 「外部記憶装置（ディスク）」の効率化を目的としていること。
- 「ディスクI/O回数の最小化」が最大の利点であること。これを知っているかどうかで、B木の目的を理解しているかが問われます。
構造と性能の理解:
- ノードのサイズがディスクブロックサイズに合わせて設計される点。
- データの挿入時にノードが分割（スプリット）することで平衡性を維持する点。
- 探索時間がデータの対数に比例する（$O(\log N)$）ため、非常に高速である点。
関連構造との区別:
- 二分探索木（BST）やAVL木は主に主記憶（メモリ）内での効率を追求しますが、B木は外部記憶（ディスク）の効率を追求します。この利用目的の違いを明確に理解しておきましょう。
- B+木との違いも重要です。B+木はリーフノードにすべてのデータを持ち、さらにリーフノード間が連結されている（シーケンシャルアクセスに強い）という特徴があり、データベースのインデックスとしてB木よりもさらに広く使われています。