空间数据索引RTree（R树）完全解析及Java实现

• 第一部分 空间数据的背景介绍
  • 空间数据的建模
    • 基于实体的模型（基于对象）Entity-based models (or object based)
  • 常用的空间数据查询方式
  • 空间数据获取的方法
  • R树
    • 简介
    • R树的数据结构
    • 一个更具体的使用场景
    • 一棵R树满足如下的性质：
    • 结点的结构
  • R树的操作
    • 搜索
    • 插入
      • 插入操作存在的情况
  • • • 如何合理地分裂到两个组
    • 删除
      • 另一个例子再次理解删除
• 第二部分 R树的Java实现
  • UML

第一部分 空间数据的背景介绍

空间数据的建模

基于实体的模型（基于对象）Entity-based models (or object based)

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

常用的空间数据查询方式

• 窗口查询：给定一个查询窗口（通常是一个矩形），返回与查询窗口相重叠的物体。



点查询：给定一个点，返回包含这个点的所有几何图形。

空间数据获取的方法

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

  • 在二维的情况下，我们称之为最小限定矩形。MBR(minimum bounding retangle)
    

  • 三维的情况下，我们称最新限定箱MBB(minimum bounding box)
    

• 通过索引操作对象的MBB来进行查询一共分为两步

  • Filtering: 过滤掉MBB不相交的数据集，剩下的MBB被索引到的称为一个数据的超集。
    

  • Refinement: 测试实际的几何形状会不会满足查询条件，精确化。
    

  • 如何用数据表示一个MBR

    通常，我们只需要两个点就可限定一个矩形，也就是矩形某个对角线的两个点就可以决定一个唯一的矩形。通常我们使用（左下，右上两个点表示）或者使用右上左下，都是可以的。

     　　　　　　

　　　　表示一个点的数据：

　　　　public class Point{ //用一个类来表示一个点
　　　　    public Float x;
　　　　    public Float y
　　　　}

　　　　表示一个MBR的数据

 
　　　　public class MBR{
　　　　    public Point BottomLeft;
　　　　    public Point TopRight;
　　　　}

• 如何判断两个MBR是否相交？ >如果一个MBR的TopLeft或者BottomRight的（x，y）位于另一个MBR的xRange和yRangle里面，则说明这两个MBR相交。



R树

对于B/B+-Trees 由于它的线性特点，通常用来索引一维数据。（比它大的往一边走，比它小的往一边走，但只是在一个维度下进行比较）。
B树是一棵平衡树，它是把一维直线分为若干段线段，当我们查找满足某个要求的点的时候，只要去查找它所属的线段即可。这种思想其实就是先找一个大的空间，再逐步缩小所要查找的空间，最终在一个自己设定的最小不可分空间内找出满足要求的解。一个典型的B树查找如下：




要查找某一满足条件的点，先去找到满足条件的线段，然后遍历所在线段上的点，即可找到答案。B树是一种相对来说比较复杂的数据结构，尤其是在它的删除与插入操作过程中，因为它涉及到了叶子结点的分解与合并。

简介

B树是解决低纬度数据（通常一维，也就是一个数据维度上进行比较），R树很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想（如果B树在一维的线段进行分割，R树就是在二维甚至多维度的空间），并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。


我们说过，B树是采用切分线段来缩小数据查询范围的一种思想，我们又说了，R树是b树的多维版，以及R树也采用了B树的这一种分割的思想，那么，如果说线段的分割是一维的分割。那二维的分割就应该是区域的分割，而三维的就是几何空间的分割了。要注意的是R树并不只是二维空间数据的索引而已，它还可以索引三维甚至更高维。

一个三维的R树


此外R树还可以退化成一维，但是分割的线段存在重叠问题，效果不如Btree。


R树的数据结构

如上所述，R树是B树在高维空间的扩展，是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。

根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针（即缩小到某个区域下去进行查询，还是采用缩小范围的思想），查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。下图1是R树的一个简单实例：




解释一下这张图。

• 首先我们假设所有数据都是二维空间下的几何形状，图中仅仅标志了R8，R9，R10区域中的数据，其他的叶子节点仅仅用MBB表示。为了实现R树结构，我们用一个最小边界矩形恰好框住这个不规则区域，这样，我们就构造出了一个区域：R8。R8的特点很明显，就是正正好好框住所有在此区域中的数据。其他实线包围住的区域，如R9，R10，R11等都是同样的道理。这样一来，我们一共得到了12个最最基本的最小矩形。这些矩形都将被存储在子结点中。
• 下一步操作就是进行高一层次的处理。我们发现R8，R9，R10三个矩形距离最为靠近，因此就可以用一个更大的矩形R3恰好框住这3个矩形。
• 同样道理，R15，R16被R6恰好框住，R11，R12被R4恰好框住，等等。所有最基本的最小边界矩形被框入更大的矩形中之后，再次迭代，用更大的框去框住这些矩形。

