第七章空间索引结构
空间索引技术是从空间数据库中获取空间数据的有效方法，是提高空间数据查询和各种空 间分析效率的关键技术。建立空间索引是为了缩小空间数据的搜索范围，以便在空间数据查询 时不必遍历整个空间数据集，只访问空间索引数据便可快速得到一条特定的空间查询语句所请 求的空间数据，或得到包含全部空间查询结果的一个较小的空间数据集。
索引文件中包含的数据称为索引数据，索引结构是索引数据的数据结构及索引创建与维护 算法的总称。空间索引结构是按照空间数据在空间分布上的特性来组织和存储索引数据的索引 结构。一种良好的空间索引结构应满足下列三个要求：
一、 存储效率高：相对于被索引的数据集而言，索引数据的数据量应尽量小。否则，访问 索引数据可能成为数据查询与更新的效率瓶颈。
二、 查询效率高：空间索引结构需要选择良好的索引数据结构，设计具体的基于索引的空 间访问方法（SAM Spatial Access Method），必须能够高效的实现以下几种基于位置的查询：
1、 点选择：从数据集中找出包含给定点的所有空间对象。 2、 范围查询：查询与给定对象间的距离小于某个给定值的所有空间对象。
3、 区域（窗口）查询：查找含在区域内、与区域相交或部分位于区域中的所有空间对象。 窗口是一个特殊的区域，窗口查询是 GIS中最常用、最基本的查询。
4、 K-最邻近查询：给定一个参照对象（点、线或区域）
，查询距离参照对象最近的 K - 1
个空间对象。
5、 空间关系查询：相交、相邻、包含等拓扑关系查询，方位关系和基于距离的各种查询。 6、 其他查询：将满足一定空间条件的两个空间对象集合进行空间连接，空间集合运算等也 是- 一种空间访问。
三、 更新效率高：许多 GIS应用中会涉及海量且不断变化的空间数据集。数据集中数据对 象的增加、修改和删除将直接导致索引数据的更新， 索引数据与被索引的数据集必须保持一致， 才能保证基于索引数据的查询结果的正确性。索引数据的更新操作包括：插入索引项，将新数
据对象的索引项添加到索引数据中；删除索引项，把数据对象的索引项从索引数据中删除；修 改索引项，在索引数据中先删除再增加该数据对象的索弓I。数据集经常变化时，要求其索引数 据的更新开销不要很大，特别要避免更新时引起的索引重组。因此，需要考虑新增索引项和删 除索引项时，索引结构的快速更新能力。
很难设计一种空间索引结构同时能够提供高效的存储、高效的查询和高效的更新，实际应 用中总是牺牲某些方面的效率来换取另外方面的效率。
索引结构可分为静态索引和动态索引结构。静态索引结构针对静态不变的数据，索引只建 一次，不需要更新，强调索引数据的存储效率和查询效率，不强调索引更新的效率。动态索引 结构强调数据在动态更新过程中保证较高的查询效率和索引空间存储效率，往往以牺牲索引更 新效率为代价，这种牺牲是有限度的。
索引结构还分为内存索引和外存索引，外存索引需要考虑磁盘页面访问的效率瓶颈问题。 这里主要研究面向海量空间数据的、 2D空间对象的外存索引结构。
7.1空间索引分类
非空间数据库中存储的数据为结构化数据，通常以主关键字建立索引文件，以非主属性建 立倒排文件，索引项按自然数序列或字符顺序排列。空间数据库存储的数据为结构复杂、不能 完全结构化的空间数据，为了支持基于位置的各类查询和分析，需要以表示空间对象几何形状 的坐标数据为索引字段来建立空间索引。非空间数据库的索引结构不能满足空间数据库的索引 需求，必须研究和设计专用的空间索引结构和基于索引的空间访问方法（ SAM Spatial Access
Method )。
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所示。
C 7 ) （237）（
C 15 ) 13）C 15 23 }
C 2 3 7 ） c 9 10 13 15 ）
（n）
1、 索引的查找
⑹ 图 7-1 B 树：（a）插入［23,OID］前,（b）插入［23,OID］后
索引查找从树根开始，通过比较关键字大小，查找相应的子树，直到叶结点。一次查找中 读入物理页的数量等于树的深度，复杂度是被索引数据集大小的对数。
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 （ Minimal Bounding Box ）或
MBR（Minimum Bounding Rectangle） 就是空间对象几何形状的一种近似表示。
以 [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 。基于对象的分割不是空间的一种完全划分。
三、 空间索引结构的具体分类 综合现有研究及参考文献，可将主要的空间索引技术分类如下：
空间索引结构(学生)分解
