摘要

R 树是最为著名的矩形访问方法（Access method）之一，其算法的基本原理是对中间节点的外接矩形面积进行启发式的优化。我们在一个标准实验平台下对各种数据、各种查询、各种操作进行了大量的实验，并根据实验结果设计了 R* 树。R* 树可以对路径中每个外接矩形的面积、边长（margin）和叠加程度进行综合优化，并将整个路径上所有外界矩形的优化结果合并起来考虑。（原文是incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory）。我们在标准的实验平台下对两种数据结构进行了详细的性能比较，结果证明，与现有的各种 R 树变种相比，R* 树都有明显的性能优势。这里的 R 树变种包括 Guttman 的线性 R 树、二次 R 树（或者叫平方 R 树），也包括 Greene 的 R 树变种。R* 树具有全面的性能优势，不论是针对矩形数据还是针对多维点数据、不论是查询操作还是地图叠加等各种空间操作，R* 树的性能优势均有所表现。从实际应用的角度来讲，R* 树在下面两个方面对用户有强烈的吸引力：第一，R* 树不论对点还是其他各种空间数据都能提供有效的支持；第二，R* 树的实现代价仅比 R 树略高。

1、引言

本文将对复杂的空间对象进行近似，并在此基础上研究空间访问方法（Spatial Access Method，SAMs）。对空间对象的近似是用空间对象的最小外包矩形来表示的，外包矩形的各边与数据空间的各坐标轴平行。这种近似方法比较简单，但它有一个重要的特性，即这种方法可以用少量的字节来代表复杂的空间对象。虽然这种近似方法会导致大量的信息丢失，但空间对象的最小外包矩形仍然保存了对象的一些必要的几何属性，包括空间对象的位置、空间对象在各坐标轴方向的扩展范围。

从参考文献【SK 88】可知，已知的空间访问方法所组织的最小外包矩形是基于一种底层的点访问方法（Point Access Method，PAM），SAM 分为三类：对象分割/复制（clipping），对象映射（transformation），对象界定（又称区域重叠技术）（overlapping region）。（译者注：对象映射是把非点对象映射为高维/低维空间中的点，然后利用点/一维存取方法索引映射后的数据集，如常见的空间填充曲线方法将高维空间中的空间对象线性映射到一维空间，用空间排列码（如 Morton 码、Hilbert 码、Gray 码等）作为地址码建立索引。对象分割/复制是把子空间相交的数据对象分割成几个子对象，分别存储在几个互不重叠的子空间内，在子空间中复制对象本身或其标识符，如 R+ 树、Cell 树、线性四叉树等。对象界定又称区域重叠技术，它允许子空间的相互重叠，一个数据对象唯一对应于一个子空间，如 R 树，R* 树等。）

储存矩形的最著名的空间访问方法是 R 树。按照我们的分类原则，R 树是一种采用对象界定技术的高度平衡树，是点访问方法 B+ 树在 k 维空间上的自然扩展。B+ 树使用了重叠区方法，因此 R 树很容易实现，这种特性有助于 R 树的普及。

R 树算法基于启发式优化，所使用的优化标准（optimization criteria）是：最小化中间节点中的每个外接矩形的面积。这是一种最直接的优化标准，但并没有证据证实这是最佳的优化标准。这种优化标准会带来类似下述的一些疑问：为什么不最小化最小外包矩形的边界或者重叠区（而最小化最小外包矩形的面积）？为什么不优化存储空间的利用率？为什么不同时优化上述的所有内容？上述几种标准能不能以一种消极的方式进行交互（interact in a negative way）？只有使用工程学的方法才能找出各种优化原则之间的最佳结合。

采取工程学方法的必要条件是要有一个标准的实验平台，供我们用各种不同的数据、不同的查询、不同的操作来运行大量的实验。我们实现了这样一个标准的实验平台，并使用这个平台来进行性能对照，尤其是对点访问方法进行性能对照。

作为我们研究的结果，我们设计了一种新的 R 树变种，称为 R* 树，在所有的实验中，R* 树表现出的性能都比现有的各 R 树变种更出色。在很多与现实相近的数据和操作中，R* 树所表现出的性能优势是相当可观的。除了常规的点查询、矩形求交、矩形邻接查询（rectangle enclosure query）外，我们还分析了 R* 树在地图叠加操作时的性能。我们调用了空间链接（Spatial join）操作，因为空间链接是在地理和环境数据库系统中最重要的操作之一。

本文按如下结构组织：第二章中，我们介绍了 R 树原则，包括它的优化标准；第三章中，我们介绍了 Guttman 和 Greene 提出的 R 树的几种变种；第四章中，我们详细介绍了我们所涉及的 R* 树；第五章中，我们说明了 R* 树与 R 树各变种进行对比的结果；第六章总结全文。

