我已经阅读了几篇关于K-D树与R树的SO帖子，但是我仍然对我的特定应用有疑问。
对于我的Java应用程序，我想维护相对较少的空间数据点（数十万）。关键是数据插入将不会批量加载，而是频繁且增量地插入。我还应该提到，我将在空间域的子区域上执行大量的周期性范围查询。
我已经读过K-D树通常不支持增量构建，而R树由于保持平衡状态而更适合于此。
但是，在研究了此处建议的解决方案之后：
Java commercial-friendly R-tree implementation?
我发现这些实现不易于返回范围搜索中的点列表。但是，我发现：http://java-ml.sourceforge.net/具有一个非常好的K-D树实现，该树可以快速工作并且在测试点集（〜25K）方面优于标准数组存储。此外，我已经读到R树在处理点时会存储冗余信息（因为点是min = max的矩形）。
由于我使用的点数较少，因此，如果我使用的数据库应用程序存储了数百万个点，那么两种结构之间的区别是否不那么重要？
最佳答案
R树无法存储点是不正确的。它们被设计为支持矩形，并且将需要在内部节点上这样做。但是一个好的实现应该在叶级存储点，并且在那里大约具有两倍的数据容量。
您可以琐碎地存储点，并将它们显示为最小= max的“矩形”，显示给树管理代码。
您的数据不小。小将是100个对象。对于100个对象，R树没有多大意义，因为它可能仅包含一个叶子。为了获得良好的性能，R树需要良好的扇出。 k-d树的扇出度始终为2；它们是二叉树。在10万个对象的情况下，一个k-d树将非常深。假设扇出数为100（对于动态r树，则每页最多应允许200个对象），则可以在三层树中存储100万个点。
我使用了ELKI R * -tree，它的速度非常快。但这不是商业友好的，除非您获得了不同的许可：它是AGPL-3许可的，这是一个copyleft许可。
此外，该API并非为独立使用而设计。如果要使用它们，最好的方法是使用完整的ELKI框架，而不是尝试提取R * -tree。
如果您的数据是低维的（例如3维）并且具有有限的边界，请不要低估基于网格的简单方法的性能。特别是对于内存操作。在许多情况下，我什至不去使用Octree，而只是为我的用例定义最佳网格，然后使用对象列表实现它。在每个网格单元内保持按一个坐标排序，以进一步提高性能。