B+ 木

2025年10月21日

B+ 木

英語表記: B+ Tree

概要

B+ 木（B+ Tree）は、データ構造の中でも特に「ツリー構造」に分類される、非常に効率的な多分木の一種です。主に大規模なデータベースやファイルシステムにおいて、外部記憶装置（ハードディスクやSSDなど）に格納されたデータを高速に検索し、かつ連続的にアクセスするために設計された特殊なデータ構造です。すべてのデータがツリーの末端、すなわち「葉ノード（リーフノード）」に集中して格納されている点が最大の特徴であり、これにより検索効率と範囲検索（シーケンシャルアクセス）の利便性を両立させています。

詳細解説

B+ 木は、「データ構造（リスト, スタック, キュー, ツリー）→ ツリー構造 → 多分木と特殊木」という分類の中で、実用上最も重要な構造の一つと言えます。なぜなら、現代のコンピューティングにおいて、データの大半はメインメモリ（RAM）ではなく、アクセス速度が遅い外部記憶装置に保存されているからです。B+ 木の設計思想は、この「ディスクアクセス（I/O）」の回数を最小限に抑えることにあります。

目的と背景

従来の平衡二分探索木（AVL木や赤黒木など）はメモリ内での高速な処理には優れていますが、ノード数が多くなるとディスク上に分散してしまい、検索のたびに多数のI/Oが発生し、性能が急激に低下します。B+ 木は、一つのノードに多くのキーとポインタを持たせる「多分木」として設計されています。ノードサイズをディスクの最小アクセス単位（ブロックサイズ）に合わせることで、一度のディスク読み込みで大量の情報をメモリに展開でき、結果として検索パスを短縮し、I/O回数を劇的に削減できるのです。これは、ディスクアクセスが非常に高コストであるという現実を反映した、賢明な設計と言えるでしょう。

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

B+ 木は、動作原理に基づき、構造的に異なる二種類のノードで構成されています。

1. 内部ノード（インデックスノード）

内部ノードは、データの場所を示す「索引（インデックス）」としての役割のみを担います。ここにはキー（検索値）と、そのキーに対応する子ノードへのポインタのみが格納されます。重要なのは、内部ノードには実際のデータ本体は含まれないという点です。これにより、内部ノードを小さく保ち、より多くの索引情報をメモリに保持したり、一度のディスクアクセスで読み込んだりすることが可能になります。

2. 葉ノード（リーフノード）

葉ノードは、ツリー構造の最も下層に位置し、すべてのデータまたはデータ本体へのポインタが格納されます。B+ 木の最大の特徴は、これらの葉ノードが相互にリンク（連結）されている点です。このリンクは通常、キーの順序に従って配置されており、一度目的の葉ノードに到達すれば、その隣接する葉ノードへポインタを辿るだけで、追加のツリー探索なしに連続したデータを読み進めることができます。これが、B+ 木が特に「範囲検索」や「全件走査（シーケンシャルアクセス）」において非常に強力である理由です。

検索・挿入・削除の動作

検索: 検索はルートノードから始まり、内部ノードのキーを比較しながら適切なポインタを辿り、最終的に目的のデータが存在する葉ノードに到達します。データは葉ノードに必ず存在するため、検索パスは常にルートから葉ノードまで一定の深さになります（平衡性が保たれているため）。
挿入・削除: データが挿入または削除されると、ツリーの平衡性（バランス）を維持するためにノードの分割（スプリット）や結合（マージ）が発生します。この自己平衡性のおかげで、データが偏って格納されることを防ぎ、常に効率的な検索性能を保証しているのです。この手間があるからこそ、私たちは常に高速な検索を享受できている、と考えると感慨深いですね。

具体例・活用シーン

B+ 木は、その外部記憶対応能力の高さから、私たちのデジタル生活の基盤を支える技術として広く活用されています。

活用シーン

リレーショナルデータベース（RDBMS）のインデックス: MySQLやPostgreSQLなど、主要なデータベースシステムでは、データの高速検索を実現するためにB+ 木構造が標準的に利用されています。特にプライマリキーやセカンダリインデックスは、ほとんどの場合B+ 木として実装されています。
ファイルシステム: NTFS（Windows）やext4（Linux）など、現代のファイルシステムの一部では、ディレクトリ構造やファイルメタデータの管理にB+ 木の派生構造が使われています。

