Love life, love sports, love to learn, & love...
Love life, love sports, love to learn, & love...
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 树略高。
本文将对复杂的空间对象进行近似，并在此基础上研究空间访问方法（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 树各变种进行对比的结果；第六章总结全文。
R 树的结构与 B+ 树类似，它可以完整地存储多维矩形而不需要将其切成若干块，也不需要将其转换为更高维的点。
在 R 树的非叶节点中，条目（entry）的存储形式是 {cp，Rectangle}，其中，cp 是一个指针，指向这个条目对应的子节点在 R 树中的存储位置；Rectangle 是一个最小外包矩形，它是“这个条目对应的子节点中的所有条目的矩形”的最小外包矩形。叶节点中条目的存储形式是 {Oid，Rectangle}，其中 Oid 指向数据库中的一条记录，描述了一个空间对象；Rectangle 是这个空间对象的外接矩形。另外，叶节点中条目也可能以这种形式存储：{dataobject，Rectangle}，<译者注：这可能意味着 R 树直接保存空间对象，而不是与另外的一个数据库相连>。后一种存储方式的基本结构与前一种类似。下文主要讨论前一种存储方式。
记 M 是一个节点中条目数的上限，规定一个参数 m 作为节点中条目数的下限，要求 2 <= m <= M/2。则 R 树具有如下性质：
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 或者 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 的影响大得多。
R 树是一种动态的结构。因此所有优化检索性能的方法都是在插入新的数据矩形的时候实施的。插入算法会调用另外两个算法，在这两个算法中一些关键的决策能保证较高的检索性能。这两个算法分别是算法 ChooseSubTree 和算法 Split。算法 ChooseSubtree 从根开始运算，向下一直检索至叶节点，在每一层都选择最适合容纳新条目的子树。如果算法 ChooseSubtree 最终找到的节点已经保存了 M 个条目，不能再插入更多条目了，则调用算法 Split。算法 Split 会用最适当的方法把 M+1 个条目分配到两个节点当中去。
下面我们将分析和讨论现有的各种 R 树变种提出算法 ChooseSubtree 和算法 Split。首先考虑 Guttman 提出的最普通的 R 树。
算法 ChooseSubtree
很明显，这种优化方法是试图最小化路径矩形的覆盖面积，也就是前述的原则 O1。这个操作可能还会降低矩形间的重叠，对 CPU 的消耗也相对较低。
Guttman 讨论了三种 Split 算法，其时间复杂度分别与节点中的条目数成指数、平方、线性关系。三种算法的设计原则都是减小分裂后产生的两个矩形的覆盖面积。指数分裂算法可以得出面积最小的分裂结果，但是会消耗过多的 CPU 时间。其他的两个算法都是试图得出近似最优的结果。在 Guttman 的实验中，线性分裂算法的结果与平方分裂算法的结果表现出了相近的检索性能。我们也实现了基于线性分裂算法的 R 树和基于平方分裂算法的 R 树，但是我们用不同分布、不同叠加状况、不同的 M 和 m、不同数目的数据记录进行了大量测试后认为，基于平方分裂的 R 树产生了更好的性能。本文第 5 章详细列出了测试结果。基于我们的实验结果，本文仅详细讨论平方分裂算法。
算法 QuadraticSplit：把 M+1个条目分成两组
算法 PickSeeds
算法 DistributeEntry：
算法 PickNext：
算法 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个条目分为两组
算法 ChooseAxis：
算法 Distribute：
Greene 的分裂算法基本上只考虑了一个标准，即选择一个合适的坐标轴作为分裂的基础。虽然选择一个正确的坐标轴确实十分重要，但是我们的实验表明，必须使用更多的几何优化标准，以更好地提升检索性能。除了分组的问题以外，在某些情况下 Greene 的分裂算法无法选择出正确的轴，因此可能导致很糟糕的分裂结果。图 2b 描绘的情形就是这样的。
对于选择理想插入位置的问题，之前的 R 树版本只考虑了面积参数。在我们的试验中，我们测试了面积、边长、重叠区面积三个参数的不同组合。其中重叠区面积是这样定义的：
设 E1-Ep 是节点中的 p 个条目，则
Overlap(Ek) = 第 K 个条目对应矩形与节点中的其他 p-1 个条目对应矩形的重叠面积之和
（公式略。译者注：注意是重叠面积之和，如果是三个矩形重叠，那么重叠面积算3遍）
根据我们的实验，检索性能最高的 R 树变种应当使用下面的算法。
算法 ChooseSubtree
对于寻找最佳非叶节点的方法，Guttman 提出的最原始的方法比其他备选算法的性能都高。但是对于选择最佳的叶节点，最小化重叠面积可以令性能稍有提高。
在我们提出的这个算法里，CPU 的时间消耗与节点中的条目数的平方成正比，这是因为对每个条目都要计算它与其他条目的重叠面积。然而，对于较大的节点我们可以减少对一些条目的计算，因为如果一个矩形距离待插入的记录太远，那它基本不可能是插入目标。因此，为了降低 CPU 时间消耗，上述的算法可以进行如下修改：
算法修改：寻找接近最优的插入目标（原文是determine the nearly minimum overlap cost，寻找接近最小的重叠面积）
对于二维的空间，我们发现如果 p 是 32 的时候检索性能不会受到影响（译者注：它这里想表达的意思可能是当 p 为 32 时这种修改后的算法只会使插入性能提高、不会使检索性能降低）。对于更高维的情况现在尚不清楚。虽然即使经过这种修改我们的算法仍会比原始算法消耗更多的 CPU 时间，但是却可以降低磁盘访问次数，因为这避免了在插入前进行额外的匹配查询（match query）（译者注：我很不解这个结论，因为从描述上看，如果一次读取一个完整页面也就是一个节点的话，两种算法的磁盘访问次数都等于树的高度，不存在降低磁盘访问次数的问题。除非每次只读若干条目，不读一个完整的节点）。
实验表明，对算法 ChooseSubtree 的优化可以提升检索性能，尤其是在下面这种情况下的性能提升尤其明显：查询矩形较小，而被查询的数据文件由一些分布不均匀的小矩形或者点构成。其他情况下 Guttman 算法的性能与我们这个算法的性能相似，因此我们这个算法的主要优势在于健壮性的提升。
R* 树使用下述方法寻找最佳的分裂方案。沿着每个轴，按照先左坐标后右坐标的方法对条目进行排序，形成若干序列。对于需要分裂的 M+1 个条目，每个序列都有 M-2m+2 种可能的分配方法。其中第 k 中分配方法是把前 m-1+k 个条目分为一组，剩下的分为另一组。
对每一种分配方法，计算其效益值（goodness value）（译者注：其实是反效益值，越小越好），根据效益值决定最终选用哪一种分配方法。有三种不同的效益值计算方法，又有三种不同的效益值使用方法，我们试验了不同组合的性能。
三种计算方法：
公式中的 bb 表示一组矩形的外包盒（bounding box）。
三种使用方法：
（译者再注：从下文的算法上看，好像这三种使用方法不是这样解释的。不过这个跟最终的算法关系不太大。）
得到的值用于决定依哪个轴进行分裂，或者直接决定最终分组方案（依照指定的轴）。总体来说，性能最高的 R* 树是根据下面这种算法进行构建的。
算法 Split
算法 ChooseSplitAxis
算法 ChooseSplitIndex
对于分裂算法，我们在试验取的 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) 次计算。
不管是 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
算法 Insert
算法 OverflowTreatment：
（译者注：原文没有说明这个算法的参数是一个节点还是一个子树，从算法描述上来看，这应该是对一个节点的操作）
算法 ReInsert
（译者注：我不明白它在步骤 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* 树结构改善。
测试的时候会把树里从根到叶的一个枝存在内存里。另外，如果插入或删除操作的时候出现了新的条目，这个条目也会存在内存里。
测试时页面大小为 1024 字节，这可以存 56 个条目，但测试的时候定义 M 为 50。
测试使用了六个数据文件，包含大概 10 万个 2 维矩形。矩形坐标在 0 到 1 之间。数据文件的性质用下面几个参数来表示。第一，矩形中心的分布情况。第二，n，矩形数。第三，μ，矩形的平均面积。第四，nv = σ/μ，其中 σ 表示面积的方差，nv 表示面积的标准差。nv 与分布无关，矩形的面积与平均面积的差距越大则 nv 越大，原文还说了依据，nv 可以表示平均的重叠面积。
下面罗列了 F1 至 F6 一共六套数据。
测试使用了三种方式。第一，矩形相交查询，给定一个矩形，要求返回与其相交的所有矩形。第二，点查询，给定一个点，要求返回所有包含这个点的矩形。第三，包含查询，给定一个矩形，要求返回所有包含这个矩形的矩形。
测试了每次查询需要的磁盘访问次数，为了测试建立树算法的性能还测试了每次插入算法的磁盘访问次数、树建立完成后的存储效率。另外，用空间链接（Spatial Join）操作代表叠加操作进行了测试。对于空间链接的定义是，如果文件 A 中的一个记录与文件B中的记录相交，则返回一个空间链接结果。对于空间链接结果，测试其每次操作的磁盘访问次数。
R* 树性能显然更好：
这一节的主要内容是测试 R* 树对于访问点数据的性能。之前的访问都是矩形数据。
仍然测试存储效率、插入时间消耗、查询时间消耗。
结果表明 R* 树对于访问点的性能提升比访问矩形的性能提升更好。R* 树甚至比双层四叉树（是不是这个意思？原文2-level grid）性能更好。双层四叉树仅在插入操作方面的性能更好，因此看起来它更适合需要经常插入的情景。
实验表明，本文所提出的 R* 树不论是访问数据库中的多维点还是多维空间数据都有很好的效果。在所有的实验里，R* 树的性能都比其他 R 树变种高。对于点数据的访问，性能提升更明显。R* 树甚至于比双层四叉树更好。
R* 树主要是考虑降低面积、边长、路径矩形的重叠。因为综合考虑了三者，R* 树即使面对分布非常不规则的数据时也表现得十分稳定。又由于强制插入算法的使用，避免了不必要的分裂，R* 树得到了动态的重构，存储效率得到了提升。R* 的实现代价仅比 R 树的实现代价稍高
在接下来的工作中，我们将研究，如果像参考文献【SK90】所述的那样使用前缀（原文是 Prefixes，是什么意思？）或者使用格网逼近（grid approximation），能不能提高删除。我们也会继续改善 R* 树，使其能更有效的管理多边形。
