空间索引结构1(遥感)

1、空间索引结构 空间索引技术是提高空间数据查询和各种空间索引技术是提高空间数据查询和各种空间分析效率的关键技术。空间索引可缩小空间分析效率的关键技术。空间索引可缩小空间数据的搜索范围，使访问不需要遍历整空间数据的搜索范围，使访问不需要遍历整个空间数据集。个空间数据集。索引文件中的数据称为索引数据，索引结索引文件中的数据称为索引数据，索引结构是索引数据的数据结构及索引创建与维护构是索引数据的数据结构及索引创建与维护算法的总称。算法的总称。空间索引结构是按照空间数据在空间分布空间索引结构是按照空间数据在空间分布上的特性来组织和存储索引数据的索引结构。上的特性来组织和存储索引数据的索引结构。空间索引结

2、构 u空间索引结构应满足下列三个要求：空间索引结构应满足下列三个要求：一、存储效率高：一、存储效率高：相对于被索引的数据集而言，索引数据的数据量应尽量小。否则，相对于被索引的数据集而言，索引数据的数据量应尽量小。否则，访问索引数据可能成为数据查询与更新的效率瓶颈。访问索引数据可能成为数据查询与更新的效率瓶颈。二、查询效率高：二、查询效率高：选择良好的索引数据结构，设计具体的基于索引的空间访问方法选择良好的索引数据结构，设计具体的基于索引的空间访问方法（SAM Spatial Access Method），高效实现以下的查询：），高效实现以下的查询：1、点选择：从数据集中找出包含给定点的所有空间

3、对象。、点选择：从数据集中找出包含给定点的所有空间对象。2、范围查询：查询与给定对象间的距离小于某个给定值的所有、范围查询：查询与给定对象间的距离小于某个给定值的所有空间对象。空间对象。空间索引结构 3、区域（窗口）查询：查找含在区域内、与区域相交或部、区域（窗口）查询：查找含在区域内、与区域相交或部分位于区域中的所有空间对象，窗口是一个特殊的区域。分位于区域中的所有空间对象，窗口是一个特殊的区域。 4、K-最邻近查询：给定一个参照对象（点、线或区域），最邻近查询：给定一个参照对象（点、线或区域），查询距离参照对象最近的查询距离参照对象最近的K 1个空间对象。个空间对象。 5、空间关系查询：相

4、交、相邻、包含等拓扑关系查询，方、空间关系查询：相交、相邻、包含等拓扑关系查询，方位关系和基于距离的各种查询。位关系和基于距离的各种查询。 6、其他查询：将满足一定空间条件的两个空间对象集合进、其他查询：将满足一定空间条件的两个空间对象集合进行空间连接，空间集合运算等也是一种空间访问。行空间连接，空间集合运算等也是一种空间访问。空间索引结构 三、更新效率高：三、更新效率高：数据对象的增加、修改和删除将导致索引数据更新，索引数据与数据对象的增加、修改和删除将导致索引数据更新，索引数据与被索引的数据集必须保持一致。被索引的数据集必须保持一致。索引数据的更新操作包括：插入索引项、删除索引项和修改索引

5、索引数据的更新操作包括：插入索引项、删除索引项和修改索引项（先删除再增加）。数据集经常变化时，需要考虑新增索引项和删项（先删除再增加）。数据集经常变化时，需要考虑新增索引项和删除索引项时，索引结构的快速更新能力。除索引项时，索引结构的快速更新能力。很难设计一种空间索引结构同时能提供高效的存储、高效的查询很难设计一种空间索引结构同时能提供高效的存储、高效的查询和高效的更新，实际应用中总是牺牲某些方面的效率来换取另外方面和高效的更新，实际应用中总是牺牲某些方面的效率来换取另外方面的效率。的效率。索引结构可分为静态索引和动态索引结构，还分为内存索引和外索引结构可分为静态索引和动态索引结构，还分为内存

6、索引和外存索引，外存索引需要考虑磁盘页面访问的效率瓶颈问题。存索引，外存索引需要考虑磁盘页面访问的效率瓶颈问题。 空间索引分类非空间数据库中存储的数据为结构化数据，通常以主关键字建立索引文件，以非主属性建立倒排文件，索引项按自然数序列或字符顺序排列。空间数据库存储的数据为结构复杂、不能完全结构化的空间数据，为了支持基于位置的各类查询和分析，需要以表示空间对象几何形状的坐标数据为索引字段来建立空间索引。非空间数据库的索引结构不能满足空间数据库的索引需求，必须研究和设计专用的空间索引结构和基于索引的空间访问方法（SAM Spatial Access Method）。u 非空间索引与非空间索引与SA