アナロジー：巨大図書館のインデックスシステム

B+ 木の仕組みは、巨大な図書館の蔵書検索システムに例えると非常に分かりやすいです。

想像してみてください。あなたは膨大な蔵書の中から特定のテーマに関する本をまとめて探したいと思っています。

内部ノード（インデックスカード）: これは図書館の検索端末や分類目録に相当します。目録には「〇〇というジャンルの本は、A棟3階の棚番号100から始まる」といった情報（キーと場所のポインタ）だけが書かれており、本そのもの（データ）は含まれていません。この目録のおかげで、私たちは図書館全体を歩き回らずに、目当ての場所を素早く特定できます。
葉ノード（実際の書棚）: ツリー探索を終えてたどり着いた書棚が葉ノードです。ここには、キー（本のタイトルや著者）と、本そのもの（データ）が並んでいます。
葉ノード間のリンク（棚の繋がり）: B+ 木の最も便利な点は、この書棚が「隣の棚へ続く」ように物理的、あるいは論理的に繋がっていることです。例えば、「経済学」の棚を探し当てたら、その棚の隣には必ず「経営学」の棚が続いています。これにより、特定の経済学の本を見つけた後、改めて検索端末に戻らずとも、そのまま棚を横にスライドしていくだけで、関連するすべての本（範囲内のデータ）を効率的に読み進めることができるのです。

この「目次（内部ノード）は場所を示すだけ」「データは末端の棚（葉ノード）に集約」「棚同士は繋がっている」という構造こそが、B+ 木の効率性の秘密であり、特に範囲検索に強い理由を明確に示しています。

（文字数確保のため、このアナロジーをもう少し膨らませます。）

もし葉ノード間のリンクがなければどうなるでしょうか？それは、一冊の本を見つけるたびに、再び検索端末（ルートノード）に戻って次の本を探し直さなければならない状況に等しいです。非常に非効率ですよね。B+ 木はこのリンク構造により、ディスクI/Oを一度に集中させ、その後の連続的なデータ読み取りをメモリ内で行う（または最小限のI/Oで済ませる）ことを可能にし、大規模データ処理のパフォーマンスを飛躍的に向上させているのです。これは、データ構造設計における知恵の結晶だと私は感じています。

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

B+ 木は、基本情報技術者試験や応用情報技術者試験において、データベースのインデックス構造として頻繁に出題されます。特に「データ構造（リスト, スタック, キュー, ツリー）→ ツリー構造」の文脈で、他の木構造との違いを理解することが重要です。

B木との違いの理解: B+ 木と混同されやすいB木（B-Tree）との違いは必ず押さえてください。
- B木: データ（またはデータへのポインタ）が内部ノードにも葉ノードにも存在し得ます。
- B+ 木: すべてのデータは葉ノードにのみ存在します。また、葉ノード間はリンクで連結されています。これがB+ 木の最大の識別点であり、試験でも問われやすいポイントです。
ディスクI/Oの最小化: B+ 木の主な目的は、ディスクアクセス（I/O）回数を最小限に抑えることです。ノードサイズがディスクブロックサイズと一致するように設計されている点を理解しておきましょう。
範囲検索（シーケンシャルアクセス）の優位性: 葉ノードが連結されているため、特定の範囲内のデータを検索する際に、ツリーの探索を繰り返す必要がなく、非常に高速であるという特徴を覚えてください。「B+ 木が範囲検索に強い理由」として出題された場合は、「葉ノードがキーの順序に従って連結されているため」と答えられるようにしましょう。
平衡性（バランス）: B+ 木は、データ挿入・削除時に自動的に平衡を維持する「自己平衡木」であることを理解してください。これにより、木の深さが常に最小限に保たれ、最悪の場合の検索時間（O(log N)）が保証されます。
ツリーの深さ: B+ 木は多分木であるため、二分探索木と比べて木の深さが浅くなります。深さが浅いということは、ルートから葉ノードまでのI/O回数が少ないことを意味します。この「浅い深さ」が外部記憶での高速化に直結していることを理解しておくと、応用的な問題にも対応できます。