一种顾及导航数据属性的K-DA树索引方法

杨佳颖，毛 健，崔铁军，刘朋飞

（天津师范大学地理与环境科学学院，天津 300387）

现实世界中有许多数据与空间位置相关，而空间索引是一种依据空间对象的位置和形状或空间对象间某种空间关系，按照一定顺序排列的数据结构，对海量空间数据进行筛选，进而提高空间操作速度和效率的方法.空间索引方法的选择直接决定了地理空间数据检索的整体性能.

导航体验的好坏主要取决于导航数据的显示效率，而导航数据显示的核心是道路.道路又分为不同等级，不同等级的道路是否显示取决于当前用户选择的地图显示范围.当地图显示的范围较大时，导航显示较高等级的道路；当地图显示范围较小时，则显示该区域内的详细道路.传统空间索引往往仅依据当前选择范围指导系统读取该当前范围内所有等级的道路数据，而并不是所需显示等级的道路数据，导致导航数据读取时间过长，效率降低，因此导航数据的读取时间是影响导航数据显示效率的关键.道路等级存在于导航数据的属性中，如果能在传统空间索引的检索中加入对道路等级属性的判读，仅读取需要显示的等级道路势必会提高导航数据的显示效率.导航数据的多级显示可以通过划分道路等级来实现，而道路等级信息存在于导航数据的属性中，因此，传统空间索引与属性索引相结合可以在多尺度显示的前提下提高导航数据的索引效率.传统的属性索引依靠关键字来进行检索，多用于B+树索引，它与空间索引是2种不同的索引形式，虽然属性索引和空间索引的发展都已经相对成熟，但二者结合的应用还较少[1-2].现有的空间索引方法通常只考虑空间位置，对于导航数据的多级显示特点未给予足够支持[3-4].本研究从传统空间索引K-D入手，结合导航数据道路等级属性，构建一种顾及属性的空间索引机制，在保证索引效率的同时，减少当数据目标较大时系统产生的数据冗余.

1 传统K-D树空间索引技术

K-D树是Bentley[5]在1975年提出的一种二叉索引树，它支持k维空间点数据，每个K-D树的节点根据大小将所表示的k维空间分为大于节点值和小于节点值两部分，每个节点中都分散存储了空间点数据.此外，K-D树继承了二叉索引树简单、索引效率高的特点.一棵完整的K-D树的节点描述包括中间节点（COUNT，DEPTH，＜CP1，MBR1＞，＜CP2，MBR2＞）和叶子节点（COUNT，DISLEVEL，＜OI1，MBR1＞，＜OI2，MBR2＞，…，＜OIM，MBRM＞）.其中＜OIi，MBRi＞为数据项；OIi为空间对象标识；MBRi为该空间对象在k维空间中的最小外接矩形；CPi和MBRi为索引项，CPi为指向子树根节点的指针，MBRi表示其子树索引空间.COUNT≤M表示该节点中索引项或空间对象的个数，DEPTH表示该节点在树中的深度.若m和M分别为索引项或数据集的最小和最大个数，H为树的深度，N为空间对象总个数，则H∈[logmN，logMN]，LEVEL≤H.K-D树的具体实现形式如图1所示，其中A点为根节点，包含了指向左、右两棵子树的指针；B、C和G为中间节点，包含了指向父节点的指针和指向其左、右两棵子树的指针；D、E、F、H和I为叶节点，包含了指向父节点的指针以及数据的地址等信息.

图1 K-D树的形式Fig.1 Form of K-D tree

K-D树属于动态索引结构，为非平衡树[6].同时，K-D树在每一层的分枝决策都可以通过该层的分辨器对相应对象进行实现，并以此类推，在各维中不断划分，直至某一节点中的点数小于给定的最大点数，结束这种划分.刘宇等[7]对此问题加以研究，对本研究具有一定的指导意义.随着嵌入式导航的快速发展，国内外学者在以上几种空间索引的基础上，结合嵌入式导航数据的特点，进行了一系列研究和改进.刘春等[8]研究了道路数据的空间组织，分析了路网的3个描述层次，并概括了路网的基本组成要素和用来描述路网的数据集，同时采用K-D树进行空间索引和组织，组成路网的主要要素道路节点.由于K-D树实现算法简单，且符合导航数据通过不同等级属性（尤其是道路等级）的对比进行筛选的特点，可以大幅提高空间索引的效率.

2 顾及属性的空间索引构建

2.1 设计思想

根据导航数据中不同等级道路显示取决于当前地图显示范围的特点，在不改变传统空间数据存储结构的前提下，将道路等级属性嵌入到K-D树索引中，在依据用户选择进行检索时，使新空间索引不仅进行空间范围的判断，同时进行简单道路等级的判断，从而进一步减少导航数据的读取量，提高导航数据的显示效率.

2.2 基本算法

K-DA树的构建过程如图2所示.