7、M非空间索引结构一般为B树和hash文件结构，这种索引结构可以准确的定位和查找所需数据，复杂度为对数函数。一、索引的假设和要求一、索引的假设和要求（一）B树和hash文件结构遵从的假设1、被索引的数据集所占空间远远大于内存空间；2、磁盘访问比内存访问慢得多；3、对象按物理页分组，页是内存和外存交换数据的单位（大小为1K到4K），读/写一页为一次I/O操作。4、访问一个具体对象时，该对象所在页可能在内存中，或不在内存中需要调入内存。非空间数据库的索引操作中，CPU时间与I/O操作时间相比可忽略不计，访问方法的效率用I/O数衡量。空间索引的操作中，有些情况下需考虑CPU时间，但不考虑页的缓存，使用

8、一页时才调入内存。（二）SAM应满足的要求空间索引是依据空间对象的空间位置、几何形状及空间分布特征，按一定顺序排列的一种数据结构。空间访问方法SAM的设计基于B树和hash表相同的假设，但B树和hash表均不适合于空间索引。SAM应满足下列要求：1、时间复杂度：点选择和区域查询应具有线性复杂度。SAM访问一个数据集合的子集所用的时间，应小于以集合元素数量的线性函数为复杂度的序列查找算法。2、空间复杂度：如果被索引的集合占据n页，索引的大小应该是n级的。3、空间索引结构必须考虑动态性：适合于空间索引项的增加和删除，大多数空间索引结构在索引查找方面是高效的，复杂度为被索引集合中元素数量的对数。二、

9、非空间数据库中的二、非空间数据库中的B+树索引树索引 B+树是B树的一个变种，B+树是一个平衡树，所有叶子位于相同的深度。B+树的每个结点为一个索引单元，存贮多个索引项，对应磁盘上一个物理页，每个索引单元存贮索引项的数量由物理页容量和索引项大小来确定。结点上每个索引项的内容为KEY，PRT，叶结点的PRT指向关键字为KEY的数据对象，非叶结点的PRT指向孩子结点。每个结点中的索引项按关键字升序排序，非叶结点中每个索引项左子树中的关键字小于等于该索引项的关键字，右子树中的关键字大于该索引项的关键字。图7.1为一个B+树索引结构的例子：例子：有一组关键字集合2，3，7，9，10，13，15构成的索

10、引文件， 索引数据采用B+树结构来组织。假设每个结点最多存贮四个索引项，结果如图7.1a所示。 1、索引的查找索引查找从树根开始，通过比较关键字大小，查找相应的子树，直到叶结点。一次查找中读入物理页的数量等于树的深度，复杂度是被索引数据集大小的对数。2、插入索引项插入新的索引项E = 23，PRT。1）从根结点搜索，该索引项应插入到第二个叶子中。2）插入时该叶结点满了，必须分裂，原结点的一部分索引项保留在原索引单元内（9，10，13），另一部分索引项和E形成一个新的叶结点（15，23）。3）按照B+树的定义，应将左边叶结点（9，10，13）中最右边一个关键字13插入父结点中，插入新索引项后的B

11、+树如图7.1b所示，仍然是平衡树。B+树是一种较好的外存空间索引结构，时间复杂度是数据集合中元素数量的对数，空间复杂度使索引空间的利用率为50%以上，动态性能支持随机插入和删除。B+树的上述优点是以关键字有序为基础的，空间数据不具备这样的特点，不能简单照搬。 u空间索引分类空间索引分类 空间索引技术的基本原理空间索引技术的基本原理是采用基于空间位置或基于空间对象的分割方法，把研究查询空间划分为若干区域，每个区域为一个索引单元，存储多个空间对象的索引项。考虑到空间位置上的邻近度，按照空间位置邻近的对象其索引项的位置也应该邻近的原则来组织空间索引数据。空间索引支持的最主要的查询是定位查询和窗口查

12、询。一、空间对象的近似空间对象的几何形状错综复杂，表示几何形状的坐标序列是变长的，直接以坐标序列为索引字段建立的空间索引，其索引项很长且变长。为此，需要将空间对象的形状进行某种近似，平行于坐标轴的、包含特定空间对象的最小外接矩形MBB（Minimal Bounding Box）或MBR(Minimum Bounding Rectangle)就是空间对象几何形状的一种近似表示。 以 MBB，OID 为索引字段建立空间索引，每个空间索引项具有固定的长度，最少包含三种成分MBB，OID，PRT，OID为对象标识，MBB为相应对象的最小外接矩形，PRT为指向几何数据的指针，OID直接将MBB映射到存放

13、几何形状和属性的物理页。 空间索引介于空间计算算法与空间数据之间，用于过滤大量与空间计算无关的数据，以提高空间操作的效率。SAM只加速了索引项中MBB的查找（过滤），在此基础上还要对几何图形进行精确查找。基于空间索引的空间查询分两步完成，第一步利用空间索引结构和空间访问方法SAM对数据集进行过滤（初选），在索引表中查找满足查询条件的MBB，结果为对象的一个超集（多个OID）。第二步对初选结果进行准确查找，在超集中通过空间计算算法，求取满足查询条件的精确对象。二、空间分割与空间索引单元划分建立空间索引的第一步是按照一定的方式将被查询空间分割成多个索引单元。有两种对空间进行划分的方法，形成两大类空

