分布式空间数据库中矢量数据多级空间索引方法研究

徐道柱,焦洋洋,金 澄

(1.信息工程大学 地理空间信息学院，河南 郑州 450052;2 地理信息工程国家重点实验室，陕西 西安 710054;3.西安测绘研究所，陕西 西安 710054)

分布式空间数据库中矢量数据多级空间索引方法研究

徐道柱1,2,3,焦洋洋2,3,金 澄1,2,3

(1.信息工程大学 地理空间信息学院，河南 郑州 450052;2 地理信息工程国家重点实验室，陕西 西安 710054;3.西安测绘研究所，陕西 西安 710054)

随着网格计算、云计算等技术在地理信息领域的应用，海量空间数据的高效组织与管理成为提供各种数据和功能服务的基础，空间索引是其中的关键问题，文中在分布式空间数据库系统架构基础上，提出一种适应分布式环境下的分层+分块的矢量数据存储组织模型，设计包括矢量数据面片索引、矢量数据层索引、矢量数据块索引以及数据块内索引在内的多级空间索引。实现表明，文中设计的空间索引支持并发创建和高并发条件下的数据高效访问。

分布式；空间数据库；多级索引；矢量数据；HHCode索引

面对飞速增长的海量空间数据，传统的数据管理方式已经显得力不从心。随着网格计算、云计算等技术在地理信息领域的应用，分布式系统架构与并行处理技术可大大提高地理信息管理、分析和应用的性能，已经成为研究的热点。

海量空间数据的高效组织与管理是提供各种数据和功能服务的基础，空间索引是其中的关键问题。空间索引方法大致可分为线性索引、网格索引和树形索引三大类[1]，这几类索引特点不同，适用场合也各不相同。线性索引是将索引项组织为线性结构，结构直观简单，但对海量空间数据的管理效率较低。网格索引结构简单，效率较高，当实体增加导致实体分布不均匀需重构索引[2]。树形索引是应用较为广泛的空间索引结构，衍生索引结构比较多，高维索引大都基于树形索引实现[3-4]。随着分布式系统研究逐渐成为热点，分布式、并行索引成为空间索引的研究热点，文献[5-6] 研究了ArcSDE在基础地理信息数据库存储和设计的应用；文献[7-10]研究了MR-tree、R 树和多级R-tree等空间索引的并行化实现；文献[11]对四叉树进行面向列式存储扩展改进，文献[12-14]将VoR-Tree、双层倒排网格索引、空间k近邻查询与MapReduce编程模型相结合进行分布式改造。

本文结合分布式环境下矢量数据的存储组织模型，设计了一种多级空间索引，并对相关索引进行并行化改造提升索引效率，并针对数据存储、索引构建、查询访问进行相关实验。

1 分布式空间数据库系统架构

分布式空间数据库系统架构是矢量数据存储组织模型以及空间索引设计的基础，在进行矢量数据存储组织模型和空间索引设计时需要充分考虑分布式架构下矢量数据的使用特点，有的放矢，才能充分发挥分布式架构在存储量、吞吐量以及并发性等方面的优势。分布式空间数据库系统架构由存储层和矢量数据访问引擎组成。如图1所示。

图1 分布式空间数据库系统

1)存储层。存储层作为分布式空间数据库的物理存储中心，由关系型数据库和分布式数据库组成，其中关系型数据库用于存储矢量数据层的属性数据、元数据，资源目录等结构化信息；分布式数据库由于存储矢量数据，等半结构化数据文件。

2)矢量数据访问引擎。矢量数据访问引擎主要为上层应用提供统一的矢量数据存储访问接口。其内部使用数据调度缓存、多级空间索引查询等手段实现对矢量数据的高效存储与访问。

2 矢量数据组织模型及多级空间索引设计

2.1 分布式存储组织模型

传统的矢量数据模型，采用将矢量图层和地理目标进行集中组织存储，如果一个图层的地理目标众多，会带来数据访问慢、空间索引维护困难、建立空间索引耗费时间长等一系列问题，很难支持多尺度数据的快速获取、网络环境下的“渐进式”传输以及地理信息客户端的“自适应”动态可视化等应用。

