B木

概要

B木（B-tree）は、コンピュータサイエンスにおいて、特に大規模なデータ集合を外部記憶装置（ハードディスクドライブやSSDなど）上で効率的に管理するために考案されたデータ構造である。従来のAVL木や赤黒木といった平衡二分探索木が主にメインメモリ上での高速処理を目的とするのに対し、B木は、ノードあたりの情報量を増大させる「多分木」の特性を採用することで、ディスクアクセス（I/O）の回数を劇的に削減することを最大の目標としている。

ディスクアクセスはメインメモリ上の操作に比べて遥かに時間がかかるため、このI/O回数の削減は、データベースやファイルシステムといったI/Oバウンドなシステムにおいて極めて重要な性能向上をもたらす。B木の設計思想は、ノードのサイズを物理的なディスクブロックやページサイズに一致させることにある。これにより、一度のディスクアクセスでノード全体をメモリに読み込むことができ、データの検索や走査に必要なディスクシークの回数を最小限に抑えることが可能となる。

B木の構造は、データが格納されるノードが多数のキーと、それに対応する子ノードへのポインタを持つ点に特徴がある。B木の「次数」（Degree）は、ノードが保持できるキーの最大数や子ノードの最大数を定義する重要なパラメータであり、この次数は通常、物理的なディスクブロックやページサイズに合わせて設定される。

特徴と動作原理

B木は、その設計においてノードの容量を最大限に活用し、平衡性を厳格に維持することで、大規模データセットの管理を最適化する。

ノード構造と平衡性

B木のノードは、キーをソートされた順序で格納し、各キーの間には子ノードへのポインタが配置される。全てのノードには、規定された範囲内（例えば、次数が $m$ であれば $\lfloor m/2 \rfloor - 1$ から $m-1$ 個）のキーが格納される。このキーの数と子ノードへのポインタの数は、データセットの規模に関わらず、常に一定の規則に従って制御される。

特に重要な特性は「完全な平衡性（Perfect Balance）」である。B木の定義により、根ノードから任意の葉ノードまでの深さ（高さ）は常に等しい。この特性が保証されることにより、データの検索にかかる最悪時間計算量（Worst-case time complexity）が $O(\log_m n)$ となる。ここで $n$ は全データ数、$m$ は次数である。底が $m$ である対数が示すように、次数 $m$ が大きいほど、木の高さは低くなり、必要なI/O回数は減少する。例えば、次数 $m$ が1000である場合、数百万件のデータに対しても、検索に必要なディスクアクセスはわずか2〜3回で済む。

挿入と分割（Split）

B木に新しいデータが挿入され、あるノードが許容される最大キー数を超過した場合、そのノードは二つのノードに「分割」される。この際、中央のキーが新しい親ノードに昇格され、新しい二つの子ノードを指すポインタが親に追加される。この分割操作は必要に応じて親ノード、さらに根ノードまで伝播し、もし根ノードが分割された場合、木の高さが一段階増えることになる。この厳密な管理メカニズムによって、B木はデータの追加や削除が行われても、自己平衡性を常に維持する。

削除と結合（Merge）

データの削除が行われ、あるノードのキー数が最小キー数を下回った場合、まずそのノードは隣接する兄弟ノードからキーを借り受ける操作（再配布）を試みる。再配布が不可能な場合は、兄弟ノードと「結合」される。結合が行われた場合、親ノードのキーが子ノードに降格され、全体の高さが維持されるか、あるいはノード数が減少した結果として木の高さが減少する。これらの操作は、B木の最小キー数の制約（ノードの最小充填率）を維持するために必須であり、挿入時と同様に木の深さ全体にわたって再帰的に適用される可能性がある。

具体的な使用例・シーン

B木の主要な応用分野は、外部記憶装置上の索引付けを必要とする全ての情報システムであり、特に速度と堅牢性が求められる環境で利用される。

データベース管理システム (DBMS) のインデックス

