基于多级混合空间索引的境界数据组织模型

刘静祯等

[摘要]境界样图数据是境界审核的重要依据，在自动化的境界审核系统中，高效管理和检索境界样图数据是系统的关键。本文通过分析境界样图数据的特点，综合比对目前成熟的数据索引方式，提出了基于多级混合空间索引的境界样图数据组织模型，阐明了索引建立的基本原理和实现机制，为境界样图在计算机中的储存管理提供了有效支撑。

[关键词] 境界审核 境界样图数据 混合空间索引

Abstract： Boundary sample data is the important basis of state audit， in the state of automated audit system， efficient management and retrieval state image data is the key to the system. In this paper， through analyzing the characteristics of the boundary sample plot data， comprehensive than the mature data index method， is proposed based on the state of multistage hybrid spatial index sample figure data organization model， and illustrates the indexes to establish the basic principle and implement mechanism， for the boundary sample in figure in a computer store management provides effective support.

Key words： Boundary audit Boundary hybrid spatial index sample figure data

1 引言

境界是一个国家与相邻国家之间领土权属的分界线[1]。境界通常使用地图、文字等多种形式加以表达，其中地图是表示境界的最常用、最主要的形式。境界表示错误或处理不当会造成行政管辖区域权责不清，产生相关行政区域之间不必要的纠纷，其准确性和合法性尤为重要。因此，地图出版前对涉及境界的地图内容进行严格的质量检查和审核就成为一项必不可少的重要环节[2]。为了提高境界审核的精度和效率，降低境界审核的劳动强度，目前许多单位都在研制自动化的境界审核系统，但在较大地理范围的境界审核系统中，如何高效管理和快速检索作为审核依据的境界样图数据是系统实现的一个重要难点，本文针对境界数据的特点提出了计算机系统管理下的境界样图数据管理模型。

2 境界数据的特点

在大范围的境界审核系统中，境界样图数据有以下几个特点。首先，在实际的境界数据管理中，不仅涉及到大量的系列比例尺（1：400万、1：100万、1：25万和1：5万）境界样图数据，很多情况下还会遇到许多非系列比例尺地图（如1：75万）的境界，因此，系统不仅要建立系列比例尺的境界样图数据库，还应根据实际业务需求派生出各种非系列比例尺的境界样图数据库，这就导致标准样图库所要管理的地图比例尺种类众多，地图数量巨大。第二，标准国界样图所涉及的数据格式也非常复杂，包括栅格、矢量和PDF等三中格式的地图数据，以1：5万地形图为例，一幅5万地形图PDF出版原图的数据量（仅底图显示数据）就达到40M左右，境界样图数据图所管理的数据量也非常巨大[3]。第三，境界样图数据在分幅时是沿国界呈带条状分布，与传统的矩形分幅方式有很大不同。因此，如何对要素类型多样、内容繁杂海量境界样图数据进行有效组织管理等问题成为境界审核系统实现的瓶颈。

3 境界数据的多级混合空间索引模型

3.1混合空间索引模型的提出

本文针对境界数据的特点，在目前成熟可靠的数据索引模型基础上，提出了基于多级网格和R树的一种多级混合索引方案，该索引的基本思想首先将地理空间通过多级粗网格划分建立多级索引，然后再将每个不可再分的网格建立R树索引。此种索引结构不仅能有效降低数据冗余，减少重叠节点，在数据的动态维护上算法性能也要优于R树索引模型。

境界查询应用分为精确查询和非精确查询两种。对于精确查询的方式，为了达到精确查询的要求，须要将地理空间的网格划分的足够小，当网格过多时极大地降低数据的检索查询效率[4]。因此，为了在不影响效率的情況下满足精确查询的要求，需要对境界采用多级网格划分的策略。

首先将整个地理空间划分为M1行N1列的第一级网格块。每个一级网格块还可进行第二级的划分，每个块都可划分为任意列和行的下一级块。每个块根据实际需求确定是否进行下一级划分。采用动态链表储存该结构，应用指针指向下一级的网格划分。当块不能再进行划分时则表示该块的多级网格索引建立完毕，最后为最低一级的网格块建立R树索引，从而建立起混合索引[5]。

