B*木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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**木の定義も見られた。

参考文献[編集]

脚注[編集]

[ヘルプ]

関連項目[編集]

外部リンク[編集]