基于改进四叉树的地理实体快速查询算法

彭召军，王青山，熊 伟，李柏地

（1.信息工程大学，河南 郑州 450001；2.78138部队，四川 成都 610000）

基于改进四叉树的地理实体快速查询算法

彭召军1，王青山1，熊 伟1，李柏地2

（1.信息工程大学，河南 郑州 450001；2.78138部队，四川 成都 610000）

通过改进传统四叉树的数据组织和节点分配，将被索引的地理实体要素合理地分配到树中对应的节点中，减少了数据冗余，节点的分布也更为合理。以地理实体数据为例，综合比较了不同数据集在建立索引前后空间查询效率上的差异。结果表明，该算法具有较高的查询性能和实用价值。

四叉树；地理实体；空间查询

空间索引是指在存储空间数据时，依据空间对象的位置、形状或空间对象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形以及指向空间对象实体的指针[1]。传统的数据库索引技术主要有B-树、B+-树、二叉树、ISAM索引和哈希索引等[2]，这些技术都是针对一维属性数据设计的，不能直接用于空间数据库的索引。针对多维空间数据具有的空间关系复杂、数据量大、数据表达困难[3]等特点，本文在传统四叉树的基础上，通过改进其空间分割、节点分配及数据组织方式，设计了一种基于改进四叉树的地理实体快速查询算法；并利用真实地理实体数据，对算法进行了测评，取得了良好的效果。

1 四叉树索引

四叉树索引是一种面向主存的空间索引技术，是建立在对区域循环分解原则之上的一种层次数据结构，在计算机图形处理、图像处理及GIS中有广泛的应用。空间四叉树算法是一种空间均匀网格剖分算法，其将包含整个场景的空间按x、y方向分割成4个子方块网格，从而组成一棵四叉树。若某一子方块网格中所包含的要素数量大于给定的阈值，则对该子方块作进一步递归分割，直到四叉树的每一个叶子节点的子方块所含要素数量均小于给定的阈值为止[4-5]。

1.1 地理实体的最小外包矩形

在实际应用中，最小外包矩形能够很好地描述地理实体的属性特征。如图1所示，以线状要素和面状要素为例，通过建立要素的最小外包矩形，确定各要素在四叉树中的层次，再依据最小外包矩形的范围将各要素分配到四叉树相应的节点中去。

图1 四叉树分割和地理实体要素的节点分配

1.2 改进四叉树的数据结构

如图2、3所示，传统四叉树和改进四叉树的主要区别为：

1）在改进四叉树中，判断一个地理实体位于第i（i =0,1,2,…,n-1，i

2）在改进四叉树中，节点的分裂完全按照地理实体要素的数据分布特点而定，分裂后得到4个相等子节点矩形，根节点或某些中间节点可能不包含对象，某些节点可能包含多个对象。只要对象的最小外包矩形满足1）中的条件，对象就会被准确地分配到四叉树对应的层级中，四叉树的节点也分裂到对应的层级。

3）在改进四叉树中，为了控制树的深度，根据地理实体数据的特点，系统动态设置一个分裂的最大深度MaxDepth。当四叉树的层级达到MaxDepth时，四叉树节点不再继续向下分裂，而是将此地理实体要素加入到四叉树中层级为MaxDepth所对应的父亲节点中。

4）对于某一地理数据集，在改进四叉树索引中，设置一个节点的最小度MinDegree。对一棵已经建立好的四叉树进行“节点最小度”处理，如果四叉树节点中存储的地理实体要素个数小于MinDegree，则将此节点中的要素添加到此节点的父亲节点中去，再将此节点设为空。

图2 传统四叉树的数据结构（以线状要素为例，N为层数）

图3 改进四叉树的数据结构（以线状要素为例，N为层数）

2 空间查询算法的实现

2.1 四叉树索引的构建

2.1.1 索引树的创建

