MBR · 面积增量 · quadratic split

R-tree 与最小外接矩形

前三个结构都在划分平面：把区域切开，每个点属于且只属于一块。一旦被索引的对象有了形状，划分就不成立：一个矩形可以横跨好几块。

R-tree 反过来做：不划分空间，而是把对象分组，每组用一个矩形框住。框与框允许重叠。代价是一次查询可能同时下好几条分支，收益是任何形状的对象都能进去，且插入与删除都有定义。

1 · 索引矩形而非点

定义 1.1（MBR） 一组对象的 minimum bounding rectangle 是包含它们全部的最小轴对齐矩形。它由四个数确定：各对象在两个维度上的最小值与最大值。

定义 1.2（R-tree） 一棵平衡树，全部叶子在同一层。叶子存对象（或对象的 MBR 加一个 id），内部节点存孩子的 MBR。除根之外，每个节点的条目数落在 $[m, M]$ 内， $m \le M/2$ 。查询时，与查询矩形不相交的条目整枝剪掉。

「内部节点的 MBR 恰是其孩子 MBR 的并」这条是 R-tree 的核心不变量，插入路径上每个节点都要顺手更新它。测试里逐节点递归核对这一条（spatial.test.ts 的「MBR 不变量」），三组不同的 $(m, M)$ 各验一次。

点集也能进 R-tree：一个点就是边长为 0 的退化矩形，rectIntersects 在退化情形下自动退化成 rectContains。本系列的四个结构因此能跑同一批 range 与 kNN 查询，结果集逐项相同。

图 1-1 · R-tree 的层次 MBR 与范围查询。不同颜色对应不同层，可切换只看某一层、改扇出上限并拖动查询窗，读数给出访问节点数与同层兄弟的总重叠面积。

2 · 插入选枝与分裂

插入一个新矩形要回答两个问题。

第一个是往哪条分支下。Guttman 的判据是面积增量最小：算把新矩形并进每个孩子的 MBR 各要新增多少面积，取最小的那个；并列时取面积本身更小的。直觉上这是在「尽量别把框撑大」，因为框撑得越大，将来与查询矩形相交的概率越高，剪枝越无力。

第二个是满了怎么分。节点条目数超过 $M$ 时要拆成两个，且两边都不能少于 $m$ 。拆法的目标是让两个新 MBR 尽量不重叠，因为重叠区域里的任何一次查询都要同时下两条分支。

定义 2.1（quadratic split） 先 PickSeeds：枚举全部条目对，取「合并后浪费面积」 $\text{area}(A \cup B) - \text{area}(A) - \text{area}(B)$ 最大的一对，分别作两组的种子。再反复 PickNext：对每个待分配条目算它并入两组各需的面积增量，取两者差最大的那条先分配，放进增量小的那组。名字里的 quadratic 指 PickSeeds 的 $O(M^2)$ 枚举。

「让重叠尽量小」到底值多少，可以量出来。把 quadratic split 换成一个不看几何的对照组，即按当前条目次序对半切。1000 个随机矩形、 $m = 2$ 、 $M = 8$ ：

分裂策略	同层兄弟总重叠面积	范围查询访问节点	MBR 判定次数
quadratic split	519 747	18.16	99.51
按次序对半切	8 007 735	51.98	303.19

重叠面积差 15.4 倍，查询访问的节点数差 2.9 倍。分裂算法不是可有可无的润色，它决定了这棵树还算不算索引。

图 2-1 · 同一批矩形在两种分裂策略下的树形。左侧是 Guttman 二次分裂，右侧是按次序对半切。可改扇出上限与对象数量，读数给出两者的总重叠面积与查询访问节点数。

3 · 扇出上限的影响

$M$ 决定树高。1000 个矩形， $M = 4$ 时高 6、共 528 个节点； $M = 50$ 时高 2、共 30 个节点。

$m$	$M$	树高	节点数	兄弟总重叠	访问节点	MBR 判定
2	4	6	528	844 788	36.44	110.70
2	8	4	250	519 747	18.16	99.51
4	10	4	165	569 697	15.02	103.41
8	20	3	75	488 378	9.66	132.88
20	50	2	30	220 793	4.76	163.09

原先的猜想是扇出越大、MBR 框得越松、兄弟重叠越严重。表里第五列反着走： $M$ 从 4 加到 50，总重叠从 84.5 万降到 22.1 万。成因不在几何而在计数口径：总重叠是按「同层兄弟对」累加的， $M$ 大则节点少、兄弟对也少。这说明「总重叠面积」这个指标把两件事搅在了一起（单个节点框得紧不紧、以及有多少个节点），横向比不同 $M$ 时它并不可靠；比不同分裂策略时（ $M$ 固定）才是干净的。

最后两列则是清楚的： $M$ 越大，访问的节点越少（4.76 对 36.44），但每个节点里要逐条判的 MBR 越多（163.09 对 110.70）。这正是一维索引答不了的问题 §5 那两个指标的分工，也是磁盘上的 R-tree 一律取大 $M$ 的原因：一次节点访问是一次页面 I/O，节点内的几十次矩形比较是免费的。

4 · 与 B-tree 的血缘

R-tree 的形状规则与 B-tree 逐条对应：全部叶子在同一层、非根节点的条目数落在 $[m, M]$ 、插入靠分裂向上生长、树高由 $M$ 决定。这不是巧合，Guttman 1984 年那篇论文的副标题就写着「a dynamic index structure」，目标是把 B-tree 的磁盘友好性搬到空间数据上。

两处不同都来自「一维有序」这个前提的丢失。B-tree 的孩子区间互不相交且有序，查一个 key 沿唯一一条路径下降；R-tree 的兄弟 MBR 可以重叠，一次点查询也可能要下多条分支。B-tree 的分裂只有一种选择（从中间切），因为 key 有序；R-tree 的分裂有 $2^M$ 种分组方式，好坏差 15 倍，只能靠启发式。

5 · R*-tree 的改良

Beckmann 等人 1990 年的 R*-tree 改了三处，全部围绕「重叠」：

选枝时，在叶子的上一层改用「重叠增量最小」而不是「面积增量最小」，因为面积小不等于重叠小，而查询代价直接由重叠决定。分裂时，候选切分不再枚举全部分组，而是沿每个维度把条目按上下界排序、取若干个切点，用 margin 选维、用重叠面积选切点。margin 是两个新 MBR 的周长之和，它偏好方形而非细长的框，而方形的框与随机查询矩形相交的概率更低。第三处是强制重插：节点第一次溢出时不分裂，而是把离中心最远的约 30% 条目摘下来重新插入，给它们一次换分组的机会。

第三处的收益最不直观，也最大。原因是 R-tree 的形状对插入次序敏感：先插的对象把框的位置定死了，后来的只能将就。重插相当于给树一个局部重整的机会。

值得一提的是本系列实测到的一个反例。原以为插入次序会大幅影响树的质量，于是把 1000 个矩形按 $x$ 排序后重插一遍：总重叠只从 519 747 降到 496 296，差 4.5%。有序插入既没有显著改善也没有显著恶化。quadratic split 的 PickSeeds 只看几何、不看次序，而排序只改变了条目到达的先后。R*-tree 的重插之所以有效，是因为它改的是分组，不是次序。

6 · 参考文献

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.
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990). The R*-tree: An efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 322–331.
Sellis, T., Roussopoulos, N., & Faloutsos, C. (1987). The R+-tree: A dynamic index for multi-dimensional objects. Proceedings of the 13th VLDB Conference, 507–518.
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.