2、R 树的算法原则和可能的优化标准

R 树的结构与 B+ 树类似，它可以完整地存储多维矩形而不需要将其切成若干块，也不需要将其转换为更高维的点。

在 R 树的非叶节点中，条目（entry）的存储形式是 {cp，Rectangle}，其中，cp 是一个指针，指向这个条目对应的子节点在 R 树中的存储位置；Rectangle 是一个最小外包矩形，它是“这个条目对应的子节点中的所有条目的矩形”的最小外包矩形。叶节点中条目的存储形式是 {Oid，Rectangle}，其中 Oid 指向数据库中的一条记录，描述了一个空间对象；Rectangle 是这个空间对象的外接矩形。另外，叶节点中条目也可能以这种形式存储：{dataobject，Rectangle}，<译者注：这可能意味着 R 树直接保存空间对象，而不是与另外的一个数据库相连>。后一种存储方式的基本结构与前一种类似。下文主要讨论前一种存储方式。

记 M 是一个节点中条目数的上限，规定一个参数 m 作为节点中条目数的下限，要求 2 <= m <= M/2。则 R 树具有如下性质：

• 根节点如果不是叶节点，那它至少有两个子节点。
• 一个非叶节点如果不是根节点，那它的子节点数都介于 m 与 M 之间。
• 一个叶节点如果不是根节点，那它包含的条目数介于 m 与 M 之间。
• 所有的叶子节点都位于同一层。

R 树、R* 树都是完全动态的，插入、删除操作可以与查询操作混合进行，而且不需要进行定期的全局重建。很显然，这种结构允许不同子树的最小外包矩形发生重叠，因此这种结构在进行精确匹配搜索（exact match query）的时候会产生多条搜索路径。对于这个问题可以参看参考文献【Gut 84】。稍后本文将会论证上述允许重叠区域的技术并不一定导致较差的平均检索性能。另外，本文引入一个术语“路径矩形”（Directory Rectangle），其几何含义是“包围若干下级矩形的最小外包矩形”。（原文是which is geometrically the minimum bounding rectangle of the underlying rectangles）

R 树的主要思想可以归结为：对给定的任意一组矩形，将其分为若干个子集，每个子集中的矩形数介于 m 与 M 之间，然后对子集动态建立外包盒，要求这样建成的 R 树应当能高效地支持任意大小的查询矩形所要求的任意一种检索操作。现在已经知道，能够影响检索性能的参数有很多个，且这些参数间会以一种复杂的方式相互影响。因此，对任意一个参数的优化都有可能对其他参数造成影响，从而使得 R 树的整体性能发生恶化。此外，由于每个最终记录的矩形（原文是data rectangle）会有不同的大小和形状，路径矩形会动态地变大和缩小，所以很难确定对某个参数进行的某种优化是否真的能够成功。因此，我们使用了基于大量不同实验的启发式解决方法来解决这个问题。上述的大量不同实验是在一个系统化的框架中完成的。

本章将讨论与检索性能有密切关系的几个参数。此外，本章还会分析不同的参数与优化标准之间的相互依存关系。

• 原则O1：路径矩形所覆盖的面积应该最小化。也就是说，被最小外包矩形所覆盖、但是没有被其下级矩形（原文是enclosed Rectangle）所覆盖的区域，不妨称之为“死空间（dead space）”，应当最小化。考虑到在进行空间操作的时候，我们需要决定树里的哪些路径要被遍历，而最小化的路径矩形覆盖面积可以令我们在树的较高层次忽略掉不需要遍历的路径，因此这一操作有助于提升性能。
• 原则O2：不同路径间矩形的重叠应当最小化。这个操作也可以减少需要被遍历的路径数目。
• 原则O3：路径矩形的边长应当最小化。这里所谓的边长是指矩形的所有边或棱的长度之和<译者注：含义类似于周长>。面积一定的情况下边长最小的形状是正方形。因此如果最小化边长而不是最小化面积，将会是路径矩形更接近正方形。如果查询矩形是较大的正方形，那么最小化的边长可以提供较高性能（这句话原文是Essentially queries with large quadratic query rectangles will profit from this optimization）。更重要的是，最小化边长可以在根本上改善树的结构。正方形更容易被包围，因此如果某层的外包盒更接近正方形，那么其上一层的路径矩形就会相对较小。因此如果按照各边的长度的方差来给矩形分组，将边的方差较小的分为一组并构建外包盒，则这种分组方法可以减少路径矩形的面积。（这句话的原文是Thus clustering rectangles into bounding boxes with only little variance of the lengths of the edges will reduce the area of directory rectangle）
• 原则O4：存储时的空间利用率应当优化。较高的存储空间利用率可以令树的高度保持较低，所以通常会减低查询成本。有证据表明，查询矩形越大受这个参数的影响就越大，因为如果检索涉及的结果有很多，那么每个节点中的矩形数目就会对检索性能产生较大影响。（这句话原文是这样的：Evidently, query types with large query rectangles are influenced more since the concentration of rectangles in several nodes will have a stronger effect if the number of found keys is high）。