14、间索引结构，很多SAM都属于这两类结构之一。1、空间驱动结构：采用基于空间位置的分割方法，将研究区域的2D空间进行完全划分，划分为多个矩形或正方形范围，每个范围定义为一个空间索引单元，对象在2D空间的分布是独立的，对象按一定原则分配到不同的矩形单元。也可将研究区域的2D空间划分为多个凸多边形范围，每个凸多边形近似表示一个空间对象的几何形状。例如：将研究空间用规则的正方形格网进行分割，每个正方形网格为一个空间索引单元，索引多个空间对象。空间对象覆盖多个相邻的空间索引单元时，在其覆盖的每个索引单元中各有一个索引项，索引项中包含空间对象标识OID。2、数据驱动结构：是一种基于对象的分割，对2D研究区

15、域的空间分割直接由分布在其中的空间对象来确定，对空间对象集合进行分割。每个空间对象用它的最小外接矩形MBB近似表示，每个空间索引单元的形状也是一个矩形区域，它包含多个空间对象的最小外接矩形MBB。空间索引单元的面积大小取决于其索引的空间对象集合的面积、形状和分布，索引单元中存储空间对象的最小外接矩形MBB。基于对象的分割不是空间的一种完全划分。三、空间索引结构的具体分类综合现有研究及参考文献，可将主要的空间索引技术分类如下：空间索引非线性索引线性索引网格空间索引基于树的索引基于凸多边形基于约束基于MBBR树系列树CELL系列BSP树CELL树CP树OS-CELL树PR树GPR树LUR树R+树R

16、*树R-Link树Qr树Sr树TV树X树SDR树线性映射结构网格文件线性四叉树点对象R树 索引结构中，如果将2D或3D分布的空间索引单元，按照一定的方式组织成线性形式，相应的索引称为线性空间索引。相反，以非线性形式来组织空间索引单元，相应的索引称为非线性空间索引。一、线性索引线性索引主要有线性映射结构与线性四叉树。1、线性映射结构：首先，用均匀或不均匀的正方形格网对被索引空间区域进行划分；然后，采用填充曲线对索引空间进行填充（如Hilbert Curve曲线），取填充曲线编码为索引单元的序号，将索引单元按序号排序建立线性索引结构。这里，空间划分是基于位置的完全划分，建立的索引为空间驱动的、线性

17、组织的、规则的网格空间索引结构。2、线性四叉树：每一个空间对象用其MBB近似表示，对含有MBB集合的空间进行四叉树划分，划分后的不均匀网格作为索引单元，每个单元分别编号，叶结点根据编号组织成B-树结构，这种结构叫线性四叉树。二、非线性索引非线性空间索引按索引的逻辑组织方式分成网格空间索引和基于树的空间索引。（一）网格空间索引网格空间索引简称称网格索引，是基于位置的空间驱动结构。它将被索引空间用平行于坐标轴的横竖线条划分成大小相等或不等的网格，每个网格为一个索引单元，记录每个网格所包含的多个对象的标识。空间查询时，先计算出对象所在的网格，然后在网格中快速查询对象。网格索引分为均匀网格索引和网格文

18、件索引，可以索引点对象及用MBB近似的其他类型的空间对象。网格索引以二维数组结构来存储，是一种非线性空间索引结构。 （ （2）CELL树、CP树、OS-CELL树 CELL树与BSP树相似，BSP树将被索引空间一分为二，CELL树则将被索引空间划分成多个凸多边形，然后依次再对每个凸多边形进行相似的划分，直到到达预定的精度为止，CELL树是一棵多叉树。CELL树与BSP树的相同之处是子空间相互间不覆盖，优点是磁盘1/0次数较少，但索引项中凸多边形的存储需较多空间，且进行几何形状的精确匹配时计算也较复杂。 CP树是CELL树的一种变种树，采用CELL树同样的空间划分方法，但允许子空间部分覆盖。特点

19、是与R树相比，具有较小的子空间覆盖面积，磁盘1/0次数较少，同样索引项中对凸多边形的存储需较多的空间，且进行空间对象的精确匹配时计算较复杂。 OS-CELL树也是CELL树的一种变种树，只是针对CELL树中存在的特大空间对象，对CELL树进行改进、完善和优化。由于特大空间对象占据较大的被索引空间，其在CELL树中可能会被分割成多个凸多边形，当特大空间对象较多时，CELL树的叶节点分裂会相当频繁，使CELL树的重构时间增多，有效访问速度变慢；每个特大空间对象可能存放到多个磁盘块中，增加CELL树的高度，从而增加磁盘1/ 0次数，恶化CELL树的搜索性能。OS-CELL树分配特大盘块专用于存储特大

20、空间对象，在父节点中添加指向该特大盘块的指针。对普通几何对象而言，OS-CELL树的特点与CELL树相同。 2、基于约束的空间索引其代表O树采用空间近似算法，将几何对象按axby=c(a，b)，c (a，b) (-1，0，1)表示为一组约束表达式，相应于笛卡尔坐标空间中的六条曲线中的某种组合，然后根据空间对象间的空间关系建立空间索引树。特点是能够自然地表示空间对象间的空间关系，但对空间对象的精确匹配需较多的计算。3、基于MBB的空间索引基于MBB的树状空间索引均将空间对象近似为其MBB，根据MBB间的空间关系建立相应的树形结构，这类空间索引主要指R树系列。自1984年Guttman提出R树以来

