一种改进的嵌入式电子地图空间索引

劳洁莹，孙志磊

(浙江工业大学 信息化办公室，浙江 杭州 310014)

一种改进的嵌入式电子地图空间索引

劳洁莹，孙志磊

(浙江工业大学 信息化办公室，浙江 杭州 310014)

摘要：空间索引在嵌入式设备中有广泛的应用，按照不同的空间映射方式，可以分为不同的索引方法，如二叉树索引、网格索引、四叉树索引和R树索引及其变种，指出了各种空间索引的利弊和适用环境.目前嵌入式系统中硬件资源不足，人们对其功能的需求却在不断的增加，因此如何快速的检索到需要的空间数据以满足相应的功能成为了一个亟需的问题.根据各个索引方法优势以及其相关的使用环境，提出了一种四叉树和R*-树相结合的空间索引—QR*-树索引，此空间索引虽然在存储空间上比R*树略有增加，但是在插入、删除、查找等操作中的性能远远优于R*-树，非常适合作为嵌入式系统的数据库空间索引，最后在S3C2440平台上验证了其有效性.

关键词：电子地图；QR*-树；嵌入式系统

An improved spatial index method for embedded electronic map

LAO Jieying, SUN Zhilei

(Information Manager, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:Spatial index is widely used in the embedded devices, which can be divided into various different index methods depending on space mapping method, such as binary tree index, grid index, quad tree index and R tree index. The advantages and disadvantages of various spatial index methods and the application environment are pointed out. But the hardware resources in embedded systems are insufficient for meeting the increasing requirements. Therefore, how to quickly retrieve spatial data needed to meet the corresponding function has become an urgent issue. A new spatial index-QR*-tree index method combined with quad tree and R*-tree is proposed in this paper. Although this spatial index has a little increase in storage space than R*- tree, but the performances in the insertion, deletion and search operations are far superior that R*- tree. It’s very suitable for database spatial index in embedded system. The experiments show that the QR*-tree index in the S3C2440 platform has a good performance.

Keywords:electronic map; QR*-tree; embedded system

嵌入式导航设备由于良好的可移动性得到了广泛的应用，但是相对于PC而言，嵌入式设备的硬件资源比较匮乏，存储空间较小、处理器的主频较低.随着人们需求的不断增加，嵌入式设备上需要实现的功能越来越多，需要同时实现地图的显示、路径的寻优和兴趣点的搜索等功能.近年来，随着三维电子地图的出现和国家城镇化速度的加快，电子地图的数据量大大增加了.因此，如何快速的检索到需要的空间数据以满足相应的功能需求成为了一个重要的问题.

空间索引是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构[1].索引是介于算法和数据之间的一种辅助的结构，通过它可以排除大量与操作无关的数据，提高检索的效率.空间索引的优劣是衡量一个嵌入式GIS的重要指标[2].GIS经历了40多年的发展，基于PC的GIS系统已经比较成熟，近年来，随着移动导航设备的飞速发展，嵌入式GIS成为研究焦点.有不少的学者对空间索引进行了研究并提出了一些空间索引算法，如网格索引、四叉树索引、R-树索引、R+-树索引等.不过每种索引方法都有各自的优缺点和适应的领域，通过对这些索引方法的研究，提出了一种适合嵌入式GIS的空间索引方法—QR*-树.QR*-树索引结构结合了Quadtree(四叉树)和R*-树各自的优点，将要搜索的领域用四叉树的结构划分成为小的单元，然后在每个小的单元中建立R*-树索引结构，如此既减少了数据量的冗余又提高了检索的速度.最后使用Android平台验证了此种索引方法的有效性和实用性.

1空间索引算法性能对比

GIS经历了多年的发展，得到了广泛的应用.空间索引是它其中的重要组成部分，决定着GIS性能的好坏，很多学者对其进行了研究，提出了不少的空间索引的方法.对于空间索引，按照不同方式，可以分为不同的类别.从空间目标的映射方式不同，可以分为基于空间目标排序的索引方法和专门的索引方法；根据存储介质的不同可以分为内存空间索引和外存空间索引；根据划分区间的规则性，将其分为规则区域划分索引结构和R树及其变种索引结构.

1.1规则划分索引结构

规则划分索引是指对待建立空间索引的空间领域采用规则剖分的方法建立起来的空间索引.规则剖分的形状多采用便于操作的矩形，由此产生且常用的空间索引有BSP树索引、网格索引和四叉树索引.BSP树结构又称为二叉树，即将待建立索引的区域递归的剖分成为规则的两个区域，直到满足剖分的停止条件为止.BSP树索引结构剖分方法比较简单，易于实现.但是也存在缺点，由于BSP树节点最多有两个子节点，若作为大范围电子地图的空间索引，BSP树的深度势必会比较大，如此检索的效率便不高.由于空间物体的分布不均匀，空间剖分时可能并非等分，如果所形成的BSP树不平衡，最坏的情况可能退化成为线性索引结构，其检索效率便会大大的下降.规则划分的空间索引结构应用最为广泛的是网格索引和四叉树索引.

网格索引的建立方法是将待建立索引的空间区域均匀的划分成为R*S矩形单元，空间实体和网格单元形成了多对多的关系.即一个网格单元可能包含多个空间对象，而一个空间对象也可能位于多个网格单元之中.对于每个网格，可以通过Hilbert编码将二维映射成为一维，既有利于存储，也利于查询.由于Hilbert曲线具有空间聚类性，可以基本保证空间相邻的网格在存储空间上亦是相邻.查询某个空间实体时，可以通过空间实体的经、纬度坐标立刻计算出它所在的网格，通过网格的行、列号可以立刻计算出它的Hilbert编码，然后便可定位该空间实体所在的存储空间的位置.由于网格索引是多对多的索引结构，因此它存在数据冗余的缺点.由于一个空间实体可能落入多个网格之中，因此为了保证每个网格中数据的完整性，多个网格中都必须存储该空间实体的ID，这样该空间实体的ID被多次存储，造成了数据冗余，网格划分越精细，数据的冗余就越多.网格索引作为空间索引的另一大问题是网格划分的精细程度非常难以确定.如果划分得过于细致，那么会造成实体ID数据冗余量大增且维护索引本身的数据量也会增加；而如果网格划分过于粗略，那么每个网格中的空间实体的数据量会较多，不能够对空间实体进行精确定位，实体的检索效率又会大大降低[3].

四叉树索引又称为四元树，它的每个非叶子节点都有四个子节点，每个节点表示一块区域，每个区域的形状可以是规则的矩形或者其它形状，于1974年由Raphael Finke和J. L. Bentley提出[4].四叉树可以分为点四叉树、区域四叉树和CIF四叉树.作为空间索引，区域四叉树应用最为广泛.区域四叉树索引的建立方法是将待建立空间索引的区域递归的划分为四个子区域，直到满足划分的停止条件，子区域的大小是相等的，划分的停止条件可以根据实际情况而定.每个区域中包含了各种的空间实体，区域和空间实体之间也是多对多的映射关系，即每个区域可以包含多个空间实体，同时一个空间实体也可能位于多个区域之中.MX四叉树和PR四叉树是两种最典型的区域四叉树，MX四叉树是一棵平衡四叉树，每个节点的子空间是均等的，结构比较简单.MX树的每个叶子节点要么是黑色节点，表示该节点空间包含空间实体；要么是空节点，表示不包括任何空间实体数据.MX四叉树的主要缺点是对MX四叉树进行更新后，可能会导致它的深度发生变化，每个叶子节点的位置都会发生变化.PR四叉树是完全的四叉树，如果其区域中包含的数据点数多于1，那么就均匀四分该区域，因此每个叶子节点区域中包含的数据点都不会超过1.空间实体数据的分布不均匀，完全四叉树作为空间索引会造成数据的严重冗余.在空间实体稀疏的区域，会出现很多空的区域；在空间实体分布稠密的区域，会出现很多一个空间实体落入多个区域的情况，造成索引结构数据和空间实体ID数据冗余.

1.2R树及其变种索引

与区域划分不同，人们提出了另外一类空间索引结构R树及其变种.R树索引结构[5]由学者Guttman提出，它和B树比较类似，但是B树比较适合作为一维数据的索引，而R树比较适合作为高维数据的索引.R树一经提出，便在空间索引领域得到了广泛的应用，针对R树的不足，人们提出了一些R树的变种索引结构，如R+树、R*-树、QR树、SS树和X树等.

R树是B树在高维的延伸，它的平衡度高，因此空间利用率比较高.R树由若干节点构成，R树的每个叶子节点都位于R树的最底层，并且每个非叶子节点包含的子节点的个数有上限和下限，这是为了保持空间的有效利用.每个节点对应一个最小的包围盒，此包围盒是包含该节点中所有空间对象的最小外接图形.包围盒的形状可以是规则的矩形、圆形或者其他图形.每个节点中包含了一个引用，此引用指向该节点的孩子节点或者该节点包含的空间实体的数据.如图1所示，有8个实体，每个实体的外接矩形编号是从4~11，编号为1，2，3的矩形分别表示它们的包围盒，1号包围盒包含了实体6，7，8；2号包围盒包含了实体9，10，11；3号包围盒包含了实体4，5.每个包围盒对应R树中的一个节点，这些节点构成的R树索引结构如图2所示，0号节点表示根节点，它有3个子节点，分别为1，2，3.节点4~1都是叶子节点.

图1　空间实体分布及包围盒Fig.1　The distribution of spatial entity and bounding box

图2　R树索引结构图Fig.2　R-tree index structure

R树索引的存储效率相对较高，检索的效率也较高，检索的时间复杂度为logN.但是R树也存在弊端，它的主要缺陷是节点的包围盒区域相互重叠，重叠的区域面积和次数与空间实体的分布均匀度成反比，与空间的数量成正比.包围盒重叠会影响空间实体的检索效率，当要检索的空间实体位于几个包围盒的重叠区域以内，那么在检索该空间实体时，这几个包围盒都需要查询，就降低了检索的效率，并且检索的时间也没法准确的估计.为了解决这个问题，人们提出了R树一些变种.典型的有R+树、R*-树.R+树是由Sellis等于1987年提出的，它结合了R树和KDB的优点，规定R树的所有叶子节点的包围盒不能够有重叠情况[6].如果有存在包围盒重叠的情况，那么就将包围盒划分为多个包围盒.由于接近了包围盒重叠的情况，因此空间实体的检索效率提高了，但是用于维护空间索引的数据量增加了，并且对空间索引结构的更新变得非常的复杂和繁琐.Beckmann等于1990年提出了另外一种R树的变种—R*-树，此种索引结构仍然允许包围盒的空间重叠，但是它优化了节点分裂的方式，提出了强制重新插入的技术，在一定程度上提高了检索的性能，但是作为高维的空间索引，性能仍然不能够达到要求[7].

人们还提出了一些其他的R树索引的变种，如SS树和X树等.SS树的特点是，它的包围盒是圆不是矩形，对邻近元素的查询效率提高了，并且节省了存储空间.但是操作起来非常复杂[8].X树结合了R树和线型数组的优点，在一定程度上减少了包围盒重叠的情况，但由于X树中的超级节点的子节点个数不定，在高维的空间索引中，检索效率不高.

2四叉树和R*树的组合索引

现实世界丰富多彩，空间实体的数量巨大且分布非常的不均匀；嵌入式系统的资源非常有限，存储空间小、处理速度慢，因此作为嵌入式系统的空间索引需要考虑时间和空间的利用率，权衡它们之间的关系.R树系列的索引常常作为空间索引，特别是R*-树，不过虽然R*-树在一定程度上减少了包围盒区域重叠的情况，但是R*-树非叶子节点的包围盒区域重叠情况还是在所难免，并且会随着空间实体数量的增加而增加.综合考虑时空的利用率，提出了一种规则划分和R树索引相结合的空间索引方法—QR*-树.QR*-树结合了四叉树和R*树的优点.首先对空间区域建立四叉树索引，然后在每个小的四叉树节点单元区域中建立R*-树索引，将R*-树索引的搜索空间限定在了一个小的区域当中，减少了R*-树索引中的重叠情况，同时减少了四叉树的数据冗余.

2.1QR*树空间索引结构

QR*-树是一种组合的空间索引，它融合了四叉树和R*-树的思想.QR*-树由一棵区域四叉树QT和m棵R*-树组成，m可表示为

其中：d为空间的维度；k为区域四叉树的深度.区域四叉树有m个节点，分别用QT0，QT1，…，QTm-1表示.此区域四叉树将要研究的空间区域S剖分成了m个k级的子空间，每个子空间等级由高到低分别用S0，S1，…，Sm-1表示，其中S=S0，每个级别的子空间相互之间不相交且并集等于S.

图3　空间剖分实例图Fig.3　The instance of space partition

图4　实例QR*-树空间索引结构图Fig.4　The instance of QR*- tree spatial index structure

非叶子节点：,,…,>

叶子节点：,,…,>

其中：RANK表示该节点在R*-树中的等级；NUM表示包含的子节点或者空间对象的数量；C_Pi为指向该节点孩子节点的指针；MBRi表示孩子节点或者空间实体的最小外接矩形；O_Pi表示空间实体的指针或者空间实体标识.

2.2基本操作

空间索引的优劣通常使用它的更新和查询操作效率来衡量，提出的QR*-树索引结合了两种索引的思想，因此各种操作也略微复杂一点.

2.2.1查找

空间查找中最典型的便是区域查找.首先给定一个查找的区域SS，查找与区域SS相交或者完全落入SS中的空间实体.区域查找必须遍历所有与给定区域SS相交的子空间所对应的R*-树索引.查找的过程为：从QR*树的根节点开始，对每个四叉树节点，遍历其子节点，若子节点对应的空间与SS不相交，则不用再查找该条支路；若子节点对应的空间与SS相交，且SS与对应的空间索引R*-树也相交，那么在该R*-树中继续查找；然后递归的调用如上方法，遍历所有的四叉树节点.

如图3所示，查找与区域SS相交或者完全落入SS中的空间实体，步骤如下：

2)S0的子空间S1，S3，S4，S与区域SS不相交，因此排除它们及其子区域.