索引机制首先将整个空间进行一级划分，可以按网格块的划分方式将空间分为多个一级索引块。对于没有包括任何地理目标或地理目标一部分的索引块，则不需要对此索引块进行二级划分；只是完整的包含一个地理目标的索引块，只需在此类索引块中建立以其唯一地理目标为根结点的R树索引；包含有多个地理目标的索引块，如果对此索引块直接建立R树索引，则此索引会包含数量过多的结点，因此需要对这类索引块进行二级格网划分[6]。为使每个地理目标尽可能被一个索引块完整的包含，根据地理目标的分布情况，对索引块有针对性地进行二级划分。在二级网格里，根据每个地理目标所跨的索引块树来建立R树索引，R树中的节点对象数量等于地理目标所跨的索引块数。

3.2 境界数据的混合空间索引模型建立

从全国范围看，境界数据主要是为显示境界线及其周围50公里范围的地理要素上的内容，在分幅上以经纬线为轮廓线自由分幅，在空间分布上呈现出沿国界线走向的带状分布形态。本课题中组织上分为纵向和横向两种模型，纵向模型主要是指多个比例尺的境界数据的嵌套集成，例如一幅1：100万的境界样图下涵盖多幅1：25万图幅。横向模型是指同一比例尺下的境界审核样图沿国界线走向呈基本的带状分布排列。

鉴于境界样图数据的以上特点，系统在对样图划分网格时遵循以下原则：①以系列比例尺为等级进行逐级划分；②同一比例尺下以图幅为基本单元，用图幅所在经纬线划分网格。③在逐级划分时，若下一级的网格完全不包括国界线两侧50公里范围内的地理要素，则将此网格舍去，不进行索引。通过以上方式划分网格后，不但能够使系统在进行不同比例尺境界样图的切换显示时的快速索引，满足用户从宏观到微观的不同详细程度调阅查看需求，还将与境界审核需求无关的多余数据舍去，减少了对样图数据的索引量，提高了数据索引的效率。系统的网格划分原理如图1。

当屏幕获得用户的查询范围后，系统根据网格索引文件中的经纬度坐标范围来判断需要调用的图幅。另外，由于许多国界要素范围跨度较大，若在各图幅内接着以网格划分的形式来索引，不但索引量巨大，而且许多目标会被重复索引，造成系统性能的浪费，因此在每幅图内对重要的境界要素建立R树索引，便于用户快速准确的在各比例尺的图幅中对该要素进行查询，组织模型如图2。

4 结论

通过多级混合空间索引储存管理境界样图数据，不仅能有效的避免境界样图数据的重复冗余储存，还可极大提高计算机根据用户指令调用境界样图的速度。实践证明，将此数据模型应用到境界审核系统中后，能大幅减少系统数据库的存储量，提高系统的运行效率。

参考文献：

[1]范玉茹，赵未来，等.基于MapX的行政境界信息管理系统的设计与实现[J].海洋测绘， 2005，25（6）：61-64.

[2]Taylor， D.R.F. Geographic Information System： The Microcomputer and Modern Cartography. Pergamon Press.1991.

[3]武晓淦，张卫星，等.全国省级行政区域界线管理系统设计与实现[J].地理信息世界，2003，1（3）：34-37.

[4]T.Robinson.The K-D-B-Tree：A search structure for large multidimensional dynamic indexes[C].In：Proc ACM SIGMOD Conf， Ann Arbor， Michigan， 1981：10-18.

[5]阎超德，赵学胜.GIS空间索引方法述评[J].地理与地理信息科学界，2004，20（4）：23-26.

[6]陶志刚.地理空间索引技术研究[J].测绘学院学报，2002，19（1）：73-75.

[作者简介] 刘静祯（1976-），女，陜西西安人，工程师，硕士，主要研究方向为地理信息系统设计。