Geomatics Square
NO.6 2011 (Total 113)
科技交流
基于空间数据库的几种常用空间索引技术研究
白航
（广东省国土资源测绘院，广州510500）
摘要:空间数据库是地理信息系统(GIS)的基础和核心，空间索引技术通过对存储介质上数据位置信息的描述来提高数据查询、检索及获取效率；其好坏直接影响空间数据库系统的可用性和可扩展性。
本文介绍了几种常见的空间数据库索引技术：简单格网空间索引、K-D 树空间索引、R 树空间索引、四叉树空间索引等；系统总结了空间数据库索引技术的研究进展，探讨了其发展前景和存在问题。
关键词:空间数据库；空间索引；GIS
1.引言
空间数据库技术是随着GIS (地理信息系统)的发展而兴起的一门新技术，复杂的地理环境和海量、多维、结构复杂的空间数据导致了基于空间数据库查询、检索及空间计算的开销一般要比关系数据库大的多，特别是查询语句中条件谓词包含一些对空间数据操作或连接的一些函数，这些函数的计算开销远比数值计算或字符串比较等要大。
若使用传统的关系型数据库管理系统(DBMS)来管理空间数据，其存在固有缺陷，用顺序扫描的方法查询的效率非常低。
因此为了提高查询效率，采用空间索引技术十分必要。
2.空间数据库索引技术
空间数据用来表示空间物体的位置、形状、大小和分布特征等方面信息，适用于描述二维、三维或多维分布的区域现象。
空间数据库是计算机物理存储介质上存储的地理空间数据的总和。
数据库的索引机制可以用来快速访问某条特定查询所请求的数据，而无需遍历整个数据库。
传统的关系数据库为了提高检索效率，一般都会建立一系列的索引机制，如B 树等，但这些都是一维索引，无法处理空间数据库中的二维和多维的
空间数据。
空间数据库索引技术是通过对存储在介质上的数据位置信息的描述，来提高空间数据库的查询性能和数据获取效率，索引技术的好坏直接影响到空间数据库系统的成败。
空间数据索引作为一种辅助性的空间数据结构，介于空间操作算法和地理对象之间，通过筛选、排除大量与特定空间操作无关的地理对象，缩小了空间数据的操作范围，从而提高空间操作的速度和效率。
3.几种常见的空间索引技术
3.1简单格网空间索引
格网空间索引的原理简单，即把目标空间实体集合所在的空间范围划分成一系列大小相同的格。
如图3-1所示，每一个格相当于一个桶（bucket ），记录落入该格内的空间实体的编号。
基于格网索引的查找思路也较简单，在数据分布较均匀的情况下，查询效率较高。
但格网的大小直接影响了索引表的大小，格网太小，索引表会急剧膨胀，维护索引表本身的花费增加，查询效率随之下降；反之，落在一个格内的空间实体可能会过多；因此格的大小严重制约着查询效率的提高。
8
Geomatics Square
NO.6 2011 (Total 113)
图4
四叉树结构的空间索引
科技交流
3.2 K-D 树空间索引
K-D 树是早期用于索引多维空间数据的数据结构之一。
K-D 树的每层都把空间划分为两个部分，沿着树的根结点进行一维划分；依次划分下一层结点，尽量保证左右子树中的结点数目均衡，当结点中包含的点数少于叶子结点中包含的最大点数时停止划分。
下图显示了用K-D 树索引来表示一个二维点集。
每条线对应树中的一个结点，叶子结点中包含的最大点数阈值设置为1，线号表示对应结点出现在树中的层数。
为了平衡K-D 树的深度，可结合B 树来得到K-D-B 树索引结构，但此类索引树对于占据一定空间范围的空间实体而言（如线和多边形），构造空间索引仍然不方便。
因为当使用数据库表构造K-D 树的索引表时，树型结构的递归层次深，导致查询效率降低。
3.3 R 树空间索引
R 树是B 树在多维空间上的自然扩展，是由Guttman 提出的最早支持多维空间存取的方法之一。
R 树是一种高度平衡树，可控制树的深度，采用对象的最小外包矩形（MBR ）来近似表示空间实体。
R 树有如下几条特性：(1)叶结点中存储该结点对应的空间要素的
MBR 和空间要素标识；(2) MBR 二维上是矩形，三维上是长方体，以此类推到高维空间；(3) 非叶结点存放其子女结点集合的整体外包络矩形和指向其子女结点的指针。
R 树是一种动态索引结构，其查询、插入、删除可同时进行，而且不需要定期的对树结构重新组织。
R 树适合于多维空间查询，不过由于空间数据分布的偶然
性，使得各层节点MBR 容易重叠，导致实际执行空间查询时，会产生多个查询分支，很大程度上降低了空间查询的效率。
在最坏的情形下，一个空间查询会退化成线性搜索。
若使用外部数据库来描述R 树，在缺乏特定的快速物理数据块访问接口情况下，效率也会大打折扣。
3.4 四叉树空间索引
在基于固定网格划分的四叉树空间索引机制中，
工作空间在X 、Y 方向上进行2N 等分，形成2N×2N 的网格，并以此建立N 级四叉树。
在四叉树中，空间要素
标识记录在其外包络矩形所覆盖的每一个叶结点中。
但当同一父亲的四个兄弟结点都要记录该空间要素标识时，则只将该空间要素标识记录在该父亲结点上，并按这一规则向上层推进（如图4）。
层次型的树状结构并不适合使用数据库表来直接描述，可通过对四叉树的各层节点进行编码，来反映四叉树的层次结构。
四叉树索引在内存中的层次型树状结构，其查询效率较高。
图1
简单格网索引
图2 用K-D
树表示一个二维空间中的点集
图3 空间实体分布与R
树索引构造图
9
Geomatics Square
NO.6 2011 (Total 113)
科技交流
4.空间数据库索引技术的发展
随着数字城市、定位服务、网络服务等应用的普及和推广，空间索引技术作为空间数据库的核心内容正朝着高维、网络化、基于空间关系等方面发展。
4.1 高维空间索引
三维GIS 、多媒体数据库和时空数据库等对多维空间目标的搜索与更新效率的要求日益迫切，有必要研究一种可扩展的高维索引技术，能同时高效地检索一维、二维或高维的空间数据。
高维数据索引的一项关键技术是降维，在降维后的子空间里运用一维或者二维空间索引技术。
降维的方法有空间填充曲线、奇异值分解、距离映射算法等。
4.2 基于空间关系的动态索引
空间数据库中的空间目标大多是不规则几何形状的，且存在着复杂的空间关系（如目标A 与B 相邻近，目标A 位于目标B 的西南方等），许多查询与分析操作都是基于目标间的空间关系。
当前空间索引技术的劣势在于基于空间目标的位置信息建立索引结构，来提高空间数据库系统中的区域查询效率，难以根据目标间的空间关系建立有效的索引机制。
若能根据空间目标间的空间关系（如邻近关系、方向关系等）动态地建立索引，这必将极大地提高空间查询和空间分析效率，从而有效地扩展空间数据库系统的数据组织、数据分析和数据维护功能。
4.3 基于Web 的空间索引
基于Web 的空间数据库为信息的高度共享提供了可能，改变了传统数据信息传输、发布、共享及应用的过程和方式，是空间信息系统发展的必然趋势。
基于Web 的空间数据库还有许多关键问题尚未突破，如何基于分布式体系结构实现快速、高效的空间信息检索，并提供数据传输和显示机制将成为研究热点。
4.4 空间数据仓库索引
面向事务处理的空间数据库已满足不了现实需求，空间数据仓库从管理转向决策处理，能够满足新的
空间信息集成方案。
空间数据仓库通过专业模型对不同源数据库中的原始业务数据进行主题抽取和聚集，从而为用户提供一个综合的、面向分析的决策支持环境。
这一过程需要一套高效的数据索引技术作为保证，因此，空间数据仓库的索引技术必将得到不断地完善与发展。
5.结束语
GIS 在数字城市、计算机视觉、人工智能等领域中应用不断深入，空间数据库容量将达到TB 、PB 级，空间数据库索引技术和查询优化算法是提高空间数据处理效率的一个重要手段，是空间数据库中的一个重要组成部分。
针对空间数据本身的特点及检索查询特征，国内外的学者已开发出许多空间索引技术，但仍处于初级阶段，需不断改进，如高效索引树算法和复杂空间查询方法的优化、查询操作中集合过滤方法、动态索引结构的建立等。
参考文献
[1] 郭际元,周顺平,刘修国.空间数据库[M].中国地质大学(武汉),2005.
[2] 邱建华.空间数据可索引技术研究[D].武汉大学, 2004.[3] 何雄.空间数据库引擎关键技术研究[D].中国科学院研究生院(计算机技术研究所),2005.
[4] 文强.空间数据库引擎关键技术研究[D].电子科技大学,2007.
[5] 郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海交通大学出版社,2006.
[6] 郭龙江,李建中.空间数据库的索引技术[J].黑龙江大学自然科学学报,2005,03.
[7] 李杨.基于最小边界圆和最小包围扇形的空间索引方法[D].哈尔滨理工大学,2009.
[8] 滕连泽,刘洪斌,武伟.基于空间数据不同索引方法的比较[J].计算机与现代化,2006,01.
[9] 何珍文,郑祖芳,刘刚,吴冲龙.动态广义表空间索引方法[J].地理与地理信息科学,2011,05.
10。
