B木（B-Tree）とは、データベースやファイルシステムで大量データを効率的に管理・検索するための「自己平衡型多分岐探索木」データ構造で、各ノード（節点）が複数のキーと子ノードへのポインタを持ち、すべての葉ノードが同じ深さにあるのが特徴です。ディスクI/Oを最小化するように設計されており、検索・挿入・削除を高速に行えるため、RDBMSのインデックスなどで広く利用されています。
画像参照：https://zenn.dev/farstep/books/learn-database-index-basics/viewer/basics-of-b-plus-tree-index
B木の主な特徴と仕組み
- 自己平衡性: データの追加・削除時に自動でバランス調整を行い、木の高さ（深さ）が一定に保たれます。これにより、最悪ケースでも検索時間が一定（対数時間）に収まります。
- 多分岐: 1つのノードが複数のキー（例えば、{10, 20, 30}）と、それに対応する複数の子ノード（4つ）を持ちます。これは、二分木の「1つのノードが最大2つの子を持つ」という制約を緩和したものです。
- ディスクアクセス最適化: ノードに複数のキーを格納することで、ディスクから読み込むブロックあたりの情報量を増やし、ディスクアクセス回数を減らします。これは、ハードディスクなどブロック単位での読み書きに最適化された記憶装置で特に有効です。
- 構造: キーはノード内で昇順に並べられ、各キーの間に子ノードへのポインタがあります。検索する値がどの範囲に属するかで、適切な子ノードをたどっていきます。
B木の派生形
- B+木: データを葉ノードのみに格納し、葉ノード同士が連結されているのが特徴。挿入コストは増えるが、データ範囲検索（範囲スキャン）が非常に高速になるため、多くのデータベースで使われます。
- B*木: B+木と似ていますが、ノードの利用率を高めるための分割ルールが異なります。
B木の用途
- データベース: 主にRDBMSのインデックス構造として利用され、テーブル内のレコードを高速に検索します。
- ファイルシステム: ディレクトリ構造の管理などに利用されます。
B木は、大量のデータを扱うシステムにおいて、検索性能と管理の効率性を両立させるための非常に重要なデータ構造です。
コメント