disk - 二次記憶上の KD ツリー?

Question

kd-tree、Range tree、quad-treeなどの範囲検索データ構造の一部を知っています。しかし、すべての実装はメモリ内にあります。パフォーマンスの高い I/O 効率でセカンダリ メモリに実装するにはどうすればよいでしょうか?

条件は次のとおりです。

1): 2 次元上の点の静的セット。

2): クエリのみで、インセットや削除はありません。

3): 二次記憶に適応します。

ありがとう。

Answer 1

構築中にツリーをメモリに収めることができる場合:

1. kd ツリーを構築します。

2. 下から上へ、ハードウェア サイズのブロックに収まるできるだけ多くのポイントを収集します。

3. このブロックにデータを書き込みます。

4. 2.～3.を繰り返します。すべてのデータをディスクに書き込むまで、再帰的に。

クエリを実行するときは、ディスクからページをロードし、別のページへの参照に到達するまでツリーのこの部分を処理します。次に、このページを読み込んで続行します。

または、同じトップダウンを行うこともできますが、その場合はより多くのディスク領域が必要になる可能性があります。上記のアプローチでは、ルートページのみがほぼ空になる可能性があります。