当前位置：首页 > news >正文

空间数据结构管理---RTree（上篇）

news 来源：原创 2024/5/18 11:07:33

R树是一种用于处理多维数据的数据结构，用来访问二维或者更高维区域对象组成的空间数据.R树是一棵平衡树。树上有两类结点：叶子结点和非叶子结点。每一个结点由若干个索引项构成。对于叶子结点，索引项形如(Index，Obj_ID)。其中，Index表示包围空间数据对象的最小外接矩形MBR，Obj_ID标识一个空间数据对象。对于一个非叶子结点，它的索引项形如(Index，Child_Pointer)。 Child_Pointer 指向该结点的子结点。Index仍指一个矩形区域，该矩形区域包围了子结点上所有索引项MBR的最小矩形区域。

1 R-tree数据结构

通常，我们不选择去索引几何物体本身，而是采用最小限定箱 MBB（minimum bounding box) 作为不规则几何图形的 key 来构建空间索引。在二维空间中，我们称之为最小边界矩形MBR(minimum bounding retangle)。

通常，只需要两个点就可限定一个矩形，也就是矩形某个对角线的两个点就可以决定一个唯一的矩形。通常使用左下，右上两个点表示或者使用右上，左下两个点来代表这个矩形。判断两个MBR是否相交即判断一个MBR的某个顶点是否处在另一个MBR所代表的范围内。

下图是R-tree构造的实例，并假定每个节点限定子节点个数为3。

叶子节点

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

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

非叶子节点

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

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

2 R-tree的搜索

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

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

查找示例如下：

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

2.1 范围搜索

在范围搜索（Range query）中，输入为搜索矩形（查询框），返回与搜索矩形相重叠的实体。

从根节点开始，每个非叶子节点包含一系列外接矩形和指向对应子节点的指针，而叶子节点则包含空间对象的外接矩形以及这些空间对象（或者指向它们的指针）。对于搜索路径上的每个节点，遍历其中的外接矩形，如果与搜索框相交就深入对应的子节点继续搜索。这样递归地搜索下去，直到所有相交的矩形都被访问过为止。如果搜索到一个叶子节点，则尝试比较搜索框与它的外接矩形和数据（如果有的话），如果该叶子节点在搜索框中，则把它加入搜索结果。

假定Q为我们的搜索范围，R-tree的根节点为root。我们查询的语句为range-query(root; q)。

如下灰色区域是进行的查询Q。节点 $^{U}1$ ， $^{U}2$ ， $^{U}3$ ， $^{U}4$ ， $^{U}5$ ， $^{U}6$ 是查询访问过的节点。

2.2 最近邻搜索

对于最近邻搜索(nearest neighbor search)来说，可以查询一个矩形或者一个点。先把根节点加入优先队列，然后查询优先队列中离查询的矩形或者点最近的项，直到优先队列被清空或者已经得到要求的邻居数。从优先队列顶端取出每个节点时先将其展开，然后把它的子节点插回优先队列。如果取出的是子节点就直接加入搜索结果。

3 R-tree的插入

通常，R树的构造算法旨在最小化所有MBR的周长或面积总和。

插入节点时，算法从树的根节点开始递归地向下遍历。检查当前节点中所有外接矩形，并启发式地选择在哪个子节点中插入（例如选择插入后外接矩形扩张最小的那个子节点），然后进入选择的那个子节点继续检查，直到到达叶子节点。满的叶子节点应该在插入之前分割，所以插入时到达的叶子节点一定有空位来写数据。由于把整棵树遍历一遍代价太大，在分裂叶子节点时应该使用启发式算法。把新分裂的节点添加进上一层节点，如果这个操作填满了上一层，就继续分裂，直到到达根节点。如果根节点也被填满，就分裂根节点并创建一个新的根节点，这样树就多了一层。

在上图中有几个问题没有解决，R-tree在构造时如何选择需要插入的节点、如何处理节点个数溢出情况。

插入算法首先在树的每一层都要决定把新的数据插入到哪个子树中。经典R树的实现会把数据插入到外接矩形需要面积拓展最小或周长拓展最小的那个子树。一般在选择子树时，如果当前节点N不是叶子结点，则遍历N中的结点，找出添加该数据时扩张最小的结点。如果有多个这样的结点，那么选择面积最小的结点，并继续向下遍历。如下给出选择子树的伪代码：

当下降到叶子节点时，叶子结点的改变信息会向上传递至根结点以改变每个父节点的信息（MBR信息）。在传递变换的过程中，若节点个数溢出情况出现时，R-tree的节点会进行分裂，这时更新上一层的父节点的MBR，并创建指向新生成的节点的指针，如果父节点依旧出现节点个数溢出的情况，则不断向上分割，直到达到根节点。如果根节点也被填满，就分裂根节点并创建一个新的根节点。其伪代码如下：

对于分裂操作，我们希望分裂后的节点所形成的MBR的重叠区域尽可能小，也就是得到一个相对最优的空间划分，尽可能满足MBR的拓展最小，并且分裂出的节点分布均匀（在这里令分裂的每个部分的最小个数为原始个数B的0.4，即满足|S1|>=0.4B and |S2| >= 0.4B）。其示意图如下，显然左边的更好。

