R-Tree

R-Tree

​ R-Tree是一颗用来存储高维数据的平衡树，它把B树的思想扩展到了多维空间，采用了B树分割空间思想，并在添加、删除操作时采用合并、分解节点的方法，保证树的平衡性。

数据结构

​ 每个R树的叶子节点包含了多个指向不同数据的指针，这些数据可以存放在硬盘中，也可以存放在内存中。根据R树的这种数据结构，当需要进行一个高维空间查询时，只需要遍历少数几个叶子节点所包含的指针，查看这些指针指向的数据是否满足要求即可。

​ R树采用了MBR的方法，从叶子节点开始用矩形（Rectangle）将空间框起来，节点越往上，框住的空间就越大，从而实现对空间的分割，如下图所示：

​ 先看图b，首先假设所有数据都是二维空间下的点，图中标识了R8区域中的数据，将那个不规则图形看作是多个数据围成的一个区域，为了实现R树，用一个MBR框住这个不规则图形，这样就形成了一个区域R8。采用同样的方法，一共得到了12个最基本的MBR，这些MBR将被2存储在叶子节点中。下一步是进行高一层的处理，我们发现R8、R9和R10这三个矩形距离最为靠近，因此就可以用一个更大的矩形R3恰好框住这三个矩形，同样，R15和R16恰好被R6框住，R11和R12恰好被R4框住等等。所有最基本的MBR被框入更大的矩形中后，再次迭代，用更大的框框住这些矩形

R树的性质

1. 除根节点外，所有叶子节点包含有m至M个记录索引，作为根节点的叶子节点所具有的记录个数可以少于m，通常 m = M / 2
2. 对于所有在叶子中存储的记录，I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形
3. 每个非叶子节点拥有m至M个孩子节点，除非它是根节点
4. 每个非叶子节点上的每一个记录，I是最小的可以在空间上完全覆盖这些记录所代表的点的矩形
5. 所有叶子节点都位于同一层，因此R树为平衡树

叶子节点

​ 叶子节点所保存的数据形式为：(I, tuple-identifier)，其中，tuple-identifier表示的是一个存放于数据库中的tuple，也就是一条记录，它是n维的。I是一个n维空间的矩形，并可以恰好框住这个叶子结点中所有记录代表的n维空间中的点，其结构如下图所示：

​ 下图是在二维空间中，叶子节点所要存储的信息

非叶子节点

​ 非叶子结点存放的数据结构为：(I, child-pointer)，其中，child-pointer是指向孩子结点的指针，I是覆盖所有孩子结点对应矩形的矩形，如下图所示：

​ 图中，D、E、F、G为孩子节点所对应的矩形，A为能够覆盖这些矩形的MBR，A就是这个非叶子节点所对应的矩形

R树的搜索

​ 假设T为一颗R树的根节点，查找所有搜索矩形S覆盖的记录

1. 查找子树：如果T是非叶子节点，且T对应的矩形与S有重合，那么检查所有T中存储的记录，在T的子树中继续执行搜索操作
2. 查找叶子节点：如果T是叶子节点，且T所对应的矩形与S有重合，那么直接检查T所指向的所有记录，返回符合条件的记录

查找示例如下：

​ 阴影部分是搜索矩形区域，他与根节点对应的最大矩形有重叠，因此搜索操作会作用在其两个子树上，两个子树对应的矩形分别为R1与R2，搜索R1，发现与R1中的R4有重叠，继续搜索R4，最终在R4所包含的R11与R12两个矩形中查找是否有符合条件的记录。搜索R2的过程类似，很想然，搜索是一个迭代操作

R树的插入

​ R树的插入操作与B树的插入操作类似，当新的记录需要被加入叶子节点时，若叶子节点溢出，那么我们需要对叶子节点进行分裂操作。显然，叶子节点的插入比搜索要复杂，插入操作需要一些辅助方法才能完成

​ 假设我们需要将新记录E插入给定的R树中：

1. 为新记录E找到适合插入的叶子节点：调用选择叶子节点的方法，选取一个合适的叶子节点L来放置记录E
2. 在选取的叶子节点L中插入新记录E，如果没有足够的空间，则调用分裂节点方法以获得两个节点L与LL，这两个节点包含了所有L中的记录以及新记录E
3. 将调整向上传递，对节点L进行调整操作，如果进行了分裂操作，那么同时需要对LL进行调整操作
4. 对树进行增高操作，如果节点分裂向上传递导致了根节点的分裂，那么需要创建一个新的根节点，并且让它的两个孩子节点分别为原来那个根节点分裂后的两个节点

选择叶子节点

​ 选择叶子节点插入新记录E：

