|
B木（びーき）は、コンピュータサイエンスにおけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。 実システムでも多用されており、データベースマネージメントシステムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木や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木と呼ぶ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「B木」の詳細全文を読む スポンサード リンク
|