21、，学者根据不同应用对R树的需求，对R树进行了各种改进，形成了诸多R树的变种，如图7-2所示。当前主要的空间索引结构归纳为网格索引、线性四叉树、R树结构、划分树结构和线性映射结构等类型。本章主要探讨这几类空间索引的索引结构，索引建立和简单的查询操作。 （二）基于树的空间索引基于树的空间索引是一种基于对象的数据驱动结构。首先采用某种几何形状近似算法，将被索引空间中的空间对象表示为其近似体，然后将近似体按确定规则组织成树形结构。基于树的空间索引按几何形状近似技术的不同可分为基于凸多边形的空间索引、基于约束的空间索引和基于MBB的空间索引。1、基于凸多边形的空间索引基于凸多边形的空间索引又称划分树结构

22、，它将被索引空间划分成凸多边形，然后再对凸多边形进行同样的划分，直到该划分满足特定精度为止。用凸多边形近似表示对象的形状。（1）BSP树 BSP树是一种二叉树，它将被索引空间逐级进行一分为二的划分，形成一棵二叉树BSP树。空间索引技术的基本原理空间索引技术的基本原理是采用基于空间空间索引技术的基本原理是采用基于空间位置或基于空间对象的分割方法，把研究空间位置或基于空间对象的分割方法，把研究空间划分为若干区域，每个区域为一个索引单元，划分为若干区域，每个区域为一个索引单元，存储多个空间索引项，按照空间位置邻近的对存储多个空间索引项，按照空间位置邻近的对象其索引项的位置也应该邻近的原则来组织空象其

23、索引项的位置也应该邻近的原则来组织空间索引数据。间索引数据。空间索引按照对空间的划分方式分为空间空间索引按照对空间的划分方式分为空间驱动的索引和数据驱动的索引；按照索引文件驱动的索引和数据驱动的索引；按照索引文件的数据结构又分为线性索引和非线性索引。的数据结构又分为线性索引和非线性索引。空间索引技术的基本原理空间对象的几何形状错综复杂，表示几何形状的坐空间对象的几何形状错综复杂，表示几何形状的坐标序列是变长的，直接以形状数据为索引字段将导致索标序列是变长的，直接以形状数据为索引字段将导致索引项很复杂。为此，首先将空间对象的几何形状采用某引项很复杂。为此，首先将空间对象的几何形状采用某种近似的简

24、单图形来表示，平行于坐标轴且包含特定空种近似的简单图形来表示，平行于坐标轴且包含特定空间对象的最小外接矩形间对象的最小外接矩形MBB（Minimal Bounding Box）或或MBR(Minimum Bounding Rectangle) 是空间对象几是空间对象几何形状的一种近似表示。何形状的一种近似表示。以以 MBB，OID，PRT为索引项建立空间索引，可为索引项建立空间索引，可使每个空间索引项具有固定长度。其中：使每个空间索引项具有固定长度。其中：OID为对象标为对象标识，识，MBB为对象的最小外接矩形，为对象的最小外接矩形，PRT为指向几何数据为指向几何数据的指针，的指针，OID直接

25、将直接将MBB映射到存放几何形状和属性的映射到存放几何形状和属性的物理页。物理页。 空间索引技术的基本原理空间索引介于空间计算算法与空间数据之间，用于过空间索引介于空间计算算法与空间数据之间，用于过滤大量与空间计算无关的数据，以提高空间操作的效率。滤大量与空间计算无关的数据，以提高空间操作的效率。 SAM只加速了索引项中只加速了索引项中MBB的查找（过滤），在此基础的查找（过滤），在此基础上还要对几何图形进行精确查找。上还要对几何图形进行精确查找。基于空间索引的空间查询分两步完成：基于空间索引的空间查询分两步完成：第一步利用空间索引结构和空间访问方法第一步利用空间索引结构和空间访问方法SAM对

26、数据对数据集进行过滤（初选），在索引表中查找满足查询条件的集进行过滤（初选），在索引表中查找满足查询条件的MBB，结果为对象的一个超集（多个，结果为对象的一个超集（多个OID）。）。第二步对初选结果进行准确查找，在超集中通过空间第二步对初选结果进行准确查找，在超集中通过空间计算算法，求取满足查询条件的精确对象。计算算法，求取满足查询条件的精确对象。 空间驱动的索引结构空间驱动索引结构的主要特征是采用空间驱动索引结构的主要特征是采用某种格网对某种格网对2D空间进行划分，将空间划分空间进行划分，将空间划分成小区域，每个小区域为一个成小区域，每个小区域为一个索引单元索引单元，每个索引单元每个索引单元

