MX-CIF四叉樹的批量加載算法

Question

我的應用程序從一個映射文件加載一個〜100k項目（矩形）的集合，然後構建一個MX-CIF四叉樹作爲快速查找的索引。四叉樹在啓動時構建，其內容在運行時不會更改。

（在MX-CIF四叉樹，項目存儲由完全包含它的最小的節點...內部和葉節點可包括項）

在第一遍中，我發現的外區段集合，所以我知道根節點有多大。

在第二遍中，我將每個項目添加到完全包含它的最小節點。一旦一個節點傳遞了一定數量的項目，它就會被拆分並且子項在新的父項目和4個子項目節點之間重新分配。

鑑於我預先準備了所有的項目，我怎樣才能更高效地構建樹？

Answer 1

你真的需要MX-CIF樹嗎？ 對於矩形我建議使用X-Tree或PH-Tree。

如果您事先知道整個數據集（批量加載），則X樹從R樹導出並具有優秀的插入時間。他們也有很好的範圍查詢性能。一個示例實現可以在這裏找到： XXL Library

PH-Tree在批量加載時稍慢，但是如果對象之後被更新/移動，PH-Tree會稍微慢一些。範圍查詢性能與X樹相似，但PH樹在提取小結果集時速度更快（主要成本在於提取值，而對於X樹，主要成本在於處理查詢（找到第一個節點，...））。 PH樹實現可在此處獲得：PH-Tree

聲明：我參與開發PH樹。