R 树——动态空间索引结构

一些术语

本文特别定义了一些术语用于表示不同的对象，正确地区分这些术语有助于更好的理解 R 树。

空间数据库（Spatial database）：存储真正的空间数据对象（比如点、面片等）的地方，它由大量的空间数据对象组成，这些数据对象几乎没有任何（或者仅有简单的）组织形式。
叶子节点（Leaf node）：树中最底层的节点，没有子节点的节点。R 树中的叶子节点由一定数目的索引记录构成。
非叶节点（Non-leaf node）：树中除叶子节点之外的节点。R 树中的非叶节点由一定数目的条目构成。
索引记录（Index records）：叶子节点中存储的数据形式，一条索引记录指向空间数据库中的一个数据对象。
元组（Tuple）：空间数据库中存储的数据形式，一条元组就是一个空间数据对象，并且每个元组都有一个唯一的标识符。
条目（Entry）：又称索引条目（Index entry），R 树节点中存储的数据形式，当为叶子节点时，此条目就是索引记录。

R 树简介

R 树是一种与 B 树类似的高度平衡树。这种索引是动态的，不需要定期重建。索引记录（Index Records）保存在叶节点中，索引记录包含指向数据对象的指针。（译者注：原文中索引的终端叶子节点中存储的是索引记录而不是真正的空间对象）

空间数据库由一系列元组（tuple）构成，每个元组代表一个空间对象，并且每个元组都有一个唯一的标识符，标识符的作用是用于检索。

R 树中的叶子节点所存储的条目（entry）的形式为（也即索引条目的形式为）：

（I，tuple-identifier）

其中，Tuple-identifier 是一个指向空间对象的指针。I 是一个 n 维矩形，表示空间对象的外接包围盒，该包围盒的表示形式为：

I=(I0,I1,...,In-1)

其中 n 为维数，Ii 为某一维上的闭区间 [a,b]，而且，a 或 b 可以为无穷。（译者注：原文中写到允许矩形 I 趋向于无穷大，却没有写到是否允许矩形 I 在某个维度上宽度为 0）

R 树中的非叶节点中所存储的条目的形式为：

（I，child-pointer）

其中，I 是其所有子节点的外廓矩形的总外廓矩形。Child-pointer 是指向下一级节点的指针。

注意：R 树中的节点中保存有多个条目，每个条目都有一个外廓矩形及相应子节点的指针。并非每个节点有一个外廓矩形及若干指针。

记 M 为一个节点中的最大条目数。取 m <= M/2，约定此 m 为一个节点中的最小条目数。此时，R 树具有如下性质：

若叶节点不是根节点，则每个叶节点所包含的索引记录个数介于 m 与 M 之间；
对于叶节点中的索引记录（I，tuple-identifier），I 是其最小外包矩形；
若非叶节点不是根节点，则其中包含的子节点个数介于 m 与 M 之间；
对于非叶节点中的条目（I，child-pointer），I 表示能够覆盖其所有子节点的外包矩形的外包矩形。（译者注：原文中没有使用索引记录（index record）这个词，而用了条目（entry），索引记录只用在叶子节点中）
根节点若非叶节点，则其至少有两个子节点。
所有叶子节点都在同一层。

一个有 N 个索引记录的R树，其高度最大为 logm（N）-1，这是因为其每个节点至少要有 m 个记录。节点的总个数最多为 N/m + N/m2 + …… + 1。最差的情况下，除根节点外的各节点空间利用率为 m/M。通常情况下节点中的条目数不会只有 m 个，所以树的实际高度通常小于 logm（N）-1，空间利用率通常高于 m/M。如果节点中有超过 3 或 4 个条目，这个 R 树就会非常宽，从而导致绝大多数空间都用于保存叶节点，也就是保存索引记录。不同的 m 值会影响索引的性能。

搜索算法