1. 初始化N为根节点
2. 如果N为叶子节点，则直接返回N
3. 如果N不是叶子节点，则遍历N中的节点，找出添加E扩张最小的节点，并把该节点定义为F，如果有多个这样的节点，则选择面积最小的节点
4. 遍历F为根节点的子树，重复第二步操作

调整操作

​ 叶子节点的改变向上传递至根节点以改变沿途中各个非叶子节点对应的矩形区域，在此过程中可能会产生节点的分裂：

1. 初始时将N设为L
2. 如果N为根节点则停止操作
3. 设P为N的父节点，En为P中指向N的记录，调整En，对En的MBR进行扩展得到新的MBR
4. 如果N有一个刚刚被分裂而产生的节点NN，则创建一个指向NN的记录Enn，如果P有足够空间存放Enn，则将Enn添加到P中，如果没有则对P进行分裂操作，已得到P和PP
5. 如果N == L且发生了分裂，则把NN置为PP，从第二步开始操作

插入操作示例如下：

​ 上图中，我们需要插入R21这个矩形，我们先选择一个合适的叶子节点用于插入R21。根节点中有两个记录，分别时R1和R2，R1已经完全覆盖了R21，而如果向R2中添加R21则会使R2扩展很多，因此我们选择R1插入，然后进行下一级操作。相比于R4，向R3中添加R21更合适，因为在R3中使用R21进行扩展，扩展部分的面积较小。因此我们需要在R8、R9、R10所在的叶子节点中插入R21，但由于叶子节点没有足够的空间，因此需要进行分裂操作，如下图所示：

R树的删除

​ R树的删除与B树的删除有所不同，但是都会涉及压缩等操作。

​ 假设要将一条记录E从指定的R树中删除：

1. 找到含有记录E的叶子节点：调用查找叶子节点方法，找到含有记录E的叶子节点L，如果查找失败则直接终止
2. 将记录E从L中删除
3. 对叶子节点L执行压缩树操作
4. 经过上述调整后，如果根节点只包含一个孩子，则将这个唯一的孩子设为根节点

查找叶子节点

​ 在以T为根节点的R树中找到含有记录E的叶子节点：

1. 如果T不是叶子节点，则检查T中的每一条记录F，找出与E对应矩形相重合的F（不需要完全覆盖）。对于满足条件的F，对其指向的子树重复操作，直至找到E或检查完所有记录
2. 如果T是叶子节点，则检查每个记录是否有E存在，如果有则返回T

压缩树

​ L为含有被删记录E的叶子节点，删除E后，如果L的记录数小于最低要求m，则必须将该叶子节点L从树中删除，L中的剩余记录需要重新插入树中，重复此操作直到根节点，在此过程中需要修改沿途中所有节点对应的MBR的大小

1. 初始时N = L，并初始化一个用于存储被删除节点L包含的剩余记录的链表Q
2. 如果N为根节点，则跳到第六步，否则令P为N的父节点，En为P中指向N的记录
3. 如果N含有记录数小于m，则从P中删除En，并把N中记录加入Q中
4. 如果N未被删除，则调整En的MBR
5. 令N = P，重复第二步
6. Q中的所有记录需要被重新插入，属于叶子节点的记录可以直接使用插入操作，而属于非叶子节点的记录必须在插入删除之前所在层的节点，从而确保它们指向的子树处于相同层

删除示例如下：

​ 假设节点最大记录数为4，最小为2。上图中，我们需要删除记录c，首先使用查找叶子节点操作找到c所在的叶子节点R11。将c从R11删除后，R11只剩一条记录，少于2，因此要执行压缩操作。c被删除，R11剩余的记录被插入链表Q，然后向更高一层节点进行此操作，这样R12会被插入到Q中，重复上述过程直至根节点

​ 到达根节点时，根节点的记录R1也被插入到Q中，这样根节点只剩下了R2，我们会执行重新插入操作，插入R3、R12、d到它原来所在的层，之后根节点只剩一个记录了，我们直接把这个根节点删除，它的孩子节点R5、R6、R7、R3所在的节点被设为新的根节点，删除操作结束

区域划分

​ 将一个区域中的所有矩形划分成合适的两部分，是影响R树检索效率的一个重要因素

1. 以面积划分：划分后两部分的MBR之和最小，但是此过程需要穷举，因此时间复杂度很大（指数级）

2. 平方耗费法：（平方级）

   1. 从要划分的矩形集中选取再划分后最不可能在同一类中的两个矩形作为种子，作为两类中的第一个矩形
   2. 将剩余的矩形一次分配到这两个类中

   注：该方法不能保证分裂后MBR和最小