我想知道是否存在比四叉树更适合放置系统的空间分区数据结构。更适合的意思是数据结构在搜索查询和使用更少的内存时具有O(logn)或更少的时间复杂度。我想知道什么样的数据结构可以组织我的数据使查询速度比四叉树更快。它都是二维的，而且都是不重叠的矩形。我目前有一个四叉树，它工作得很好，而且速度很快，我只是想知道是否有一种数据结构使用更少的资源，并且在这种情况下比四叉树更快。
最快的可能是在GPU上强制执行。
同样，也值得尝试不同的实现，我发现实现之间的性能差异非常大。
另一个提示:用实际数据衡量性能(可能是多个场景)，数据和使用特征可能对索引性能产生巨大影响。
其中一些特征是(你已经提到了"矩形数据"one_answers"2 d"):
- 你的数据集有多大
- 矩形之间有多少重叠?
- 你需要经常更新数据吗?
- 你的小矩形和大矩形之间有很大的差异吗?
- 你有密集的矩形簇吗?
- 你覆盖的面积有多大?
- 你的坐标是整数还是浮点数?
- 如果操作的执行时间不同或者应该保持一致，是可以的吗?
- 可以预加载数据吗?你需要更新索引吗?
四叉树可能是一个很好的初始选择。然而，他们也有一些问题，例如:
- 它们可以用密集的簇变得非常深(和低效)
- 当矩形之间有很多重叠时，它们的效果不太好
- 如果合并或分裂节点，更新操作可能需要更长的时间。
另一个流行的选择是R-Trees(我发现R-star-Trees是最好的)。一些属性:
- 平衡(对于可预测的搜索时间很好，但由于重新平衡，更新时间可能非常不可预测)
- 实现起来相当复杂。
- r - tree也可以预加载(需要更长的时间，但允许查询更快)，这被称为STR-Tree (sort -tile- recursive -r - tree)
PH-Tree可能值得一看(免责声明:自我广告):
- 与四叉树相似，但深度受限于数据的位宽(通常为32或64位)。
- 不平衡。合并或分割保证只移动一个条目(=cheap)
- 更倾向于整数坐标，但对于浮点数据也能很好地工作。
- 实现可以是相当有效的空间(他们不需要存储所有的坐标位)。然而，并不是所有的实现都支持这个功能。此外，这种效果是不同的，并且在整数坐标下最强。
我在这里做了一些测量。测量包括一个2D数据集，其中我将OpenStreetMap的线段存储为方框，相关图表标记为"OSM-R"(R代表矩形)。
-
无花果。3a显示了将给定数量的数据插入树的时间
-
无花果。9a显示内存使用情况
-
无花果。15a显示了平均返回1000个条目的查询的查询次数
-
无花果。17a显示了当改变查询窗口大小时(在有1M项的索引上)查询性能的变化
-
无花果。41a显示了包含1M项的索引的平均更新时间
-
PH/PHM为PH- tree, PHM在存储坐标前将坐标转换为整数
-
RSZ/RSS是两种不同的R-Tree实现
-
STR是STR- tree
-
Q(T)Z是四叉树
如果您正在使用Java，请查看我的空间索引集合。其他编程语言也存在类似的集合。