图2 顾及属性情况下K-DA树的构建过程Fig.2 Construction of the K-DA tree in view of the attributes

（1）首先定义一棵完整的K-D树，这棵树具有传统K-D树索引的形式，叶节点中不带有属性信息（如图2中黑色部分所示）.

（2）在树的叶节点中添加属性信息（如图2中红色部分所示）.

（3）为使属性判定尽量上移，需要从叶子节点开始，递归构建每个节点的属性信息，直至根节点.一般过程为：若同一棵子树的2个叶节点所包含的属性信息一致，则将该属性信息移至这2个叶节点对应的父节点处，如属性信息不一致，则父节点属性为null.如图2中红色部分所示，设H和I两叶节点所包含的属性信息一致，均为att1，则其父节点G的属性信息为att1；而D和E两叶子节点属性信息不同，则其父节点B的属性为null，以此类推直到根节点A.

构建完成后，K-DA树的节点由中间节点（COUNT，DEPTH，＜CP1，MBR1，ATT1＞，＜CP2，MBR2，ATT2＞）和叶子节点（COUNT，DISLEVEL，＜OI1，MBR1，ATT1＞，＜OI2，MBR2，ATT2＞，…，＜OIM，MBRM，ATTM＞）组成.其中＜OIi，MBRi＞为数据项；OIi为空间对象标识；MBRi为该空间对象在k维空间中的最小外接矩形；ATTi为叶节点中储存的属性；＜CPi，MBRi＞为索引项，CPi为指向子树根节点的指针，MBRi代表其子树索引空间；COUNT≤M代表该节点中索引项或空间对象的个数；DEPTH表示该节点在树中的深度.若m和M分别为索引项或数据集的最小和最大个数，H为树的深度，N为空间对象总个数，则H∈[logmN，logMN]，LEVEL≤H.

2.2.1 K-DA树的算法思路

构建K-DA树算法的主要步骤为：

（1）对每个对象构建最小外包矩形：根据外包矩形的构建方法，对每个对象（每条道路）建立最小外包矩形，当有一个对象小于特定值导致最小外包矩形很小时，对它及其相邻的对象放在一起构造最小外接矩形.

（2）构建整体的最小外包矩形：根据已构建好的若干对象的最小外包矩形，通过获取将要包含的最小外包矩形的min x、max x、min y和max y，逐个构造出包含所有对象的最小外包矩形.

（3）构造子树：设定K-DA树的最大深度maxdepth，判定条件为若当前深度小于树的最大深度，叶节点的最小对象数要大于2，且满足外包矩形的面积大于最小阈值或对象列表数大于5，则通过比较当前对象最小外包矩形中点的x1与所得最小外包矩形中点的x2，将x1小于x2的对象放入左子树objBuckets[0]，将x1大于x2的对象放入右子树objBuckets[1]，再分别对左右子树进行类似判断，继续划分左右子树直至叶节点，其中，叶节点中存储了地址和属性信息.

（4）如果不满足判定条件，则当前节点为叶节点.

（5）当节点被判定为叶节点后，将属性嵌入叶节点中，当一棵子树2个叶节点所嵌入的属性相同时，则将叶节点中的属性嵌入至这2个叶节点对应子树的父节点中.具体构建算法为

2.2.2 索引查询过程

（1）构建用户所要求的窗口，从K-DA树的根节点开始由上至下进行递归查询.如有节点的对象不为空（即节点中包含道路对象），则将其判定为叶节点.此时开始依次判断叶节点中道路对象的最小外接矩形是否与用户要求的窗口有相交部分.如果有相交部分，则将该叶节点中的属性（道路等级）与用户要求的属性（道路等级）进行对比.如属性（道路属性）匹配，则将叶节点对应的数据输出；如属性（道路等级）不匹配，则不输出叶节点对应的数据.如果叶节点中道路对象的最小外接矩形与用户要求的窗口没有相交部分，则不输出对应的数据.以上过程将“先读取后判断”转化为“先判断再读取”，避免了冗余数据的读取.

（2）当某节点中的对象为空时（即节点中不包含道路对象），其不是叶节点，而是中间节点，也称非叶节点.在非叶节点的情况下，判断非叶节点的最小外接矩形与用户要求的窗口是否有相交部分.如果有相交部分，则继续判断非叶节点中的属性（道路等级）和用户要求的属性（道路等级）是否匹配.如果属性（道路等级）匹配，则继续向下查询子节点时不需要再对比属性；如果非叶节点中的属性为空，证明该节点2个子节点的属性不一样，则继续向下查询子节点.如果非叶节点的最小外接矩形与用户要求的窗口没有相交部分，则停止查询，依次类推.

以上过程的具体实现算法为

3 实验

3.1 实验方法

（1）硬件条件：实验所用嵌入式设备处理器为四核，运算速度为1.2 GHz；运行内存为2 GB；手机储存为16 GB.

