查询区域可能包含树中所有的点，这种情况下，drain方法将会遍历所有的点，性能将会是不能接受的O(n)。但是，当范围查询算法检测到查询的范围不和kd树的某个节点表示的范围相交的话，那么将会剪除对子树的查找。节省的开销取决于维度和输入数据的一些特性。有研究(Preparata和Shamos，1985）表明范围查询算法的性能是O(n1-1/d+r)，r是结果集中点的数目。随着维度的增加，性能逐渐下降。图9-25是一个O(n1-1/d)算法的期望性能，该图表明在小维度下，算法的性能逐渐逼近O(n)。因为还需要考虑r，所以实际性能将会偏离图9-25的理想曲线。
图 9-25 O(n1-1/d)算法的期望性能我们很难生成测试范围查询算法性能的数据。我们只能通过和穷举算法进行比较来证明此算法的效率。下面这些情况下，我们使用n个d维点作为输入来进行比较。这些点的坐标值区间是[0,4096]。
情况1：查询区域包含树中所有的点
我们构建了一个包含kd树中所有点的查询区域。这个例子告诉我们的区间查询算法能够提供的最大性能改进，这种情况下，其性能和kd树的维度d无关。我们会执行大约5～7次实验，然后能看到kd树相关的操作所需要的开销。在表9-7中，穷举算法的开销随着维度d的增加而增大，因为计算d维点之间距离的操作是O(d)而不是常数。穷举算法在高维度上性能轻易地超过了基于kd树的最邻近点算法。
情况2：微小区域
因为结果集中的点数r能较大程度地影响算法的性能，我们构建一系列的场景，使得在维度增加的情况下，r并不改变。由于输入集合的一致性，我们不可能简单地构造一个查询区域。如果我们这样做，那么选择的输入集合总数将会是(1/2)d，也就是说，维度d的增加会导致r的增加。实际上，我们会构建一些查询区域，这些区域的规模随着维度的增加而增加。例如，二维的查询区域会返回0.23*n个点。但是，在三维上，查询区域应该扩展更大的范围。这样的话，我们就能预先限定因子k，结果集包含k*n个点。我们也会比较kd树的实现和穷举方法的实现，n的范围从4096～131 072，d从2～15，结果如图9-26所示。左边的表是kd树实现的典型行为，右边是穷举算法的线性行为。k=0.23时，kd树的实现只是在d=2和n≤8192时表现较好。
图 9-26 第二种情况下，范围查询算法和穷举算法的比较情况3：空区域
我们这样来构造一个查询区域，这个区域就是输入中的一个点。性能见表9-8。kd树能够在很短的时间内就计算完成。我们记录的时间都不到1毫秒。