B木

出典: フリー百科事典『ウィキペディア（Wikipedia）』

B木（びーき、B-tree）は、コンピュータプログラムにおけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。

実システムでも多用されており、データベースマネージメントシステムの多くはB木による索引を実装している（厳密にはB木の改良型であるB+木やB*木を使うことが多い）。

[編集] 構造

多分木の平衡木(バランス木)である。1 ノードから最大 m 個の枝が出るとき、これをオーダー m のB木という。後述する手順に従って操作すると、根と葉を除く「内部ノード」は最低でも m /2 の枝を持つことを保証できる。

各ノードは、枝の数 - 1 のキーを持つ。枝₁ ～ 枝_m と キー₁ ～ キー_{m -1} を持つとき、枝_i には キー_{i -1} より大きく キー_i より小さいキーだけを保持する（キーの重複を許す場合はどちらかに等号をつける）。