如果要令路径矩形的面积和互相之间的重叠面积较小，就需要减小对节点中矩形存储数目的限制，因此最小化这两个参数会导致较低的存储效率。另外，如果要做到 O1 或者 O2，就需要以更自由的方法选择每个矩形的分组，而这将导致上层矩形的形状变得不像正方形。如果要做到 O1，那么路径矩形间的重叠就会增加，因为这会降低数据空间的覆盖程度。（译者注：我没有理解这句话的逻辑，那个原则导致什么降低了？原文是the overlap between directory rectangles may be affected in a positive way since the covering of the data space is reduced）。至于对几何形状的优化，如果要最小化边长，就会降低存储效率。然而，由于接近正方形的路径矩形更容易包围起来（packing better），所以这容易保证较高的存储效率<译者注：这是什么逻辑？>显然，对于一个充分大的查询矩形来说，存储效率对性能的影响另外三个参数 O1-O3 的影响大得多。

3、R 树的变种

R 树是一种动态的结构。因此所有优化检索性能的方法都是在插入新的数据矩形的时候实施的。插入算法会调用另外两个算法，在这两个算法中一些关键的决策能保证较高的检索性能。这两个算法分别是算法 ChooseSubTree 和算法 Split。算法 ChooseSubtree 从根开始运算，向下一直检索至叶节点，在每一层都选择最适合容纳新条目的子树。如果算法 ChooseSubtree 最终找到的节点已经保存了 M 个条目，不能再插入更多条目了，则调用算法 Split。算法 Split 会用最适当的方法把 M+1 个条目分配到两个节点当中去。

下面我们将分析和讨论现有的各种 R 树变种提出算法 ChooseSubtree 和算法 Split。首先考虑 Guttman 提出的最普通的 R 树。

算法 ChooseSubtree

• 步骤CS1：记 N 为根节点。
• 步骤CS2：如果 N 是叶节点则返回 N，否则选择 N 中最适合插入新数据的条目，选择标准是当插入新数据时，相应矩形的面积增加最小。如果某两个条目插入新数据后面积增加程度相等，则选择其中面积较小的那个。
• 步骤CS3：将 N 置为步骤 CS2 中选出的条目所指向的那个节点，返回步骤 CS2 继续运算。

很明显，这种优化方法是试图最小化路径矩形的覆盖面积，也就是前述的原则 O1。这个操作可能还会降低矩形间的重叠，对 CPU 的消耗也相对较低。

Guttman 讨论了三种 Split 算法，其时间复杂度分别与节点中的条目数成指数、平方、线性关系。三种算法的设计原则都是减小分裂后产生的两个矩形的覆盖面积。指数分裂算法可以得出面积最小的分裂结果，但是会消耗过多的 CPU 时间。其他的两个算法都是试图得出近似最优的结果。在 Guttman 的实验中，线性分裂算法的结果与平方分裂算法的结果表现出了相近的检索性能。我们也实现了基于线性分裂算法的 R 树和基于平方分裂算法的 R 树，但是我们用不同分布、不同叠加状况、不同的 M 和 m、不同数目的数据记录进行了大量测试后认为，基于平方分裂的 R 树产生了更好的性能。本文第 5 章详细列出了测试结果。基于我们的实验结果，本文仅详细讨论平方分裂算法。

算法 QuadraticSplit：把 M+1个条目分成两组

• 步骤QS1：调用算法 PickSeeds 选择两个条目，分别作为两组的第一个条目。
• 步骤QS2：循环调用算法 DistributeEntry，直至所有的条目都已经被分配到某一组、或者某一组已经有了 M-m+1 个条目。
• 步骤QS3：如果还有余下的条目，则将其全部放入条目较少的那个组里，以保证这个组里的条目数大于下限 m。

算法 PickSeeds

• 步骤PS1：对于每一对条目 E1 和 E2，生成其最小包围矩形 R，计算 d = area® – area(E1.Rectangle) – area(E2.reactangle)。
• 步骤PS2：选择得出的 d 最大的那一组 E1 和 E2。

算法 DistributeEntry：

• 步骤DE1：调用算法 PickNext 选择一个要被分配的条目。
• 步骤DE2：将选出的条目插入一个组中，选择组的原则是加入这个条目后外包矩形的面积增加较小。如果插入新条目后两个组外包矩形的面积相当，则选择插入外包矩形面积较小的那个组里。若两个组的面积也相当，则插入条目较少的那个组里。