结合分布式空间数据库系统架构下的矢量数据的使用特点，面向矢量数据并行入库、高效访问的应用需求，采用关系数据库和分布式半结构化数据库相结合的技术思路，提出了一种适应分布式环境下的分层+分块的矢量数据存储组织模型，具体结构如图2所示。

该矢量数据存储组织模型从结构上由存储层、调度层和应用层组成：

1)存储层。描述了矢量数据的物理存储环境，即将矢量数据通过网格剖分生成的所有矢量数据面片以小文件的形式存储于分布式存储环境下的各个数据节点上，实现了对海量矢量数据的分布式存储需求；

2)调度层。描述进行矢量数据访问时，矢量数据从存储层调度的方式。即根据调度条件(如空间范围)，首先确定当前调度的矢量数据所在的矢量面片文件并从存储层读取，然后根据矢量面片文件中的矢量数据层索引信息，快速获取需要访问的矢量数据层，并根据矢量数据层中的空间索引信息，计算符合条件的矢量数据标识和对应的矢量数据块，最后根据数据块内索引获取所有的矢量数据，构成目标集并缓冲到内存，为应用层访问做好数据准备。通过数据调度缓存、多级空间索引查询，调度层极大地提高矢量数据的访问效率；

3)应用层。提供面向用户的矢量数据的存储访问方式。当调度层完成矢量数据的调度后，会将符合调度条件的数据以目标集的形式分批加载到应用层。

通过分布式空间数据库系统架构下矢量数据的存储组织模型设计，解决了海量矢量数据并行入库和高效访问的应用需求。针对海量矢量数据并行入库应用需求，将海量矢量数据依据网格部分规则(如：Google剖分等)将海量矢量数据根据空间范围划分若干个矢量数据网格，而一个矢量数据网络对应一个物理上的矢量数据面片文件，每个矢量数据面片文件中包括某个空间范围内的所有矢量数据层的矢量数据。通过这种剖分规则将海量矢量数据化整为零，以矢量面片文件的形式存储在分布式数据库的各个数据节点上，以实现多客户端并行存储。通过分布式技术解决了海量矢量数据的存储以及高并发访问的问题，但是其对单用户的矢量数据访问效率并未有帮助，甚至会降低访问效率，为此本文设计了一种多级空间索引机制，以提高矢量数据的单次访问效率。

图2 矢量数据存储组织模型

2.2 多级空间索引

根据矢量数据的分布式存储组织模型，矢量数据是以矢量数据面片的形式组织存储的，矢量数据面片是矢量数据物理调度的最小单元，为了提高矢量面片的访问效率，设计以矢量数据面片对应的矢量网格行列号作为其文件名，当进行空间范围查询时，可以快速计算该范围覆盖的行列号集，从而快速定位符合条件的矢量面片文件。而在矢量数据面片内部通过矢量数据层索引、矢量数据块索引以及数据块内索引等多级索引提高矢量数据的命中率，极大地提高矢量数据的单次访问效率。其结构如图3所示。

图3 矢量数据面片结构

由矢量数据面片结构图可以看出，矢量数据面片由矢量数据层索引信息和若干矢量数据层组成，其中在每个矢量数据层又由空间索引节点信息、矢量数据块信息等构成；

矢量数据层索引信息记录了该矢量数据面片包含的每个矢量数据层的名称，以及在矢量数据面片内的存储位置等信息；

空间索引节点信息是用于描述创建空间索引时生成的所有空间索引节点，一个空间索引节点包括节点信息(节点Code、级别等)、包含的矢量目标个数、每个矢量目标的标识、范围、几何类型、分级编码等信息。一个矢量数据桶里包括1～N个空间索引节点；

矢量数据块和空间索引节点一一对应，空间索引节点中只包含矢量目标的标识、几何类型等信息，而矢量数据块将一个空间索引节点覆盖的相邻矢量目标数据以数据块的形式打包，主要包括矢量目标块内索引信息、包含的矢量目标个数、每个矢量目标几何信息、拓扑信息、属性信息等。