27、包含多个索引项，包含多个索引项，每个索引每个索引项项索引一个空间对象索引一个空间对象。索引单元按照一定的索引单元按照一定的数据结构数据结构来组织。来组织。如果组织成线性结构，则相应的空间索引如果组织成线性结构，则相应的空间索引为线性索引，如果组织成非线性结构，则为线性索引，如果组织成非线性结构，则相应的空间索引为非线性索引。相应的空间索引为非线性索引。网格索引网格索引是一种空间驱动的非线性索引结网格索引是一种空间驱动的非线性索引结构，其基本特征是用正方形或矩形格网对研究构，其基本特征是用正方形或矩形格网对研究区域的区域的2D空间进行划分，每个网格单元为一空间进行划分，每个网格单元为一个索引单元

28、，索引多个空间对象，索引单元按个索引单元，索引多个空间对象，索引单元按行列号组织成行列号组织成2D目录。目录。网格索引包括均匀网格索引和网格文件索网格索引包括均匀网格索引和网格文件索引，均匀网格适合于索引空间点对象；网格文引，均匀网格适合于索引空间点对象；网格文件是均匀网格的改进，是一种多关键字索引，件是均匀网格的改进，是一种多关键字索引，可索引点对象和对象的可索引点对象和对象的MBB，能够与，能够与B+树简树简单集成，在商用数据库单集成，在商用数据库Oracle中已实现。中已实现。 均匀网格索引均匀网格索引 一、均匀网格的特征一、均匀网格的特征 设几何对象均为点对象。研究区域为一个设几何对象

29、均为点对象。研究区域为一个Sx*Sy大小的空间，将其划分为大小的空间，将其划分为nx*ny个相同大个相同大小的网格，每个网格的边长为小的网格，每个网格的边长为Sx/nx*Sy/ny，起始，起始坐标为坐标为(Xo,Yo)。每个网格为一个索引单元，对应于磁盘上一个每个网格为一个索引单元，对应于磁盘上一个物理页，每个网格中的点存入相应的磁盘页中。物理页，每个网格中的点存入相应的磁盘页中。每个索引单元包含的索引项数量是有限制的，每个索引单元包含的索引项数量是有限制的，不能超过一个物理页的存储容量。不能超过一个物理页的存储容量。 均匀网格索引均匀网格索引图图7-3 均匀网格均匀网格 如图如图7-3，索引

30、组织成，索引组织成2D数组数组DIR1:nx,1:ny形式的目形式的目录表，每个目录项录表，每个目录项DIRi，j 对应一个索引单元。一个索引对应一个索引单元。一个索引单元包含形式为单元包含形式为OID, PageID的多个索引项，存储为一个的多个索引项，存储为一个物理页。物理页。OID为空间对象的主码，为空间对象的主码，PageID为该索引单元对为该索引单元对应的物理页标识。应的物理页标识。均匀网格索引均匀网格索引（二）基于均匀网格索引的空间访问（二）基于均匀网格索引的空间访问1、插入新点：假设新点的坐标为（、插入新点：假设新点的坐标为（x，y），计算新点），计算新点所在网格（索引单元）的行

31、列号。新点的索引目录项为所在网格（索引单元）的行列号。新点的索引目录项为DIRi，j，假设对应的磁盘页，假设对应的磁盘页DIRi，j.PageID为为(a，b)所所在的页在的页P(a，b)，将新点插入，将新点插入P(a，b)页中。页中。2、点查询：假设鼠标当前位置的坐标为、点查询：假设鼠标当前位置的坐标为 (x，y)，计算，计算鼠标位置所属索引单元的行列号鼠标位置所属索引单元的行列号i=(X-Xo)/(Sx/nx)+1和和j=(Y-Yo)/(Sy/ny) +1，读入对应的磁盘页，读入对应的磁盘页DIRi，j.PageID，扫，扫描该页中所有点对象，判断哪些点对象与描该页中所有点对象，判断哪些点

32、对象与(x，y)点重叠。点重叠。3、窗口查询：计算窗口、窗口查询：计算窗口W覆盖的网格集合覆盖的网格集合S=Ci,j，对对S中的每个读取中的每个读取DIRi，j.PageID，返回这些页中包含的，返回这些页中包含的所有点对象，即为窗口所有点对象，即为窗口W范围内包含的点对象。范围内包含的点对象。 均匀网格索引均匀网格索引格网分辨率的选择取决于被索引点对象的数量。格网分辨率的选择取决于被索引点对象的数量。假设共有假设共有N个点对象，每页存储的最大点数为个点对象，每页存储的最大点数为M，则至少需要有则至少需要有N/M个网格。如果某个网格中的点数个网格。如果某个网格中的点数超过超过M，多出的点放到溢