算法 PickNext：

• 步骤PN1：对于尚未分组的每个条目 E，计算 d1 = 当把 E 插入第一组时外包矩形面积增加的程度，d2 = 插入第二组时外包矩形面积增加的程度
• 步骤PN2：返回 d1 和 d2 面积之差的绝对值最大的那个条目

算法 PickSeeds 把如果放在一起会产生最多面积浪费的两个矩形选出来。在这种情况下两个距离最远的矩形会被选出来。值得一提的是，如果需要被分裂的矩形大小差距很大或者它们之间有大量重叠，那选出来的种子（seeds）通常是面积较小的矩形。算法 DistributeEntry 把剩余的条目根据“面积最小”的标准进行分配。算法 PickNext 选择在相应情况下对面积影响最大的条目（entry with the best area-goodness-value）。

这套算法中，如果算法 PickSeeds 选出的是较小的种子，就有可能产生问题。如果有一个 d 维矩形，它在 d-1 维里与种子相距很远，但是在剩下的那一维里与种子的坐标很接近，那么这个矩形将优先被分配到相应的种子那一组里。这种插入导致的“面条形”外包矩形的面积增加会很小，但这个矩形的长度很长。这会导致糟糕的分裂结果。（译者注：这显然是因为算法只考虑了面积而没有考虑其他因素造成的）。另外，算法倾向于把第 a+1 个待分配的矩形与第 a 个待分配的矩形放入同一个种子中（原文是the algorithm tends to prefer the bounding rectangle, created from the first assignment of a rectangle to one seed）。这个因为当第 a 个矩形放入某个种子后，种子的外包矩形就会变大，那么再放入下一个条目的时候外包矩形的面积增加幅度可能相对较小。这种恶性循环有可能一直进行。另一个问题是，如果一个组中保存的条目数到达上限 M-m+1，那么剩下的条目不管其形状如何都会被分配到另外一个组里。第 4.3 节的图 1b（图略，下同）显示的例子显示了上述的所有问题。这些问题可能使分裂的结果又较大的重叠，也可能使条目的分配不均匀，而后者会降低存储效率。

我们用基于平方分裂算法的 R 树测试了不同的 m 值，m 值分别为 M 值的 20%、30%、35%、40%、45%。结果表明当 m 是 M 的 40% 时检索性能最好。

在比较 R 树与其他保存矩形的数据结构的时候，Greene 提出了下面这个替代的分裂算法。为了选择插入新条目的最佳路径，他使用了 Guttman 的算法 ChooseSubtree。

算法 GreeneSplit：把M+1个条目分为两组

• 步骤DS1：调用算法 ChooseAxis，以决定接下来的分裂操作要与哪个轴垂直。
• 步骤DS2：调用算法 Distribute。

算法 ChooseAxis：

• 步骤CA1：调用 PickSeeds（见p 5（译者注：这里没有说明p 5是什么）），选择当前节点中两个距离最远的矩形。
• 步骤CA2：对每个轴记录两个种子的距离（但原文用的是 separation 而不是 distance）
• 步骤CA3：对 CA2 算出的距离进行标准化（Normalize），标准化的方法是先求出所有节点的总外包矩形，然后用 CA2 的每个距离除以这个总外包矩形在相应轴上的投影。（原文是 Normalize the separations by dividing them by the length of the nodes enclosing rectangle along the appropriate axis）
• 步骤CA4：CA3 算出的距离称为标准化距离（Normalized Separation），选出标准化距离最大的轴作为返回值，算法结束。

算法 Distribute：

• 步骤D1：沿选定的轴，根据矩形在轴上投影的左坐标给矩形排序。
• 步骤D2：将前 (M+1)/2 个条目放入一个组，另外 (M+1)/2 个条目放入另外一组。
• 步骤D3：如果 M+1 是奇数，那么经过步骤 D2 后还会剩下一个条目，将这个条目加入一个组当中，选择目标组的原则是将这个条目插入这个组后，相应组的外包矩形面积增加较少。

Greene 的分裂算法基本上只考虑了一个标准，即选择一个合适的坐标轴作为分裂的基础。虽然选择一个正确的坐标轴确实十分重要，但是我们的实验表明，必须使用更多的几何优化标准，以更好地提升检索性能。除了分组的问题以外，在某些情况下 Greene 的分裂算法无法选择出正确的轴，因此可能导致很糟糕的分裂结果。图 2b 描绘的情形就是这样的。

4、R* 树

4.1、选择子树

