GIS空间数据库（16）R树索引

R树索引是一种高效的空间索引，它是B树在多维空间的扩展，也是平衡树。R树的结构类似于B+树的平衡树。

R树及其特点

对于一棵M阶的R树，R树中每个非叶子结点都由若干个(p，MBR)数据对组成。MBR(Minimal Boundary Rect)为包含其对应孩子的最小边界矩形。这个最小外接矩形是个广义上的概念，二维上是矩形，三维空间上就是长方体MBV(Minimum Bounding Volume)，以此类推到高维空间。p是指向其对应该子结点的指针。

叶子结点则是由若干个(OI，MBR)组成，其中MBR为包含对应的空间对象的最小外接矩形。OI是空间对象的标号，通过该标号可以得到对应空间对象的详细的信息。

R树查找

伪代码如下：

Algorithm R_Search(N,W) {
    /*在根结点为N的R树中查找所有与W相交的数据矩形*/

    if (N.LEVEL==0) //N是叶子结点
        //  Return all data rectangles that intersect with W；
    else //N不是叶子结点
        for (i=1;i<N.COUNT;i++)
            if (N.MBRi;Intersect with W)
              R_Search (N.pi,W);
}

R树插入

伪代码如下：

Algorithm R_Insert(N,P){
/*向根结点为N的R树中插入数据矩形P*/
  if (N.LEVEL==0) {
        Insert P into N;
        if (N overfill) Split N;
    }
  else {//N是中间结点
      // Choose the entry in N whose rectangle needs 
      // least area enlargement to include the new data rectangle.
      // Resolve ties by choosing the entry with the rectangle of
      // smallest area (Let's suppose it's entry is the answer)
      R_Insert(N.pi,P);
      // Adjust N.MBRi to enclose all rectangle in its child node；
    }
}

R树删除

伪代码如下：

Algorithm R_Delete(N,P){
/*从根结点为N的R树中删除数据矩形P*/
  if (N：LEVEL==0) 
  {//N是叶结点
      if (N包含P)
      {
          // 从N中删除P
          N.COUNT=N.COUNT-1;
          return true;
      }
      else
          return false;
  }
  else
  {
      for (i =1;i<N.COUNT;i++)
          if (N.MBRi intersects with P)
            if (R_Delete(N.pi,P))
                if (N.pi,COUNT=m)
                    // Adjust N.MBRi to enclose all child's rectangles；
                else
                {
                    // Reinsert all remain entries of N.pi and delete N.pi；
                    // if N underfilled， Reinsert alI         
                    // remain entries of it and
                    // delete it too...；〗
                }
  }
}

地图对应的R树结构