第三章 空间数据索引与空间查询语言,本章教学目标 掌握常用的空间数据索引原理及其构造； 掌握基于点集理论的9-交模型基本知识、常用的空间操作算子； 了解基本的三维空间关系； 熟悉基于对象-关系的空间查询语言的构造； 了解XML查询语言XQuery基本语法。,本章主要内容 1 空间数据索引技术 1.1空间数据索引结构的分类 1.2矩形范围索引 1.3单元格网索引 1.4R-树类索引 1.5四叉树编码索引 1.6多级索引 1.7索引技术比较 2空间拓扑关系的表达 2.1几何对象的边界、内部和外部的概念 2.2基于点集理论的9-交模型 2.3基于9-交模型的拓扑关系定义 2.4空间操作算子 2.5三维空间拓扑关系,3空间查询语言 3.1关系代数 3.2SQL基础 3.3扩展SQL以处理空间数据 3.4强调空间的查询示例 3.5对象关系查询语言 3.6基于XQuery的GML空间数据查询语言,1空间数据索引技术,空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。 空间索引的目的是为了在GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。,1.1空间数据索引结构的分类,根据处理数据的类型：可以分为点数据类和空间数据类。 点数据类是指那些只能处理点数据的索引结构，如k-d-tree、TV-tree等； 空间数据类指既能处理点数据，又可以处理线、矩形等具有一定形状的数据的索引结构，如R-tree、R*-tree等。 根据索引创建时数据组织形式：可以分为静态结构类和动态结构类。 静态结构类是指用批处理的方式将全部数据构建成索引，不能支持动态的插入和删除，如packed R-tree； 动态结构类指数据依次插入而生成的索引结构，如动态R-tree、动态R*-tree等。, 根据划分方法的不同：可以分为数据划分方法类、空间划分方法类以及混合型划分方法类。 数据划分方法是根据数据所在的位置进行层次划分，如R-tree等； 空间划分方法则是将整个数据空间逐渐划分为互相邻接的子空间，如k-d-tree、四叉树等； 混合型是指既根据空间进行划分又根据数据进行划分，如Hybrid-tree等。 根据索引的组织形式：可以分为树形结构类和非树形结构类。 树形结构类指索引结构是按照树的形式组织的，如k-d-tree、R-tree等； 非树形结构类是指索引结构不是按照树的形式组织的，如VA-File等。, 根据目录节点的形状：可以分为矩形、球形和混合形。 在构造索引结构的时候，目录节点形状的选择直接影响检索的效率 选择为矩形的有k-d-tree、R-tree、R*-tree等； 选择为球形的有SS-tree、TV-tree等； 将矩形和球形结合起来的称为混合形，如SR-tree等。,1.2矩形范围索引,1.2.1 索引原理 其基本原理就是对空间要素的外包络矩形进行索引。 在进行空间范围查询时，分为两级过滤（筛选） 初次过滤根据空间要素外包络矩形来过滤掉大部分不在查询范围的空间要素，因为空间要素外包络矩形已被索引，所以初次过滤过程比较快，花费的代价比较小。 第二级过滤则用查询空间范围直接和初次过滤结果集中空间要素的二进制边界坐标比较，从而得到查询的准确结果。,1.2.2索引维护及适应性 矩形范围索引由关系数据库直接维护，用SQL语句模型可以直接创建和删除，在添加、更新和删除空间要素时，不需要SDE来维护索引的变化。 查询效率： 空间要素在30万以下时，具有很高的效率，矩形范围查询初次过滤的响应时间均在1秒之内 空间要素在30万以上时，查询效率下降，空间要素个数在200万左右时，利用该索引查询进行初次过滤，响应时间在518秒之间。,1.3 单元格网索引,基本思想是将研究区域用横竖划分为大小相等或不等的网格，记录每一个网格所包含的空间要素。 当用户进行空间查询时，首先计算出查询空间要素所在的网格，然后通过该网格快速定位到所选择的空间要素。 1.3.1 传统单元网格索引编码 在建立地图数据库时需要用一个平行于坐标轴的正方形数学网格覆盖在整个数据库数值空间上，将后者离散化为密集栅格的集合，以建立制图物体之间的空间位置关系。 通常是把整个数据库数值空间划分成3232（或6464）的正方形网格，建立另一个倒排文件栅格索引。 每一个网格在栅格索引中有一个索引条目(记录)，在这个记录中登记所有位于或穿过该网格的物体的关键字，可用变长指针法或位图法实现。,1 2 3 4 5 32,33 34 35 37 64,65 66 67 68 (11) 96,1,1,1,1,1,1,1,1,栅 格 序 号,图3-1-3栅格索引,1,缺陷： 由于传统型单元网格编码方式过于简单，使得编码值在空间上不能保持连续性，即空间上相邻的网格编码不连续，所以在使用SQL模型进行查询时，只能使用IN语法。这样，如果查询涉及的网格编码太多，则容易超出SQL模型的长度。,1.3.2 改进型单元网格索引编码,改进型单元网格索引将传统型编码由1维升至2维，变成X和Y方向上的编码；将空间要素的标识、空间要素所在的网格的X和Y方向上的编码、以及空间要素的外包络矩形作为一条数据库记录存储。 如果一个空间要素跨越多个网格，则同样存储多条记录。,表3-1-1,1.3.3网格单元大小因素,与空间要素的外包络矩形大小相比： 网格单元很大时，将导致每个网格单元内包含有很多空间要素。第一阶段选择的网格虽少，但导致第二阶段将不得不处理大量网格内的空间要素的边界比较，潜在地增加了查询的时间。 如果网格单元太小，小于空间要素外包络矩形的平均大小，将会导致空间索引表产生大量的网格单元，并且很多网格单元都索引出相同的空间要素。当大量的空间要素外包络矩形被网格单元切割时，空间索引表变大，因而查询网格单元时间增长。,最佳网格的大小可能受图层平均查询的影响，如果用户经常对图层执行相同的查询. 网格的大小的确定： 经验数据表明，网格的大小为查寻空间范围的1.5倍时，效率较高。 经验数据表明，网格单元的大小取空间要素外包络矩形平均大小的3倍时，可极大的减少每个网格单元包含多个空间要素外包络矩形的可能性，获得较好的查询效率。,1.3.4 索引维护和适应性,索引维护 添加空间要素时，按规则计算出该空间要素的网格编码，添加到索引表中； 更新空间要素时，删除该空间要素的索引记录，重新计算网格编码，添加到索引表中； 删除空间要素时，直接删除该空间要素的索引记录即可。 索引性能 单元网格空间索引的效率在网格单元大小适中的时候非常高。 由试验数据表明，空间要素个数在200万左右时，如果网格单元大小划分合理的话，利用该索引查询进行过滤，响应时间最短可在2秒之内。 所以该类型索引适用于大型数据量的，空间范围确定的GIS应用。,1.4 R-树类索引,R-Tree最早是由Guttman于1984年提出，是B+树在K维空间的自然扩展。 R-Tree是一个高度上平衡的树形结构索引。 典型的R-Tree变种有： R*-TREE，其采用比R-Tree更为复杂的插入和结点分裂算法，从而提高检索效率； R+-TREE，能保证各个树结点互不相交； 压缩R-Tree(Packed R-tree)，其适用于静态空间数据； 希尔伯特R-Tree(Hilbert R-tree)，其采用分形维的R-Tree。,1）-Tree,R-Tree的建立规则 设M为R-Tree中每个节点最多包含的索引记录条数，为每个节点包含的最少索引记录条数，则有 M/2。 R-Tree还具有以下特性： 每个叶节点包含M条索引记录象，除非它为根； 一个叶节点上的每条索引记录了（I，元组标识符），I是最小外包矩形，在空间上包含了所指元组表达的K维数据对象； 每个中间节点都有M个子节点，除非它为根； 对于中间节点中的每个（I，子节点指针），I是在空间上包含其子节点中矩形的最小外包矩形；, 根节点最少有两个子节点，除非它是叶节点； 所有的叶节点出现在同一层； 所有MBR的边与全局坐标系的轴平行。 R-Tree的优点： R-Tree的重叠性使得删除和插入操作比较容易 R-Tree的重叠性保证了至少50%的空间利用率 R-Tree的缺点： R-Tree的重叠性在维数增高时很可能会导致索引次数和存储空间的大量增加 R-Tree的重叠性严重影响查询效率,2）R+-TREE,针对R-Tree兄弟节点之间存在的重叠问题，Timos Sellis等人提出了R+-TREE索引结构。 R+-Tree具有如下特性： 对于中间节点的每个项（I，child-pointer），当且仅当R被I覆盖时，以child-pointer指向的节点为根的子树包括一个矩形R。唯一的例外是当I是一个叶节点的矩形。在这种情况下，R与I只重叠； 对于中间节点的任何两个项（I1，child-pointer1）和（I2，child-pointer2），I1与I2之间的重叠是零； 在R+-TREE中，一个空间对象的MBR可能被两个或多个高层节点中的矩形分割； 根节点最少有两个子节点，除非它是叶节点； 所有的叶节点出现在同一层。,3）R*-Tree R*-Tree通过修改插入、分裂算法，并通过引入“强制重插入”对R-Tree的性能进行改进。R*-Tree在选择插入路径时同时考虑矩形的面积、空白区域和重叠的大小，而R-Tree只考虑面积的大小。 R*-Tree和R-Tree一样允许矩形的重叠。 R*-TREE通过以下准则对R-Tree的插入、分裂算法进行了优化： 中间节点的MBR所覆盖区域的面积应最小，即插入一个空间对象时，应将它插入到MBR覆盖面积扩大程度最小的节点中； 中间节点MBR所覆盖的区域间重叠最小，这样同样可以减少所需搜索的路径； 中间节点所覆盖的区域的周长应最小，即几何形状尽量接近正方形； 增大节点的存贮利用率，以降低索引树的高度。,4）Hilbert R-Tree 基本思想：R-Tree、R*-TREE等高维索引结构的性能受维数的制约，在高维时性能往往变差。所以，如果存在一种映射关系，使得高维数据可以在低维空间有一个对应，而且，高维空间数据之间的关系能够在低维的映射中得到一定的保留，那么，仅需对低维空间的数据进行处理即可。 它选择了Hilbert曲线作为一种高维到低维的映射。 建立在这种映射之上的Hilbert R-Tree把各个数据矩形的中心映射为Hilbert曲线上的一个值，然后，把这些值按升序排列。以此为基础，建立叶节点，叶节点之上再建立中间节点。这样，就可以获得一棵空间利用率接近100%的Hilbert R-Tree。 Hilbert R-Tree是一种高效的高维索引结构，它的建树算法也为并行处理提供了可能，但缺点是Hilbert R-Tree难以实现有效的K-邻近查询。,5）Cell树 6）X-Tree 7）SS-Tree 8）SR-Tree,1.5四叉树编码索引,四叉树索引有满四叉树索引和一般四叉树索引 1.5.1基于固定网格划分的四叉树索引 1）索引原理 将地理空间的长和宽在X和Y方向上进行2N等分，形成2N2N的网格，并以此建立N级四叉树。 其中，树的非叶结点（即内部结点）数的计算公式为： MAX_NONLEAFNODE_NUM= 叶结点（即外部结点）数的计算公式为：MAX_LEAFNODE_NUM= 2N2N=4N。,结点编号原则： 若非叶结点从四叉树的根结点开始编号，从0到MAX_NONLEAFNODE_NUM-1， 叶子结点则从MAX_NONLEAFNODE_NUM开始编号，直到MAX_ NONLEAFNODE_NUM +MAX_LEAFNOD