33、出区，溢出区与索引区域，多出的点放到溢出区，溢出区与索引区域用指针相连。用指针相连。所有的网格共用一个溢出区，溢出区可能由多所有的网格共用一个溢出区，溢出区可能由多个磁盘页连接成溢出区链。如果个磁盘页连接成溢出区链。如果o点存储在溢出区链点存储在溢出区链的第的第q页，则点查询的页，则点查询的I/O数为数为q。最坏的情况下，所。最坏的情况下，所有点都位于同一网格中，索引结构为磁盘页的线性有点都位于同一网格中，索引结构为磁盘页的线性列。点的频繁插入会导致较长的溢出链，而点删除列。点的频繁插入会导致较长的溢出链，而点删除会导致空页。对于某些具体分布，这种索引不能满会导致空页。对于某些具体分布，这种索

34、引不能满足磁盘存储的要求足磁盘存储的要求。均匀网格索引均匀网格索引如图如图7-4中例子，每个网格所存的最大点数中例子，每个网格所存的最大点数M=4，k,l,m,n,o五个点对象位于同一个网格中，对应于磁盘五个点对象位于同一个网格中，对应于磁盘页页P。将。将k,l,m,n四个点放入四个点放入P页，页，o放入溢出区，将溢放入溢出区，将溢出区与出区与P页相连。页相连。图图7-4 均匀网格中的溢出页均匀网格中的溢出页 网格文件索引网格文件索引二、点对象的格网文件二、点对象的格网文件格网文件与均匀格网的相同之处是采用平行于坐标轴的格网格网文件与均匀格网的相同之处是采用平行于坐标轴的格网对空间进行完全划分

35、，每个网格单元为一个索引单元，索引单元对空间进行完全划分，每个网格单元为一个索引单元，索引单元组织成组织成2D目录形式。与均匀格网不同的是，每次发生溢出时，动目录形式。与均匀格网不同的是，每次发生溢出时，动态的将网格单元在横向或纵向上分裂为两个单元，可根据网格单态的将网格单元在横向或纵向上分裂为两个单元，可根据网格单元中点对象的分布情况来选择进行纵向还是横向划分；网格文件元中点对象的分布情况来选择进行纵向还是横向划分；网格文件中的网格单元为大小不相同的矩形单元，多个网格单元可对应同中的网格单元为大小不相同的矩形单元，多个网格单元可对应同一个磁盘页。一个磁盘页。 （一）格网文件的数据结构（一）格

36、网文件的数据结构 格网文件由三种数据结构来实现，索引目录格网文件由三种数据结构来实现，索引目录DIR是一种与均是一种与均匀网格中的索引目录类似的匀网格中的索引目录类似的2D数组，差别是两个相邻单元可共享数组，差别是两个相邻单元可共享同一磁盘页；同一磁盘页；Sx,Sy是两个线性数组，表示沿两坐标轴的划分。是两个线性数组，表示沿两坐标轴的划分。图图7-5中的例子描述了这种结构，假设网格的最大容量中的例子描述了这种结构，假设网格的最大容量M=4。 网格文件索引网格文件索引图7-5均匀网格文件的插入 网格文件索引网格文件索引网格文件索引网格文件索引网格文件索引网格文件索引三、格网文件索引三、格网文件索

37、引MBB用网格文件对用网格文件对MBB进行索引，最简单的情况是每个覆盖进行索引，最简单的情况是每个覆盖MBB的的网格单元都保存该网格单元都保存该MBB的索引项。的索引项。MBB与网格单元的关系有三种：与网格单元的关系有三种：MBB包含网格单元、网格单元与包含网格单元、网格单元与MBB相交、网格单元包含相交、网格单元包含MBB。前两。前两种情况，每个网格单元都建立种情况，每个网格单元都建立MBB的索引项，一个的索引项，一个MBB有多项索引。有多项索引。例子：有例子：有15个个MBB，每页的最大容量为，每页的最大容量为4。图。图7-6为用均匀网格建为用均匀网格建立的索引：立的索引： 图图7-6 基

38、于基于MBB的均匀网格索引的均匀网格索引 网格文件索引网格文件索引图图7-7为用网格文件建立的索引：为用网格文件建立的索引： 图图7-7 基于网格文件的基于网格文件的MBB索引索引 网格文件索引网格文件索引（一）索引项插入（一）索引项插入1、插入对象、插入对象14如图如图7-8，将对象，将对象14插入图插入图7-7中的索引单元中的索引单元DIR1，3时，时，DIR1，3中的索中的索引项超过引项超过4项，对应的磁盘页项，对应的磁盘页p5也溢出。在也溢出。在X3处对处对DIR1，3进行水平分裂，将进行水平分裂，将X3存入存入Sx中，现有中，现有3*（2+1）= 9 个目录项。目录单元个目录项。目录

39、单元DIR1，1和和DIR2，1 同指同指向向p1页，页，DIR1，2和和DIR2，2同指向同指向p3页。原来页。原来p5页中的对象由于对象页中的对象由于对象14的插的插入，分裂成了入，分裂成了p5和和p6两页，两页，DIR1，3指向指向p5，DIR2，3指向指向p6。对象。对象5有两个有两个索引项分别存储在索引项分别存储在p5和和p6两页中，对象两页中，对象6 有四个索引项分别存储在有四个索引项分别存储在p5、p6和和p3中。中。 图图7-8 对象对象14的插入的插入 网格文件索引网格文件索引2、插入对象、插入对象15图图7-9为目录不分裂而磁盘页溢出的情况。为目录不分裂而磁盘页溢出的情况。

