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

       R+树索引的主要特征是在R+树中兄弟节点对应的空间区域没有重叠，这样划分空间可以使空间搜索的效率提高。R+树也是R树的一个变种，在R+树中，兄弟节点对应的空间区域没有重叠，这样划分空间可以使空间搜索的效率提高。R+树对空间的划分及其索引对象的MBR组织如下：

       R+树查找

       算法Search(R,W)/R：R+树的根结点,W：查找矩形窗口/

S1.[查找中间结点]

If R是非叶结点 then

  For R的每一索引项(p,MBR) DO

      If MBRW then Search(p,WMBR)

S2.[查找叶子结点]

If R是叶子结点 then

  检查R的每一数据项(OI,MBR)

  RETURN所有与W相交的数据矩形

       由查找算法可知,与R树相比,对于区域查找,查找路径应该可以减少,但依旧可能有多条;对于点查找,则可以通过一条路径得到查找结果。

       R+树插入

Algorithm Insert(R,IR){

/*R为R+树的根结点,IR为要插入的数据矩形*/

    I1.[查找中间结点]

    if (R是非叶结点) then

        for (p,MBR) do

          if (MBRIR0) Insert(CHILD,IR);

    I2.[查找叶子结点]

    if (R是叶结点) then

      if (R已有M个数据项)then SplitNode(R);

      else 插入IR于R;

}

       R+树删除

Algorithm Delete (R,IR){

/*R为R+树的根结点,IR为要删除的数据矩形*/

Dl.[查找中间结点]

if (R是非叶结点)then

  for R的每一索引项(p,MBR)do

    if (MBRIR0) then Delete(CHILD,IR);

D2.[查找叶子结点]

if (R是叶结点) then

  从R中删除IR且调整R的父结点中对应的目录矩形;

}

      结点分裂

Algorithm SplitNode(R){

SN1[寻找一个划分]

调用Partition;

// 设(p,MBR)为与R相关联的索引项,S1与S2表示划分得到的两个子区域,

// 创建两个新结点n1=(p1,MBR1)与n2=(p2,MBR2),MBRi=MBRSi,i=1,2;〗

SN2[填充新结点]

For (R的每一项(pk,MBRk) do

  if (MBRkMBR==MBRk) then // MBR k完全包含于MBRi

      put(pk,MBRk) in ni;

  else // MBR k与MBR1及MBR2都重叠。

      if (R是叶结点) then

        put (pk,MBRk) in n1 与n2;

      else

        〖用划分线继续分裂(pk,MBRk)所指结点,设得到的新结点为：nk1=

      (pk1,MBRk1),nk2=(pk2,MBRk2),MBRki完全包含于MBRi,将 

          nki加入到ni,i=I,2;〗

SN3[向上传播结点分裂操作]

if (R是根结点)

    创建一新根结点,n1与n2为其两孩子结点;

else

  // 在R的父结点PR中,用n1与n2替换R。

  // 如果PR的索引项个数超过M,那么调用SplitNode(PR)。

}