2.2.1 矢量数据层索引

矢量数据层索引信息记录了该矢量数据面片包含的每个矢量数据层在矢量数据面片内部的存储偏移量，当需要访问该矢量面片中某个矢量数据层时，可以通过该索引信息快速定位矢量数据层在矢量数据面片内的存储位置，实现了矢量数据层随机访问的能力。

2.2.2 矢量数据空间索引

矢量数据空间索引是在HHCode(Helical Hyper-spatial Code)的索引机制的基础上进行了改造，即将HHCODE空间索引数据块化。每个HHCODE空间索引对应一定空间范围内的目标集合，并将跨HHCODE空间索引的目标进行升级，提升至上一级HHCODE空间索引节点，构建空间索引节点树，实现矢量数据按块查询调度，以满足对矢量数据的高效空间查询需求。

HHCode(Helical Hyper-spatial Code)是目前国际上空间数据索引采用的主要技术之一。 它是由CHS(Canadian Hydrographic Service)于1990年开发的将多维数据转换为一个整数值的一种编码技术。

一维HHCode是对一维矢量数据进行二分形成的二进制编码，m维HHCode是对m维矢量进行二分形成的二进制编码。以二维地图为例，HHCode编码方法如下：

首先，对二维地图所在的地图范围进行逐级四分，每次划分用2个1比特标识所选区域，分别标识北/南、西/东方向。这样，经过n级划分就得到2个n比特串，从高位到低位依次代表从小到大的级别。然后，将这两个位串按位交叉存储成一个2n比特的值，所得的二进制编码即为区域的n级HHcode编码值。设1标识北和东，0标识南和西，2维空间的2级与3级HHCode的编码如图4所示。

图4 二维空间的HHCode编码

基于HHCode编码技术的空间索引本文用HHCODE索引表示。地理目标的HHCODE索引由它所在区域的HHCode编码表示，索引值为HHCode编码值，索引级别为HHCode编码的级别，一个完整的HHCODE索引表示为<值，级>()。例如，对于图5中的点P，经过4级递归划分后，其北/南方向上的二进制位串位为0011，东/西方向上的二进制位串位为1001，将两个位串交叉存储后得到点P的HHCODE索引的值为01001011，HHCODE索引的级为4，点P的完整的HHCODE索引为<01001011，4>。

图5 地理目标的HHCODE索引

对于线目标和面目标，由于它们都具有大小，所以可能需要不同划分级别上的多个HHCODE索引才能完整的覆盖整个目标。例如，在图5中，面B的索引为<101100,3>，面A的完整的索引如下：

<100010,3>、<100011,3>、<100111010,4>、<100111011,4>、<101000,3>、<101001,3>、<101011,3>、<10101001,4>、<101100,3>、<101110,3>、<10110100,4>、<10110110,4>、<10111000,4>。

一个HHCODE索引对应整个空间范围中的一个空间区域，通过HHCODE索引可以检索到这个空间区域，称这个空间区域为相应的HHCODE的索引区域。尽管HHCODE仅以一对整数值定位空间区域，但它却包含了丰富的空间关系信息，具体表现：

1)HHCODE索引能够体现空间数据之间的相等关系。如果的索引区域与的索引区域相同，则level 1 = level 2，且code 1 = code 2；

2)HHCODE索引能够体现空间数据之间的包含关系。如果的索引区域包含的索引区域，则level 1 ≤ level 2，且code 2由高到低第1位到第2level 1位与code 1相等；

3)HHCODE索引能够体现空间数据之间的相交关系。如果的索引区域与的索引区域相交，两个索引的索引区域相等或具有包含关系。

