range · kNN · 相交检测

一维索引答不了的问题

B+ tree 能索引一列数字，靠的是数字有全序：任取一个区间，它在索引里就是连续的一段，二分定位到起点再顺着扫即可。这条性质是一维专属的。二维坐标不存在这样的全序——把点按 $x$ 排好， $y$ 相邻的两个点可能落在索引的两端；按 $x + y$ 排、按到原点的距离排，同样各自丢掉一个方向。

本页先把要解决的问题说清楚：空间查询长什么样，一维索引在它面前具体差在哪里，以及后面四个结构各自在哪个自由度上做文章。

1 · 空间查询的谱系

后面所有结构都要回答的是同一组问题，形状只有三种。

定义 1.1（range query） 给定轴对齐矩形 $R$ 与点集 $P$ ，求 $\{p \in P : p \in R\}$ 。地图上「当前视窗里有哪些店铺」就是这一类，也叫 window query。

定义 1.2（kNN query） 给定查询点 $q$ 与整数 $k$ ，求 $P$ 中离 $q$ 最近的 $k$ 个点。 $k = 1$ 时即最近邻。

定义 1.3（intersection query） 被索引的对象带形状时，求与查询矩形相交的全部对象。碰撞检测的 broad phase 与地块检索都属此类。

三者的难度并不相同。range query 的答案由一个显式条件界定，遍历一遍就能算出真值；kNN 的答案则依赖全局比较——在看完所有点之前，无法断言手上这个点是不是最近的。这个差别决定了后面每个结构的 kNN 实现都要比 range 实现多一套剪枝逻辑。

图 1-1 · 同一批点上的三类查询。可切换查询类型并拖动查询点或查询窗，观察结果集怎样随之改变，以及朴素解法各自要看多少个点。

第三类查询里被索引的不是点而是矩形，这一点值得单独记住：它把「包含」换成了「相交」，而相交是对称的、且一个对象可以同时与多个索引单元相交。R-tree 之所以允许兄弟节点的外接矩形互相重叠，根子正在这条性质上。

2 · 排序索引的读放大

把二维压成一维最省事的做法是只索引一个坐标。按 $x$ 建 B+ tree，range query 就变成两步：二分出 $x \in [R.x_0, R.x_1]$ 的那一段，再对段内每个点检查 $y$ 。

正确性没问题，代价在第二步。512 见方的场地上撒 2000 个均匀随机点，60 见方的查询窗平均命中 27.25 个点，而 $x$ 带里躺着 234.13 个候选——8.59 倍的读放大，全部花在把候选扔掉上。

图 2-1 · 按

x

排序的索引在二维范围查询下的候选集。橙色竖带是索引能定位到的范围，绿色点是真正命中的。可拖动查询窗并改窗口边长，观察候选与命中的比值。

原先的猜想是窗口越小、读放大越轻，理由是候选集也在缩。实测反了过来：同一点集上把窗口边长从 60 放大到 160，命中数从 27.25 涨到 194.77，候选数只从 234.13 涨到 619.61，放大比反而从 8.59 降到 3.18。成因是 $x$ 带的高度恒等于全场高度，与查询窗的高度无关：窗口在竖直方向缩得越狠，被白读的比例越高。极端情形是查询一个点：候选集仍是一整条竖带。

读放大不随查询变小而收敛，这条性质让「先按 $x$ 筛再过滤」在小窗口高频查询的场景下彻底不可用，而地图与游戏里恰恰全是小窗口高频查询。

3 · 最近邻的额外困难

range query 至少还能圈出一个候选集。kNN 连这一步都做不到。

按 $x$ 排序的索引面对「离 $q$ 最近的点」时，唯一能利用的是：若某点的 $x$ 与 $q_x$ 相差 $d$ ，则它离 $q$ 至少 $d$ 。算法可以从 $q_x$ 出发向两侧扩张，边扩边维护当前最优距离 $r$ ，当 $x$ 方向的差已经超过 $r$ 时停止。这个算法是正确的，但它的代价取决于点在 $x$ 上的分布与在 $y$ 上的分布有多不相关：所有点挤在同一条竖线附近时， $x$ 差恒为 0，扩张永远停不下来，退化成全表扫描。

二维索引给出的是另一种下界：不是「 $x$ 差至少多少」，而是「到这一整块区域至少多远」。一个矩形区域到查询点的最小距离，用四则运算就能算出来：

d_{\min}(R, q)^2 = \left(\max(R.x_0 - q_x,\ 0,\ q_x - R.x_1)\right)^2 + \left(\max(R.y_0 - q_y,\ 0,\ q_y - R.y_1)\right)^2

这个下界同时用上了两个维度，所以不会因为某一维退化而失效。它是后面四个结构的 kNN 实现共用的剪枝依据，引擎里写作 rectDist2。

4 · 划分平面的两个自由度

四个结构的差别，可以压到两个问题上。

第一个问题是格线由谁决定。uniform grid 与 quadtree 的格线位置只由坐标系决定，与数据无关——前者一次切到底，后者按局部密度决定切多深，但每一刀都落在区域的正中。k-d tree 与 R-tree 反过来，格线位置由数据决定：前者让切分面穿过 median，后者让矩形贴着实际对象的外接框。数据无关的划分好处是格子的位置可以直接算出来（不用查表、天然适合并发写），坏处是分布一倾斜就有大量空格子。

第二个问题是被索引的对象是点还是形状。索引点时，每个点属于且只属于一个格子，划分是真正的划分；索引形状时，一个对象可能横跨多个格子，于是要么把它复制进每个相交的格子，要么允许索引单元互相重叠。R-tree 选了后者。

注 · 第三条路不做任何划分。把 $x$ 与 $y$ 的二进制位交错成一个整数，空间邻近性被部分保留下来，于是可以直接塞进现成的一维有序结构。这条路的正文在 geohash 与 Z-order，它不需要新的数据结构，只需要一个编码函数。

5 · 本系列的记账口径

比较空间索引不能比墙钟时间：同一段 JavaScript 在两次运行里能差三倍，JIT 预热、GC 时机、数组是否退化成字典都会盖过算法本身的差别。本系列的每次查询改为记两个整数。

一个是访问的节点数：递归进入过几个树节点、或扫过几个格子，含那些一进去就被剪掉的。另一个是点级判定次数：做了几次「这个点在不在矩形里」或「这个点离查询点多远」。两个数在引擎里就是 Stats 的 nodes 与 dists，每个结构的 rangeQuery 与 kNN 都返回它。

这两个数常常给出相反的排名，选型对照 §1 有完整的表。之所以两个都要记，是因为一次节点访问的单价随部署形态变化：在内存里它是一次指针解引用，比一次浮点比较还便宜；在磁盘上它是一次页面 I/O，抵得上几万次内存比较。R-tree 长成高扇出的样子，正是按后一种单价设计的。

6 · 参考文献

Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509–517.
Finkel, R. A., & Bentley, J. L. (1974). Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4(1), 1–9.
Guttman, A. (1984). R-trees: A dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, 47–57.
Samet, H. (2006). Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.