B*木

B木とは

B木（B-tree）は、B木から派生した木構造の一種であり、主にファイルシステムにおけるデータ管理に用いられます。特に、HFSやReiser4ファイルシステムでの採用例があります。

B木との違い

B木では、ルートノードを除く全てのノードが、最低でも半分はデータで埋まっている必要があります。しかし、B木では、ノードが2/3まで埋まった状態を維持するように設計されています。この点がB木との大きな違いです。

B木では、ノードが満杯になった場合、即座にノードを分割するのではなく、キーを隣接するノードと共有します。具体的には、連続する2つのノードが満杯になった場合に、それらを3つのノードに分割するという方法を採用します。このメカニズムにより、ノードの利用効率を高め、より少ないノード数でより多くのデータを管理することが可能になります。

また、B木では、各ノードの左端のキーは常に未使用のまま残しておくという特徴があります。

B木とB木の混同

一般的に、B木はB木の一種として扱われることが多く、「B木」という名称で言及されることはあまりありません。そのため、B木の解説においてB木の特性が説明されることもあります。

B+木との比較

B木と混同されやすいデータ構造として、B+木があります。B+木は、データが全て葉ノードに格納される構造を持ちます。さらに、葉ノードが連結リストを構成している場合が多いという特徴があります。B+木は、データの挿入コストを増大させる代わりに、検索効率を向上させることを目的とした構造です。B木とは異なる設計思想に基づいています。

その他の派生

IEEEカンファレンスICCI '93においては、B*木というさらに特殊な構造の定義も存在します。これはB木の更なる派生形として研究されたものです。

まとめ

B木は、B木の改良版として、ノードの利用効率を高めたデータ構造です。ファイルシステムにおけるデータ管理の効率化に貢献します。B木、B+木といった関連するデータ構造との違いを理解することで、より深くB木を理解することができます。

参考文献

Dictionary of Algorithms and Data Structures entry for B-tree

関連項目

B木
* B+木

もう一度検索