对于选择理想插入位置的问题，之前的 R 树版本只考虑了面积参数。在我们的试验中，我们测试了面积、边长、重叠区面积三个参数的不同组合。其中重叠区面积是这样定义的：

设 E1-Ep 是节点中的 p 个条目，则

Overlap(Ek) = 第 K 个条目对应矩形与节点中的其他 p-1 个条目对应矩形的重叠面积之和

（公式略。译者注：注意是重叠面积之和，如果是三个矩形重叠，那么重叠面积算3遍）

根据我们的实验，检索性能最高的 R 树变种应当使用下面的算法。

算法 ChooseSubtree

• 步骤CS1：记根节点为 N
• 步骤CS2：如果 N 是叶节点，返回 N，算法结束。如果 N 不是叶节点，再考察 N 中的指针是指向叶节点还是指向中间节点。如果指向叶节点，则应最小化重叠面积。具体做法是，选择最适合容纳新记录的条目，选择的标准是：加入新记录后相应条目的重叠面积增加程度最小。如果重叠面积增加相等，则下一个判断原则是面积增加程度最小。如果面积增加程度也相等，则选择矩形面积最小的那个条目。如果不是指向叶节点，也就是说指向中间节点，则应最小化面积。具体做法是，选择最适合容纳新记录的条目，选择标准是插入新的记录后相应条目的面积增加最小。如果面积增加程度相等，则选择面积最小的那个条目。（译者注：原文的描述是 Choose entry whose rectangle need least overlap/area enlargement，注意，它说的是 Entry 的 Enlargement 而不是 N 的 Enlargement，这其实与前文 overlap 的定义不一致。但是其含义是可以理解的。）
• 步骤CS3：把 N 置为步骤 CS2 中选出的那个条目的指针指向的节点，然后返回步骤 CS2 重新计算。

对于寻找最佳非叶节点的方法，Guttman 提出的最原始的方法比其他备选算法的性能都高。但是对于选择最佳的叶节点，最小化重叠面积可以令性能稍有提高。

在我们提出的这个算法里，CPU 的时间消耗与节点中的条目数的平方成正比，这是因为对每个条目都要计算它与其他条目的重叠面积。然而，对于较大的节点我们可以减少对一些条目的计算，因为如果一个矩形距离待插入的记录太远，那它基本不可能是插入目标。因此，为了降低 CPU 时间消耗，上述的算法可以进行如下修改：

算法修改：寻找接近最优的插入目标（原文是determine the nearly minimum overlap cost，寻找接近最小的重叠面积）

• 步骤1：根据插入新记录后矩形面积增加的程度（注意是面积而不是重叠面积）把 N 里面的各个条目进行升序排列
• 步骤2：将序列中的前 p 个条目记为条目组 A
• 步骤3：将 A 中的条目视为 N 中的所有条目，调用前述的步骤 CS2 选择最优的插入位置。

对于二维的空间，我们发现如果 p 是 32 的时候检索性能不会受到影响（译者注：它这里想表达的意思可能是当 p 为 32 时这种修改后的算法只会使插入性能提高、不会使检索性能降低）。对于更高维的情况现在尚不清楚。虽然即使经过这种修改我们的算法仍会比原始算法消耗更多的 CPU 时间，但是却可以降低磁盘访问次数，因为这避免了在插入前进行额外的匹配查询（match query）（译者注：我很不解这个结论，因为从描述上看，如果一次读取一个完整页面也就是一个节点的话，两种算法的磁盘访问次数都等于树的高度，不存在降低磁盘访问次数的问题。除非每次只读若干条目，不读一个完整的节点）。

实验表明，对算法 ChooseSubtree 的优化可以提升检索性能，尤其是在下面这种情况下的性能提升尤其明显：查询矩形较小，而被查询的数据文件由一些分布不均匀的小矩形或者点构成。其他情况下 Guttman 算法的性能与我们这个算法的性能相似，因此我们这个算法的主要优势在于健壮性的提升。

4.2、R* 树的分裂

R* 树使用下述方法寻找最佳的分裂方案。沿着每个轴，按照先左坐标后右坐标的方法对条目进行排序，形成若干序列。对于需要分裂的 M+1 个条目，每个序列都有 M-2m+2 种可能的分配方法。其中第 k 中分配方法是把前 m-1+k 个条目分为一组，剩下的分为另一组。

对每一种分配方法，计算其效益值（goodness value）（译者注：其实是反效益值，越小越好），根据效益值决定最终选用哪一种分配方法。有三种不同的效益值计算方法，又有三种不同的效益值使用方法，我们试验了不同组合的性能。

三种计算方法：

1. Area-value = area[bb(first group)] + area[bb(second group)]
2. Margin-value = margin[bb(first group)] + margin[bb(second group)]
3. Overlap-value = area[ bb(first group) ∩ bb(second group)]

