二分探索とハッシュと二分探索木とB木の比較

二分探索、ハッシュ、二分探索木、B木がわかりやすく比較されていたのでメモ。

アルゴリズムクイックリファレンス

P.126-127

二分探索には、基本的に2つの変形がある。第1は、動的なデータを取り扱うもので、これは探索性能がひどく低下しないように保守しながら、効率的にデータを追加削除できるように実装を調節しなくてはならない。集まりを貯えるのに配列を用いていると、挿入削除は極めて非効率となる。なぜなら、配列の全要素が正しい値を保持するようにしなければならないからだ。挿入の際には、配列を（物理的または論理的に）拡大して、平均して全体の半分の要素を1つ後方に移動する必要がある。削除では、配列を縮小して、半分の要素を1つ後方に移動する必要がある。削除では、配列を縮小して、半分の要素を添字1つ前方に移動する。どちらの操作も性能的に受け入れがたいほど遅くなるだろう。
集まりがメモリ内に収まるなら、衝突連鎖を用いるハッシュに基づいた探索方式に切り替えたほうが良い。後で述べる「5.4 ハッシュに基づいた探索」を見てほしい。動的なデータを探索する分かりやすい方法を示している。もう1つの手法は、メモリ内に二分探索木を構築することである。挿入探索が十分ランダムで、木に偏りが生じないならば、この方法は実装が単純である。しかし、経験上、そのような場合はまれであり、もっと複雑な探索木、平衡二分探索木（balanced binary search tree）を使わなければならない場合が多いだろう（Cormen et al.,2001）。
第2の変形は、データが動的なだけでなく大きすぎてメモリに収まらない場合を扱う。この場合には、探索時間の大半は2次記憶への入出力操作に食われてしまう。1つの効率的な解は、Bツリー（B-Tree）と呼ばれるn分木を用いることだ。これは、2次記憶上で性能が出るように調整した多段階の木である。Bツリーの詳細な分析は（Cormen et al.,2001）にある。例を使ったウェブ上の解説は http://www.bluerwhite.org/btree/ にある。

P.149

他にも平衡木構造はある。もっともよく使われるのは前述したAVL木である。赤黒木やその他の平衡二分木は、メモリ内にデータを持つ探索には正しい選択だ。データ集合がメモリ内に保持できないほど大きい場合には、別の種類の木が使われる。各節点がn>2個の子を持つn次の木構造である。よく使われるものは、Bツリーと呼ばれ、巨大データ集合でディスクアクセスの回数を最小化するという点では、優れた性能を示す。Bツリーは、関係データベースの実装によく使われている。

「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)

P.76

単方向リストは、「次の要素を指し示すポインタ」を使って、データを連鎖させて、順番を管理するデータ構造です。ここで紹介する二分木は、「次の要素を指し示すポインタ」が2つある単方向リストといえるものです。