二級存儲器上的KD樹？

Question

我知道一些範圍搜索數據結構，例如kd-tree，Range樹和quad-tree。 但是所有的實現都在內存中，我如何在高性能I/O效率的輔助內存上實現它們？

這裏是條件：

1）：一組靜態上的兩個尺寸點。 2）：僅用於查詢，不插入或刪除。

3）：適應二級存儲器。

謝謝。

Answer 1

如果你能在施工期間適應樹到內存：

1. 構建kd樹。

2. 底部向上收集儘可能多的點以適合您的硬件尺寸塊。

3. 將數據寫入此塊。

4. 重複2.-3。直到您將所有數據寫入磁盤。

查詢時，從磁盤加載頁面，處理這部分樹，直到您到達對另一頁的引用。然後加載此頁面並繼續。

或者，你可以做同樣的自頂向下，但是你可能需要更多的磁盤空間。在上述方法中，只有根頁面可以接近空白。