公式中的 bb 表示一组矩形的外包盒（bounding box）。

三种使用方法：

• 某个轴或者某个序列里的最小值（译者注：每个轴有 M-2m+2 个分组方法，每种分组方法都有 3 个效益值，这里想要表达的可能是 3M-6m+6 个效益值中的最小值，也可能是这里所述的最小值有三个。译者倾向于第一种解释。这样的结果是用户指定一个轴，返回一个针对此轴效益值最低的分组方法）
• 各轴每种分组方法的 3 个效益值求和，选其中的最小值（译者注：这应该也是用户指定一个轴，返回一个针对此轴效益值和最低的分组方法）
• 全局最小值（返回全局效益值最小的分组方法，不要求用户指定一个轴）

（译者再注：从下文的算法上看，好像这三种使用方法不是这样解释的。不过这个跟最终的算法关系不太大。）

得到的值用于决定依哪个轴进行分裂，或者直接决定最终分组方案（依照指定的轴）。总体来说，性能最高的 R* 树是根据下面这种算法进行构建的。

算法 Split

• 步骤S1：调用算法 ChooseSplitAxis 来决定依哪个轴进行分裂（即分裂线垂直于哪个轴）
• 步骤S2：调用算法 ChooseSplitIndex，决定沿这个轴的最佳分组方法
• 步骤S3：按照上一步的结果把条目分成了两组

算法 ChooseSplitAxis

• 步骤CSA1：对每一个轴都进行如下操作：对所有条目先根据左坐标再根据右坐标进行排序，然后按照上文所述方法对每个轴都确定一组分组方案，然后计算这个轴上所有分组方案的 margin-value 之和，记为 S。
• 算法CSA2：将 S 值最小的轴作为分裂轴

算法 ChooseSplitIndex

• 步骤CSI1：沿着选定的分裂轴，选择 overlap-value 最小的分组方案。如果有两个方案的 overlap-value 相等，则选择 area-value 最小的方案。

对于分裂算法，我们在试验取的 m 分别为M的 20%、30%、40% 和 45%。实验表明当 m 是 M 的 40% 时性能最好。另外，我们在同一个 R* 树的整个生命周期里使用不同的 m 值，试图使几何属性与存储效率产生联系。但是即使采用下面这个方法，检索性能仍然比不采用时差：分别用用 m1 = 0.3M，m2 = 0.4M 进行分裂操作，如果 split（m2）产生了重叠而 split（m1）没有产生重叠（译者注：原文是 yield overlap，这里所说的重叠是什么重叠？难道一定能做出不重叠的分裂方案？不能这么保证吧），则采用 Split（m1）。否则采用 split（m2）。

关于 R* 树分裂算法的性能，我们提出如下几点。对于每一个轴或者说维度，需要进行两次排序，时间复杂度是 O(M log(M))。从一个实验结果上来看，这占用了分裂算法一半的时间。剩下的时间是这样消耗的：对于每一个轴，计算边长需要 2(2(M-2m+2)) 次计算，计算重叠面积需要 2(M-2m+2) 次计算。

4.3、强制插入

不管是 R 树还是 R* 树，在把条目分配给节点的过程中都是不确定的。也就是说，用不同的次序插入同一组条目会建成不同的树。由于这个原因，R 树建立早期插入的节点会干扰 R 树的结构。R 树生长早期插入的数据会按照当时的情况被放在某个路径矩形里，但是以当前的观点来看它所在的位置已经不能保证较高的检索性能了。进行分裂操作的时候，路径矩形会进行局部的重组，但是这种重组太简单，因此急需一种更加强大的、更全局性的机制来对数据结构进行重组。

记录的删除有可能导致节点下溢，如果下溢的节点在原来的父节点位置下进行合并，那上面说的这个问题会更严重。因此现有的对待下溢节点的方法是删除节点，把里面的记录重新插入 R 树。这种方法可以通过调用算法 ChooseSubtree 来把下溢节点中的记录分配到不同的节点中。

正如预计的那样，这种对旧数据矩形的删除和再插入会提升检索性能。我们使用线性 R 树进行了下面这个简单的实验。插入 20000 个均匀分布的矩形，删除前面 10000 个，然后把它们重新插入。实验结果是，对不同类型的查询而言，处理后的 R 树查询性能提升了 20% 到 50%。因此随机删除一半的数据然后把它们重新插入回树里似乎是一种非常简单的调整 R 树数据文件（datafile）的方法。但是这是一个静态的情景（译者注：我不知道它所说的 this is 指代的是什么。R 树应当不是一个静态的情景啊？），对于接近静态的数据文件来说打包算法（the pack algorithm）是一种很复杂的解决方法。

