median 切分 · 回溯剪枝 · 维度灾难

k-d tree 与最近邻回溯

quadtree 的格线仍落在区域正中，与数据无关。k-d tree 把这最后一点无关性也去掉：切分面直接穿过数据的 median，于是每一刀都把点数对半分，树高不依赖分布。

代价是这棵树只对建好的那批点成立。插入一个新点，median 就不再是 median。

1 · 轮流按维度切

一个节点只切一维，切完把维度轮换给孩子。

定义 1.1（k-d tree） 一棵二叉树，深度 $d$ 的节点按第 $d \bmod k$ 维切分（ $k$ 为空间维数）。节点自身存一个点 $p$ ，左子树的全部点在该维上不大于 $p$ ，右子树不小于 $p$ 。取 $p$ 为该维上的 median 时，两侧点数之差不超过 1。

建树用 quickselect 就地找 median，不必整体排序。每层 $O(n)$ 、共 $\log n$ 层，总计 $O(n \log n)$ 。实现里那个 quickselect 的 pivot 取三点中值而不是随机，目的是可复现：同一批点永远建出同一棵树，测试与正文里的数字才对得上。

2000 个点建出的树高实测 11，而 $\log_2 2000 = 10.97$ 。这不是巧合而是定义的直接推论：median 切分保证每层点数对半，树高恒为 $\lfloor \log_2 n \rfloor + 1$ 。测试里这条写成一个上界断言， $n$ 取 1、2、7、100、1000 各验一次。

图 1-1 · k-d tree 的逐层切分。竖线是按

x

切、横线是按

y

切，颜色区分维度，线的粗细表示层深。可改层数上限与点分布，观察切分面如何贴着数据而非坐标系。

与 quadtree 并排看，两者的差别可以压成一句：quadtree 问「这块区域该不该再切」，k-d tree 问「这批点该在哪切」。前者的格子位置能由坐标直接算出，后者必须沿树下降才知道。

2 · 范围查询与树高

范围查询递归下降，在每个节点上做两件事：判本节点存的那个点是否在矩形内，以及判两侧子树要不要下去。后者只看一维——查询矩形在切分维上的下界若不超过切分值，左子树就有可能有货。

访问的节点数随查询窗增大而增：2000 个点上 60 见方的窗平均访问 61.36 个节点，160 见方的访问 267.95 个。值得注意的是「访问节点数」与「点级判定次数」在 k-d tree 上恒相等，因为 k-d tree 的每个节点都存着一个点，进了节点就得判它。这与 quadtree 不同：那边的内部节点不存点，访问它只是一次矩形相交测试。

这条差别在选型对照 §1 的表里看得最清楚：同一批查询下 k-d tree 的两个指标都是 61.36，quadtree 是 65.76 与 28.05。谁更快，取决于「访问一个节点」与「判定一个点」哪个更贵。

3 · 最近邻的回溯与剪枝

kNN 是 k-d tree 最出名的用法，全部效率集中在一步判断上。

算法沿树下降，每到一个节点：算本节点那个点到查询点的距离并更新候选集；然后按查询点落在切分面哪一侧，先递归近侧；近侧回来后，检查「查询点到切分面的距离」是否小于「当前第 $k$ 名的距离」。是则远侧还有可能有更近的点，必须下去；否则整棵远侧子树剪掉。

\text{下远侧} \iff (q_{a} - p_{a})^2 \le r_k^2, \qquad a = d \bmod k,\ r_k = \text{当前第 } k \text{ 名的距离}

次序不能反。先搜近侧的意义是尽快把 $r_k$ 压小，后面的判断才有力；先搜远侧算法仍然正确，但 $r_k$ 一直是 $\infty$ ，剪不掉任何东西。

图 3-1 · 最近邻查询的回溯过程。绿圈是当前第

k

名的距离，红色切分线是刚判定过的切分面。可单步推进、改

k

并拖动查询点，读数给出访问节点数与它占

n

的比例。

实测的剪枝强度相当可观。2000 个均匀点、200 次查询： $k = 1$ 平均访问 14.71 个节点，占 $n$ 的 0.74%； $k = 5$ 是 22.14 个、1.11%； $k = 20$ 是 58.54 个、2.93%。 $k$ 涨 20 倍，访问量只涨 4 倍，因为 $r_k$ 随 $k$ 增长的速度是 $\sqrt{k}$ 。

