空间数据多级索引结构的算法实现和分析

《空间数据多级索引结构的算法实现和分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《空间数据组织与分析》结课论文题目：多级空间索引算法分析学院：研究生学院专业：大地测量学与测量工程班级：硕研12级3班姓名：张鼎凯学号：2012020344日期：2012年12月05日摘要：空间数据库的索引是提高空间数据库存储效率和空间检索性能的关键技术。介绍了空间数据库中建立索引的常用技术，给出了一种多级空间索引，详细讨论了该索引的建立算法以及应用该索引的检索算法，并进行了算法分析。关键词：计算机软件；间数据库；空间索引；空间检索；算法分析1空间索引技术简介空间索引是指依据空间对象的位置和形状或空

2、间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间数据一般是是多维的，在此主要介绍二维空间数据的索引。近年来，国外学者提出应用空间基数分区对空间数据进行管理，已得出了几种空间数据索引结构。例如Robinson提出的K-D-B树[2]，Guttman提出R树结构[

3、3]，Freeston提出的BANG文件[4]，Beckmann提出的R*树结构[5]等。国内则学者提出了QR-树[6]，网格索引[7][8]等索引结构，并进行了有关索引结构的性能分析和查询优化研究[8][9]。众多的索引结构可以说各有优缺点。总的来说，可分为以四叉树为代表的网格文件结构和以R树及其变种为代表的动态索引技术。1.1四叉树结构　四叉树索引是栅格文件索引技术的代表。栅格文件索引技术的基本思想是将一张地图规则地划分成多个互不相交的栅格，且要求所有栅格覆盖全地图，然后再利用栅格对地图上的空间

4、对象进行索引。如K-D树、K-D-B树、四叉树、八叉树等均基于此思想。我们在此主要介绍一下四叉树空间索引技术。四叉树空间索引是将一张地图逐步四等分，且依次编号，如图1（a）所示，其层次由用户依需要而定。划分的结果可生成如图1（b）的四叉树结构。从此结构中可确定被索引类中每个对象实例的被索引属性值属于那一个最小范围块，并将其ID加到该最小范围块所带的链表中。查询时根据用户关心的区域，选中区域所在最小范围块中的对象。四叉树的查询在最坏情况下效率较低，而且四叉树的动态性较差。建立索引后，如果又扩大地图范围

5、增加新对象时，必须重新建立四叉树索引，因而缺乏灵活性。图1四叉树结构Fig.1thestructureofquarteredtree1.2R树结构　R树是在B树的基础上通过对空间数据递推分区，并以分区后的区域作为关词建立起的一种层次结构。它不对地图预先划分，可随着地图中空间对象的增加而使原有的范围块分裂，具有B树的动态平衡性。其中叶结点包含指向数据库中实际几何物体的指针，所有叶结点都在同一层上，且可以实现多维索引。非叶结点完全包含了子结点的区域。图2（a）表示了地图上的两个范围A、B（用虚线框起），

6、相互有覆盖。图2（b）是与之对应的一个4阶R树结构。当空间对象加入B范围时，R树会相应分裂。同样，当删除空间对象时，会引起R图2R树结构Fig.2thestuctureofR-Tree树结点的合并。R树结构的主要优点在于空间利用率高，每个空间对象在树中只表示一次。R树的查询效率较高，但分区可能产生重叠。在R树结构中频繁插入或删除对象时，由于要动态地保持树的平衡，可能会产生震荡而降低效率。2多级空间索引的基本结构多级空间索引实质上仍属于网格索引结构[7][8]，其基本思想是将整个空间纵横分成若干个均等

7、的小块，每个小块都作为一个桶，将落在该小块内的实体对象的标识号放入该小块对应的桶中。为适应精度要求，小块还可以再细分，直到不可分为止。设将空间分成m*n个小块，左下角为坐标原点，则每个小块可表示为Block[i,j]，0≤i

8、方法引入了点索引、线索引和面索引。假设桶Buck[i]中存放的实体集合为Set_Buck[i],其中0≤i