用地图的例子来解释，就是所有的数据都是餐厅所对应的地点，先把相邻的餐厅划分到同一块区域，划分好所有餐厅之后，再把邻近的区域划分到更大的区域，划分完毕后再次进行更高层次的划分，直到划分到只剩下两个最大的区域为止。要查找的时候就方便了。

下面就可以把这些大大小小的矩形存入我们的R树中去了。根结点存放的是两个最大的矩形，这两个最大的矩形框住了所有的剩余的矩形，当然也就框住了所有的数据。下一层的结点存放了次大的矩形，这些矩形缩小了范围。每个叶子结点都是存放的最小的矩形，这些矩形中可能包含有n个数据。

以餐厅为例，假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办？

• 打开地图（也就是整个R树），先选择国内还是国外（也就是根结点）。
• 然后选择华南地区（对应第一层结点），选择广州市（对应第二层结点），
• 再选择天河区（对应第三层结点），
• 最后选择天河城所在的那个区域（对应叶子结点，存放有最小矩形），遍历所有在此区域内的结点，看是否满足我们的要求即可。

R树的查找规则跟查地图很像吧？对应下图：



一个更具体的使用场景

假设我们有一个地图路网要进行道路的快速索引，那么我们可以将每一条路的最小MBB作为R树的数据单元来进行构建R树。


每一条路使用一个最小MBB来进行包裹，使它成为R树的叶子结点（也就是那些数据结点）


（这里采用的是R树的改进版本R*树）然后对于建立起来的R树在进行查找道路的使用就可以使用我们那种“缩小范围”的查找思想。从上往下一层一层查找。


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

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

结点的结构

先来探究一下叶子结点的结构。叶子结点所保存的数据形式为：(I, tuple-identifier)。

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



Rectangle代表可以包裹E1,E2,E3,E4.E5的最小限度框。


R树的操作

搜索

R树的搜索操作很简单，跟B树上的搜索十分相似。它返回的结果是所有符合查找信息的记录条目。而输入是什么？输入不仅仅是一个范围了，它更可以看成是一个空间中的矩形。也就是说，我们输入的是一个搜索矩形。
先给出伪代码：

Function：Search
描述：假设T为一棵R树的根结点，查找所有搜索矩形S覆盖的记录条目。

• S1:[查找子树] 如果T是非叶子结点，如果T所对应的矩形与S有重合，那么检查所有T中存储的条目，对于所有这些条目，使用Search操作作用在每一个条目所指向的子树的根结点上（即T结点的孩子结点）。
• S2:[查找叶子结点] 如果T是叶子结点，如果T所对应的矩形与S有重合，那么直接检查S所指向的所有记录条目。返回符合条件的记录。

我们通过下图来理解这个Search操作。



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

插入

插入操作存在的情况

R树的插入操作也同B树的插入操作类似。当新的数据记录需要被添加入叶子结点时，若叶子结点溢出，那么我们需要对叶子结点进行分裂操作。显然，叶子结点的插入操作会比搜索操作要复杂。插入操作需要一些辅助方法才能够完成。
来看一下伪代码：

【Function：Insert】
描述：将新的记录条目E插入给定的R树中。

• I1：[为新记录找到合适插入的叶子结点]开始ChooseLeaf方法选择叶子结点L以放置记录E。
• I2：[添加新记录至叶子结点] 如果L有足够的空间来放置新的记录条目，则向L中添加E。如果没有足够的空间，则进行SplitNode方法以获得两个结点L与LL，这两个结点包含了所有原来叶子结点L中的条目与新条目E。
• I3：[将变换向上传递] 开始对结点L进行AdjustTree操作，如果进行了分裂操作，那么同时需要对LL进行AdjustTree操作。
• I4：[对树进行增高操作] 如果结点分裂，且该分裂向上传播导致了根结点的分裂，那么需要创建一个新的根结点，并且让它的两个孩子结点分别为原来那个根结点分裂后的两个结点。

 

【Function：ChooseLeaf】
描述：选择叶子结点以放置新条目E。
- CL1：[Initialize]设置N为根结点。
- CL2：[叶子结点的检查] 如果N为叶子结点，则直接返回N。
- CL3：[选择子树] 如果N不是叶子结点，则遍历N中的结点，找出添加E.I时扩张最小的结点，并把该结点定义为F。如果有多个这样的结点，那么选择面积最小的结点。
- CL4：[下降至叶子结点] 将N设为F，从CL2开始重复操作。

