B-Tree by Java -- B木のすごく簡単な実例

【B木のすごく簡単な実例】 B木アルゴリズム(B-Tree algorithm)とは、 ファイルシステムやデータベースの実装の基礎となる平衡探索木のアルゴリズムです。 平衡探索木では、要素の検索・挿入・削除などの操作が、 いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。 何の工夫もしない単なる２分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に \(O(n)\) の計算量が必要になる場合があります。 例えば図1.のような場合、数字の入っている丸をノードと呼び、 出発点となる最上位のノードを根と呼びます。 左図の平衡探索木では、 木の根である 4 から数えて 7 に到達するのに 3 個のノードをたどるだけで済みますが、 右図のバランスの崩れた木の場合は、根の 1 から数えて 7 に到達するのに 7 個のノー

[masterq]

"ハードディスクなど遅いブロックデバイス上に探索木を展開した場合、 まさに枝をたどるコストが支配的になります"