查找算法Search(R,SS)(其中：R表示QR*-树的根节点；SS表示要查找的空间区域)：

1) 集合S表示所有根节点的子空间(包括根节点的空间)的并集.

2) 如果S中所有元素都与SS都不相交，则返回没有满足要求的空间实体.

4) 对所有节点递归的调Search(R.C_P,SS).

通过以上查找步骤表明：QR*-树的查找，先从四叉树开始，再到子空间对应的R*树.

2.2.2插入

1) 如果R是叶子节点，则直接调用R*-树的插入算法插入M即可.

2) 如果R是非叶子节点，那么查找R的所有子节点空间，找出包含M的最小的子空间Si，然后调用Insert(Si, M)；若不能够在R的子空间中找到包含M的最小空间，则将M插入到根节点中.

2.2.3删除

1) 如果R为叶子节点，则直接调用R*-树的删除算法删除M即可.

2) 如果R为非叶子节点，那么查找R的所有子节点空间，找出包含M的最小的子空间Si，然后调用Delete(Si,M)；若不能够在R的子空间中找到包含M的最小空间，则从根节点中删除M.

3实验评估

将提出的改进空间索引QR*-树与R*树索引进行对比，验证QR*树作为空间索引的优势.实验环境的硬件平台以S3C2440为微处理器，其主频为400 MHz，其他的硬件配置为：128 M MDDR，256 M Nand Flash和8 G SD卡.软件平台采用Android2.2.实验数据采用杭州的电子地图，实验结果如表1所示，其中leveli表示QR*树索引中四叉树的深度为i.从表1中可以看出：QR*树索引每项所占的存储空间比R*-树略大一点，其存储的开销随着四叉树的增加而增加，但是增加的幅度并没有太多.而对空间索引的各种操作：插入、删除、查询，QR*-树空间索引比R*-树空间索引所涉及的存储空间都要少，并且在四叉树深度不是太大的情况下，四叉树深度越大，各种操作性能越好.