R 树搜索算法与 B 树类似，都是从根节点向下搜索。然而，在搜索到某个节点后，接下来可能需要搜索这个节点下属的几个子树（而不是只搜索其中一个）。也就是说，搜索不是单向的。因此，在某些糟糕的情况下，R 树可能无法保证性能。虽然如此，对于绝大多数的数据来说，R 树的更新算法可以保证 R 树有一个相对较好的结构，能够保证在进行搜索的时候，无关的区域不会参与检索，只有在搜索区域附近的数据才会被检索（examine）。

下面描述搜索算法 Search。我们将一个索引条目（Index Entry）记为 E，其中的外廓矩形记为 EI，其中的指针，不管它是叶节点中的指针还是中间节点中的指针，我们均将其记为 Ep。下文均使用类似的约定。

算法 Search：

记 R 树的根节点记为 T。搜索查找所有与搜索矩形 S 相交的索引记录：

步骤 S1：搜索子树——如果 T 不是一个叶节点，则检查其中的每一个条目 E，如果 EI 与 S 相交，则对 Ep 所指向的那个子树根节点调用 Search 算法。（译者注：Search 算法接收的输入为一个根节点，所以在描述算法的时候，原文称对子树根节点调用 Search 算法，而不是对子树调用 Search 算法）
步骤 S2：搜索叶节点——如果 T 是一个叶节点，则检查其中的每个条目 E，如果 EI 与 S 相交，则 E 就是需要返回的检索结果之一。

插入算法

为一个新的数据元组而往 R 树中插入一个索引记录的方法与 B 树的插入类似，都是将索引记录加入叶节点当中，如果节点上溢就进行节点分裂。节点分裂有可能导致上一级的节点也发生分裂，分裂操作有可能一直向上传递。

算法 Insert：

往 R 树里插入一个索引条目 E：

步骤 I1：为新记录寻找保存位置——调用算法 ChooseLeaf，选择一个用于保存 E 的叶节点 L。
步骤 I2：将记录存入叶节点——如果节点 L 中有存储空间，则将 E 保存在里面。否则使用算法 SplitNode 执行节点分裂操作，节点 L 将变成两个新节点 L 和 LL，L 和 LL 中保存了 E 和旧 L 中的所有条目。
步骤 I3：向上传递树的变化——对节点 L 调用算法 AdjustTree。如果步骤 I2 中进行过节点分裂操作，那还要对 LL 调用算法 AdjustTree。
步骤 I4：树的长高——如果节点的分裂操作向上传递导致根节点分裂，那就要新建一个根节点。新的根节点的两个子节点就是旧根节点分裂后形成的两个节点。

算法 ChooseLeaf

选择一个叶节点用于保存新的索引条目 E：

步骤 CL1：初始化——记 R 树的根节点为 N。
步骤 CL2：检查叶节点——如果 N 是个叶节点，返回 N。
步骤 CL3：选择子树——如果 N 不是叶节点，则从 N 中所有的条目中选出一个最佳的条目 F，选择的标准是：如果 E 加入 F 后，F 的外廓矩形 FI 扩张最小，则 F 就是最佳的条目。如果有两个条目在加入 E 后外廓矩形的扩张程度相等，则在这两者中选择外廓矩形较小的那个（原文为：Resolve ties by choosing the entry with the rectangle of smallest area）。（译者注：由于节点结构是“节点包括若干条目，每个条目都有外廓矩形”，所以 F 是一个条目而不是一个节点；同样是由于这个原因，CL2 必须在 CL3 之前执行，否则就会产生试图往一条索引记录里插入另一条索引记录的错误）
步骤 CL4：向下寻找直至达到叶节点——记 Fp 指向的孩子节点为 N，然后返回步骤 CL2 循环运算，直至查找到叶节点。

算法 AdjustTree

由叶节点 L 向上运算直至根节点，目的是调整外廓矩形，并将节点分裂的结果向上传递：