为了实现动态的重组，R* 树强制将插入路径上的所有条目进行重新插入。下面这些算法都认为 R* 树允许将条目插入树的各层当中，这个假定类似于算法 Deletion 的要求（原文是 the following algorithm is based on the ability of the insert routine to insert entries on every level of the treeas already required by the deletion algorithm）。除了对上溢情况的处理外，这个算法与 Guttman 所述的原始算法相同，因此仅在这里简要介绍。

算法 InsertData

• 步骤ID1：调用算法 Insert 以便插入一个新的数据矩形。由于插入的不是一个最终数据而是一个中间节点中的条目，所以还需要传入一个参数，即这个中间节点所在的层。下文中这个参数被翻译为“层号”。

算法 Insert

• 步骤I1：调用算法 ChooseSubtree，将层号作为参数传入，以寻找适合插入条目 E 的节点 N
• 步骤I2：如果 N 的条目数小于 M，就将 E 插入 N。如果 N 有 M 个条目，则调用算法 OverflowTreatment，并把层数作为参数传入这个算法中以便重新插入或者分裂
• 步骤I3：如果调用了算法 OverflowTreatment 并进行了分裂，则需要判断其上层是否也需要调用算法 OverflowTreatment，如果有必要则调用之。如果算法 OverflowTreatment 令根节点也发生了分裂，则建一个新的根节点
• 步骤I4：调整插入路径上的所有外包矩形，使外包矩形在范围上最小化。

算法 OverflowTreatment：

（译者注：原文没有说明这个算法的参数是一个节点还是一个子树，从算法描述上来看，这应该是对一个节点的操作）

• 步骤OT1：如果传入的层号不是根、并且这是本次数据插入过程中（译者注：注意是本次数据插入过程中而不是数据重插入过程中）在相应层次上第一次调用算法 OverflowTreatment，则调用算法 ReInsert，否则调用算法 Split。

算法 ReInsert

• 步骤RI1：对于节点 N 中的 M+1 个条目，计算其矩形中点与 N 的矩形中点之间的距离
• 步骤RI2：按照步骤 RI1 算出的距离把条目按降序排列
• 步骤RI3：从 N 中移除前 P 个条目，然后调整 N 的外包矩形
• 步骤RI4：在步骤 RI2 所定义的序列中，从高到低或者从低到高，调用算法 Insert 来重新插入这些条目。从高到低的重新插入称为“远端重插入（far insert）”，反之称为“近端重插入（close insert）”

（译者注：我不明白它在步骤 RI3 里移除了距离中心最远的 p 个条目，然后把距离中心近的其他条目进行重新插入？那移除的那些怎么处理？文中没讲，怀疑是这样的：把步骤 RI2 中的前 p 项进行重新插入，插入的次序是步骤 RI1 里定义的次序。另外，把与中心的距离视作一个参数，这或许是一个不错的方法）

插入一个新的数据矩形后，每层的第一次上溢处理都对 p 个条目进行了重新插入。如果重新插入的位置还是原来的位置，那么将导致这个节点发生分裂。相应的，如果重新插入到其他的位置，则可能引起其他节点的分裂，但是很多情况下也有可能不发生分裂。考虑到性能的问题，参数 p 对叶节点和非叶节点可能取不同的值。我们也对不同的 p 值进行了试验，结果表明，对叶节点和非叶节点的 p 都取 M 的 30% 能够获取最佳性能。另外，对于所有的数据和查询而言，近端重插入比远端重插入性能要好。因为近端重插入倾向于把条目插入条目原本的位置，这正是我们所希望的，因为这样一来外包矩形的面积会减小，那么在下一次调用算法 ChooseSubtree 的时候这个节点被选中的可能性就较小。

（译者注：这段话描述不是很清楚，我感觉可能是这样。第一，整个插入路径上的所有相关条目都要被插入一遍。第二，插入的时候，如果上溢，先不进行分裂，而是把上溢的那个节点里的p个条目再重新插入一遍。于是这个逻辑就比较复杂了。首先，插入一个数据记录的时候是插入到叶节点，会发生分裂，分裂向上传递，整个树被处理一遍。然后插入倒数第二层的节点，插入的时候有可能上溢从而有更多的倒数第二层的条目需要重新插入，此时再重新插入导致的分裂就直接分裂了，分裂就要向上一层重新插入，此时的插入又要调用OverflowTreatment。看起来是这样的，对于上溢和分裂的处理，R树是算法AdjustTree，R*树使用算法OverflowTreatment来代替算法AdjustTree。R树的做法是需要分裂时分裂、插入上一级。R*树则多了一步重新插入，也多了对整个路径条目的重新插入）。