表1　QR*-树与R*-性能对照

4结论

QR*-树索引结合了四叉树和R*-树的优点，是由一棵四叉树和若干棵R*-树组成.由于空间实体的分布往往是不均匀的，某些空间的R*-树索引包含的实体数量会比较少，QR*-树索引所占的存储空间比R*-树略大，但是在插入、删除、查找等方面的性能远远优于R*-树且数量越多，优越性越明显.最后，实验证明QR*-树空间索引非常适合作为嵌入式系数据库的空间索引.

参考文献：

[1]沈永增,王燕,郑晔.基于ARM-Linux导航电子地图数据模型[J].浙江工业大学学报,2010,38(2):186-191.

[2]沈永增,姚萌萌,周巍.空间数据在嵌入式导航系统中的索引[J].计算机系统应用,2010,19(4):85-87.

[3]赵波,边馥苓.面向移动GIS的动态四叉树空间索引算法[J].计算机工程,2007,33(15):86-87.

[4]维基百科.四叉树[EB/OL].[2013-03-13].http://zh.wikipedia.org/wiki/四叉树.

[5]黄晓明,杨红雨.基于R树的空管GIS数据模型索引的设计[J].微计算机信息,2008,24(8):144-146.

[6]SELLIS T K, ROUSSOPOULOS N,FALOUTSOS C. The R+-tree :a dynamic index for multi-dimensional objects[C]//Proceedings of the 13th VLDB.Brighton,England：The Proceedings of the VLDB Endowment，1987:507-518.

[7]BECKMANN N,KRIEGEL H P,SCHNEIDER R, et al. The R*-tree:an efficient and robust access method for points and rectangles[C]//Proceedings of SIGMOD.Anlantic City,New Jersey：ACM SIGMOD,1990：322-331.

[8]薄树奎.空间数据库中最近邻和反最近邻查询技术的研究[D].秦皇岛:燕山大学,2004.

(责任编辑：刘岩)

中图分类号：TP399

文献标志码：A

文章编号：1006-4303(2015)03-0340-06

作者简介：劳洁莹(1980—)，女，浙江杭州人，工程师，主要从事应用研究，E-mail：ljy@zjut.edu.cn.

基金项目：浙江省教育厅科研项目(20130251)

收稿日期：2014-12-15