步骤 AT1：初始化——将 L 记为 N。如果 L 已经被分裂成为了 L 和 LL，则将 LL 记为 NN。
步骤 AT2：检查运算是否结束——如果 N 是根节点，算法中止。
步骤 AT3：调整父节点中相应条目的外廓矩形（原文是 Covering Rectangle）——记 P 是 N 的父节点，记 En 是 P 里表示 N 的那个条目。调整 EnI，使其恰好能够无冗余地包括 N 中的所有条目的外廓矩形。
步骤 AT4：向上传递节点分裂的结果——如果由于节点分裂产生了一个新的节点 NN，则新建一个条目 Enn，其中的 Ennp 指向 NN，EnnI 是 NN 的最小外廓矩形。如果 P 有空间容纳 Enn，则将 Enn 加入 P 当中。如果节点 P 已满，则对节点 P 执行算法 SplitNode，生成新的 P 和 PP，P 和 PP 包括旧的 P 中的所有条目和条目 Enn。
步骤 AT5：上移——如果 P 发生了分裂，则令 N=P，令 NN=PP，然后返回步骤 AT2 重新开始运算。

算法 SplitNode

这个算法非常复杂，下文将专门介绍。

译者总结

基本过程是这样的：先找到一个用于插入的位置。如果能直接插入，则直接插入，然后调整其父节点的外廓矩形。注意是父节点中的外廓矩形而不是它插入的那个节点的外廓矩形，这是由节点的存储结构决定的。

如果插入不能直接插入，则进行节点分裂然后插入。这个比较复杂了。分裂后的一个节点会占用旧节点的位置，对这个节点要进行父节点调整。对于另外一个新节点，需要将其作为一个条目插入到原本那个节点的父节点中。这又是一个插入操作，又有可能产生节点分裂。但是在算法描述中这里不再调用算法 Insert，而是直接从 AT2 重新计算，相当于重新调用算法 AdjustTree。换言之，插入操作不是一个简单的递归或者循环，真正递归的是算法 AdjustTree。另外，这究竟是递归还是循环尚不清楚。从算法描述上来说，这更接近循环。最后，如果有分裂的话，有可能导致根节点分裂，这又产生了一个新建根的问题。

删除算法

算法 Delete

从 R 树中移除索引记录 E：

步骤 D1：寻找包含记录的节点——调用算法 FindLeaf 来定位包含 E 的叶节点 L。如果没有找到，则算法中止。
步骤 D2：删除记录——将 E 从 L 中移除。
步骤 D3：传递变化——调用算法 CondenseTree，传入 L（原文是 Passing L）。
步骤 D4：缩短树——如果树在经过调整后，根节点只剩下了一个子节点，那么就把这个子节点当成根节点。

算法 FindLeaf

R 树的根节点为 T，查找包含索引条目 E 的叶节点：

步骤 FL1：查找子树——如果 T 不是叶节点，则逐个检查 T 中的每个条目 F，看 FI 是否与 EI 相交。若相交，则对 Fp 指向的子树根节点调用算法 FindLeaf。如此递归直至查找到 E 或者所有的条目都被检查过。（译者注：按我的理解最后一句话有问题，第一，如果查找结果为空，则只需要查找根节点 T 中的所有条目 F，不必遍历整个树；第二，步骤 FL1 不可能找到 E，E 保存在叶节点中，它肯定会在 FL2 中被找到。）
步骤 FL2：如果 T 是一个叶节点，则逐个检查 T 中的每一个条目看有没有 E。原文是这样写的：Check each entry to see if it matches E。如果找到了 E，返回 T。（译者注：对于这个描述我有点困惑，因为这个算法没有说明什么叫 it matches E。换言之，这个算法中的 E 是以什么方式传入的？不应该是一个地址吗？这样根本不需要检查it matches E，只有it is E或者it is not E两种情况。）

算法 CondenseTree

