一种支持多版本空间数据的索引方法

张亚军，华一新

(信息工程大学地理空间信息学院，河南郑州450052)

一、引 言

在具有版本管理功能的地理信息系统中，多版本空间数据一般采用空间数据库来管理［1-2］。随着空间数据库的不断更新，空间数据在不同时间段对应着不同的版本［3］(如图1所示)。

图1 多版本空间数据示意图

为了实现对不同版本空间数据的快速检索，建立其空间数据库索引是关键。

二、现状分析

目前，空间数据库常用的索引方法有格网索引、四叉树索引和R树系列索引3种［4-5］，这方面的研究相对比较成熟，基本思想都是对研究的空间区域进行划分(如图2所示)，用最小外接矩形(MBR)来代替空间对象的形态参与计算，算出每个划分区域所对应的索引号以及空间对象所对应的索引号。其中区域划分和索引号编码是算法的核心，研究成果较多［4-8］，本文不再赘述。

图2 区域划分示意图

由上图可以看出，格网索引和四叉树索引属于静态索引，在计算索引号时空间区域大小保持不变，用户在进行空间数据更新导致版本提升时不能超出该区域范围，否则区域大小的改变会引起整个索引的重建。图3以格网索引为例，数据库更新前线状目标 L 由点 P0、P1、P2、P3、P4、P5组成，原始空间区域为R0，计算其经过的格网如图中所示。如果用户修改线状目标L(例如增加点P6)得到一个新版本，则修改后的空间区域变为R1，此时区域R0中已经计算的索引号就会随着区域R1的产生而变化，极端情况下需要对整个空间区域中的目标进行索引重建。因此，对多版本空间数据的索引属于动态索引，其索引随版本提升而动态变化。

由于R树索引对空间区域采用的是动态划分，因此比较适合随时间动态变化数据库的索引，研究也较多［9-10］。但对于格网和四叉树而言，就必须解决静态与动态之间的平衡。为此本文对格网和四叉树索引算法进行了改进，提出了一种支持多版本空间数据的索引方法——固定网格大小空间索引。

三、固定网格大小空间索引

1.索引的基本思想

固定网格大小空间索引方法的基本思想是：根据原始数据大小来确定网格大小，并记录数据的中心点或质心的坐标;然后根据由里向外“螺旋形编码”的原则对每一个空间数据进行映射编码(如图4所示)。

图4 固定网格大小索引方法

对于格网索引，因为编码是由里向外的，并且中心点或质心固定，所以对数据库中的空间数据来说，只要其位置不变，索引号也就永远不变且唯一;如果其位置发生改变则可以重新计算得到一个新的索引编码，这种编码在其生命周期中也是不变的。除空间数据本身的修改外，还存在另一应用环境，就是新增加一个地理实体。依据“固定网格大小索引”的思路，该新增加的数据在整个空间区域的划分中也唯一对应一个索引编码，索引的关键就是每个格网及对应编码的解算。因此对格网索引来说，采用该方法能有效解决目标动态变化的索引问题，较好地满足了数据库中多版本空间数据索引维护要求。

对于四叉树索引，传统四叉树编码是递归地把空间区域分成四等分。但固定网格大小索引思想是空间区域大小可以任意变化，因此必须采用反向区域划分方法(如图5所示)。

图5 四叉树反向区域划分

图中显示了两层和三层的四叉树反向区域划分方法，反向区域划分是从四叉树的最低层进行区域划分，最低层划分的基准格子大小为“固定格网大小”，逐步向上，每向上一层基准格子大小乘以2，并且每一层都采用固定网格大小索引的编码方式。四叉树的根结点编码永远为0，其他层每个结点的编码算法描述如下。

假设某个结点位于四叉树的第n层，其固定网格大小索引计算的编码为num，那它的编码Index为：Index=n*para+num，其中para是常量，取值不小于四叉树最低层最大的编码值。通过编码算法就可计算出数据库中每个空间数据所对应的编码或索引号，计算的方向是从下到上、由里向外。

2.方法的实现过程

通过上面内容的分析可知，固定网格大小空间索引方法的实现主要是数据库中空间数据索引号的建立、更新和删除3个主要部分。

(1)数据库中索引原理

与文件空间索引不同，基于数据库的空间索引不能直接操纵磁盘，很难对数据库内核中索引算法进行改进，只能通过映射的索引号间接实现对空间数据的索引(如图6所示)。

图6 数据库中空间索引建立示意图

图中空间数据库中的土地利用数据表(假设表名为soil)通过空间数据到索引号的映射算法计算出每块土地数据所对应的索引号，并记录在表中的SDI字段中。如果GIS客户端计算出所查询空间范围所对应的SDI值(假设为66)，那么在GIS平台就可以通过SQL语句“select* from soil where SDI=66”来检索数据库中所需地块数据。

由此可见，在数据库中，空间数据索引的关键就是设置某一列索引号的值，

