B*木

B*木（英: B*-tree）は、B木から派生した木構造の一種で、HFS や Reiser4 ファイルシステムで使われている。根ノード以外のノードは、B木のように1/2ではなく、2/3まで埋まった状態になる。このため、ノードがいっぱいになったとき即座に分割するのではなく、キーを次のノードと共有する。連続する2つのノードがいっぱいになると、それを3つのノードに分割する。また、常に左端のキーは使わずに残しておく。一般に総称して「B木」と呼ばれることが多く、「B*木」と呼ばれることは滅多にない。

B*木とB+木は異なる。後者は、データが葉ノードのみに格納されたものである（さらにそれが連結されて連結リストを構成するようになっているものも多い）。B+木は、挿入のコストを増大させて、検索を効率化したものである。

IEEEカンファレンスICCI '93 (Anestis A. Toptsis 1993)においては B**木の定義も見られた。

参考文献[編集]

Anestis A. Toptsis; Chang, Carl K.; Koczkodaj, Waldemar W.; et.c. (27 May 1993). "B**-tree: a data organization method for high storage utilization". Computing and Information, 1993. Proceedings ICCI '93. Sudbury, Ontaro, Canada: IEEE Computer Society Press. pp. 277–281. ISBN 0-8186-4212-2. OCLC 30738554. 2007年2月17日閲覧。