麻辣GIS微信平台

更多 GIS 干货

微信关注不错过

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树结构

相关阅读

麻辣GIS-Sailor

作者:

GIS爱好者,学GIS,更爱玩GIS。

声明

1.本文所分享的所有需要用户下载使用的内容(包括但不限于软件、数据、图片)来自于网络或者麻辣GIS粉丝自行分享,版权归该下载资源的合法拥有者所有,如有侵权请第一时间联系本站删除。

2.下载内容仅限个人学习使用,请切勿用作商用等其他用途,否则后果自负。

手机阅读
公众号关注
知识星球
手机阅读
麻辣GIS微信公众号关注
最新GIS干货
关注麻辣GIS知识星球
私享圈子

留言板(小编看到第一时间回复)