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**木の定義も見られた。
参考文献.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-100{font-size:100%}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}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
表
話
編
歴
データ構造
その他
コレクション(英)
コンテナ
代数的データ型
素集合データ構造
永続データ構造
並行データ構造(英)
配列構造(英)
配列
可変長配列
ビット配列(英)
接尾辞配列
スタック
キュー
両端キュー
リングバッファ
疎行列
リンク構造(英)
連結リスト
スキップリスト
展開リスト
XOR連結リスト
優先度付きキュー
検索構造(英)
連想配列
ハッシュテーブル
ハッシュ配列木(英)
ハッシュ関数
コンシステントハッシュ法
分散ハッシュテーブル
連想リスト(英)
木構造
二分木
二分探索木
二重連鎖木
デカルト木(英)
トップ木(英)
T木(英)
平衡二分木
AA木
AVL木
赤黒木
スプレー木
スケープゴート木
ツリープ
2-3木
2-3-4木
フィンガーツリー
B木
B+木
B*木
Bx木(英)
UB木(英)
ダンス木(英)
H木(英)
X木(英)
M木(英)
トライ木
基数木
接尾辞木
三分探索木
Cトライ(英)
X-fastトライ(英)
Y-fastトライ(英)
ハッシュ木(英)
BSP木
四分木
八分木
インターバル木
レンジ木(英)
セグメント木(英)
カバー木(英)
メトリック木(英)
BK木(英)
kd木
暗黙k-d木(英)
vp木(英)
R木
R+木(英)
R*木(英)
ヒルベルトR木(英)
優先R木(英)
多重木
多分木(英)
三分木(英)
スパゲッティスタック
フェニック木
リンクカット木(英)
フュージョン木(英)
ヴァンエムデボアス木(英)
指数木(英)
SPQR木(英)
PQ木(英)
(a,b)木(英)
ヒープ
二分ヒープ
三分ヒープ(英)
D分ヒープ(英)
二項ヒープ
2-3ヒープ(英)
Beap(英)
フィボナッチヒープ
左翼ヒープ(英)
ペアリングヒープ(英)
傾斜ヒープ(英)
ソフトヒープ(英)
ウィークヒープ(英)
グラフ構造
有向グラフ
有向非巡回グラフ
二分決定グラフ
ハイパーグラフ
有向非巡回ワードグラフ(英)
抽象データ型
リスト