About: B*木

B*木（英: B*-tree）は、B木から派生した木構造の一種で、HFS や Reiser4 ファイルシステムで使われている。根ノード以外のノードは、B木のように1/2ではなく、2/3まで埋まった状態になる。このため、ノードがいっぱいになったとき即座に分割するのではなく、キーを次のノードと共有する。連続する2つのノードがいっぱいになると、それを3つのノードに分割する。また、常に左端のキーは使わずに残しておく。一般に総称して「B木」と呼ばれることが多く、「B*木」と呼ばれることは滅多にない。 B*木とB+木は異なる。後者は、データが葉ノードのみに格納されたものである（さらにそれが連結されて連結リストを構成するようになっているものも多い）。B+木は、挿入のコストを増大させて、検索を効率化したものである。 IEEEカンファレンスICCI '93においては B**木の定義も見られた。