由于HHCODE本身包含丰富的空间关系信息，因此，利用HHCODE索引可以快速判断符合某一个范围的所有HHCODE索引区域，而每个HHCODE索引区域都对应一个以HHCODE索引的level和code唯一标识的空间索引节点，空间索引节点里记录了对应的HHCODE索引范围内所有矢量目标的标识、范围、主属性等信息，当进行空间条件查询时，根据空间范围条件可以快速计算出其覆盖所有HHCODE索引范围，进而获取到对应的所有空间索引节点和矢量数据块，然后从这些空间索引节点中提取符合条件的矢量目标标识，根据矢量目标标识和矢量数据块内索引快速从矢量数据块中提取矢量目标数据，通过这种方式极大地提高矢量数据的访问效率。

2.2.3 矢量数据块内索引

矢量数据块内索引记录了该块内每个矢量目标在矢量数据块内的存储位置，其由矢量目标标识和矢量目标在块内的偏移量构成，通过需要获取的矢量目标标识，获取该矢量目标在矢量数据块内的偏移量，达到矢量目标快速加载、随机访问的目的。

3 实验与分析

3.1 实验环境和实验数据

本文在实验环境中对提出的矢量数据存储组织模型和多级空间索引进行了实验验证，实验硬件环境包括43台存储服务器用于部署分布式文件系统和分布式数据库，6台存储服务器用于部署关系数据库，25台客户端机器用于部署待入库数据和并行入库、并发访问程序；实验软件环境包括改进后的分布式文件系统HDFS、分布式数据库HBase、达梦关系数据库(DM7 MPP版本)和并行入库、并发访问实验软件。实验数据包括多比例尺、多源矢量数据300 GB。

3.2 实验案例和结果分析

3.2.1 数据入库和多级索引建立

将试验数据分摊部署在并行客户端机器上，启动并行入库程序，表1为分布式矢量数据入库和传统数据库管理系统入库效率对比实验结果。

表1 分布式矢量数据入库和传统数据库管理系统入库效率比较

实验结果分析：

1)通过分布式矢量数据入库、多级索引创建实验结果可以看出，随着数据量的增长，在客户端数量不变的情况下，入库时间呈线性增长趋势，单台客户端入库速度保持稳定。

2)通过传统数据库管理系统入库、索引创建实验结果可以看出，随着数据量的增长，在客户端数量不变的情况下，入库时间呈线性增长趋势,单台客户端入库速度略有下降。

3)通过对两者实验结果相比较可以看出，通过分布式矢量数据入库，虽然矢量数据平均入库效率没有提升，反而下降，但总体矢量数据装载时间大大缩短，且可管理数据量大大提升。

3.2.2 数据并发访问效率

在25台客户端部署并发访问程序，每台客户端上分别模拟若干个并发访问用户，并为每个测试执行者分配参数文件序号，执行并发访问5 min，记录每个并发访问用户5 min内向系统发送请求的个数、系统成功处理请求的个数、系统处理请求成功率，以及成功处理请求的最小、最大、平均响应速度。表2为矢量数据并发访问测试记录表。

实验结果分析：

1)通过分布式矢量数据访问实验结果可以看出，随着并发访问量的增加，5 min访问时间内系统处理请求成功率没有发生明显变化，矢量数据并发访问成功率都达到99%以上；但是矢量数据并发访问单位时间内获取的要素个数却呈逐步下降的趋势，这与矢量数据的属性数据需要使用关系数据库进行管理有关，当访问量增加时，关系数据库的响应效率将有所下降。

表2 矢量数据并发访问测试记录表

2)通过基于传统数据库的矢量数据访问实验结果可以看出，随着并发访问量的增加，5 min访问时间内系统处理请求成功率呈现下降趋势，而且在矢量数据并发访问单位时间内获取的要素个数呈现逐步下降趋势，说明传统数据库在并发访问量增大的情况下，其处理能力在逐渐下降。

4 结束语