リレーショナルデータベース（RDB）において、B木は最も標準的なインデックス構造として採用されている。特に、検索効率の最適化が求められるプライマリキーやセカンダリインデックス（補助索引）の構造として不可欠である。MySQL (InnoDB)、PostgreSQL、Oracle Database、SQL Serverなど、主要なデータベースシステムは全てB木、またはその派生形であるB+木を基盤としている。インデックスを使用することで、テーブル全体をスキャンすることなく、対数時間の検索で特定のデータ行の位置を特定できる。これにより、クエリの実行速度が飛躍的に向上する。B木が提供する順序付けられた構造は、等値検索だけでなく、範囲検索（例: WHERE price BETWEEN 100 AND 200）にも極めて効率的に対応できる。

ファイルシステム構造

オペレーティングシステムのファイルシステムも、大規模なディレクトリ構造やメタデータを管理するためにB木あるいは類似の構造を利用する。例えば、AppleのHFS+や、MicrosoftのNTFS、Linuxで使われる一部のファイルシステムは、ファイルの場所、アクセス権限、タイムスタンプなどの情報を効率的に検索するためにB木を採用している。これにより、ディレクトリの探索やファイル名の検索を高速に行うことができる。B木の平衡性により、ディレクトリの階層が深く、ファイル数が多くなっても、一貫した高速なアクセス時間が保証される。

関連する概念

B木にはいくつかの重要な派生形が存在し、それぞれ特定の目的に合わせて最適化されている。これらの派生形は、B木の基本的な平衡構造とディスクI/O最適化の哲学を継承しつつ、特定の操作（範囲検索や充填率など）を改善している。

B+木 (B-plus tree)

B+木はB木をさらにデータベース用途に特化させた構造であり、現在RDBのインデックスとして最も広く利用されている。B+木の特徴は、データの格納方法に存在する。全てのデータ値（レコードへのポインタ）は葉ノード（リーフノード）にのみ格納され、内部ノードにはキー情報のみが格納される。これにより、内部ノードの密度が高まり、木の高さがさらに低くなる傾向がある。加えて、葉ノード同士がリンク（通常、順方向または双方向）で繋がれているため、範囲検索やシーケンシャルアクセス（順次アクセス）が極めて効率的になる。データベースでは範囲検索が頻繁に発生するため、B+木はB木よりも優位性を持つ。

B*木 (B-star tree)

B木は、B木のノードの利用効率をさらに高めることを目的に設計された構造である。B木ではノードが最大容量に達した際にすぐに分割されるため、平均充填率は約67%程度に留まる可能性があるが、B木ではノードの分割を行う前に、隣接する兄弟ノード間でキーを再配布（ローテーション）しようと試みる。これにより、ノードの平均充填率を向上させ（通常、約80%以上を保証）、ストレージの利用効率を高め、結果としてI/O回数をわずかながら削減する効果がある。

外部メモリと内部メモリのデータ構造の対比

B木、B+木は、ノードサイズをディスクブロックに合わせることで外部記憶装置に最適化されている。これに対し、AVL木や赤黒木（Red-Black tree）は内部記憶装置（メインメモリ）に最適化された平衡二分探索木である。これらはノードが保持するキー数が一つであるため、木の高さは高くなるが、メモリ上でのポインタ操作や比較演算が高速であるため、メインメモリ上のデータ構造としては優位性を持つ。B木がディスクI/Oの回数最小化に焦点を当てるのに対し、内部メモリ用の木構造はCPUキャッシュの利用効率や演算回数の最小化に焦点を当てている点で、設計目標が明確に異なる。

由来・語源

B木は1972年にイリノイ大学の計算機科学者であったルドルフ・バイヤー（Rudolf Bayer）とエドワード・M・マクレイト（Edward M. McCreight）によって発表された。彼らの論文「Organization and maintenance of large ordered indices」で初めてその概念が定義され、外部記憶装置上の索引構造に革命をもたらした。

「B」の語源については、考案者らによる公式な言及がないため、現在も複数の説が混在している。最も有力な説は、考案者の一人である「Bayer」の頭文字であるというもの、あるいはその構造上の特性を指す「Balanced（平衡）」の頭文字であるという説である。その他にも、発表当時彼らが研究を行っていたボーイング社のプロジェクトに関連していたため「Boeing」のBであるという説や、単に「Better」や「Bushy（茂った）」の頭文字であるという説も存在するが、研究コミュニティでは、その機能性を鑑み「Balanced」または考案者に敬意を表し「Bayer」を由来とする見解が一般的である。

使用例

(記述募集中)

関連用語

• (なし)