我最近正在阅读关于R树及其变体的论文和代码：线性、二次、R*-树，以及R树包装（STR）。在我看来，不同的技术在树创建、范围搜索和knn搜索的时间复杂性方面是不同的。STR树似乎比其他树更好。然而，这些论文是上个世纪的。我只是想知道，近20年后，目前最好的R树变体是什么？
另一个较新的树是X树（也基于R树）。
如果你正在寻找通用的空间索引，而不仅仅是R树，我可以推荐PH树。它可以很容易地在矩形或范围查询方面与R-Tree变体竞争，具有很好的kNN查询支持（在21维方面仅比Cover Tree慢50%），它可以很好地扩展大型和/或集群数据集，并且非常节省空间。最棒的可能是它具有出色的更新性能，插入/移动/删除所需的时间几乎不超过查找时间。另一个优点是，它不需要重新平衡，这意味着任何更新都不会影响超过2个节点。
缺点：
- 低维的实现相当复杂，但如果您对Java实现很满意，这里是我的
- 高维度的实现不那么复杂，但对于小于10个维度的实现速度较慢
- 它更喜欢集群数据，但对于分布更均匀的数据，性能仍然可以
R*树被证明工作得很好，并继续成为首选变体。
STR等批量加载技术是快速（更好）构建初始树的绝佳补充，而不是逐个插入对象。
因此，通常情况下，您会想要一个带有STR批量加载的R*-树。