---

【Function：AdjustTree】
描述：叶子结点的改变向上传递至根结点以改变各个矩阵。在传递变换的过程中可能会产生结点的分裂。

• AT1：[初始化] 将N设为L。
• AT2：[检验是否完成] 如果N为根结点，则停止操作。
• AT3：[调整父结点条目的最小边界矩形] 设P为N的父节点，EN为指向在父节点P中指向N的条目。调整EN.I以保证所有在N中的矩形都被恰好包围。
• AT4：[向上传递结点分裂] 如果N有一个刚刚被分裂产生的结点NN，则创建一个指向NN的条目ENN。如果P有空间来存放ENN，则将ENN添加到P中。如果没有，则对P进行SplitNode操作以得到P和PP。
• AT5：[升高至下一级] 如果N等于L且发生了分裂，则把NN置为PP。从AT2开始重复操作。

有足够的空间插入的情况，由于插入的x所在的区域P2的数据条目仍然有足够的空间容纳条目x，且x的区域面积即MBR也位于区域P2之内，所以这种情况下，我们认为x拥有足够的插入空间。



需要增大MBR的插入情况，由于插入的y所在的区域P2的数据条目仍然有足够的空间容纳条目y，但是y的区域面积即MBR并不完全位于P2的区域之内，因此我们在插入数据y后会导致P2区域的相应扩大。



需要进行分裂的插入情况，由于插入的w所在的区域P1的数据条目已经没有足够的空间容纳条目w，因为假设我们定义R树的阶m=4，而区域P1已经容纳了四个条目「A，B，C，K」了，插入w后孩子数为5，以及超过m=4了，所以要进行分类操作，来保证树的平衡性。



采用分裂算法（下面会进行介绍）对结点（或者说区域）P2进行合理地分裂。使其分裂成P1（包含A，B）和P5（包含k，w）两个结点。并且需要向上传递这种分裂。由于分裂之后原来根结点「P1，P2，P3，P4」变成了「P1，P2，P3，P，P5」，因此根结点的孩子数由4变成5，超过了阶数m=4.所以根结点要（采用我们的分裂算法）进行分裂，分裂成Q1（包含P1，P5，P2）和Q2（包含P3，P4）两个结点，由于此时分裂已经传递到根结点，所以生成新的根结点记录Q1，Q2。



如何合理地分裂到两个组



挑选种子有多个方法，这里Quadratic（二次方）方案，对于所有条目中的每一对E1和E2，计算可以包裹着E1，E2的最小限定框J=MBR(E1, E2) ，然后计算增量d= J-E1-E2.计算结束后选择d最大的一对（即增量最大）。（这里为什么要这样呢：之所以要挑选d最大的一对，是因为如果d较大，说明挑选出来的两对条目基于对角线离得比较远，这样的好处就是分裂后的两个分组可以尽量不重叠）





挑选出seed1和seed2之后，就将剩下的要分配的分裂条目分个这两个seed使它们各称为一个组。而这个分配的原则就是离谁比较“近”就和谁一组。这里的“近”指的是任何一个条目MBB–E和seed1，seed2分别计算可以包裹着E和seed1的最小限定框J1=MBR(E，seed1)， 可以包裹着E和seed2的最小限定框J2=MBR(E，seed2)。再分别计算增量d1=J1-E-seed1，d2=J2-E-seed2。d1，d2哪个小就说明哪个“近”。



（-_-）!!!所以分裂的具体情况还是很复杂的，真想不懂这些大神怎么会想得到这些。除了上述Quadratic的分裂算法之外还有其他的分裂算法，如下图中间图，但是分裂的效果都不如R*树（R树的改进版）的算法好。




删除

R树的删除操作与B树的删除操作会有所不同，不过同B树一样，会涉及到压缩等操作。相信读者看完以下的伪代码之后会有所体会。R树的删除同样是比较复杂的，需要用到一些辅助函数来完成整个操作。
伪代码如下：

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

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

【Function：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树删除记录过程中的CondenseTree操作是不同于B树的。我们知道，B树删除过程中，如果出现结点的记录数少于半满（即下溢）的情况，则直接把这些记录与其他叶子的记录“融合”，也就是说两个相邻结点合并。然而R树却是直接重新插入。
具体的例子



假设结点最大条目数为4，最小条目数为2。在这张图中，我们的目标是删除记录c。首先使用FindLeaf操作找到c所处在的叶子结点的位置——R11。当c从R11删除时，R11就只有一条记录了，少于最小条目数2，出现下溢，此时要调用CondenseTree操作。这样，c被删除，R11剩余的条目——指向记录d的指针——被插入链表Q。然后向更高一层的结点进行此操作。这样R12会被插入链表中。原理是一样的，在这里就不再赘述。