空间索引是海量空间数据的高效组织与管理的关键问题，本文在分布式空间数据库系统架构基础上，结合矢量数据的使用特点和应用需求，采用关系数据库和分布式半结构化数据库相结合的技术思路，提出了一种适应分布式环境下的分层+分块的矢量数据存储组织模型，在此基础上设计了包括矢量数据面片索引、矢量数据层索引、矢量数据块索引以及数据块内索引在内的多级空间索引，并针对数据存储、索引构建、查询访问进行了相关实验。实现表明，本文设计的空间索引支持并发创建和高并发条件下的数据高效访问。在多级索引中矢量数据分片、矢量数据空间索引数据块化改造等方面还需进一步深入研究、优化参数，以期进一步提高数据管理效率。

[1] 何珍文,郑祖芳,刘刚,等.动态广义表空间索引方法[J]. 地理与地理信息科学,2011,27(5):9-15.

[2] 周勇. 改进的层次网格空间索引技术研究与实现[D]. 福州：福州大学,2004.

[3] 盖森,张心悦,喻峰,等.多尺度位置键空间索引方法[J]. 测绘科学,2015,40(8):147-151.

[4] 龚俊,朱庆,张叶廷,等.顾及多细节层次的三维R 树索引扩展方法[J].测绘学报,2011,40(2):249-255.

[5] 孙朝犇,马学民,路轩轩,等. ArcSDE在基础地理信息数据库更新中的应用[J].测绘与空间地理信息,2016,39(1):79-81.

[6] 李德元,姚文龙,杨二龙,等. 基于ArcSDE文件地理数据库存储和设计的应用研究[J].测绘与空间地理信息,2016,39(1):82-84.

[7] 付仲良,刘思远.MR-tree空间索引的Voronoi图改进及其并行空间查询方法[J]. 武汉大学学报(信息科学版),2012,37(12):1490-1494.

[8] 赵园春,李成名,赵春宇.基于R 树的分布式并行空间索引机制研究[J]. 地理与地理信息科学,2007,23(6):38-81.

[9] 付仲,刘思远,田宗舜,等.基于多级R-tree的分布式空间索引及其查询验证方法研究[J]. 测绘通报,2012 (12):42-46.

[10] 郑祖芳.分布式并行时空索引技术研究[D]. 武汉：中国地质大学,2014

[11] 涂振发.云计算环境下海量空间数据高效存储关键技术研究[D]. 武汉：武汉大学,2012.

[12] 杨文奇,刘 杰,陈飞轮.基于MapReduce 的并行VoR-Tree 索引[J].地理空间信息,2013,11(6):109-111.

[13] 赵敏超,杜震洪,张丰,等.基于MapReduce和双层倒排网格索引的KNN算法[J].浙江大学学报(理学版),2014,41(6):703-708.

[14] 陈飞轮.基于MapReduce的VoR_Tree索引并行构建技术研究[D].江西赣州：江西理工大学,2012.

[责任编辑：李铭娜]

Research on multilevel spatial index method of vector data in the distributed spatial database

XU Daozhu1,2,3,JIAO Yangyang2,3，JIN Cheng1,2,3

(1.School of Surveying and Mapping, Information Engineering University, Zhengzhou 450052, China;2.State Key Laboratory of Geo-information Engineering, Xi’an 710054, China;3.Xi’an Station of Surveying and Mapping, Xi’an 710054, China)

Distributed computing and cloud computing technology have been applied to the field of geographic information, offering a variety of data and function services based on the efficient organization and management of massive spatial data. Spatial index is the key problem. Based on distributed spatial database system architecture, the paper proposes a layered and blocked vector data storage organization model which adapts to the distributed environment, along with a multilevel spatial index that included patch index, layer index, block index and inside block index of the vector data. The experiments illustrate that the model designed in the paper supports the concurrent create spatial index and efficient data access under the condition of high concurrency.

distributed; spatial database; multilevel index; vector data；HHCode index

著录：徐道柱,焦洋洋,金澄.分布式空间数据库中矢量数据多级空间索引方法研究[J].测绘工程，2017，26(10)：1-6.

10.19349/j.cnki.issn1006-7949.2017.10.001

2016-07-18

国家自然科学基金资助项目(41201469)

徐道柱(1982-),男,助理研究员,博士研究生.

TP391

A

1006-7949(2017)10-0001-06