4 · 回溯条件里的等号

上面那个式子写的是 $\le$ 。最初的实现写的是 $<$ ，浮点坐标上跑了多个种子、几百次随机查询，结果全部与朴素排序一致，看不出问题。

打穿它的是整数格点：12 × 12 的等距格点、间距 8，查询点取格心。 $k = 4$ 时实现给出的第四名是 id 77，朴素全量排序给的是 id 66，两者到查询点的距离完全相等。差别在稳定次序上：本系列约定距离并列时按 id 升序，66 该顶掉 77，而 $<$ 让那棵含 66 的远侧子树被剪掉了。

改成 $\le$ 之后一致。这个错误在随机浮点数据上几乎不可能触发：两个点到查询点的距离要精确相等，需要坐标本身有对称性，而均匀随机数不会给出对称性。所以测试里那条断言用的是手工构造的等距格点，不是随机点集。只在结构化输入上暴露的错误，随机测试兜不住。

注 · 距离并列时返回谁属于实现自由，规范并不要求任何特定次序。但一旦对外声称「结果与朴素排序一致」，这个自由就没了：并列的处理方式必须与 oracle 完全对齐，否则测试会时红时绿。本系列把口径写死成先比距离、并列时比 id 的双键升序，四个结构与朴素基线共用同一个比较函数。

5 · 维度灾难

k-d tree 的剪枝在 2 维极强，在高维完全消失。这不是实现问题，是几何问题。

维数上升时，随机点之间的距离迅速集中： $d$ 维单位立方体里两个随机点的距离期望约 $\sqrt{d/6}$ ，而标准差只有 $O(1)$ 。查询点到最近邻的距离与到第 100 名的距离越来越接近，也就与「到切分面的距离」越来越接近。回溯条件里那个比较几乎恒成立，远侧永远要下。

2000 个点、 $k = 1$ 、每维 40 次查询，访问节点数占 $n$ 的比例实测：

维数	2	3	4	6	8	10	12	16	20	32
访问比例	0.82%	1.60%	1.94%	9.04%	26.18%	62.24%	89.41%	99.77%	100.00%	100.00%

10 维已经访问了六成节点，16 维是 99.77%，比线性扫描还贵：每个节点除了算距离还多一次回溯判断。测试里把这条曲线钉成两个断言：2 维必须低于 $n$ 的 2%，16 维必须高于 90%。

图 5-1 · 访问节点数占

n

的比例随维数的变化。折线是实测值，虚线是线性扫描的 100% 基准。可改点数与

k

，观察拐点位置几乎不随规模移动。

拐点的位置几乎不随 $n$ 变化，这一点值得强调：把点数从 2000 加到 20000 不会让 10 维变得可用。高维近邻检索走的是另一条路：放弃精确性，用 LSH 或 HNSW 之类的近似方法。它们的目标不是「找到最近邻」而是「以高概率找到足够近的邻居」，那是另一个题目。

6 · 静态结构的代价

median 建树给出的平衡是一次性的。插入一个新点，可以沿树下降到叶子挂上去，但它不再保证平衡：连续插入 $n$ 个有序点会长出一条链。

主流做法是不支持插入。前端最常用的 k-d tree 实现 kdbush 直接以此为设计前提：建一次、查很多次，数据变了就整棵重建。重建是 $O(n \log n)$ ，对几万个点来说是几毫秒，比维护平衡便宜也简单。

需要动态更新时的替代品有三个方向：quadtree（插入 $O(\text{深度})$ ，形状与数据无关所以插入不破坏任何不变量）、R-tree（为动态更新设计，分裂与合并都有定义）、以及定期重建加上一个小的「增量缓冲区」，查询时同时查主树与缓冲区，缓冲区涨到一定大小就合并重建。

7 · 参考文献

Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509–517.
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977). An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3(3), 209–226.
Weber, R., Schek, H.-J., & Blott, S. (1998). A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. Proceedings of the 24th VLDB Conference, 194–205.
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999). When is "nearest neighbor" meaningful? Proceedings of the 7th ICDT, 217–235.