【B木のすごく簡単な実例】 B木アルゴリズム(B-Tree algorithm)とは、 ファイルシステムやデータベースの実装の基礎となる平衡探索木のアルゴリズムです。 平衡探索木では、要素の検索・挿入・削除などの操作が、 いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。 何の工夫もしない単なる2分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に \(O(n)\) の計算量が必要になる場合があります。 例えば図1.のような場合、数字の入っている丸をノードと呼び、 出発点となる最上位のノードを根と呼びます。 左図の平衡探索木では、 木の根である 4 から数えて 7 に到達するのに 3 個のノードをたどるだけで済みますが、 右図のバランスの崩れた木の場合は、根の 1 から数えて 7 に到達するのに 7 個のノー
![B-Tree by Java -- B木のすごく簡単な実例](https://cdn-ak-scissors.b.st-hatena.com/image/square/c4f4c17e4b95151e6a3d4a06d05837639fb55ca0/height=288;version=1;width=512/http%3A%2F%2Fwwwa.pikara.ne.jp%2Fokojisan%2Fb-tree%2Fbtree.png)