B木(ビーき)とは | 意味や読み方など丁寧でわかりやすい用語解説

B木は、主にデータベースやファイルシステムで利用される木構造のデータ構造である。特徴は、常に平衡状態を保ち、多分岐である点だ。これにより、ハードディスクのような低速な記憶装置へのアクセス回数を最小限に抑え、効率的なデータ検索、挿入、削除を実現する。特に、ディスクI/Oのコストが高い環境で優れた性能を発揮するように設計されている。

B木が開発された背景には、コンピュータの主記憶装置（RAM）と補助記憶装置（ハードディスクやSSDなど）との速度差がある。RAMは高速だが容量が限られ、補助記憶装置は低速だが大容量である。補助記憶装置からデータを読み書きする際には、データの読み出し位置をシークし、ブロック単位でまとめてデータを転送する。このシークにかかる時間が非常に長く、データアクセス性能のボトルネックとなることが多い。そこで、ディスクへのアクセス回数を減らすことを目的としてB木が考案された。

B木の「B」は、発明者の一人であるBayerの頭文字、またはバランス（Balanced）を意味すると言われている。その名前が示す通り、B木は常に平衡木である。つまり、木の根から任意の葉ノードまでのパスの長さが全て同じである。これにより、どのデータを検索する場合でも、ディスクへのアクセス回数がほぼ一定になり、最悪の場合の性能劣化を防ぐ。

B木の各ノードは、複数のキーと、それらに対応する子ノードへのポインタ（またはブロックアドレス）を保持する。一般的な二分探索木が一つのノードに最大2つの子ノードしか持たないのに対し、B木はより多くのキーと子ノードを持つことができる。この「多分岐」がB木の大きな特徴である。ノードが保持できるキーの最大数や子ノードの最大数は「次数」（またはオーダー）と呼ばれるパラメータによって決定される。次数が大きいほど、一つのノードに多くの情報が詰め込まれ、木の高さが低くなる。木の高さが低ければ、根から葉ノードまでの経路が短くなり、ディスクアクセスの回数を減らすことができる。これは、ディスクから一度に大量のデータをブロックとして読み込むことができる特性を最大限に活用する設計思想に基づいている。

B木のノードは、いくつかの重要な特性を持つ。まず、各ノード内のキーは常に昇順にソートされている。これにより、ノード内でのキーの検索は高速に行える。次に、根ノードを除くすべてのノードは、少なくとも「次数/2」個のキーを保持しなければならないという制約がある（端数は切り上げ）。これにより、ノード内のスペースが無駄になることを防ぎ、データ密度を高く保つ。また、根ノードは、木の全体のキー数が2個未満の場合を除いて、少なくとも1つのキーを持つ。

B木におけるデータの探索は、二分探索木に似ているが、ノード内での検索と、子ノードへの移動を繰り返す点が異なる。探索対象のキーと現在のノード内のキーを比較し、適切な子ノードを選択して再帰的に探索を進める。多分岐構造により、一度のディスクアクセスで読み込んだノードから、次に進むべきパスを効率的に決定できるため、必要なディスクI/O回数は非常に少なくなる。ディスクアクセスは、ノードを読み込む際にのみ発生し、ノード内でのキー比較はメモリ上で行われるため高速である。

データの挿入時には、まず挿入するべき葉ノードを探す。その葉ノードに空きがあれば、キーを適切な位置に挿入する。しかし、ノードが満杯の場合、そのノードは二つに分割（スプリット）される。真ん中のキーを親ノードに昇格させ、残りのキーを二つの新しいノードに振り分ける。この分割操作は、親ノードが満杯の場合にはさらに親ノードも分割される、というように再帰的に木の根に向かって伝播する可能性がある。最終的に根ノードが分割された場合、新しい根ノードが作成され、木の高さが増える。この過程で常に木の平衡性は保たれる。

データの削除も同様に、まず削除するべきキーを含むノードを探す。キーを削除した後、ノード内のキーの数が最小限の制約（次数/2）を下回る場合がある。この場合、隣接する兄弟ノードからキーを借りてくる（再分配）か、それが不可能であれば兄弟ノードと結合（マージ）する必要がある。結合操作は、親ノードのキーを一つ引き下げることを伴い、親ノードもキーの数が最小制約を下回る可能性があるため、再帰的に根に向かって伝播する場合がある。これらの操作によっても、B木の平衡性は維持される。

B木の最大の利点は、ディスクI/Oの効率性である。木の高さが低く保たれるため、ディスクアクセスの回数が少なく、大規模なデータセットに対しても高速な検索性能を提供する。また、ノード内のスペースを有効活用し、データの挿入や削除操作が頻繁に行われても、木の平衡性が自動的に維持されるため、性能が劣化しにくい。

これらの特性から、B木はリレーショナルデータベースのインデックス構造として広く採用されている。例えば、プライマリキーやセカンダリインデックスは、B木またはその派生形であるB+木によって実装されることが多い。ファイルシステムにおいても、ディレクトリ構造の管理やファイルブロックの割り当てなど、B木やその概念が応用されている。大規模なデータを扱うシステムにおいて、B木は高速で信頼性の高いデータ管理の基盤として不可欠な存在である。