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

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

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

参考文献編集

  • Anestis A. Toptsis; Carl K Chang; Waldemar W Koczkodaj;et.c. (1993-05-27). “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. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=315364 2007年2月17日閲覧。 

脚注編集

[脚注の使い方]

関連項目編集

外部リンク編集