4

我的应用程序从地图文件中加载约 100k 项（矩形）的集合，然后构建 MX-CIF 四叉树作为快速查找的索引。四叉树是在启动时构建的，它的内容在运行时不会改变。

（在 MX-CIF 四叉树中，项目由完全包含它的最小节点存储......内部和叶节点都可能包含项目）

在第一遍中，我找到了集合的外部范围，因此我知道根节点有多大。

在第二遍中，我将每个项目添加到完全包含它的最小节点。一旦一个节点传递了一定数量的项目，它就会被拆分，并且子节点会在新的父节点和 4 个子节点之间重新分配。

鉴于我已经预先准备好所有项目，我怎样才能更有效地构建树？

4

1 回答 1

1

您真的需要 MX-CIF 树吗？对于矩形，我建议使用 X-Tree 或 PH-Tree。

X-trees 是从 R-trees 派生的，如果您提前知道整个数据集（批量加载），则它具有极好的插入时间。它们还具有非常好的范围查询性能。可以在此处找到示例实现： XXL 库

PH-Tree 在批量加载时稍微慢一些，但如果对象在之后更新/移动，则速度要快得多。范围查询性能类似于 X-tree，但 PH-tree 在提取小结果集时更快（主要成本在于提取值，而对于 X-tree，主要成本在于处理查询（找到第一个节点） , ...))。此处提供 PH-tree 实现：PH-Tree

免责声明：我参与了 PH-tree 的开发。

于 2015-02-06T11:29:11.843 回答