树的压缩。叶节点 L 中刚刚删除了一个条目。现在要评估这个节点的条目数是否太少，如果太少，应将这些条目移到其他节点中。如果有必要，要逐级向上进行这种评估。调整向上传递的路径上的所有外廓矩形，使其变小。

步骤 CT1：初始化——记 N=L，定义 Q 为需要评估的节点集合，初始化的时候将此集合置空。
步骤 CT2：查找父条目，注意是父条目，不是父节点——如果 N 是根节点，转到步骤 CT6。如果 N 不是根节点，记 P 为 N 的父节点，并记 En 为 P 中代表 N 的那个条目。
步骤 CT3：评估节点是否下溢——如果 N 中的条目数小于 m，意味着节点 N 下溢，此时应当将 En 从 P 中移除，并将 N 加入 Q。注意 N 是一个节点，他把一个节点放入 Q 了。
步骤 CT4：调整外廓矩形——如果 N 没有被评估（我的理解是，如果 N 没有下溢），则调整 En 的外廓矩形 EnI，使其尽量变小、恰好包含 N 中的所有条目。
步骤 CT5：向上一层——令 N=P，返回步骤 CT2 重新执行。
步骤 CT6：重新插入孤立条目——对 Q 中所有节点的所有条目执行重新插入。叶节点中的条目使用算法 Insert 重新插入到树的叶节点中；较高层节点中的条目必须插入到树的较高位置上。这是为了保证这些较高层节点下的子树的叶子节点、与其他叶子节点能够放置在同一层上。这里需要注意，第一，Q 中的都是节点，也就是说，Q 中保存的是节点，如果节点不是叶节点，那 Q 中实际上保存了子树；第二，但是算法要求不是把 Q 重新插入进去（Q 已经下溢了，已经被放弃了），而是把 Q 中的条目插入进去，如果这个条目是一个底层的索引条目，那可以调用算法 Insert 进行插入，但是如果这个条目是中间条目，本文没有描述清楚应该怎么插入，这一点很严重。

上文所描述的处理下溢节点的流程与 B 树中的相应操作不同。B 树中对这个问题的处理方法是将两个或更多个相邻的节点合并起来。对于 R 树来说，虽然其中没有像 B 树中那样的“相邻节点”的概念，但 R 树仍然可以借用与 B 树类似的处理方法：下溢的节点与其某个兄弟节点合并，选择目标兄弟节点的原则是合并后面积的增加最小；或者，把节点中的各个条目分配入兄弟节点中。这两种模仿 B 树的解决方法都有可能导致节点的分裂。选择“重新插入”这一解决方法是出于两个原因。其一，这种方法同样可以完成任务，并且更容易实现。这种方法会有比较好的性能，因为重新插入操作所涉及的磁盘页通常就是前几个步骤的查找操作所涉及的磁盘页，它们在前几步的操作中就已经调入内存了。其二，重新插入这个操作进一步优化了树的空间结构。一个条目如果长期保存在同一个父节点中，有可能导致缓慢的索引性能恶化。重新插入的方法一定程度上避免了这个问题。

更新和其它操作

如果一个数据元组的形状发生了更新，并因此导致此数据元组的外廓矩形发生变化，则相应的索引记录必须被删除、更新、然后重新插入。这是为了保证更新后的索引记录能够保存在树的正确位置上。

除上面所述的那种搜索操作外，下面几种搜索操作也比较常用。比如说，查找完全被某个区域所包含的数据对象，或者查找完全包含了某个区域的数据对象。这几种搜索都能够用前述搜索算法的直接变形（原文是straightforward variations）所实现。查找某个特定的条目的方法可以用删除操作的算法 FindLeaf 实现。批量删除，也就是说删除某个区域内所有数据对象的索引条目的方法，R 树也能够提供良好的支持。但是原文没有说应该怎么做。

节点分裂

