B+木

概要

B+木は、情報科学分野、特にデータ構造において、大規模なデータセットの管理と効率的な検索を実現するために極めて重要な役割を果たすデータ構造である。これは、基本的な多分岐木構造であるB木から派生・発展したものであり、磁気ディスクのようなランダムアクセス性能が遅い二次記憶装置（ストレージ）上でのデータ管理を最適化するために設計されている。B+木の最大の特徴は、全てのデータエントリが木構造の葉ノード（リーフノード）に集中して格納され、さらにこれらの葉ノードがキーの順序に基づいて双方向または単方向のリストとして連結されている点にある。この構造は、ストレージデバイスのページング機構と高い親和性を持ち、ディスクI/O（入出力）の回数を最小化するように工夫されている。これにより、単一のキー検索だけでなく、特定の範囲内のデータを連続的に読み出す範囲検索（レンジクエリ）において、極めて高い効率を発揮する。

具体的な使用例・シーン

B+木は、その設計思想から、ディスクベースのデータ管理システムにおいてデファクトスタンダードとして採用されている。最も代表的な使用例は、リレーショナルデータベース管理システム（RDBMS）におけるインデックスの実装である。

例えば、MySQLのInnoDBエンジンやPostgreSQL、Oracle Databaseといった主要なRDBMSにおいて、プライマリインデックス（クラスタ化インデックス）やセカンダリインデックスの内部構造としてB+木が利用されている。ユーザーが特定のレコードを検索する場合、DBMSはB+木のルートノードから目的のキーを辿り、数回のディスクI/Oで対応する葉ノードに到達する。プライマリインデックスの場合、葉ノードには実際のデータレコードが格納されており、セカンダリインデックスの場合は、主キーの値やレコードの物理アドレスが格納されているため、高速なアクセスが可能となる。B+木のノードサイズは、一般的にオペレーティングシステムやストレージのページサイズ（通常4KBや8KB）と一致するように設定されるため、一度のI/Oで効率的に必要なデータをメモリに読み込むことができる。

また、特定の範囲のデータを要求する範囲検索（例: 2023年1月から3月の間のトランザクション、特定の年齢層の顧客リストなど）を実行する場合、B+木の葉ノードが持つ連結リスト構造が絶大な威力を発揮する。DBMSは検索範囲の開始点となる葉ノードに到達した後、その葉ノードに連結されたポインタを辿り、連続するノードを順次読み進めるだけで、範囲内の全データを取得できる。これにより、多数のレコードを取得する際にも、ランダムI/Oの発生を抑制し、シーケンシャルI/Oへと変換することで処理時間を大幅に短縮することが可能となる。

メリット・デメリットと構造的特徴

B+木の構造がもたらす最大のメリットは、高い検索性能、特に範囲検索の効率性、そして大規模データに対しても安定したデータアクセス時間（時間計算量の保証）を提供することにある。

構造的特徴とメリット:

1. 低い木の高さによる高速検索: 内部ノードがデータポインタを持たず、キーのみを保持するため、ノードあたりのキー密度（分岐数）が高まる。これにより、同じデータ量を持つB木や二分探索木と比較して、木の全体的な高さが非常に低く抑えられる。結果として、大規模なデータセットに対しても、常にログスケール（$O(\log_b N)$）のアクセス時間でデータに到達でき、ディスクI/O回数が最小化される。
2. 効率的な範囲検索の実現: 葉ノードがキー順に連結されているため、開始キーを見つけた後は、シーケンシャルにノードを読み進めるだけで範囲内の全データを取得可能であり、ランダムアクセスを最小化できる。これは、ストレージの物理的な読み書き特性に最適化された設計である。
3. 平衡性の維持: B+木は常に平衡状態を維持するように設計されているため、データの挿入や削除が行われても、すべての検索操作がほぼ同じ深さを辿ることが保証される。これにより、最悪ケースの検索時間が予測可能であり、システムの信頼性が向上する。

デメリット:

1. 更新時のオーバーヘッド: データの挿入や削除によって、B+木の平衡性が崩れそうになった場合、ノードの分割（スプリット）や統合（マージ）といった複雑な再構築処理が発生する。特に大規模なノードの分割やマージは、多大なディスクI/OとCPUリソースを消費するため、頻繁な更新操作を行うシステムにおいては、そのオーバーヘッドを考慮する必要がある。
2. ストレージの冗長性: 内部ノードはインデックスとしてのキーを保持し、葉ノードも最終的なデータポインタ（またはデータ自体）とキーを保持する。したがって、純粋なB木と比較して、キー情報が内部ノードと葉ノードの両方に存在する分、インデックス構造全体が占めるストレージ容量が若干大きくなる傾向がある。ただし、この冗長性は検索性能の向上という大きな利点と引き換えに受け入れられている。

由来・語源

B+木の概念は、先行するB木（B-Tree）の構造的欠点を補完し、実際のストレージ環境、特にファイルシステムやデータベースシステムにおける性能要求に応えるために開発された。B木は1972年にルドルフ・バイエルとエドワード・マクライトによって考案されたが、B木ではデータポインタが内部ノードにも葉ノードにも分散して存在するため、ノードが持つことができるキーの数が制限され、また葉ノード間の連結がないため範囲検索に非効率的であった。特に、大規模なデータを扱う際にディスクI/Oの頻度が高くなることが、B木のボトルネックとなり得た。

B+木は、この問題を解決するため、内部ノードを純粋なインデックスとしてのみ利用し、全てのデータポインタを葉ノードに集約するという決定的な構造改良を行った。この分離戦略により、内部ノードにはデータポインタを格納するスペースの代わりに、より多くのキーを格納することが可能となり、結果として木の高さ（深さ）をより低く保つことができるようになった。木の高さが低ければ低いほど、データ検索時にストレージにアクセスする回数（ディスクI/O）が減少し、検索速度が向上する。また、葉ノード同士を連結することで、範囲を越えたシーケンシャルなデータアクセスを可能にした。この「+」記号は、B木に加わったこの重要な改良、すなわちデータ配置と葉ノード連結の追加機能を象徴していると言える。B+木は、ストレージの特性、つまりシーケンシャルアクセスがランダムアクセスよりも遥かに高速であるという事実を最大限に活用するために設計された構造である。

使用例

リレーショナルデータベース管理システム（RDBMS）におけるプライマリキーやセカンダリインデックスの標準的な実装。

関連用語

• 同義語: B+ツリー
• 関連: B木, インデックス, 二分探索木, ページング