(2)数据库中索引号的建立与更新

对于格网和四叉树索引来说，该方法使得索引号的计算只与空间目标本身有关，而与地理数据库中数据量无关，依据该索引方法可以直接计算出空间目标的索引号。假设空间目标的MBR为B=(W，H)，空间区域更新后的 MBR 为R=(Rw，Rh)，固定格网大小为b=(w，h)。以四叉树索引为例，计算索引号的步骤为：

(1)计算四叉树索引的层次L

(2)计算目标对应的索引号I

利用反向区域划分的方法，计算目标对应的最小四叉树层次l为

然后利用“从下到上、由里向外”的原则，从l到L层计算当前层次所对应的格网大小及对应的编码值，并判断目标的MBR是否完全落入所计算的格网中，如果落入则算法终止，此时格网对应的编码值，即为目标所对应的索引号。

算法的流程图如图7所示。

图7 计算目标索引号算法流程图

在数据库中索引号的建立和更新相对比较简单。假设存储的表为T1，空间目标的唯一标识为f1，计算的索引号为i1，那么就可以通过SQL语句“update T1set sdi=i1where fid=f1”建立和更新目标的索引号。

(3)数据库中索引号的删除

对于采用固定网格大小的空间索引的数据库来说，空间目标的删除与其他目标索引号没有任何关系，因此直接删除目标即可，不需要附加任何其他的索引号更新操作。

3.方法的适用度

固定网格大小的空间索引方法是在空间目标不断更新的需求下提出的，因此比较适合于随时间不断变化的空间数据库索引的构建。不管空间数据库的目标的增加，还是历史数据的保留，都能够很好地适应空间目标对数据库索引的要求。

对于格网索引，为了使目标索引号保持唯一，对于点状目标比较适用。四叉树对于线状和面状目标适用度更好。

四、效率分析

在基于数据库的海量空间数据更新应用中，通过固定网格大小的空间索引方法，本文采用MySQL5.0数据库，对全国城镇、交通、政区和水系4类数据进行试验，其数据特征如表1所示。

表1 试验数据的特征

试验的功能是3种更新操作，即增加、删除和平移某个空间目标，前置条件为3种操作都会引起整个空间区域的变化，与常用格网、四叉树索引维护所消耗时间对比如表2所示。

表2 索引维护所消耗时间对比

从表2可以看出，采用固定网格索引方法明显要比不采用要快得多。

对于固定网格大小空间索引方法，同一种数据采用不同索引方式，在数据处理效率上存在一定的差异。在上面试验条件的基础上，以交通数据为例，试验结果如表3所示(时间单位为秒)。

表3 同种数据采用不同索引效率对比

从表3可以看出，对于同种数据采用不同的索引方法，对检索空间数据的效率影响不大，但对索引的构建，索引的更新效率影响明显，最大相差可达数十倍之多。

五、结 论

针对版本管理中空间数据库动态性的特点，提出了固定网格大小空间索引方法，并对该方法的执行效率做了试验，得出以下几个方面的结论：

1)该索引算法针对的是空间数据库动态更新时索引的构建，因此适合对多版本空间数据的索引。

2)索引算法的选择对多版本空间数据的访问效率影响不大，但对于索引的建立和维护影响较深。

3)索引编码的选择对访问效率没有影响，只影响构建检索语句(SQL语句)的长度。

试验结论表明该方法提高了GIS系统对空间数据库中多版本空间数据处理能力和获取效率，达到快速响应用户空间查询的目的。

［1］ESRI.Modelling Our World［M］.USA：ESRI Press，1999.

［2］万波，周顺平，陈波，等.基于 DBMS的MAPGIS7.0版本管理的设计与实现［J］.地球科学：中国地质大学学报，2006，31(5)：600-604.

［3］张亚军，赵军喜，丁昊.空间数据版本管理的体系结构研究［J］.测绘科学，2011，36(6)：155-157.

［4］PAUL A L，MICHAEL FG，DAVID J M，et al.地理信息系统科学［M］.北京：机械工业出版社，2007：205.

［5］SHASHI S，SANJAY C，谢昆青，等.空间数据库［M］.北京：机械工业出版社，2003：114.

［6］顾军.R-Tree空间索引的优化研究［D］.南京：南京师范大学，2002.

［7］吴敏君，郭永洪，陈天滋.一种有效的混合空间索引机制［J］.计算机工程与应用，2006(29)：193-197.

［8］郭菁，郭薇，胡志勇.大型GIS空间数据库的有效索引结构 QR树［J］.武汉大学学报：信息科学版，2003，28(3)：306-310.

［9］尹章才，李霖.基于快照-增量的时空索引机制研究［J］.测绘学报，2005，34(3)：257-261.

［10］尹章才，李霖，王琤.基于HR-树扩展的时空索引机制研究［J］.武汉大学学报：信息科学版，2007，32(12)：1131-1134.