我已经阅读了几篇关于 KD Trees 与 R-Trees 的 SO 帖子，但我仍然对我的具体应用有一些疑问。
对于我的 Java 应用程序，我想维护相对少量的空间数据点（几十万）。关键是数据插入不会被批量加载，而是频繁且增量地插入。我还应该提到，我将对空间域的子区域执行大量的周期性范围查询。
我读过 KD 树通常不支持增量构建，而 R 树更适合于此，因为它们保持平衡状态。
但是，在查看了此处建议的解决方案后： Java 对商业友好的 R-tree 实现？
我没有发现这些实现很容易用于返回范围搜索中的点列表。但是，我发现： http: //java-ml.sourceforge.net/有一个非常好的 KD 树实现，它可以快速运行，并且在一组测试点（~25K）方面优于标准数组存储。此外，我读过 R 树在处理点时会存储冗余信息（因为点是最小 = 最大值的矩形）。
由于我使用的点数较少，因此这两种结构之间的差异是否比使用存储数百万点的数据库应用程序更重要？
R-trees 不能存储点是不正确的。它们旨在支持矩形，并且需要在内部节点处这样做。但是一个好的实现应该在叶子级别存储点，并且在那里大约有双倍的数据容量。
您可以简单地存储点，并将它们作为具有 min=max 的“矩形”公开给树管理代码。
你的数据不小。小就像 100 个物体。对于 100 个对象，R-tree 没有多大意义，因为它可能只包含一个叶子。为了获得良好的性能，R-tree 需要良好的扇出。kd-tree 的扇出总是 2；它们是二叉树。在 100k 个对象时，kd-tree 将非常深。假设您有 100 个扇出（对于动态 r-tree，则应允许每页最多 200 个对象），您可以在 3 级树中存储 100 万个点。
我使用了ELKI R*-tree，它非常快。但它不是商业友好的，除非您获得不同的许可证：它是 AGPL-3 许可的，这是一个 copyleft 许可证。
此外，API 不是为独立使用而设计的。如果你想使用它们，最好的方法是使用完整的 ELKI 框架，而不是试图撕掉 R*-tree。
如果您的数据是低维（例如，3 维）并且具有有限界限，请不要低估简单的基于网格的方法的性能。特别是对于内存操作。在许多情况下，我什至不会使用八叉树，而只是为我的用例定义最佳网格，然后使用对象列表来实现它。在每个网格单元内保持一个坐标排序，以进一步提高性能。
如果您想经常添加/删除/更新数据点，您可能需要查看 PH-Tree。在开源 Java 版本上可用：www.phtree.org
它的工作方式有点像四叉树，但通过使用二元超立方体和前缀共享更有效。
它具有出色的更新性能（不需要重新平衡）并且内存效率很高。它适用于较大的数据集，但 100K 对于 2 或 3 维应该没问题。