如果想要往一个已经包含了 M 个条目的满节点中添加一个新条目，就需要将 M+1 个节点分别划分到两个节点当中。划分出的两个节点应该有尽可能大的区别，为了保证这一点，两个新节点都需要经过一系列的搜索操作的检查。由于进行搜索操作的时候，一个节点是否被访问取决于它的外廓矩形是否与查询范围相交，所以节点划分的原则是两个新节点的外廓矩形的总面积应当尽可能少。注意是总面积尽可能少而不是重叠面积尽可能少。

在使用算法 ChooseLeaf 来决定新的条目插入到哪里的时候，使用的也是类似的规则。算法 ChooseLeaf 选定的子树应当是那个加入新条目后外廓矩形的面积扩大程度最小的子树。

第一，遍历算法

寻找最佳的分裂方案的最直接方法是生成所有可能的分组方案并从中选择最佳方案。然而可能的分组方案太多，大约为 2 的 M-1 次方，而 R 树的一个合理的 M 值一般为 50，所以可能的分组方案数目可想而知。我们实现了一种经过修改的遍历算法，以其作为评判其他算法的标准。但是这种算法在节点较大的时候运算速度很慢。

第二，平方成本算法

这种算法尝试选择一种总面积最小的节点分裂方案，但本方法不保证得出的方案是最佳方案。这种方法的复杂性与 M 平方相关、与空间维度线性相关。这种算法首先从 M+1 个条目中选出两个条目作为两个新组的第一个元素。这两个条目的选择原则为：两个条目如果放在同一组中，会有最多的冗余空间。也就是说，两个条目的总的外廓矩形面积，减去两个条目所占用的面积，其差最大。接下来剩余的条目将按一定的顺序分入两个组当中。顺序是这样计算的：每个条目插入 A 组或 B 组导致的面积增长程度会有所不同。插入两个组后，两个组面积增长程度差异最大的那个条目、就是接下来要插入的条目。

算法 QuadraticSplit

将一个含有 M+1 个索引条目的集合分为两组：

步骤 QS1：为两个组选择第一个条目——使用算法 PickSeed 来为两个组选择第一个元素，分别把选中的两个条目分配到两个组当中。
步骤 QS2：检查是否已经完成分配——如果所有的条目都已经分配完毕，算法中止。如果一个组中现有的条目太少，以至于剩余未分配的所有条目都要分配到这个组当中，才能避免下溢，则将剩余的所有条目都分配到这个组中，算法中止。
步骤 QS3：选择一个条目进行分配——调用算法 PickNext 来选择下一个进行分配的条目。将其加入一个组，要求它加入这个组比加入另一个组能有较小的面积增长。如果两个面积增长相同，则将其加入面积较小的那个组当中。若两个组面积也相同，则加入条目数更少的那个组当中。然后返回步骤 QS2 继续进行。

算法 PickSeeds

选择两个条目，将其分别作为两个分组中的第一个元素：

步骤 PS1：计算分组方法的效率指数——对于每一对条目 E1、E2 和同时包含 E1、E2 的外廓矩形 J，计算 d=Area（J）-Area（E1I）-Area（E2I）。（译者注：注意它没有考虑图形重叠的问题。）
步骤 PS2：选择浪费程度最大的一组——选择 d 值最大的一组 E1 和 E2 作为返回值。

算法 PickNext

在余下的所有条目中选择一个条目将其分组：

步骤 PN1：计算将每个条目分入每个组的成本——对于每个尚未分组的条目，计算 d1=将此条目加入第一组后导致的外廓矩形面积增张。同理计算 d2。
步骤 PN2：选择用于分配的最佳条目——选择 d1 与 d2 之差最大的那个条目。

第三，线性成本算法

这个算法与 M 和维度数均线性相关。本算法 LinearSplit 与平方成本算法 QuadraticSplit 相同，但是算法 PickNext 使用了一种不同的 PickSeeds 算法，而且 PickNext 算法直接选择任意一条未分组的条目将其分组。

算法 LinerPickSeed