树：R树

来自Wikioe
跳到导航 跳到搜索


关于

空间数据

基于实体的模型：

  1. 0-dimensional objects：一般使用点point来表示那些对于不需要使用到形状信息的实体。
  2. 1-dimensional objects or linear objects：用于表示一些路网的边，一般用于表示道路road。 (polyline)
  3. 2-dimensional objects or surfacic objects：用于表示有区域面积的实体。 (polygon)


常用的空间数据查询方式：

  1. 窗口查询：给定一个查询窗口（通常是一个矩形），返回与查询窗口相重叠的物体。
  2. 点查询：给定一个点，返回包含这个点的所有几何图形。

空间数据获取的方法

通常，我们不选择去索引几何物体本身，而是采用“最小限定箱”（MBB：minimum bounding box）作为不规则几何图形的 key 来构建空间索引：

  1. 二维：称之为“最小限定矩形”（MBR：minimum bounding retangle）。
    “最小限定矩形”（MBR：minimum bounding retangle）.png
  2. 三维：称之为“最小限定箱”（MBB：minimum bounding box）。
    “最小限定箱”（MBB：minimum bounding box）.png


通过索引操作对象的 MBB 进行查询，步骤：【？？？】

  1. Filtering：过滤掉 MBB 不相交的数据集，剩下的 MBB 被索引到的称为一个数据的超集。
    通过索引操作对象的 MBB 进行查询：Filtering.png
  2. Refinement：测试实际的几何形状会不会满足查询条件，精确化。
    通过索引操作对象的 MBB 进行查询：Refinement.png


使用：

  1. 用数据表示一个 MBR：
    通常，只需要两个点就可限定一个矩形，也就是矩形某个对角线的两个点（“左下右上”或“左上右下”）就可以决定一个唯一的矩形。
    用数据表示一个 MBR.png
    1. 表示一个点的数据：
    　　　　public class Point{ //用一个类来表示一个点
　　　　    public Float x;
　　　　    public Float y
　　　　}
    1. 表示一个 MBR 的数据：
    　　　　public class MBR{
　　　　    public Point BottomLeft;
　　　　    public Point TopRight;
　　　　}
  2. 判断两个 MBR 是否相交：
    如果一个MBR的TopLeft或者BottomRight的（x，y）位于另一个MBR的 xRange 和 yRangle 里面，则说明这两个MBR相交。
    判断两个MBR是否相交.png

R树

简介

R树 是 B树 在高维空间的扩展：采用 B树 分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。

每个 R树 的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。
根据 R树 的这种数据结构，当需要进行一个高维空间查询时，只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。
1984年，加州大学伯克利分校的Guttman发表了一篇题为“R-trees: a dynamic index structure for spatial searching”的论文，向世人介绍了R树这种处理高维空间存储问题的数据结构。
* Guttman, A.; “R-trees: a dynamic index structure for spatial searching,” ACM, 1984, 14

R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。

  1. 如果没有 R树 怎么解决？
    一般情况下我们会把餐厅的坐标“(x,y)”分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。
    如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌地图这种超大数据库中，这种方法便必定不可行了。
  2. R树 的解决？
    R树采用了一种称为“MBR”（Minimal Bounding Rectangle，即最小边界矩形）的方法对空间进行分割……
    R树 使我们不必遍历所有数据即可获得答案，效率显著提高。
    如下：

引子

R树 示例：

R树：一个实例1.png

R树 采用了一种称为“MBR”对空间进行分割：从叶子结点开始用矩形（rectangle）将空间框起来，结点越往上，框住的空间就越大，以此对空间进行分割。


“MBR”分割示例：（假设所有数据都是二维空间下的点）

R树：一个实例2.png
  1. 如图，“shape of data object”所标记的是一块不规则图形，我们把它看作是多个数据围成的一个区域。为了实现“R树”结构，用一个最小边界矩形恰好框住这个不规则区域，这样就构造出了一个区域：“R8”。
    其他实线包围住的区域（“R8”到“R19”）同理。【这些矩形都将被存储在页子结点】
  2. 如图，可以发现“R8”，“R9”，“R10”三个矩形距离最为靠近，因此就可以用一个更大的矩形“R3”恰好框住这 3 个矩形。【叶子节点的父节点】
    同理：“R15”，“R16”被“R6”恰好框住；“R11”，“R12”被“R4”恰好框住，等等。
  3. 重复上一步，所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。

最后，根结点存放的是两个最大的矩形，这两个最大的矩形框住了所有的剩余的矩形，当然也就框住了所有的数据。

  • 下一层的结点存放了次大的矩形，这些矩形缩小了范围。
  • 每个叶子结点都是存放的最小的矩形，这些矩形中可能包含有n个数据。


