空间索引结构(学生)

第七章空间索引结构空间索引技术是从空间数据库中获取空间数据的有效方法，是提高空间数据查询和各种空间分析效率的关键技术。建立空间索引是为了缩小空间数据的搜索范围，以便在空间数据查询时不必遍历整个空间数据集，只访问空间索引数据便可快速得到一条特定的空间查询语句所请求的空间数据，或得到包含全部空间查询结果的一个较小的空间数据集。索引文件中包含的数据称为索引数据，索引结构是索引数据的数据结构及索引创建与维护算法的总称。空间索引结构是按照空间数据在空间分布上的特性来组织和存储索引数据的索引结构。一种良好的空间索引结构应满足下列三个要求：一、存储效率高：相对于被索引的数据集而言，索引数据的数据量应尽量小。否则，访问索引数据可能成为数据查询与更新的效率瓶颈。二、查询效率高：空间索引结构需要选择良好的索引数据结构，设计具体的基于索引的空间访问方法（SAMSpatialAccessMethod），必须能够高效的实现以下几种基于位置的查询：1、点选择：从数据集中找出包含给定点的所有空间对象。2、范围查询：查询与给定对象间的距离小于某个给定值的所有空间对象。3、区域（窗口）查询：查找含在区域内、与区域相交或部分位于区域中的所有空间对象。窗口是一个特殊的区域，窗口查询是GIS中最常用、最基本的查询。4、K-最邻近查询：给定一个参照对象（点、线或区域），查询距离参照对象最近的K1个空间对象。5、空间关系查询：相交、相邻、包含等拓扑关系查询，方位关系和基于距离的各种查询。6、其他查询：将满足一定空间条件的两个空间对象集合进行空间连接，空间集合运算等也是一种空间访问。三、更新效率高：许多GIS应用中会涉及海量且不断变化的空间数据集。数据集中数据对象的增加、修改和删除将直接导致索引数据的更新，索引数据与被索引的数据集必须保持一致，才能保证基于索引数据的查询结果的正确性。索引数据的更新操作包括：插入索引项，将新数据对象的索引项添加到索引数据中；删除索引项，把数据对象的索引项从索引数据中删除；修改索引项，在索引数据中先删除再增加该数据对象的索引。数据集经常变化时，要求其索引数据的更新开销不要很大，特别要避免更新时引起的索引重组。因此，需要考虑新增索引项和删除索引项时，索引结构的快速更新能力。很难设计一种空间索引结构同时能够提供高效的存储、高效的查询和高效的更新，实际应用中总是牺牲某些方面的效率来换取另外方面的效率。索引结构可分为静态索引和动态索引结构。静态索引结构针对静态不变的数据，索引只建一次，不需要更新，强调索引数据的存储效率和查询效率，不强调索引更新的效率。动态索引结构强调数据在动态更新过程中保证较高的查询效率和索引空间存储效率，往往以牺牲索引更新效率为代价，这种牺牲是有限度的。索引结构还分为内存索引和外存索引，外存索引需要考虑磁盘页面访问的效率瓶颈问题。这里主要研究面向海量空间数据的、2D空间对象的外存索引结构。7.1空间索引分类非空间数据库中存储的数据为结构化数据，通常以主关键字建立索引文件，以非主属性建立倒排文件，索引项按自然数序列或字符顺序排列。空间数据库存储的数据为结构复杂、不能完全结构化的空间数据，为了支持基于位置的各类查询和分析，需要以表示空间对象几何形状的坐标数据为索引字段来建立空间索引。非空间数据库的索引结构不能满足空间数据库的索引需求，必须研究和设计专用的空间索引结构和基于索引的空间访问方法（SAMSpatialAccessMethod）。7.1.1非空间索引与SAM非空间索引结构一般为B树和hash文件结构，这种索引结构可以准确的定位和查找所需数据，复杂度为对数函数。一、索引的假设和要求（一）B树和hash文件结构遵从的假设1、被索引的数据集所占空间远远大于内存空间；2、磁盘访问比内存访问慢得多；3、对象按物理页分组，页是内存和外存交换数据的单位（大小为1K到4K），读/写一页为一次I/O操作。4、访问一个具体对象时，该对象所在页可能在内存中，或不在内存中需要调入内存。非空间数据库的索引操作中，CPU时间与I/O操作时间相比可忽略不计，访问方法的效率用I/O数衡量。空间索引的操作中，有些情况下需考虑CPU时间，但不考虑页的缓存，使用一页时才调入内存。（二）SAM应满足的要求空间索引是依据空间对象的空间位置、几何形状及空间分布特征，按一定顺序排列的一种数据结构。空间访问方法SAM的设计基于B树和hash表相同的假设，但B树和hash表均不适合于空间索引。SAM应满足下列要求：1、时间复杂度：点选择和区域查询应具有线性复杂度。SAM访问一个数据集合的子集所用的时间，应小于以集合元素数量的线性函数为复杂度的序列查找算法。2、空间复杂度：如果被索引的集合占据n页，索引的大小应该是n级的。3、空间索引结构必须考虑动态性：适合于空间索引项的增加和删除，大多数空间索引结构在索引查找方面是高效的，复杂度为被索引集合中元素数量的对数。二、非空间数据库中的B+树索引B+树是B树的一个变种，B+树是一个平衡树，所有叶子位于相同的深度。B+树的每个结点为一个索引单元，存贮多个索引项，对应磁盘上一个物理页，每个索引单元存贮索引项的数量由物理页容量和索引项大小来确定。结点上每个索引项的内容为[KEY，PRT]，叶结点的PRT指向关键字为KEY的数据对象，非叶结点的PRT指向孩子结点。每个结点中的索引项按关键字升序排序，非叶结点中每个索引项左子树中的关键字小于等于该索引项的关键字，右子树中的关键字大于该索引项的关键字。图7.1为一个B+树索引结构的例子：例子：有一组关键字集合{2，3，7，9，10，13，15}构成的索引文件，索引数据采用B+树结构来组织。假设每个结点最多存贮四个索引项，结果如图7.1a所示。图7-1B树：（a）插入[23,OID]前，(b)插入[23,OID]后1、索引的查找索引查找从树根开始，通过比较关键字大小，查找相应的子树，直到叶结点。一次查找中读入物理页的数量等于树的深度，复杂度是被索引数据集大小的对数。2、插入索引项插入新的索引项E=[23，PRT]。1）从根结点搜索，该索引项应插入到第二个叶子中。2）插入时该叶结点满了，必须分裂，原结点的一部分索引项保留在原索引单元内（9，10，13），另一部分索引项和E形成一个新的叶结点（15，23）。3）按照B+树的定义，应将左边叶结点（9，10，13）中最右边一个关键字13插入父结点中，插入新索引项后的B+树如图7.1b所示，仍然是平衡树。B+树是一种较好的外存空间索引结构，时间复杂度是数据集合中元素数量的对数，空间复杂度使索引空间的利用率为50%以上，动态性能支持随机插入和删除。B+树的上述优点是以关键字有序为基础的，空间数据不具备这样的特点，不能简单照搬。7.1.2空间索引分类空间索引技术的基本原理是采用基于空间位置或基于空间对象的分割方法，把研究查询空间划分为若干区域，每个区域为一个索引单元，存储多个空间对象的索引项。考虑到空间位置上的邻近度，按照空间位置邻近的对象其索引项的位置也应该邻近的原则来组织空间索引数据。空间索引支持的最主要的查询是定位查询和窗口查询。一、空间对象的近似空间对象的几何形状错综复杂，表示几何形状的坐标序列是变长的，直接以坐标序列为索引字段建立的空间索引，其索引项很长且变长。为此，需要将空间对象的形状进行某种近似，平行于坐标轴的、包含特定空间对象的最小外接矩形MBB（MinimalBoundingBox）或MBR(MinimumBoundingRectangle)就是空间对象几何形状的一种近似表示。以[MBB，OID]为索引字段建立空间索引，每个空间索引项具有固定的长度，最少包含三种成分[MBB，OID，PRT]，OID为对象标识，MBB为相应对象的最小外接矩形，PRT为指向几何数据的指针，OID直接将MBB映射到存放几何形状和属性的物理页。空间索引介于空间计算算法与空间数据之间，用于过滤大量与空间计算无关的数据，以提高空间操作的效率。SAM只加速了索引项中MBB的查找（过滤），在此基础上还要对几何图形进行精确查找。基于空间索引的空间查询分两步完成，第一步利用空间索引结构和空间访问方法SAM对数据集进行过滤（初选），在索引表中查找满足查询条件的MBB，结果为对象的一个超集（多个OID）。第二步对初选结果进行准确查找，在超集中通过空间计算算法，求取满足查询条件的精确对象。二、空间分割与空间索引单元划分建立空间索引的第一步是按照一定的方式将被查询空间分割成多个索引单元。有两种对空间进行划分的方法，形成两大类空间索引结构，很多SAM都属于这两类结构之一。1、空间驱动结构：采用基于空间位置的分割方法，将研究区域的2D空间进行完全划分，划分为多个矩形或正方形范围，每个范围定义为一个空间索引单元，对象在2D空间的分布是独立的，对象按一定原则分配到不同的矩形单元。也可将研究区域的2D空间划分为多个凸多边形范围，每个凸多边形近似表示一个空间对象的几何形状。例如：将研究空间用规则的正方形格网进行分割，每个正方形网格为一个空间索引单元，索引多个空间对象。空间对象覆盖多个相邻的空间索引单元时，在其覆盖的每个索引单元中各有一个索引项，索引项中包含空间对象标识OID。2、数据驱动结构：是一种基于对象的分割，对2D研究区域的空间分割直接由分布在其中的空间对象来确定，对空间对象集合进行分割。每个空间对象用它的最小外接矩形MBB近似表示，每个空间索引单元的形状也是一个矩形区域，它包含多个空间对象的最小外接矩形MBB。空间索引单元的面积大小取决于其索引的空间对象集合的面积、形状和分布，索引单元中存储空间对象的最小外接矩形MBB。基于对象的分割不是空间的一种完全划分。三、空间索引结构的具体分类综合现有研究及参考文献，可将主要的空间索引技术分类如下：图7-2空间索引分类索引结构中，如果将2D或3D分布的空间索引单元，按照一定的方式组织成线性形式，相应的索引称为线性空间索引。相反，以非线性形式来组织空间索引单元，相应的索引称为非线性空间索引。一、线性索引线性索引主要有线性映射结构与线性四叉树。1、线性映射结构：首先，用均匀或不均匀的正方形格网对被索引空间区域进行划分；然后，采用填充曲线对索引空间进行填充（如HilbertCurve曲线），取填充曲线编码为索引单元的序号，将索引单元按序号排序建立线性索引结构。这里，空间划分是基于位置的完全划分，建立的索引为空间驱动的、线性组织的、规则的网格空间索引结构。2、线性四叉树：每一个空间对象用其MBB近似表示，对含有MBB集合的空间进行四叉树划分，划分后的不均匀网格作为索引单元，每个单元分别编号，叶结点根据编号组织成B-树结构，这种结构叫线性四叉树。二、非线性索引非线性空间索引按索引的逻辑组织方式分成网格空间索引和基于树的空间索引。（一）网格空间索引网格空间索引简称称网格索引，是基于位置的空间驱动结构。它将被索引空间用平行于坐标轴的横竖线条划分成大小相等或不等的网格，每个网格为一个索引单元，记录每个网格所包含的多个对象的标识。空间查询时，先计算出对象所在的网格，然后在网格中快速查询对象。网格索引分为均匀网格索引和网格文件索引，可以索引点对象及用MBB近似的其他类型的空间对象。网格索引以二维数组结构来存储，是一种非线性空间索引结构。（二）基于树的空间索引基于树的空间索引是一种基于对象的数据驱动结构。首先采用某种几何形状近似算法，将被索引空间中的空间对象表示为其近似体，然后将近似体按确定规则组织成树形结构。基于树的空间索引按几何形状近似技术的不同可分为基于凸多边形的空间索引、基于约束的空间索引和基于MBB的空间索引。1、基于凸多边形的空间索引R树点对象线性四叉树空间索引非线性索引线性索引网格空间索引基于树的索引基于凸多边形基于约束基于MBBR树系列Ｏ树CELL系列BSP树CELL树CP树OS-CELL树PR树GPR树LUR树R+树R*树R-Link树Qr树Sr树TV树X树SDR树线性映射结构网格文件基于凸多边形的空间索引又称划分树结构，它将被索引空间划