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)。
}