总结一下，我们可以说：

• 第一，强制重新插入改变了相邻节点间的条目，因此可以降低重叠
• 第二，作为额外的影响，存储效率提高了。
• 第三，由于进行了较多的重组，因此会发生较少的分裂
• 第四，由于节点中位于矩形外侧的条目执行了重新插入，因此路径矩形会更接近于正方形。如前文的论述，这个现象是我们所很希望看到的。

很明显，这个算法会导致更高的 CPU 时间消耗，因为整个插入路径会被多次访问。但这个问题不会太严重，因为这个操作会减少分裂的次数。实验表明使用了重新插入机制后，插入操作的磁盘访问次数提高了 4%，但仍是 R 树变种里最少的。这很大程度上归功于重新插入机制导致的 R* 树结构改善。

5、性能对照

5.1、测试环境设定

测试的时候会把树里从根到叶的一个枝存在内存里。另外，如果插入或删除操作的时候出现了新的条目，这个条目也会存在内存里。

测试时页面大小为 1024 字节，这可以存 56 个条目，但测试的时候定义 M 为 50。

测试使用了六个数据文件，包含大概 10 万个 2 维矩形。矩形坐标在 0 到 1 之间。数据文件的性质用下面几个参数来表示。第一，矩形中心的分布情况。第二，n，矩形数。第三，μ，矩形的平均面积。第四，nv = σ/μ，其中 σ 表示面积的方差，nv 表示面积的标准差。nv 与分布无关，矩形的面积与平均面积的差距越大则 nv 越大，原文还说了依据，nv 可以表示平均的重叠面积。

下面罗列了 F1 至 F6 一共六套数据。

测试使用了三种方式。第一，矩形相交查询，给定一个矩形，要求返回与其相交的所有矩形。第二，点查询，给定一个点，要求返回所有包含这个点的矩形。第三，包含查询，给定一个矩形，要求返回所有包含这个矩形的矩形。

测试了每次查询需要的磁盘访问次数，为了测试建立树算法的性能还测试了每次插入算法的磁盘访问次数、树建立完成后的存储效率。另外，用空间链接（Spatial Join）操作代表叠加操作进行了测试。对于空间链接的定义是，如果文件 A 中的一个记录与文件B中的记录相交，则返回一个空间链接结果。对于空间链接结果，测试其每次操作的磁盘访问次数。

5.2、对结果的分析

R* 树性能显然更好：

• 第一，R* 树最为健壮。这里的健壮指的是它比其他各种R树变种的各方面性能都要好。
• 第二，R* 树在使用较小的查询矩形的时候性能更好，这是因为随着查询矩形面积变大，存储效率的影响会变大。
• 第三，在进行查询的时候，R* 树的性能是线性 R 树的 400%，是 Greene 的 R 树变种的 200%，是平方 R 树的 180%。
• 第四，跟预期的相同，R* 树的存储效率最好。
• 第五，令人惊奇的是，虽然使用了强制插入的方法，但是平均插入时间不仅没有提高，还有所降低
• 第六，空间链接操作获得的性能提升比其他查询获得的性能提升要高。对空间链接操作，R* 树比平方 R 树高出 147%，比 Greene 的 R 树高出 171%，比线性 R 树高出 261%。

5.3、一种高效的点访问方法

这一节的主要内容是测试 R* 树对于访问点数据的性能。之前的访问都是矩形数据。

仍然测试存储效率、插入时间消耗、查询时间消耗。

结果表明 R* 树对于访问点的性能提升比访问矩形的性能提升更好。R* 树甚至比双层四叉树（是不是这个意思？原文2-level grid）性能更好。双层四叉树仅在插入操作方面的性能更好，因此看起来它更适合需要经常插入的情景。

6、总结

实验表明，本文所提出的 R* 树不论是访问数据库中的多维点还是多维空间数据都有很好的效果。在所有的实验里，R* 树的性能都比其他 R 树变种高。对于点数据的访问，性能提升更明显。R* 树甚至于比双层四叉树更好。

R* 树主要是考虑降低面积、边长、路径矩形的重叠。因为综合考虑了三者，R* 树即使面对分布非常不规则的数据时也表现得十分稳定。又由于强制插入算法的使用，避免了不必要的分裂，R* 树得到了动态的重构，存储效率得到了提升。R* 的实现代价仅比 R 树的实现代价稍高

在接下来的工作中，我们将研究，如果像参考文献【SK90】所述的那样使用前缀（原文是 Prefixes，是什么意思？）或者使用格网逼近（grid approximation），能不能提高删除。我们也会继续改善 R* 树，使其能更有效的管理多边形。

上一篇： R 树：动态空间索引结构

下一篇：理查德·斯托曼的征婚启事