大型GIS空间数据库的有效索引结构QR_树

大型GIS空间数据库的有效索引结构QR_树

第28卷第3期2003年6月武汉大学学报 信息科学版

GeomaticsandInformationScienceofWuhanUniversityVol.28No.3June2003

文章编号:167128860(2003)0320306205文献标识码:A

Ξ

大型GIS空间数据库的有效索引结构QR2树

郭　菁　郭　薇　胡志勇

1

2

2

(1　武汉大学动力与机械学院,)(2　,号)

摘　要:在分析R2,GIS空间数据库的QR2树索引新方法。关键词:;　　空间数据一般可用多属性的一条记录来描

述。但传统的数据库系统不能有效地支持空间数据处理,因为:①空间数据的数据量大,结构和关系复杂;②空间目标不规则,目标之间的关系复杂(相交关系、相邻关系和包含关系),空间操作与计算比传统的关系运算代价高;③不能像传统数据库那样用某种命令对空间目标进行分类、排序。因此,空间数据处理必须采用特定的索引技术。

索引项或数据项个数(即该结点的“孩子”个数),

“水平”指示该结点在树中的层数(0表示叶结点)。插入一个空间目标,从R2树的根结点开始,找到使索引空间(MBR)的“面积”增量最小、增量相同情况下

“面积”最小的索引项,再对该索引项所对应的子树重复以上的查找操作直至叶结点。如果叶结点不“满”,则直接插入该目标,然后向上依次调整其父结点对应索引项的MBR,直至对根结点实施完调整操作;否则需对该叶结点进行分裂(切分)操作,产生一个新叶结点,然后插入到其父结点。如父结点又“满”,还需对其进行分裂操作。

如要查询所有与一指定区域相交的空间目标,则需从根结点开始,遍历所有MBR与查询区域相交的索引项所指的子树直至叶结点。如果叶结点数据项中的MBR与查询区域相交,则根据OI找到对应的空间目标,并计算其是否相交。

从树中删除一个空间目标,首先需找到存放该目标的叶结点,如果删除该目标后叶结点“下溢”,则需重新插入该叶结点中剩余的所有数据项,然后释放此叶结点的存储空间。同样,如果叶结点的删除导致其父结点的“下溢”,还需删除其父结点,然后插入剩余的所有索引项于树中的同一层。图1举例说明了R2树的结构。1.2　R2树的索引结构存在的问题

R2树的查找效率主要取决于R2树的深度及

1　R2树的空间索引结构分析

1.1　R2树的数据结构

R2树

[1]

是基于最小包围矩形MBR(最小的包

围矩形)的索引方法。它是B2树在多维空间的扩

展,是一种平衡的树结构(所有的叶结点出现在同一层上),且保证空间利用率至少在50%以上。其数据结构如下:

叶子结点:(数,水平,<OI,MBR>,<OI,MBR>,…,<OI,MBR>)

非叶结点:(数,水平,<CP,MBR>,<CP,MBR>,…,<CP,MBR>)

R2树的叶子结点存储了一组结构为(OI,MBR)的数据项,其中OI为空间目标标识,MBR为

该目标在k维空间中的最小包围矩形;非叶结点则存储了一组结构为(CP,MBR)的索引项,其中CP为指向子树根结点的指针,MBR代表其子树索引空间,为包围其子树根结点中所有索引项或数据项的MBR的最小包围矩形。“数”指示结点中用到的

Ξ收稿日期:2003203220

子树索引空间的重叠程度。R2树的深度越低,查找过程中访问的结点数就越少;子树索引空间的

项目来源:国家自然科学基金资助项目(60173045ΠF020204)。

第1页下一页