详述几种常用的栅格数据的空间索引方法

李传江 吴国皎 程 成

（1.河南省地质测绘总院，河南 郑州 450007；2.河南省地质矿产勘查开发局 第五地质勘查院，河南 郑州 450001）

进行空间索引的目的是为了在地理信息系统中对所选中的地理对象快速定位，以提升器空间操作速度以及效率。为此空间索引技术的质量就直接的影响到GIS的整体性能。地理信息索引是通过地理要素的形状、位置、地理对象之间的某种关系，将数据结构按照一定的顺序进行排列，这一过程包括三个部分，即地理对象的标识、指向地理对象的指针以及外接矩形。常用的数据结构有矢量结构与栅格结构，其中栅格数据是在连续铺盖的基础上将连续空间离散化，也就是将整个连续空间覆盖。而矢量法可看作是基于要素的方法，强调离散现象的存在。无论信息系统是一般关系型数据库还是空间型数据库，其根本任务就是进行信息检索查询。目前为止主要的空间索引方法有R树系列、四叉树、固定格网以及K-D-B树等。

1 R树系列空间索引

R树系列从诞生以来经过多年的发展已经相继出现了众多的变形，例如R+树、R3树、Hibert R树以及SR树等一系列。同时以上变形均属于一种平衡树，其结构也与B树类似。R树可以直接的实现对空间中占据一定范围的地理要素进行索引，可以按照几何对象的最小外接矩形MBR进行二维索引或者高维索引。R树的每一个非叶结点均由若干MBR单元构成，而MBR为包含有对应的空间对象的最小矩形。

R树最大的特点是兄弟结点所对应的空间区域可以互相重叠，从而极大地方便了插入以及删除操作，但是也使得空间搜索的效率大为降低。其原因在于空间中存在大量的重叠区域，为此需要经过多条路径的搜索才能得到结果。在这一基础上人们经过探索设计了R+树，这一方法不存在重叠区域，极大地提升了空间搜索效率。但是由于在删除以及插入之前要首先保证兄弟节点所对应的的空间区域不能重叠，为此又降低了插入及删除操作效率。

通过增加空间上邻近的空间对象可以提升R树的查询效果，为此在组织R树的时候可以有意识地让空间对象的远近体现在最近的共同祖先的远近上。但是如何衡量空间对象的聚集成为一个较为复杂的问题，GutTman建议使用面积指标来衡量空间上的聚集，也就是在进行插入操作中选择插入新对象后MBR面积增长最小的结点为根的子树。同样在分裂溢出点时选择各部分的最小包含矩形面积聚集最小结合方式的组合。R树在进行插入操作中将叶结点与非叶结点分开考虑，同时分裂溢出点时的方法更为复杂。针对这一问题提出了Hilbert R树，这一方法利用Hilbert曲线将多维空间对象映射到一维空间，同时利用变换来保持空间聚集的特性。

要实现R树的组合机构最优化是一个复杂的过程，以上提出的改善方法虽然有所改进但依然不能令人满意。例如不同的空间对象插入顺序会得到不同结构R树，同时随着空间对象的插入与删除，最终得到的R树的查询效率的走向不可预知。

2 四叉树空间索引机制

四叉树索引是基于空间划分组织索引的一种机制，通过将已知范围空间划分为四个等空间，如果需要还可以将其中一个或者几个再次进行划分，从而构成了一个四叉树划分空间。

2.1 基于固定网格划分的四叉树索引

N层CELLQTREE所对应的空间构成一个2n×32n的网格，空间对象的ID信息存储于每一个叶子结点中，如果同一父亲的四个兄弟结点都要记录统一ID对象，此时仅需将其记录于该父亲结点上，并按这一规定向上进行。CELLQTREE的构成类似于网格索引，一个网格可以对应多个网络，但是有效地减少了节点的重复记录。为此对于N=2的CELLQTREE空间划分以及空间的插入、删除步骤均较为简单。由于不像R树一样要进行繁复的分裂与重新插入，为此具有较大的优势。此外这种索引方式的查询也很简单，例如当需要检测出某一个多边形及其与之相较的空间对象时，通过CELLQTREE只需要检测出多边形所覆盖的叶结点以及父亲、祖先结点的多有空间对象，在此基础上经过相应的空间运算就可以检测出满足空间要求的对象。CELLQTREE作为满四叉树并采用顺序的数组存储方式，为此其内存耗费仅为链表结构的四分之一，同时由于索引结构可以放在内存中，因而不会耗费I/O。

2.2 Super Map的线性可排序四叉树空间索引

Super Map的线性可排序四叉树空间索引较之前者有两处不同，首先是结点编码方式不同，其次是结点与空间对象的对应关系不同。线性可排序的编码方式首先是将四叉树变为二叉树，然后按照中序遍历的顺序对结点进行编码。进行编码查询时要先根据查询区域得到要搜索结点编号的集合，然后用SQL语句从表中检测出符合要求的空间对象。但是这一方法不足之处在于面临四叉树结构变化时，如果向下再划分一层就需要给所有的结点进行重新编码，从而降低了可排序性四叉树的灵活性。

由此可见，四叉树较之R树有两个优势：首先是插入以及删除较为方便，耗时短；其次通过顺序存储线性表来表示索引降低了内存需要。但是以空间划分来组织索引面临着这类索引的共同问题，即可调节性差。

3 结束语

从以上两种索引方式的论述可见，四叉树空间索引较之R树具有较大的优势。首先查询速度快，其次插入以及删除方便；同时由于四叉树是以空间划分来组织索引结构的索引机制，为此需要在索引之前指导空间对象所分布的范围。但是R树也有其独特之处，例如通过数据组织索引使得索引具有很大灵活性，无需知道整个空间对象所在的范围即可建立空间索引。

[1]陈述彭.鲁学军，周成虎.地理信息系统导论[M].北京：科学出版社，1999.

[2]蔡少华.GIS图形空间关系的研究与实践[D].郑州：解放军测绘学院，1998.

[3]龚健雅.GIS中矢量栅格一体化面向目标数据模型的研究[D].武汉：武汉测绘科技大学，1991.