40、插入前插入前DIR3，2和和DIR3，3同指向同指向p4，将对象，将对象15分别插入分别插入DIR3，2和和DIR3，3中。插入后中。插入后DIR3，2和和DIR3，3中的索引中的索引项均不超过项均不超过4个，目录不用分裂，但磁盘页个，目录不用分裂，但磁盘页p4溢出。创建新页溢出。创建新页p7，DIR3，2 指向指向p4，DIR3，3 指向指向p7。 图图7-9 对象对象15的插入的插入 网格文件索引网格文件索引（二）点查询算法（二）点查询算法 1、工作过程、工作过程 第一步：给定点坐标第一步：给定点坐标P(xp，yp)，沿，沿X，Y两个方向在两个方向在Sx和和Sy中查找中查找P(xp，yp)

41、位置，得到含有位置，得到含有P的网格单元。的网格单元。第二步：进行一次磁盘操作将这个索引单元对应的磁盘页调第二步：进行一次磁盘操作将这个索引单元对应的磁盘页调入内存，读取该页所存对象的入内存，读取该页所存对象的(MBB，OID)，构成集合，构成集合E。对。对E中中的每个对象的每个对象e，测试，测试e.mbb是否含有点是否含有点P。第三步：对于包含点第三步：对于包含点P的的e.mbb，通过，通过e.oid获取其几何边界获取其几何边界数据，精确测试数据，精确测试P是否位于是否位于e.oid的几何边界之内。的几何边界之内。 网格文件索引网格文件索引2、例子：图、例子：图7-10为一个格网文件点查询的

42、例子。点为一个格网文件点查询的例子。点P位于位于DIR3，2范围之内，对应的磁盘页范围之内，对应的磁盘页p4中含有中含有4个索引项。将个索引项。将p4页调入内存，对其包含的页调入内存，对其包含的4个个mbb分别进行测试，其中分别进行测试，其中8和和12的的mbb中包含了点中包含了点P。根据对象标识。根据对象标识8和和12取出各自的几何边界数取出各自的几何边界数据，精确测试对象据，精确测试对象8和和12，求出包含点，求出包含点P的对象的对象12。图图7-10 基于网格文件的点查询基于网格文件的点查询 网格文件索引网格文件索引（三）窗口查询算法（三）窗口查询算法工作过程如下：工作过程如下：第一步：

43、计算所有覆盖窗口的索引单元。第一步：计算所有覆盖窗口的索引单元。第二步：扫描每一个索引单元，调入相应的磁盘页。读入每第二步：扫描每一个索引单元，调入相应的磁盘页。读入每个磁盘页中的对象，排序并去掉重复对象。求出那些落入窗口中，个磁盘页中的对象，排序并去掉重复对象。求出那些落入窗口中，或与窗口相交的或与窗口相交的mbb。第三步：根据各自的对象标识取出这些第三步：根据各自的对象标识取出这些mbb对应的几何边界，对应的几何边界，精确检测每个对象是否位于窗口中或与窗口相交。精确检测每个对象是否位于窗口中或与窗口相交。（四）总结（四）总结用网格文件索引用网格文件索引MBB，大多数情况下比较理想，但也存在

44、很，大多数情况下比较理想，但也存在很多问题：多问题：1、对象的多重索引增加了索引表的容量，数据集越大越严、对象的多重索引增加了索引表的容量，数据集越大越严重，索引单元接近重，索引单元接近MBB大小时，情况就更严重。大小时，情况就更严重。2、索引表容量越大，查询重复项的代价越高。、索引表容量越大，查询重复项的代价越高。3、算法的效率依赖于索引表位于内存中的假设，如果索引、算法的效率依赖于索引表位于内存中的假设，如果索引表很大，一部分要存入磁盘，管理将变得复杂，效率会受影响。表很大，一部分要存入磁盘，管理将变得复杂，效率会受影响。 Back数据驱动的索引结构 空间驱动的索引结构将整个空间划分成小区

45、域，每个小区域定义为一个索引单元，直接索引其中的空间对象或索引对象的MBB。数据驱动的索引结构则按照空间对象的位置、范围和分布，来确定索引单元的位置和范围，索引单元的全集不一定覆盖整个空间。这里主要介绍R树系列和划分树。R树 R树是一种数据驱动的索引结构，是B树的扩展。与B树相比，R树是一棵由多层嵌套的外接矩形构成的平衡树，即R树的每个结点以范围矩形mbb或目录矩形dr的形式表示一个空间范围，它界定了一个空间索引区域，定义为一个空间索引单元。R树的每个结点都是一个空间索引单元，非叶结点包含其多颗子树的索引项，叶结点包含多个数据对象的索引项，本结点的范围矩形作为自身索引项的一部分存储在它的上层结