有一点需要解释的是，我们发现这个删除操作向上传递之后，根结点的条目R1也被插入了Q中，这样根结点只剩下了R2。别着急，重新插入操作会有效的解决这个问题。我们插入R3，R12，d至它原来所处的层。这样，我们发现根结点只有一个条目了，此时根据Inert中的操作，我们把这个根结点删除，它的孩子结点，即R5，R6，R7，R3所在的结点被置为根结点。至此，删除操作结束。

另一个例子再次理解删除





















第二部分 R树的Java实现

UML



Point

package rtree;

/**
 * @ClassName Point
 * @Description n维空间中的点，所有的维度被存储在一个float数组中
 */
public class Point implements Cloneable {
    private float[] data;

    public Point(float[] data) {
        if (data == null) {
            throw new IllegalArgumentException("Coordinates cannot be null."); // ★坐标不能为空
        }
        if (data.length < 2) {
            throw new IllegalArgumentException("Point dimension should be greater than 1."); // ★点的维度必须大于1
        }

        this.data = new float[data.length];
        System.arraycopy(data, 0, this.data, 0, data.length); // 复制数组
    }

    public Point(int[] data) {
        if (data == null) {
            throw new IllegalArgumentException("Coordinates cannot be null."); // ★坐标不能为空
        }
        if (data.length < 2) {
            throw new IllegalArgumentException("Point dimension should be greater than 1."); // ★点的维度必须大于1
        }

        this.data = new float[data.length];
        for (int i = 0; i < data.length; i++) {
            this.data[i] = data[i]; // 复制数组
        }
    }

    @Override // 重写clone接口
    protected Object clone() {
        float[] copy = new float[data.length];
        System.arraycopy(data, 0, copy, 0, data.length);
        return new Point(copy);
    }

    @Override // 重写tostring（）方法
    public String toString() {
        StringBuffer sBuffer = new StringBuffer("(");

        for (int i = 0; i < data.length - 1; i++) {
            sBuffer.append(data[i]).append(",");
        }

        sBuffer.append(data[data.length - 1]).append(")"); // 最后一位数据后面不再添加逗号，追加放在循环外面

        return sBuffer.toString();
    }

    /*
     * ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ ★ 测试 ★
     * ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
     */
    public static void main(String[] args) {
        float[] test = { 1.2f, 2f, 34f };
        Point point1 = new Point(test);
        System.out.println(point1);

        int[] test2 = { 1, 2, 3, 4 };
        point1 = new Point(test2);
        System.out.println(point1);

        int[] test3 = { 11, 22 }; // 二维的点
        point1 = new Point(test3);
        System.out.println(point1);
    }

    /**
     * @return 返回Point的维度
     */
    public int getDimension() {
        return data.length;
    }

    /**
     * @param index
     * @return 返回Point坐标第i位的float值
     */
    public float getFloatCoordinate(int index) {
        return data[index];
    }

    /**
     * @param index
     * @return 返回Point坐标第i位的int值
     */
    public int getIntCoordinate(int index) {
        return (int) data[index];
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Point) // 如果obj是point的实例
        {
            Point point = (Point) obj;

            if (point.getDimension() != getDimension()) // 维度相同的点才能比较
                throw new IllegalArgumentException("Points must be of equal dimensions to be compared.");

            for (int i = 0; i < getDimension(); i++) {
                if (getFloatCoordinate(i) != point.getFloatCoordinate(i))
                    return false;
            }
        }

        if (!(obj instanceof Point))
            return false;

        return true;
    }
}

Rectangle

package rtree;

/**
 * 外包矩形
 * 
 * @ClassName Rectangle
 * @Description
 */
public class Rectangle implements Cloneable // 继承克隆接口
{
    private Point low; // 左下角的点
    private Point high; // 右上角的点

    public Rectangle(Point p1, Point p2) // 初始化时，第一个参数为左下角，第二个参数为右上角
    {
        if (p1 == null || p2 == null) // 点对象不能为空
        {
            throw new IllegalArgumentException("Points cannot be null.");
        }
        if (p1.getDimension() != p2.getDimension()) // 点的维度应该相等
        {
            throw new IllegalArgumentException("Points must be of same dimension.");
        }
        // 先左下角后右上角
        for (int i = 0; i < p1.getDimension(); i++) {
            if (p1.getFloatCoordinate(i) > p2.getFloatCoordinate(i)) {
                throw new IllegalArgu