B木
多分岐の平衡木(バランス木)である。1 ノードから最大 m 個の枝が出るとき、これをオーダー m のB木という。後述する手順に従って操作すると、根と葉を除く「内部ノード」は最低でも m /2 の枝を持つことを保証できる。
各ノードは、枝の数 - 1 のキーを持つ。枝1 ~ 枝m と キー1 ~ キーm -1 を持つとき、枝i には キーi -1 より大きく キーi より小さいキーだけを保持する(キーの重複を許す場合はどちらかに等号をつける)。
葉ノードの定義は文献によって違いが見られる。木の終端をヌルポインタのような特殊な値で表す場合、枝がすべて終端記号となっているノードを葉とする。これに対して一部の文献では、終端を表すためにキーが0個のノードを連結し、このノードを葉と定義している。すなわち、後者の定義における葉ノードの親が、前者の定義における葉ノードとなる。後者の定義をとる文献では「葉ノードはキーを持たない」ということになる。以下の記述では、前者の定義に従うものとする。
ノードはページと呼ばれることもある。特にハードディスクドライブなどの外部記憶装置を使ってB木を実現する場合によく見られる。この場合、各ノード(ページ)のサイズが、外部記憶装置のブロックサイズの整数倍になるようにオーダーを調整することが多い。
B木の中でも特に、オーダー3のものを2-3木、オーダー4のものを2-3-4木と呼ぶ。