46、点中。 R树的每个结点对应一个物理页，每个结点只能包含k个索引项，mkM，M是R树结点中包含索引项的最大数目，m是R树结点中包含索引项的最小数目，并限制2 m M/2。BacR树一、原始的R树 R树的基本结构是一棵多层嵌套的、由外接矩形构成的平衡树。每个结点的索引区域表示成一个范围矩形，每个结点为一个空间索引单元，每个索引单元有k个索引项。叶结点的范围矩形为其内部多个数据对象mbb的最小外接矩形，非叶结点的范围矩形为其多个子结点范围矩形mbb的最小外接矩形。叶结点中存放多个数据对象的索引项，每个索引项的形式为ptr，mbb，oid，其中oid是数据对象的标识，mbb是数据对象的外接矩形，ptr

47、指向存储该对象几何形状数据的磁盘位置。非叶结点中存放多个子结点索引项，每个索引项的形式为ptr，mbb，nodeid，其中nodeid是指向子结点的指针，mbb为子树的目录矩形dr，ptr是子结点对应的磁盘页地址。R树（一）R树的性质1、根结点至少有两个子结点；2、所有的叶结点都处于同一层；3、除根结点外，R树中所有结点包含的索引项数目均在m，M之间，并限制2 mM/2。图7-26显示一棵m=2，M=4的R树。M的大小取决于索引项大小Size(E)和磁盘页大小Size(P)， 。通常oid大于nodeid，因而，非叶结点和叶结点的M不同。给定M和m后，一个深度为d的R树最少可索引 个对象，至多

48、可索引 个对象。相反，要索引N个对象，R树的深度最大为 ，最小为 。假设页的大小为4K，索引项的大小为20B（16B为mbb，4B为oid），m设为页容量的40%，则 ， 。这种情况下，深度为1时可索引至少81*81=6561个对象，深度为2可索引81*81*81=531441到204*204*204=8489664个对象。对于million个对象，只需要三层，即访问三个磁盘页就可到达树叶，再读取相应的对象即可。R树（二）R树查询效率的优化R树允许兄弟结点间有区域重叠，因此，查询一个对象可能要访问多个分支，这是影响R树查询效率的主要因素。对R树查询效率的优化可考虑如下参数：1、查询区域：查询条

49、件所覆盖的区域。2、重叠区域：兄弟结点间范围矩形相互重叠的区域。重叠区域减少时，查询区域与重叠区域相交的概率减少，可减少查询时访问的分支数。3、死区域：被结点范围矩形覆盖但不被其子结点范围矩形覆盖的区域。死区域减少时，属于结点范围内的查询区域与其子结点范围矩形相交的概率增大，在该分支上找到目标数据的概率也增大，提高了分支选择的准确性。4、范围矩形周长：结点范围矩形四边长度之和。对于面积固定的矩形，周长越小，其形状越接近正方形，正方形的空间聚簇性好，易于填满父结点的范围矩形，所以减少子结点的范围矩形周长可减少父结点的死区域。5、结点利用率：结点的实际子结点数（或数据对象数）与最大子结点数（或数据

50、对象数）之比。提高结点利用率可降低树的平均高度，对于大区域查询，满足条件的数据对象数目很大，结点利用率高可在很大程度上减少结点访问数，从而提高查询效率。上述优化参数有些相容，有些互斥。一般来说，减少死区域的同时可能也减少了重叠区域，两者是相容的。而为了减少死区域，则要求结点的子结点数目能更自由，结点利用率可能会降低。减少死区域和减少重叠区域都要求结点外接矩形的形状更自由，结点范围就可能无法接近正方形。对于任意几何形状，减少周长一般也会影响到结点利用率，接近正方形的外接矩形更容易填满父结点范围矩形，也容易提高结点利用率。对于大区域查询，结点利用率对查询的影响远远大于其他三个因素。R树（三）基于R

51、树的查询点查询和窗口查询几乎完全一样，这里只介绍点查询。函数RTpointQuery实现两步：1、在每一层中查找各结点中所有含P点的子结点，因为外接矩形可以重叠，满足条件的子结点可能有多个，相同的方法直到叶结点。访问每个结点时可能发生两种情况：（1）该结点不包含P，即P落在非叶结点范围矩形的死区域，查找终止。（2）P点包含在该结点多个子结点的mbb中，这时要搜索每一棵子树，直到叶结点。2、顺序扫描第一步得到的所有叶结点，所有包含P点的数据对象的索引项mbb即为所求。 图7-26显示了点查询的例子，查询访问了R，b，c，d四个结点，P点含在对象8和12的mbb中。R树（三）R树的插入操作1、插入步骤（1）从根结点向叶子搜索，如某个结点的范围矩形包含被插入对象的mbb，则继续查找其子树，如果不包含则终止，重复此过程直到叶结点 。（2）如果叶结点 未满，则将新对象的mbb，oid插入叶结点 ；如果叶结点 已满，则将叶结点 分为裂为 两页（重构 的范围矩形），将M+1个索引项分配到两页中，在父结点f中修改 的索引项（ 的范围矩形有变化），并插入 的索引项。如果父结点f也满了，则重复