（2）软件条件：java编程软件为eclipse，需Android 4.4.4平台.

（3）数据来源：天津地区的导航数据，其中道路总数99 369条，共分8个等级.

（4）测试方案：为了测评K-DA树的性能，在Android平台分别编写K-D与K-DA树索引方法的java代码.按照查询的空间对象个数，共分8组数据，并对比相同查询范围内，传统索引与顾及属性新索引的耗时.每组数据测试10次，取其平均值作为最终结果.每次实验均需重启程序，避免内存空间对测试结果的影响.

3.2 测试结果与分析

分别取 133、1 334、2 752、4 330、7 167、11 215、14 804和20 424条道路的8组数据进行测试，得到传统索引的耗时分别为 28、121、225、381、1 069、1 585、2 100和3 372 ms，新索引方法的耗时分别为10、41、105、167、350、560、692 和 1 248 ms，结果图 3 所示.

图3 传统索引和新索引耗费的时间对比Fig.3 Comparison of the time spent between traditional and new indexes

由图3可以看出，随着查询空间对象个数的增加，2种空间索引的检索耗时都在增加.这是因为随着查询空间对象数量的增多，索引数据节点的访问次数、数据的读取次数以及属性的判定次数均随之增多，导致耗时增加.但与传统空间索引相比，K-DA在每组查询中的耗时分别约为传统索引花费时间的50%、40%和30%，且随着查询数量的增加，节约的时间更多.其原因主要为

（1）节省读取时间.传统空间索引没有顾及属性，在索引时将所有数据全部读取，并根据用户所给定的索引条件，从全部读取出的数据中筛选出符合条件的信息，再进行显示；而顾及属性的新索引已经将属性信息添加至K-D树的叶节点中，所以在索引时，根据用户给定的索引条件，可以直接筛选出符合要求的叶节点中的属性对应的数据，不用读出全部数据，因此在此环节节省大量时间.

（2）节省检索时间.传统的空间索引在检索时，需要检索所有数据，搜索范围很大.而新的K-DA检索过程中，由于在K-D树的叶节点添加了属性，缩小了需要搜索的范围，所以节约了检索时间，提高了检索的效率.

4 结论

本研究将导航数据道路等级属性与空间索引相结合，研究顾及属性的K-D树空间索引方法，提出的K-DA空间索引机制在传统K-D空间索引的基础上，扩展了属性项，使其在保留传统空间筛选功能的同时，增加了属性判断，减少了数据的冗余读取，读取速度在每组查询中的耗时分别约为传统索引耗时的50%、40%和30%，且随着数据量的增加，K-DA树索引时间与传统索引时间比例更小，索引效率更高.新索引机制不仅可以用于导航数据，还可以用于传统空间数据的索引，且算法不会对传统空间索引的本质产生影响，方法灵活，具有一定的普适性.

参考文献：

[1] 牛红光.基于R树和Petri网的多尺度表达模型研究[D].郑州：信息工程大学，2006.NIU H G.Research on Multi Scale Expression Model Based on R Tree and Petri Net[D].Zhengzhou：Information Engineering University，2006（in Chinese）.

[2]付伟.基于R树的空间索引技术的研究与应用[D].成都：四川大学，2006.FU W.Research and Application of Spatial Indexing Technology Based on RTree[D].Chengdu：Sichuan University，2006（in Chinese）.

[3] 余登峰.基于R树的空间数据索引技术研究与实现[D].武汉：中国地质大学，2006.YU D F.Research and Implementation of Spatial Data Indexing Technology Based on R Tree[D].Wuhan：China University of Geosciences，2006（in Chinese）.

[4]周帆.基于R-树的空间数据索引技术的研究与实现[D].哈尔滨：哈尔滨理工大学，2009.ZHOU F.Research and Implementation of Spatial Data Indexing Technology Based on R-tree[D].Haerbin：Harbin Polytechnic University，2009（in Chinese）.

[5] BENTLY J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM，1975，18（9）：509-517.

[6]阎德超，赵学胜.GIS空间索引方法述评[J].地理与地理信息科学，2004，20（4）：23-26.YAN D C，ZHAO X S.A review of GIS spatial indexing methods[J].Geography and Geographic Information Science，2004，20（4）：23-26（in Chinese）.

[7] 刘宇，熊有伦.基于有界K-D树的最近点搜索方法[J].华中科技大学学报（自然科学版），2008，36（7）：73-76.LIU Y，XIONG Y L.The nearest point search method based on bounded K-D tree[J].Journal of Huazhong University of Science and Technology（Natural Science Edition），2008，36（7）：73-76（in Chinese）.

[8]刘春，史文中，刘大杰.导航电子地图中道路数据的空间索引和组织[J].工程勘察，2003（1）：38-41.LIU C，SHI W Z，LIU D J.Spatial index and organization of road data in navigation electronic map[J].Engineering Investigation，2003（1）：38-41（in Chinese）.