对应于地图的情况：

  1. 打开地图（也就是整个R树），先选择国内还是国外，【对应根结点】
  2. 然后选择华南地区（对应第一层结点），选择广州市，【对应第二层结点】
  3. 再选择天河区，【对应第三层结点】
  4. 最后选择天河城所在的那个区域。【对应叶子结点，存放有最小矩形】

如图：

R树：对应于地图.png

定义（性质）

  1. 非根非叶子结点拥有“m/2”至“m”个子结点（子树）。
  2. 叶子结点包含有“m/2”至“m”个记录索引（条目）。
    • 作为根结点的叶子节点所具有的记录个数可以少于“m/2”。
  3. 对于节点（叶子、非叶子节点）的所有记录（条目），“I”是最小的可以在空间中完全覆盖这些记录所代表的点的矩形（“矩形”是可以扩展到高维空间的）。
  4. 所有叶子结点都位于同一层，因此 R树 为平衡树。
  • 【条目个数 = 子结点个数】

结构

如图，“R树的节点存储结构”：

R树：节点存储结构.png

叶子结点

叶子结点所保存的数据形式为：“(I, tuple-identifier)”，其中：

  1. “I”：是一个 n 维空间的矩形，并可以恰好框住这个叶子结点中所有记录代表的 n 维空间中的点。【框住点的最小矩形，如引子中的“R8”】
    如：“I=(I0,I1,…,In-1)”。
  2. “tuple-identifier”：表示的是一个存放于数据库中的 tuple（多元组），也就是一条记录，它是 n 维的。【所有的点，如引子中构成“shape of data object”的所有点是一个条目】


示例，在二维空间中的叶子结点所要存储的信息：

R树：在二维空间中的叶子结点所要存储的信息.png

如图，

  1. “I”所代表的就是图中的矩形，其范围是“a<=I0<=b”，“c<=I1<=d”。
  2. “tuple-identifier”，在图中即表示为那两个点。
  • 这种形式完全可以推广到高维空间。

非叶子结点

非叶子结点存放的数据结构为：“(I, child-pointer)”，其中：

  1. “I”：覆盖所有孩子结点对应矩形的矩形。【框住所有孩子节点矩形的最小矩形，如如引子的“R3”】
    如：“I=(I0,I1,…,In-1)”。
  2. “child-pointer”：表示指向孩子结点的指针。

R树操作

搜索

R树 的搜索操作：【搜索内容为“矩形”，判断条件是“与节点矩形是否有重合”】

  • 输入一个搜索矩形。
  • 返回所有符合查找信息的记录条目。


搜索过程：

  1. 如果当前节点是非叶子节点：
    1. 若当前节点的矩形（“I”）与“搜索矩形”有重合，那么对当前节点存储条目所指向的子节点进行“搜索过程”。
    2. 若当前节点的矩形（“I”）与“搜索矩形”没有重合，无匹配。
  2. 如果当前节点是叶子节点：
    1. 若当前节点的矩形（“I”）与“搜索矩形”有重合，返回当前节点存储条目中符合条件的记录。
    2. 若当前节点的矩形（“I”）与“搜索矩形”没有重合，无匹配。


示例：

R树：搜索操作：示例.png

红色查询区域，与“P3”子树“P4”子树相重叠，所以根据“缩小空间”的思想，只需要遍历“P3”和“P4”所在子树就行而无需遍历“P1”，“P2”。

插入

R树 的插入操作也同 B树 的插入操作类似：

当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。
  • 叶子结点的插入操作会比搜索操作要复杂。
  • 插入操作需要一些辅助方法才能够完成。


插入过程：

  1. 查找合适插入的叶子结点：（从根节点开始）
    1. 如果当前节点不是叶子节点：则遍历节点的子节点，找到“添加新条目时，节点矩形增量最小”的节点。
      • （如果有多个这样的结点，那么选择面积最小的结点）
    2. 如果当前节点为叶子结点，则直接返回当前叶子节点。
  2. 插入新条目至叶子节点：
    1. 如果叶子节点条目个数 < 最大值（“M”）：
      1. 插入：插入条目。
      2. 调整：（如果需要）
        1. 扩大叶子节点矩形“I”为所有条目的“MBR”。
        2. 扩大父节点矩形“I”为所有条目的“MBR”。
    2. 如果叶子节点条目个数 = 最大值（“M”）：
      1. 分裂：将该叶子节点分裂为两个新的叶子节点，用于包含已有条目与新插入条目；
      2. 调整：（如果需要）
        1. 扩大叶子节点矩形“I”为所有条目的“MBR”。
        2. 扩大父节点矩形“I”为所有条目的“MBR”。
  • 【如果父节点条目数引起“分裂”，则向上迭代“调整父节点矩形”过程】


