于 亮 苏 丹 黑龙江省黑河学院

R树下的空间数据库索引技术探讨

于 亮 苏 丹 黑龙江省黑河学院

近年来，随着计算机的广泛应用和信息处理技术的快速发展，地理信息系统（GIS）也得到了快速的发展，已经广泛应用于公共管理、科研等领域。空间数据库索引技术作为地理信息系统的核心内容，现已经成为空间数据库研究的热点。本文通过阐述空间数据库索引技术，分析了空间数据库索引的集中常见技术，以及探讨了其发展前景。

空间数据库；空间索引技术；地理信息系统；探讨；前景

由于传统的数据库在空间数据的存储、管理以及信息检索等方面都存在一定的缺陷，这就使得空间数据库的索引技术不断的发展，其索引技术越来越受到人们的重视。

引言

空间数据库是计算机物理存储介质用来存储空间数据的。对空间数据库的研究，是从上个世纪70年代的地图制图与遥控感知图像处理领域开始的，其目的是为了利用卫星资源快速的绘制出各种地图。传统的数据库为了提高信息检索效率，都会建立一系列的索引机制，索引机制无需查遍整个数据库，就可以快速访问某条特定查询的数据，例如B树。但这些都是一维索引，无法处理空间数据库中的二维、三维以及三维的空间技术。

空间数据库索引技术直接影响到空间数据库系统的成败。空间数据库索引技术的提出是由两个原因决定的：第一，计算机存储器分内存和外存两种，访问这两种存储器所花费的时间相差十万倍以上。并且在实际应用中，其空间数据都在存储在外存上，如果对外存内的空间数据的位置不加以索引，那么每查询一个数据就需要扫描整个外存上所存储的数据文件，这种数据查询的代价会严重影响系统的工作效率。因此，系统的设计者必须对磁盘上数据位置加以索引，只有通过对内存中的计算来取代对外存多余无效的访问，才能够提高系统的工作效率。第二，传统的数据库索引技术并不适用空间数据的多维空间，因为传统的数据库索引技术的数据类型都是在一个维度上，而空间数据库则具有多维空间，并且目前也并不存在从一维空间映射到高维空间。因此，传统的数据库索引技术并不能对空间数据库进行有效的索引，所以需要研究能够适用多维空间数据的索引方式。

1.常见的空间数据库索引技术

1.1 格网空间数据库索引

格网空间数据库索引就是将目标空间实体所在的空间范围划分成一系列相同大小的格。每一格都代表一个桶，用来记录该格内空间实体的编号。格网空间索引的查找方式非常简单，数据分布较均匀的话，那么查询的效率较高。但是需要注意的是，格网的大小会影响到索引表的大小，如果格网太小，索引就会膨胀，不但查询效率变低，而且对索引表的维护费用也会增加。

1.2 K-D树空间数据库索引

K-D树是早期用于索引多维空间数据的数据结构之一。 K-D树将每一层的空间都划分为两部分。 K-D树空间索引的原理是沿着树的根结点进行一维划分，依次划分下一层结点，尽量让左右子树中的结点数目均衡，如果结点中包含的点数小于叶子结点中包含的最大点数时要停止划分。另外， K-D树中的每条线都要与树中的结点相对应。采用K-D树空间索引需要注意的是，如果树型结构的递归层次越深，则查询的效率就越低。

1.3 R树空间数据库索引

R树空间数据库索引是在B树的基础上扩展了多维空间，是最早支持多维空间存取的方法之一。 R树作为一种高度平衡树，不但可以控制树的深度，而且也可以采用最小外包矩形来表示空间实体。 R树有三条特性，第一，叶节点中存储该结点对应的空间要素的最小外包矩形和空间要素标识；第二，最小外包矩形在二维空间中是矩形，而在三维中是长方体，以此类推到高维空间；第三， R树作为动态索引结构，可以同时进行删除、查询以及插入等行为，而且对树结构也不需要定期组织。不过，由于空间数据分布的不确定性，所以各层节点的最小外包矩形很容易重叠，导致在实际查询时会产生多个查询分支，在很大程度上降低了查询效率。

1.4 四叉树空间索引

四叉树空间索引的机制是基于相同网格而划分的，其工作空间是在X、 Y方向上进行的2N等分，从而形成2N×2N的固定网格，并以此建立N级四叉树。在四叉树中，空间要素的标识都记录在外包络矩形覆盖的每一个叶节点中。其在内存中的层次树状结构的查询效率较高。另外，层次型的树状结构并不适用直接描述数据库表，则可通过对四叉树的各层节点都编上码，从而反映四叉树的层次结构。

2.空间数据库索引技术的发展前景

随着数字城市、定位服务的提出和应用以及推广，空间数据库索引技术作为地理信息系统的核心，所以其也正朝着高维空间、基于空间关系等方面发展。基于三维GIS、多媒体数据库以及空间数据库对多维空间的探索以及更新效率的要求日益迫切，所以，有必要研究一种名可以扩展高维空间的索引技术，高位数据索引最关键的一项技术就是降维，在检索高维数据的同时，还能够有效的检索一维、二维的数据。向空间关系方面发展，则是由于当前的查询与分析操作都是基于目标间的空间关系，而空间数据库中的空间目标大多数都是不规则的几何形状，并且还存在着较为负责的空间关系，所以在基于空间目标的空间关系上，有必要建一个基于空间关系动态索引，这样不但可以有效地提高空间数据库的查询和分析的效率，而且还能够有效的扩展空间数据库系统的数据组织、分析以及维护等功能。

3.总结

空间数据库是随着地理信息系统的快速发展而兴起的新技术。由于地理环境较为复杂，以及海量空间数据的快速查询、检索以及空间分析计算都需要数据库进行管理，如果采用传统的关系数据库系统来管理空间数据，则查询效率较低，因此为了提高查询的效率，则选择采用空间数据库索引技术。

[1]赫玄惠.空间数据库索引技术的研究及应用[D].华北电力大学，2012.

[2]吴昊.空间数据库索引技术与应用研究[D].南京邮电大学，2013.

[3]宋明明.基于R-树的空间数据库索引技术研究与应用[D].江苏科技大学，2014.

[4]余登峰.基于R树的空间数据索引技术研究与实现[D].中国地质大学，2006.

[5]周帆.基于R-树的空间数据索引技术的研究与实现[D].哈尔滨理工大学，2009.

[6]陈敏.基于R-树空间索引的优化研究与应用[D].福州大学，2006.

[7]周长英，陈颖.空间数据库索引技术发展概况[J].黑龙江科技信息，2010，31∶84.

黑龙江省教育厅科学技术项目，项目名称：空间数据库索引技术研究，项目编号：12541573。