disk - 辅助存储器上的KD-Tree？

Question

我知道一些范围搜索数据结构，例如 kd-tree、范围树和四叉树。但是所有的实现都在内存中，我怎样才能在二级内存上以高性能的 I/O 效率实现它们呢？

这是条件：

1)：二维上的一组静态点。

2）：仅用于查询，没有插入或删除。

3）：适应二级内存。

谢谢。

Answer 1

如果您可以在构建过程中将树放入内存中：

1. 构建 kd 树。

2. 自下而上，收集尽可能多的点以适合您的硬件大小的块。

3. 将数据写入此块。

4. 重复 2.-3。递归，直到您将所有数据写入磁盘。

查询时，从磁盘加载页面，处理树的这一部分，直到到达对另一个页面的引用。然后加载此页面并继续。

或者，您可以自上而下执行相同的操作，但您可能需要更多磁盘空间。在上述方法中，只有根页面可以接近空。