在改进四叉树中，需要记录的属性有：地理实体要素的FeatureID（int型）、层次信息Level（int型）、最小外包矩形的左上角点（L_x, L_y）和右下角点（R_x, R_y）坐标（double型）、父亲节点指针Parent和4个孩子指针Child[4]。四叉树的结构定义如下：

四叉树索引的构建过程为：①确定树的根节点[6]。首先分别确定各地理实体要素(点、线、面)的最小外包矩形，并对各要素的最小外包矩形的左上角点和右下角点坐标加以比较，得到能够涵盖所有要素的最小外包矩形：rootBound(min(Left_Xi,Left_Yi, Right_Xi,Right_Yi))。②确定地理实体要素在四叉树中的层级（Level< MaxDepth），找到需要插入的子节点，条件如§1．2中所述。③将地理实体要素插入到对应的子节点中，重复上述步骤直至所有的要素插入完毕。④对建立好的四叉树作“节点最小度”处理，使每个节点的要素数量都大于MinDegree。插入算法代码为：

2.1.2 索引文件的生成

基于二进制文件在数据读写方面的优势，将四叉树索引写入二进制文件中，生成包含地理实体要素关键属性的四叉树索引文件，具体流程如图4所示。

图4 地理实体数据处理流程图

按照四叉树的编码特性和数据组织方式[7]，采取深度遍历的方式，将要素的nID、nPosition、MBR按顺序写入索引数据文件。相比于原始数据，新生成的索引数据占用空间更少，读取效率更高。在执行查询、插入、删除、更新等空间操作时，算法只需在初次执行操作时构建四叉树索引，以后仅装载包含四叉树索引的地理实体数据文件即可。依据四叉树索引的空间剖分原则和数据组织方式，读取数据时，可根据根节点的最小外包矩形的范围确定各层级子节点的最小外包矩形，依次读取各节点的数据，并把整个索引树快速还原，避免了频繁读取原始数据和重复构建四叉树索引而造成的浪费，提高了空间操作的效率。

2.2 地理实体查询算法

点查询和开窗查询是GIS中两类重要的空间查询方式。点查询是查找距离鼠标点一定阈值范围内的所有地理实体对象；开窗查询是查找在给定的区域范围内的所有要素对象（点、线、面），常见的开窗查询有按矩形、圆、多边形查询[8]。

2.2.1 点查询

点查询具体步骤为：

1）从四叉树的根节点开始，逐节点递归查询，若节点的最小外包矩形与给定阈值范围相交，记录节点中所有地理实体对象的ID；若节点不是叶子节点，以子节点为参数继续执行此过程，直到是叶子节点为止。

2）将搜索完毕后得到的所有记录存入一个整型数组中，按照ID大小进行排序，这将更加有利于从索引文件中按ID号快速提取相应的地理实体对象。

3）对数组中所有ID对应的地理实体对象遍历搜索，判断查询点的阈值范围是否与对象的外包矩形相交。若相交，说明查找成功，否则将此ID从数组中删除。

2.2.2 开窗查询

算法描述如下：

开窗查询的具体实现步骤为：

1）从根节点开始，逐节点递归搜索。若节点的最小外包矩形与查询区域相交，表明查询区域内可能包含对象，继续递归搜索直至步骤2）条件成立。

2）若查询区域包含某一节点中的某些对象（对象可能不唯一）的最小外包矩形，将这些对象添加到结果容器中，继续递归搜索直至叶子节点。容器中所含的对象即为开窗查询的最终结果。

需要说明的是，点查询和开窗查询只能对海量实体对象进行初步过滤，要想得到精确的结果，还需对结果进行精确查询判断。通过构建四叉树索引，排除了大量与查询条件无关的地理实体对象，极大地提高了整个空间查询的效率。

3 实验设计与结果分析

3.1 实验内容与设置

实验采用多个数据集，不同数据集分别代表了不同的地理实体类型和数据量。详细的数据集信息见表1。

表1 数据集信息

