选型 · 两个记账指标 · 退化条件

四个结构的横向对照

四个结构的渐近复杂度都是同一量级：范围查询 $O(\sqrt{n} + m)$ 上下，最近邻期望 $O(\log n)$ 。选型不靠这个。本页把它们放在同一点集、同一批查询下量出具体数字，再从数字倒推判据。

1 · 同一批查询下的对照

512 见方、2000 个均匀随机点；200 次 60 见方的窗口查询，200 次 $k = 5$ 的最近邻查询。格子边长 32、quadtree 容量 4、R-tree 取 $m = 2$ 、 $M = 4$ 。

结构	range 访问节点	range 点级判定	kNN 访问节点	kNN 距离计算
线性扫描	1.00	2000.00	1.00	2000.00
uniform grid	8.04	62.13	6.00	50.38
quadtree	65.76	28.05	14.38	11.20
k-d tree	61.36	61.36	22.14	22.14
R-tree	36.17	112.32	12.00	7.71

两列给出的排名是反的。按访问节点数排，grid 第一（8.04）、R-tree 第二、quadtree 垫底（65.76）；按点级判定排，quadtree 第一（28.05）、grid 第二、R-tree 垫底（112.32）。

这不是测量噪声，是三个结构的不同取舍。grid 的格子少而胖，一次访问带回一大把点；quadtree 的节点多而瘦，且能整块吞下完全落在查询窗里的叶子（见 quadtree 与 octree §4），点判定省到极致；R-tree 的每次「访问节点」要逐条判 $M$ 个 MBR，所以判定数最高，但节点数介于两者之间。

k-d tree 的两列恒相等，因为每个节点存一个点，进节点就得判它。

图 1-1 · 四个结构在同一次查询上的记账对照。可拖动查询窗、切换查询类型与点分布，表格逐行给出访问节点数与点级判定数，柱状图按当前选中的指标排序。

2 · 分布倾斜时谁退化

把同一批点换成 5 个高斯团簇，别的都不动：

结构	range 判定（均匀 → 团簇）	kNN 访问节点（均匀 → 团簇）
uniform grid	62.13 → 78.85	6.00 → 38.55
quadtree	28.05 → 21.70	14.38 → 21.75
k-d tree	61.36 → 69.78	22.14 → 66.74
R-tree	112.32 → 113.89	12.00 → 16.27

range 那一列几乎没动，kNN 那一列变化剧烈。grid 的 kNN 访问量涨了 6.4 倍，这在意料之中：团簇里的一个格子装了 70 个点，方环扫一圈就是几十次距离计算。

意外的是 k-d tree：涨了 3.0 倍，比 quadtree 的 1.5 倍差一倍。原先的猜想是 median 建树对倾斜分布免疫，理由是树高与分布无关——树高确实没变（实测仍是 11），但 kNN 访问量变了。成因是 median 平衡的是点数而不是空间体积：团簇内部的节点各自负责一块又窄又长的区域，而回溯剪枝的下界是「查询点到切分面的距离」，对细长区域给出的下界很松。quadtree 的区域永远是正方形，同样的下界紧得多。

这条对 R-tree 同样成立但程度轻微（12.00 → 16.27），因为 R-tree 的 MBR 贴着实际数据，团簇内的框虽小却仍大致成方。

警示 · 「树高不变」不等于「性能不变」。平衡性是关于点数的断言，而空间查询的代价由几何形状决定。用树高判断一个空间索引健不健康，会漏掉这一整类退化。

3 · 按场景选

把上面的数字连同各结构的更新代价合并，得到一张实际可用的表。

场景	选什么	理由
静态点集，建一次查很多次	k-d tree	树高有保证、无参数可调；不支持插入正好不是问题。前端实现见 `kdbush`
点频繁增删，位置常变	uniform grid 或 quadtree	前者定位 $O(1)$ 且天然并发安全，后者插入只需沿树下降；两者都不破坏任何全局不变量
对象是矩形或有形状	R-tree	唯一原生支持的；`rbush` 是前端的标准选择
索引在磁盘或远端	R-tree（取大 $M$ ）	一次节点访问是一次页面 I/O，高扇出把树压到两三层
已有一维索引（B+ tree、zset）	geohash / Morton code	不引入新结构，代价是范围查询要查九个格并做精确过滤
高维向量（ $d > 10$ ）	都不要	精确方法全部退化成线性扫描，走 LSH 或 HNSW 之类的近似方法
碰撞检测的 broad phase	网格或排序扫描	判据是对象尺寸方差，见均匀网格与空间哈希 §4

「都不要」那一行值得单独说明。k-d tree 与最近邻回溯 §5 的曲线显示 16 维时访问比例是 99.77%，而这个拐点几乎不随点数移动。quadtree 与 R-tree 在高维同样失效，且比 k-d tree 更早：前者的孩子数是 $2^d$ ， $d = 16$ 时一个节点有 65536 个孩子。

4 · 本系列没有覆盖的

三类东西被有意留在了外面，各有理由。

批量装载。 本系列的 R-tree 逐条插入。生产实现几乎都用批量装载：STR（Sort-Tile-Recursive）先按 $x$ 排序切成 $\sqrt{n/M}$ 条，每条内按 $y$ 排序切成叶子，一次建完，树的质量远好于逐条插入。代价是不支持增量更新，得整棵重建。

度量空间。 本系列的四个结构全部依赖坐标：切分面、MBR、格子号都要求「维度」这个概念存在。当只有一个距离函数（编辑距离、余弦距离）而没有坐标时，要换成 VP-tree、BK-tree 这类只用三角不等式剪枝的结构。

球面。 geohash 那一页用的是经纬度矩形，它在两极附近严重畸变：同样一度经度在赤道是 111 km、在北纬 80 度只有 19 km。Google 的 S2 与 Uber 的 H3 各自绕开了这一点，前者把球面投影到立方体六面再走 Hilbert 曲线，后者用六边形网格。

5 · 参考文献

Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.
Leutenegger, S. T., Lopez, M. A., & Edgington, J. (1997). STR: A simple and efficient algorithm for R-tree packing. Proceedings of the 13th ICDE, 497–506.
Yianilos, P. N. (1993). Data structures and algorithms for nearest neighbor search in general metric spaces. Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, 311–321.
Malkov, Y. A., & Yashunin, D. A. (2020). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 824–836.