空间数据库索引技术.doc

PAGE PAGE 1 收稿日期：2008-04-10 基金项目：中国核工业地质局基金项目 空间数据库索引技术 文章已发表在我的个站: HYPERLINK （核工业北京地质研究院， 北京 100029） （anzienjoylife@） 摘要 空间数据库在多个学科中得到了广泛的应用，空间数据库索引技术是空间数据库应用中的一个核心问题。空间数据库索引技术通过对存储在介质上的数据位置信息的描述，从而提高空间数据库的数据获取效率。空间数据库索引技术是提高空间数据库查询性能的关键技术，直接影响到空间数据库系统的成败。本文阐述了目前主流的空间索引技术，包括基于二叉树的索引结构、基于B-树的索引技术和基于空间目标排序的格网技术，同时详细介绍了空间索引技术在Oracle和ESRI等商用数据库中的应用情况及其未来发展趋势。 关键词 空间数据库；空间数据库索引 空间数据库已应用于地质、地理学、遥感、城市规划、自然资源管理与网络计算等多个学科，它在解决一些具有巨大挑战性的科学问题上正发挥着越来越重要的作用。随着地理信息系统、计算机辅助设计与制造、数字地球及对地观测系统等应用领域的发展，对空间数据库的性能也提出了更高的要求。不但要求空间数据库能够高效地检索海量数据，而且要求其能够有效地存储与检索时空数据。 空间数据库索引技术通过对存储在介质上的数据位置信息的描述，从而提高空间数据库的数据获取效率。空间数据库索引技术是提高空间数据库查询性能的关键技术，直接影响到空间数据库系统的成败。因此针对空间数据库索引技术的研究越来越受到学术界的广泛关注，近些年来已发展为一门新兴学科，具有十分广阔的应用前景。 1. 空间数据库 传统的数据库系统主要针对一维的属性数据而设计，无法有效地表示、存储、管理和检索多维空间数据。与传统数据库相比，空间数据库涉及对大量多维空间目标的存储与操作，将数据从一维推向了二维、三维甚至更高维，其目的是为了提供高效的地理空间数据查询能力，同时能够进行有关地理空间数据的插入、删除、更新等操作，为此建立了如实体、关系、数据独立性、完整性、数据操作和空间分析等一系列基本概念。 空间数据库系统是一个通用的软件系统，管理空间数据的存储、检索，确保数据的一致性、完整性、安全性，并提供依据空间数据的位置和范围定位它们的工具。空间数据库是对传统数据库的扩展，它除了具有传统数据库的功能外，还提供对空间数据的描述、存储和检索。 空间数据库管理的对象主要是地理空间数据。地理空间数据分为两类：一类是和空间位置、空间关系有关的数据，称为空间数据；一类是地理元素中非空间的属性信息，称为属性数据。在空间数据库中，由于空间数据表达的是地理实体的空间位置及其所载荷的属性两方面的数据，所以空间数据库如何储存和管理这两种数据，将决定空间数据库的效率和空间分析及GIS应用。目前在地理信息系统中空间数据库大多数采用的是混合式数据库结构，并正向一体化数据库结构发展[1]。 因此，对空间数据的处理是一项时间和空间开销都很高的操作。为了有效地提高对空间数据的处理效率，尤其是针对空间位置的实时查询效率，空间数据库必须利用高效的索引机制。 PAGE 6 2. 空间数据库索引技术 数据库的索引机制可以用来快速访问某条特定查询所请求的数据，而无需遍历整个数据库。传统的关系数据库为了提高检索效率，一般都会建立一系列的索引机制，如B-树等，但这些都是一维索引，无法处理空间数据库中的二维和多维的空间数据。 空间数据库索引技术以及建立在此技术之上的空间数据查询及优化算法是提高空间数据处理效率的一个重要手段，是空间数据库中的一个重要组成部分。空间数据索引作为一种辅助性的空间数据结构，介于空间操作算法和地理对象之间，通过筛选、排除大量与特定空间操作无关的地理对象，缩小了空间数据的操作范围，从而提高空间操作的速度和效率。 近年来，对空间索引的研究引起了国内外许多学者的重视，空间索引的结构与方法相继提出并实现。图1展示了空间索引技术的研究进展情况。 图1 空间索引技术的进展 空间索引技术是特定的数据结构和算法，目前主流方法都是采用树索引结构，即基于二叉树的索引技术、基于B-树的索引技术和基于空间目标排序的格网技术。 2.1 基于二叉树的索引技术 在随机情况下，二叉树具有较好的查找效率，用于重复地划分数据空间，以达到缩减查找空间、提高空间查找性能的目的。基于二叉树的索引结构有Kd树、K-D-B树、LSD树等。二叉树是二分索引树结构，主要用于索引多维数据点，但对复杂的空间目标，如折线、多边形、多面体等的索引却必须采用近似法和空间映射技术，因此针对空间关系的查询效率较低。 2.2 基于B-树的索引技术 B-树及其变体作为一类平衡的多路查找树，被广泛应用于常规数据库管理系统中，事实证明其作为大型空间数