二维索引数据结构

Question

我需要在数据上具有内存中的二维索引。使用场景：

1. 稀有批量写入-新元素将以大块添加，与读取相比，添加频率非常低。

2. 频繁读取。范围查询（a < x < b AND n < y < m）应该很快。我没有给出关于“快速”是什么的任何度量，因为它显然取决于许多超出此问题范围的事情。

3. 数据全部在内存中

我已经测试了两个选项：

1. Quadtree。不幸的是，范围查询的性能不足，尤其是在它与多个高级四边形相交的情况下。
2. R树。尽管查询比四叉树更快，但在我看来，它太复杂了。另外，我从论文中得到的是R-tree可以处理分页数据。

还有哪些其他选项需要考虑，哪些可以提供最高范围的查询性能？

Answer 1

如上面的评论所述，四叉树应该很快，但是当将其除以2多次时，就数值精度而言，它们有些困难。R树的构建速度较慢，而且更为复杂。它们确实非常适合磁盘存储，但是您可以在内存中自由调整节点大小，直到达到最佳性能为止。如果可以批量加载，请查看STR-R-Tree（排序-分片-递归），它们构建缓慢，但之后性能最佳。否则，以我的经验，R * Trees（RStarTrees）是最好的。

[如果您使用的是Java，也许您找到了我的TinSpin索引集合，则可以尝试多个索引，包括PH树（按位四叉树），该树的构建速度非常快，但使用（小） ）窗口查询。对于大窗口查询（每个窗口1000个或更多结果），Rtree可能更好。