分裂操作补充：对于所有条目中的每一对E1和E2，计算可以包裹着E1，E2的最小限定框J=MBR(E1, E2) ，然后计算增量d=J-E1-E2。计算结束后选择d最大的一对（即增量最大）（如果d较大，说明挑选出来的两对条目基于对角线离得比较远，这样的好处就是分裂后的两个分组可以尽量不重叠）。

如下给出叶子节点分裂的伪代码：

其示例如下：

非叶子节点分裂与上面类似，只不过是对MBR的坐标进行排序，如下是非叶子节点分裂的伪代码：

其示例如下：

如下给出一个节点插入的例子。假如我们希望将点m插入到R-tree中（假定节点所能容纳的最大个数B=3）。首先将点m插入到叶子节点u6中。

这时发现叶子结点个数发生了溢出，因此将其进行分裂，并向上进行更新操作。将u6分裂成了u6和u9，父节点u3添加指向u9的指针。

结果节点个数还是发生了溢出，因此对非叶子节点u3进行分裂得到u10。最后更新根节点。

4 R-tree的删除

R树的删除操作与B树的删除操作会有所不同，不过同B树一样，会涉及到压缩等操作。B树删除过程中如果出现结点的记录数少于半满（即下溢）的情况，会两个相邻结点合并。然而R树却是直接重新插入。其主要思想是，若要将一条记录从R-tree中删除，首先在R-tree中找到包含该记录的叶子节点。如果叶子结点的条目数过少（小于要求的最小值m，即发生下溢），则必须将该叶子结点从树中删除。经过这一删除操作，叶子结点中的剩余条目必须重新插入树中（先插入到链表中等待）。此操作将一直重复直至到达根结点（原来属于叶子结点的条目可以使用Insert操作进行重新插入，而那些属于非叶子结点的条目必须插入删除之前所在层的结点，以确保它们所指向的子树还处于相同的层）。同样，调整在此修改树的过程所经过的路径上的所有结点对应的MBR大小。

Delete
描述：将一条记录E从指定的R树中删除。
D1：[找到含有记录的叶子结点] 使用FindLeaf方法找到包含有记录E的叶子结点L。如果搜索失败，则直接终止。
D2：[删除记录] 将E从L中删除。
D3：[传递记录] 对L使用CondenseTree操作
D4：[缩减树] 当经过以上调整后，如果根结点只包含有一个孩子结点，则将这个唯一的孩子结点设为根结点。

FindLeaf
描述：根结点为T，期望找到包含有记录E的叶子结点。
FL1：[搜索子树] 如果T不是叶子结点，则检查每一条T中的条目F，找出与E所对应的矩形相重合的F（不必完全覆盖）。对于所有满足条件的F，对其指向的孩子结点进行FindLeaf操作，直到寻找到E或者所有条目均以被检查过。
FL2：[搜索叶子结点以找到记录] 如果T是叶子结点，那么检查每一个条目是否有E存在，如果有则返回T。

CondenseTree
描述：L为包含有被删除条目的叶子结点。如果L的条目数过少（小于要求的最小值m），则必须将该叶子结点L从树中删除。经过这一删除操作，L中的剩余条目必须重新插入树中。此操作将一直重复直至到达根结点。同样，调整在此修改树的过程所经过的路径上的所有结点对应的矩形大小。
CT1：[初始化] 令N为L。初始化一个用于存储被删除结点包含的条目的链表Q。
CT2：[找到父条目] 如果N为根结点，那么直接跳转至CT6。否则令P为N 的父结点，令EN为P结点中存储的指向N的条目。
CT3：[删除下溢结点] 如果N含有条目数少于m，则从P中删除EN，并把结点N中的条目添加入链表Q中。
CT4：[调整覆盖矩形] 如果N没有被删除，则调整EN.I使得其对应矩形能够恰好覆盖N中的所有条目所对应的矩形。
CT5：[向上一层结点进行操作] 令N等于P，从CT2开始重复操作。
CT6：[重新插入孤立的条目] 所有在Q中的结点中的条目需要被重新插入。原来属于叶子结点的条目可以使用Insert操作进行重新插入，而那些属于非叶子结点的条目必须插入删除之前所在层的结点，以确保它们所指向的子树还处于相同的层。

更多可以参考这篇博客：R-tree原理

一棵R树满足如下的性质：

    1. 除非它是根结点之外，所有叶子结点包含有m至M个记录索引（条目）。作为根结点的叶子结点所具有的记录个数可以少于m。通常，m=M/2。
    2. 对于所有在叶子中存储的记录（条目），I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（注意：此处所说的“矩形”是可以扩展到高维空间的）。
    3. 每一个非叶子结点拥有m至M个孩子结点，除非它是根结点。
    4. 对于在非叶子结点上的每一个条目，i是最小的可以在空间上完全覆盖这些条目所代表的点的矩形（同性质2）。
    5. 所有叶子结点都位于同一层，因此R树为平衡树。

更多请参考空间数据索引RTree完全解析及Java实现_佳佳牛的博客-CSDN博客_rtree原理