如果k d树初始是平衡的，那么每一层的切分线正好穿过此层的中点。我们能够在O(log n)的时间内找到目标点区域。但是，这个算法有可能会调用两个查找：一个是查找左子树，一个是查找右子树。如果这种情况频繁地出现，算法的性能会退化到O(n)，所以值得我们分析这种情况发生的频率。当从目标点到节点的垂直距离dp小于已知最小距离时，我们可能需要执行多个调用。随着维度的增长，可能会有更多的点满足这个条件。表9-6是这种情况发生几率的经验性总结。我们在单位正方形中生成n个随机二维点，n从4～131 072，在这些点上构建一棵平衡的kd树。我们会有50个查询，表9-6记录了两个递归调用和单个递归调用发生的平均次数。
我们可以看到，在随机生成的二维数据上，产生两个调用的次数是0.3*log(n)，但是在十维上，这个数目会升到342*log(n)（1000倍左右的提升）。我们可以观察到，这个估计值大约是O(log n)。但是当d增长到“足够接近”n时，会发生什么呢？图9-22的结果告诉我们，随着d的增长，两个调用发生的次数逐渐逼近n/2。事实上，d增长时，单次调用的次数遵从正态分布，其中值趋近于log(n)，两种递归调用最终恰好是各占一半。这个结论对与性能的影响就是使得查询在d增长的情况下，性能逼近log(n)。在这种极端情况下，使用kd树，性能不会好于O(n)。
图 9-22 随着n和d增长，两个递归调用的次数算法在某些特定的输入数据上性能退化非常严重。例如，我们将表9-6的输入点改成在一个半径大于1的圆内，但是查询的点还是在单位正方形中。当n=131 072时，单个递归调用的数量跳到235.8个，而两次递归调用的数量会增加到932.78个。因此最邻近点算法的性能会退化到最坏的O(n)。
我们也可以对比一下基于kd树的最邻近点算法和穷举算法的性能。我们有这样一个例子，4096个点和128个查询，那么维度d从多大开始，kd树的性能会差于最原始的穷举算法呢？我们执行了100次实验，抛弃最好和最坏的结果，取剩余98次的平均值。结果如图9-23所示，维度从10开始，原始的穷举算法的性能就开始占优。当n增加到131 072个，原始穷举算法的性能在d=12时开始占优，所以拐点出现的位置和n、d以及输入点的分布情况相关。我们不会分析在这个拐点上，构建kd树的开销是多少，因为这个开销都被分摊到了每次查询上。
图 9-23 比较kd树和穷举实现图9-23的结果证实了随着维度的增加，使用kd树获得的性能改进越来越少。等式中主要的驱动因素不是构建kd树的开销，而是将要插入kd树中的点的个数。在大规模数据集合上，节省的开销是显而易见的。另外一个影响性能的因素是维度d，计算两个d维点的欧几里德距离是O(d)的操作，随着d增加，每次计算需要更多的时间。