空间数据库实验教程：CP树、R树与度量空间索引介绍

空间索引是从普通索引演化、发展而来，其研究始于20世纪70年代，初始目的是为了提高多属性查询效率。随着空间信息系统的普及与发展，空间数据的海量性特征越来越明显，这推动了空间数据库的大力发展。空间索引作为空间数据库的重要研究内容之一，众多的学者对此进行了深入研究，并且提出了很多空间索引构建方法。从空间索引的演化过程来看，可以把空间索引技术大致分为四大类：基于二叉树、基于B树、基于Hashing和基于空间填充曲线的空间索引。从空间索引结构上可以分为点存储和扩展对象存储两种方式。按照索引是否是线性组织方式，可以将空间索引方法按照如图5-1所示进行分类，大体可以分为四大类，即线性索引、网格索引、树形索引和其他索引。

线性索引是一种最简单直观的索引，但其访问效率一般不高，在大型空间数据库中很少被采用。网格索引的基本思想是将研究区域纵横分成若干个均等的小块，每个小块都作为一个桶，将落在该小块内的地物对象放入该小块对应的桶中。从精度考虑，小块还可细分，直至不可再分为止。当用户进行空间查询时，首先计算出用户查询对象所在网格，然后再在该网格中快速查询所选空间实体，这样就大大加速了空间索引的查询速度。

目前，绝大部分的空间索引都是属于树形索引（图5-1）。树形索引根据空间性质的不同又可以划分为向量空间索引和度量空间索引，目前在三维空间数据管理中比较常用的是向量空间索引。BSP树是一种二叉树，它将空间逐级进行一分为二的划分。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。KDB树是B树向多维空间的一种扩展。它对于多维空间中的点进行索引具有较好的动态特性，删除和增加点对象也可以很方便地实现。其缺点是不直接支持占据一定范围的空间对象，如二维空间中的线和面，三维空间中的线、面、体，该缺点可以通过空间映射或变换的方法部分得到解决。

图5-1　空间索引分类

R树是Guttman于1984年提出的最早支持扩展对象存取方法之一，也是目前应用最为广泛的一种空间索引结构，许多商用空间数据库系统，如Oracle Spatial、IBM DB2Spatial DataBlade、MySQL Spatial Extensions和MapInfo Spatial Ware等均提供对R树的支持，开放源码系统PostgreSQL也实现了R树。近20多年来，许多学者致力于R树的研究，在R树的基础上衍生出了许多变种。比较典型的有R+树、R＊树。

R树是B树在k维上的自然扩展，用空间对象的MBR来近似表达空间对象，根据地物的MBR建立，可直接对空间中占据一定范围的空间对象进行索引。R树兄弟结点对应的空间区域可以重叠，会导致多路查询问题；其查询效率会因重叠区域的增大而大大减弱，在最坏情况下，其时间复杂度甚至会由对数搜索退化成线性搜索。正是这个原因促使了R+树的产生。在R+树中，兄弟结点对应的空间区域没有重叠，克服了R树中多路查询的问题。但它不允许节点空间存在重叠，会导致R+树的结点多次划分、标记，使得插入和删除操作的效率降低。R＊树是最有效的R树变种之一，能对覆盖区域、重叠面积和边界周长进行启发式地优化，并通过重新插入节点重建R树以提高其性能，但重新插入过程繁琐，计算量大，并且经实验表明，对大型复杂地质场景数据处理效果不显著。压缩R树的空间数据集是预先已知的，通过预先对数据进行合理有效的组织，可以保证其具有很高的空间利用率和良好的查询效率，但由于不能进行动态插入和删除，因而应用受到了很大限制。(www.xing528.com)

CP树是一种基于凸多边形的空间索引结构，它是B树在多维空间中的一般化形式。因此，与B树类似，也是一种平衡树，当插入或删除空间对象时，需要对结点进行分裂和合并。CP树的搜索算法与R树类似，是从根结点开始，向下搜索相应的子树，算法递归遍历所有凸多边形与查询窗口相交的子树，当到达叶结点时，边界矩形中的元素被取出并测试其是否与查询矩形相交，所有与查询窗口相交的叶结点即为要查找的空间对象。CP树是一个动态结构，CP树的生成是从空树开始，逐个插入空间对象而得。研究及实验表明，CP树的覆盖范围及重叠区域较R树明显减少，因此，它能有效减少R树中多路径查询的情形。但由于CP树以凸多边形代替MBR参与各种索引运算，大大增加了算法的复杂度，如何将CP树扩展至高维空间的分析、计算，以及如何改进凸多边形的生成算法，以提高查询效率等都是有待研究的问题。

除此之外，随着图像、视频等多媒体海量数据管理需求的涌现，上面提到的很多索引方法都被进行了高维扩展研究，并被大量使用在图像、视频、时间序列等基于内容的查询中。如向量空间索引中的Kd树、R树、X树，度量空间索引中的M树、VA文件等。一般认为，R树奠定了三维或高维空间索引的基本技术框架。此后发展的R＊树完善了R树的节点分裂与动态插入技术，使得R树系列索引更加趋于完善。由于在高维向量空间中进行距离计算的代价很大，随着数据维数的增加，R树的查询性能会迅速下降。

随后出现的度量空间索引，选取一定量的距离参考点来提前计算数据对象到各参考点的距离，按照距离对数据进行索引，查询时根据距离三角不等式来筛选数据，减少计算代价。典型的如M树，采用最优查询候选队列实现KNN查询，对与查询覆盖区域相交的数据区域进行搜索。Ciaccia等（1999）根据数据对象间的距离分布建立了M树的查询代价模型，但是多数度量空间索引对数据的分布考虑不足，仅根据距离三角不等式进行数据过滤，查询效率并不理想。在国内，一些学者也进行了跟进研究，如周学海（2002）等在R＊树上提出了ER树动态索引；冯玉才（2002）等提出了一种基于距离相似索引结构OPT树及其变种；朱庆（2011）等提出了三维R树，此后又对顾及LOD的三维R树进行了改进研究；周向东（2008）等提出了基于聚类分解的高维度量索引B+树；夏宇、朱欣焰（2009）对高维空间索引进行了较为系统的比较研究，并对VA文件等常用高维空间索引进行了改进，使其能用于空间数据相似性查询；何珍文（2013）等提出了基于间隔关系算子的多维时空索引，将时空查询转换成具有高可并行的间隔关系算子，为高维时空索引提供了一种通用可行的解决方案。

在商业软件方面，GIS领域应用现有的商品化软件在处理三维空间索引时大多采用R树。在GIS领域使用最广泛的后台商业数据库是Oracle。Oracle Spatial从Oracle 11g开始支持三维数据的管理，但对三维空间数据操纵的能力还很弱，只能处理简单的单个或复合实体、不规则三角网与点云数据等几种有限的三维数据类型，而且其R树索引方法存在兄弟节点相互重叠和节点尺寸不均匀的问题，也未考虑复杂地质空间场景的连续非均质特征，难以达到理想的三维空间查询效果。所以，Oracle Spatial中的R树虽然也能处理三维空间数据，但更多的是针对二维空间对象的处理。