算法采用C++编程语言实现，对测试数据集建立改进四叉树索引（MaxDegree=20，MaxDepth=10）。为了验证算法的性能，本文将建立了四叉树索引与未建立索引的地理实体数据集的查询性能进行比较，衡量算法性能的指标包括CPU时间和磁盘I/O次数。

3.2 实验结果分析

3.2.1 CPU时间

表2为建立了四叉树索引的地理实体数据集和未建立索引的地理实体数据集执行查询操作的CPU时间开销。表中包含了4个数据集转换成二进制文件和建立四叉树索引之后的索引文件大小、建立四叉树索引的CPU时间开销以及执行查询操作时的CPU时间开销。

表2 CPU时间/ms

1）无论是否建立索引，查询时间都随数据量的增大而不断增加。执行查询操作时，构建四叉树索引的过程所需CPU时间消耗较大；但当索引构建完成后，查询时间与未建立索引的查询时间相差了几百倍，查询效率明显提高。可以说，建立四叉树索引的数据集执行查询操作的CPU时间几乎全用在了构建索引的过程中。

2）随着数据量的不断增加，未建立索引的数据集在执行查询操作时的CPU时间消耗急剧增加。这是因为未建立索引，数据缺乏有效组织，查询操作采取的方式为简单的顺序遍历，而这种方式在数据量增多时存在固有缺陷。建立索引的数据集执行单次查询操作的CPU时间消耗随数据量的增加无明显变化。

3.2.2 磁盘I/O次数

图5显示了4个数据集执行查询操作时的磁盘I/O次数。与CPU时间消耗类似，随着数据量的增加，构建四叉树索引所花费的磁盘I/O次数显著增加。构建索引时，数据的读取和写入、索引文件的生成及四叉树构建时的递归插入等操作所需要的磁盘I/O次数远大于不建立索引时所需的磁盘I/O次数。单就查询操作的实现而言，建立四叉树索引和未建立索引所需要的磁盘I/O次数相差并不明显。

图5 4种数据集的磁盘I/O

4 结 语

本文提出了一种基于改进四叉树的地理实体要素快速查询算法，在实体数据集的查询操作中嵌入改进的四叉树索引，提高了数据查询与检索的效率，算法取得了良好的效果。但本算法也存在不足，在数据量或地形形态相差较大时，四叉树分割阈值的选取、深度的动态控制以及四叉树的平衡性对最终的查询结果和查询效率影响很大，需要对多种实验结果进行综合分析后选取合适的阈值，这是下一步需要研究解决的问题。

[1] GUO J,ZHOU D R,GUO W, et al． Research of Indexing Techniques for Spatial Databases[J]． Application Research of Computers,2003,20(12):12-14

[2] 郭薇,郭菁,胡志勇．空间数据库索引技术[M]．上海:上海交通大学出版社,2006

[3] 郭仁忠．空间分析[M]．武汉:武汉测绘科技大学出版社,2000

[4] WANG T,LIU J P,WU H H． The Extraction of Contour Lines from Grid DEM Based on Sorting[J]． Acta Geodaetica Et Cartographica Sinica,2006,35(4):392-394

[5] 夏宇,朱欣焰．高维空间数据索引技术研究[J]．测绘科学,2009,34(1):60-62,68

[6] 卢蓉,范勇,陈念年,等．一种提取标图像最小外接矩形的快速算法[J],计算机工程,2010,36(21):178-180

[7] 李建勋,沈冰,姜仁贵,等．面向影像金字塔的四叉树空间索引算法[J]．计算机工程,2011,37(10):11-13

[8] 董鹏, 杨崇俊, 芮小平, 等．一种基于改进四叉树的GIS空间选择查询算法:以ESRI shape格式文件为例[J]．计算机工程与应用,2003,39(13):58-61

P208

B

1672-4623（2017）01-0032-04

10.3969/j.issn.1672-4623.2017.01.010

彭召军，硕士研究生，主要从事地理空间数据库索引等方面的研究工作。

2015-11-24。

项目来源：国家自然科学基金资助项目（41501507）。