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

}