示例：

  1. 插入空间足够，且不需扩大矩形：
    R树：插入操作：“插入空间足够，且不需扩大矩形”.png
  2. 插入空间足够，但需要扩大矩形：
    R树：插入操作：“插入空间足够，但需要扩大矩形”.png
  3. 插入空间不足，需要分裂该节点：
    R树：插入操作：“插入空间不足，需要分裂该节点”.png
    由于插入的“w”所在的区域“P1”的数据条目空间不足，所以采用分裂算法将结点“P1”分裂为“P1”（包含“A”，“B”）和“P5”（包含“k”，“w”）两个结点；
    分裂之后导致父节点条目数过多，需要向上传递，最终导致生成新的根结点“Q1”，“Q2”。

分裂算法

分类算法有多种：

R树：常见的分裂算法.png


以“Quadratic”方案为例，其算法：

  1. 选取种子条目seed：
    R树：分裂算法“Quadratic”：选取种子条目.png
    1. 从节点所有条目中挑选两个条目（E1、E2）；
    2. 计算两个条目的 MBR 增量：“d = MBR(E1, E2) - E1 - E2”；
    3. 重复以上步骤，计算每一对条目的增量，并选取增量 d 最大的一对作为种子条目。
      • 【选择增量最大，则种子条目的矩形对角线最远，分裂之后的新节点重叠可能最小】
        R树：分裂算法“Quadratic”：增量与分裂.png
  2. 将剩下条目分配与这两个seed，使其各成为一组。
    • 【分配的原则就是离谁比较“近”就和谁一组：用增量“d1=MBR(E,seed1)-E-seed1”）与增量“d2=MBR(E,seed2)-E-seed2”的大小判断哪个近】
      R树：分裂算法“Quadratic”：距离判断.png


除了上述“Quadratic”的分裂算法之外还有其他的分裂算法，但是分裂的效果都不如“R*树”（R树的改进版）的算法好。

删除

R树 的删除操作与 B树 的删除操作会有所不同，不过同B树一样也会涉及到压缩等操作。

  • R树 的删除同样比较复杂，需要用到一些辅助函数来完成整个操作。


删除过程：

  1. 查找含有记录的叶子结点：（从根节点开始）
    1. 如果当前节点不是叶子节点：则遍历节点的子节点，找到“与条目的 MBR 有重合”的节点。
      • （向下迭代此过程）
    2. 如果当前节点为叶子结点：
      1. 若当前节点存在对应条目，返回当前节点。
      2. 若当前节点无对应条目，终止删除。
  2. 从叶子节点删除条目：
    1. 如果删除后叶子节点中条目个数 >= 条目最小值（m/2）：
      1. 删除：删除条目；
      2. 调整：（如果需要）
        1. 缩小叶子节点矩形“I”为所有条目的“MBR”。
        2. 缩小父节点矩形“I”为所有条目的“MBR”。
    2. 如果删除后叶子节点中条目个数 < 条目最小值（m/2）：
      1. 删除：
        1. 删除节点，并将节点中剩余条目加入“待插入链表”；
        2. 删除父节点条目：对父节点的迭代“删除过程”。
          • 【如果父节点出现下溢，同样进入“待插链表”】
      2. 重插入：将“待插链表”中的条目重新插入链表。
        • 【原叶子结点的条目可以使用“插入操作”进行重新插入；原非叶子结点的条目必须插入删除之前所在层的结点，以确保它们所指向的子树还处于相同的层】
    • 如果当前叶子节点即为根节点，则直接删除并调整矩形“I”即可。


与“B树”相比，若出现条目（关键字个数）下溢：

  • “B树”删除时，将会导致：从父节点借（兄弟节点关键字够多）；或与相邻节点合并（兄弟节点关键字不够）。
  • “R树”删除时，将会导致节点的条目重新插入。


删除下溢，示例：

删除记录“c”：
R树：删除操作：下溢示例1.png
上一步删除条目“c”与节点“R12”之后，这个删除操作继续向上传递，直到根结点条目“R1”被插入“Q”中，此时，根结点就只剩下了“R2”。
但是，重新插入操作会有效的解决这个问题：
插入“R3”，“R12”，“d”至它原来所处的层；（根结点只有一个条目）
根据“Inert”中的操作，把根结点删除，并将其孩子结点（“R5”，“R6”，“R7”，“R3”所在的结点）置为根结点；
至此，删除操作结束。
R树：删除操作：下溢示例2.png

参考

  1. 空间数据索引RTree（R树）完全解析及Java实现
  2. 从B树、B+树、B*树谈到R 树
  3. 什么是R树？
取自“http://wiki.eijux.com/index.php?title=树：R树&oldid=2660”