二级存储器上的KD树？

Question

我知道一些范围搜索数据结构，例如kd-tree，Range树和quad-tree。 但是所有的实现都在内存中，我如何在高性能I/O效率的辅助内存上实现它们？

这里是条件：

1）：一组静态上的两个尺寸点。 2）：仅用于查询，不插入或删除。

3）：适应二级存储器。

谢谢。

Answer 1

如果你能在施工期间适应树到内存：

1. 构建kd树。

2. 底部向上收集尽可能多的点以适合您的硬件尺寸块。

3. 将数据写入此块。

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

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

或者，你可以做同样的自顶向下，但是你可能需要更多的磁盘空间。在上述方法中，只有根页面可以接近空白。