外部記憶装置の検索を考える。
通常、アルゴリズムやデータ構造を議論する時、暗黙の仮定として、 全てのデータを保持するデータ構造を保持するのに十分なサイズのRAMをコンピュータが持つことを想定している。 しかしこの仮定は場合によっては成り立たず、 コンピュータのメモリに載りきらないほど大きなデータが存在する。そのようなケースでは、 アプリケーションはデータをHDDやSSDのような外部の記憶媒体に保存しなければならない。
外部ストレージへのデータアクセスは非常に遅い。 あるコンピュータに接続されたHDDへの平均アクセス時間は19msで、SSDの場合は0.3msであった。 対照的に、RAMへの平均アクセス時間は0.000113ms未満であった。 このケースではRAMへのアクセスはSSDの2500倍以上速く、HDDの16万倍以上速いということが分かる。
この結果は割と典型的で、RAMへのアクセス時間はHDDやSSDの数千倍は速くなる。 しかし、アクセス時間が議論の全てではない。HDDやSSDのバイトにアクセスする時、 ディスクからは（特定のバイトではなくそのバイトが含まれる）完全なブロックが読み込まれる。 これはつまり、コンピュータに接続されたドライブのブロックサイズが4096の場合、 1バイト読み込むごとにドライブは4096バイトのブロックを返すことになる。 これは、データ構造を慎重に設計することができれば、ディスクアクセスごとに4096バイト読み込まれることが、 これから行いたいあらゆる操作を実行する上で役に立つということを意味している。
今後の議論では、以下を仮定する。
- コンピュータは全てのデータが格納された外部メモリにアクセスできる
- 外部メモリはブロックに分割されており、それぞれのブロックはB-wordsからなる
- コンピュータは有限サイズの内部メモリも利用でき、ここで計算も実行できる
- 内部メモリでの計算は定数時間を仮定する (外部メモリへのアクセスと比較して十分に高速なため無視する)
本格的な外部メモリモデルでは内部メモリのサイズもパラメータになるが、今回扱うデータ構造においては、 内部メモリのサイズは O(B+log_B n) で十分である。 これは、定数個のブロックと、高さ O(log_B n) のスタックに必要なメモリである。 多くの場合は O(B) が支配的な項である。例えば比較的小さな B=32 であっても、 すべての n≦2^160 について B≧log_B nが成り立つ。
- BlockStore…外部メモリのデバイスを隠蔽したオブジェクト。メモリーブロックのコレクションを保持する
- B…メモリーブロックのサイズ
それぞれのブロックはintegerのインデックスでユニークに区別される (identified)
BlockStoreがサポートする操作
- read_block(i): インデックスがiとなるブロックのコンテンツを返す
- write_block(i, b): インデックスがiとなるブロックにコンテンツbを書き込む
- place_block(b): コンテンツbを新しいインデックスに保存し、そのインデックスを返す
- free_block(i): インデックスがiとなるブロックを解放する。
二分木 (binary trees) を一般化したB木を考える。 これは外部メモリモデルにおいて効率的なデータ構造である。 また、2-4木はB木の特別なケースで、 B=2 とすることで得られる。
任意の整数 B≧2 において、B木は以下の性質を持つ。
- 全ての葉は同じ高さを持つ
- 根ではないノード u は最小で B 個、最大で 2B 個の子を持つ
- 根では最小で2個、最大で 2B 個の子を持つ
- B木の高さを h とすると、葉の個数 l は 2B^(h-1) ≦ l ≦ 2(2B)^(h-1) を満たす
- 対数を取り整理すると h ≦ log_B l + 1
- 内部ノード u が k 個の子を持つとき、 u はちょうど k-1 個のキーを持つ
- ノードが持つキーの配列は昇順にソートされている
- u が根ではない葉ノードのとき、 u は B-1 から 2B-1 個のキーを持つ
- u が内部ノードで k-1 個のキーを持つとき、任意の i ∈ {0,..., k-2} について i 番目のキーは i 番目の子が持つすべてのキーより大きく、 i+1 番目の子が持つ全てのキーより小さい
- u.chilren[i].keys[-1] < u.keys[i] < u.children[i+1].keys[0] が成り立つ
- B木のノードが保持するデータのサイズは O(B) である
- 一つの外部メモリのブロックサイズに合うように B の値を設定する