我正在做这个项目，我必须在 3d 空间中搜索对象，效率是一个很大的问题，我认为范围树非常适合我想要做的事情，间隔树也可以工作，但我不是要从树中删除任何内容，一旦我在 3D 空间中添加了每个对象，我将只使用该结构进行搜索。
下面是我将如何使用该结构：
假设我有一个对象数组（我们称之为queryArr）（约 10,000 个对象）每个对象有 3 个参数（x，y，z）我有另一个非常大的对象数组（我们称之为totalArr）（> 5,000,000 个对象） ）。
我想在这里做的是给定的元素queryArr，找到最相似（或相同的元素totalArr）在某些情况下会出现在相同的参数对象totalArr，但在大多数情况下，不会有是具有相同参数的对象。
因此，我将搜索(x+10,y+10,z+10)和之间的所有值(x-10,y-10,z-10)。如果它没有产生任何结果，我会将 x,y,z 乘以 2 并重试，直到产生一些结果。
这样做的最简单方法是一种朴素的搜索方法，它具有复杂性， O(N*M) (N = size of queryArr, M = sie of totalArr)但这种方法非常缓慢和愚蠢。
我认为范围树是要走的路，但我自己从未实现过，我不太明白范围树如何在大于 2 的维度上工作。那么有人知道范围树的良好实现吗？我相信如果我能有一个源代码，我就能理解它们是如何工作的。
顺便说一句，如果您认为此任务有比范围树更好的结构，请告诉我我愿意接受建议。（我已经考虑过 kd-Trees 和 Interval 树）
谢谢，