我试图找出哪种结构更适合对点进行多个半径搜索，kd 树还是八叉树？在这个问题中已经提到过，但没有答案。在我看来，由于八叉树的叶子大小是固定的，因此已经可以计算出我需要访问的分支，而对于 kd 树，您必须迭代访问分支，直到覆盖半径。
我个人也正是为了这个目的才实现了投票给八叉树。我发现使用八叉树更容易获得更有效的结果。我说更容易，因为我认为有了这些微妙的区别，它实际上更多地与实现者有关，而不是与数据结构有关。但我认为对于大多数人来说，优化八叉树会更容易。
原因之一是因为 K-D 树本质上更深，是一次在一个维度上分裂的二叉树。如果您正在叶子上寻找精确的匹配元素，例如光线/三角形与树上单一、明确的路径的交点，那么这种更深层次的性质会很有帮助。当仔细分割的深层树与搜索质量的理念相匹配时，它会很有用。
如果您要在最大半径内搜索最近的点，而您最终花费大部分时间在树上上下移动，从叶子到父级再到兄弟级，那么拥有一棵深的、仔细分裂的树就没那么有帮助了祖父母、父母兄弟姐妹等等。如果您可以以缓存友好的方式访问所有内容，那么它会更平坦一些，并且您可以轻松地使八叉树缓存友好，例如连续存储所有 8 个子级，此时您可以这样做：
struct OctreeNode
{
// Index of first child node. To get to the 4th node,
// we just access nodes[first_child+3], e.g.
int first_child;
...
};
所以无论如何，如果这是两个选择，我在这种情况下投票支持八叉树。此外，对于这种类型的邻近搜索，您不一定希望八叉树太深。即使我们必须使用较浅的树查看比最佳点更多的点，这也比在树上频繁上下移动要好。如果您存储在叶子中的点是连续的，它确实有帮助。完成树的构建后，您可以通过后处理来实现这一目标。
请注意，对于这两种解决方案，您都必须查看兄弟节点。距离某个点最近的点不一定是位于同一叶节点中的点。在某些情况下，根据数据的性质，仅使用 3 维网格实际上就可以达到此目的，因为使用 3D 网格，您甚至不必费心从子项到父项再到兄弟姐妹。 3D 网格在内存使用方面似乎呈爆炸性增长，但如果将网格单元的内存开销减少到仅 32 位索引，则不一定如此。在这种情况下，100x100x100 网格占用的空间不到 4 MB。
对于 3D 和固定查询半径，八叉树是一个不错的选择。如果您需要在磁盘上工作，其他数据结构可能会更好，但 k-d-tree 在这里也不起作用。
为什么不尝试两者并看看哪种更适合您的数据？
在我的项目中，我使用八叉树进行范围搜索，它工作高效且易于实现。但从未将它与 KD-Tree 进行比较。 据我所知，对于三维数据，kd 树中此操作的最坏情况时间复杂度是 O(n^(2/3))，而八叉树只能保证 O(n)。因此，如果您关心最坏时间复杂度，请选择 KD Tree。 （我不关心最坏的时间复杂度，如果我知道在我的数据集中这永远不会发生。）
我之前对同样的问题很感兴趣，做了以下实验来对比。
Operation K-D Tree Octree
Build Tree 7 ms 12 ms
K-NN Search (k=1) 124 ms 390 ms
K-NN Search (k=10) 124 ms 395 ms
K-NN Search (k=100) 134 ms 573 ms
Radius Search (r=0.01 m) 1789 ms 126 ms
Radius Search (r=0.1 m) 1799 ms 129 ms
Radius Search (r=1 m) 2011 ms 415 ms
此外，我还针对这个结果做了一些消融研究。