B木とは、 ファイルシステムやデータベースの実装の基礎となる平衡探索木です。 平衡探索木では、要素の検索・挿入・削除などの操作が、 いかなる場合でも \(O(\log n)\) の計算量で行えます(\(n\) は要素数)。 何の工夫もしない単なる２分探索木では、 挿入や削除のパターンによっては木の茂り方のバランスが崩れてしまい、 各種操作に \(O(n)\) の計算量が必要になる場合があります。
こちらのページ では、 ノード内部の要素を線形探索するとても簡単なB木の実装を示しました。 しかし、B木のノード内の要素はソートされているのですから、 目的の要素を探すのに２分探索を使えば性能を改善することが出来ます。 ノード内の要素を２分探索すると、特に検索の性能が 赤黒木 並に改善されます。
ここでは、Java による２分探索B木のサンプルソースを示します。 ダウンロードする人はこのリンクからどうぞ。