データ構造のB+ツリーとは？仕組みとB木との違い、メリットを解説

B+ツリー（B+木）は、B木（Bツリー）を拡張したデータ構造です。B木よりも効率的な挿入・削除・検索を実現できるよう設計されており、データベースやファイルシステムのインデックス構造として広く活用されています。

B+ツリーの基本構造

通常のB木では、キーとレコード（実データ）が内部ノードと葉ノードの両方に格納されます。一方、B+ツリーでは、実際のレコードはすべて葉ノードにのみ格納され、内部ノードには検索用のキー値だけが保持されます。

さらに大きな特徴として、B+ツリーの葉ノード同士は連結リストのようにリンクされています。この構造により、範囲検索や順次アクセス（シーケンシャルスキャン）が非常に容易になります。

B+ツリーの例

B+ツリーの基本操作

B+ツリーは、検索・挿入・削除という基本的な操作をサポートしています。各ノード内の要素は常にソートされた状態で維持され、位置iにある要素の前後にはそれぞれ子ノードが存在します。

左側の子ノードにはより小さい値が、右側の子ノードにはより大きい値が格納されるため、根から葉へと一方向に探索を進めるだけで目的のデータにたどり着けます。これにより、二分探索に近い要領で効率的な検索が可能です。

B木と比較したB+ツリーの利点

• レコードへのアクセスに必要なディスクアクセス回数が一定になり、性能の予測がしやすい

• 木の高さがバランスよく保たれ、B木と比べて低く抑えられる

• 葉ノードが連結リストのように接続されているため、要素を順番に走査するシーケンシャル検索も行える

• キーがそのままインデックスとして機能する

• 実データがすべて葉レベルに集約されているため、検索処理が高速になる

まとめ

B+ツリーは、実データを葉ノードに集約し、葉同士を連結リストでつなぐことで、B木の弱点を補ったデータ構造です。ディスクI/Oの削減と安定した検索性能を実現できることから、MySQL（InnoDB）など多くのRDBMSのインデックス実装にも採用されています。大量データを扱うシステムを設計する際には、ぜひ押さえておきたい重要な概念といえるでしょう。