2022年GIS空间索引 .pdf

《2022年GIS空间索引 .pdf》由会员分享，可在线阅读，更多相关《2022年GIS空间索引 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、索引方法：网格索引点要素（图元），线、面要素，有冗余四叉树索引线、面要素，有冗余改进的四叉树索引线、面要素R树空间重叠一、网格索引，四叉树索引在 介绍空间索引之前, 先谈谈什么叫“索引“。对一个数据集做”索引“, 是为了提高对这个数据集检索的效率。书的”目录“就是这本书内容的”索引“, 当我们拿到一本新书 ,想查看感兴趣内容的时候, 我们会先查看目录, 确定感兴趣的内容会在哪些页里, 直接翻到那些页, 就 OK了, 而不是从第一章节开始翻, 一个字一个字地找我们感兴趣的内容, 直到找到为止, 这种检索内容的效率也太低了, 如果一本书没有目录, 可以想象有多么不方便 , 可见书的目录有多重要 ,

2、 索引有多重要啊！现在大家对索引有了感性认识, 那什么是“空间索引“呢？”空间索引“也是”索引“,是对空间图形集合做的一个”目录 “, 提高在这个图形集合中查找某个图形对象的效率。比如说 ,我们在一个地图图层上进行矩形选择, 确定这个图层上哪些图元被这个矩形所完全包含呢,在没有”空间索引“的情况下, 我们会把这个图层上的所有图元, 一一拿来与这个矩形进行几何上的包含判断,以确定到底哪些图元被完全包含在这个矩形内。您是不是觉得这样做很合理呢？其实不然,我们先看一个网格索引的例子：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

3、精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 我们对这个点图层作了网格索引, 判断哪些点在这个矩形选择框内, 是不需要把这个图层里所有的点都要与矩形进行几何包含运算的, 只对 a,b,c,d,e,f,g这七个点做了运算。可以推想一下 , 如果一个点图层有十万个点, 不建立空间索引, 任何地图操作都将对整个图层的所有图元遍历一次, 也就是要For 循环 10 万次；建立索引将使得For 循环的次数下降很多很多,效率自然提高很多！呵呵, 想必大家都知道空间索引的好处了, 也不知不觉向大家介绍了点图层的网格索引, 还有哪些常用的空间索引呢？这些空

4、间索引又该如何实现呢？带着这样的问题, 下面介绍几种常用的空间索引。网格索引网格索引就是在一个地图图层上, 按每个小网格宽w,高 h 打上均匀的格网, 计算每个图元所占据的网格或者所经过的网格单元集合, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 在这些网格单元中, 记录下图元对象的地址或者引用, 比如：声明一个对象二维数组List gridmn; m代表网格的行数,n 代表网格的列数, 每个数组元素为一个“集合对象” ,

5、用于存储这个网格单元所关联的所有图元的地址或引用, 这样网格索引就建立好了。下 一步 ,我们该怎么用这个网格索引呢？所有的图形显示和操作都可以借助于“空间索引” 来提高效率。举几个例子来说明“空间索引“的使用：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 一、放大开窗显示 , 正如上一节介绍的, 当我们在地图上画一个矩形想放大地图的时候 , 首先得确定放大后的地图在屏幕上需要显示哪些图元？所以, 我们需要判断这个地图中有哪些

6、图元全部或者部分落在这个矩形中。判断步骤：1, 确定所画矩形左上角和右下角所在的网格数组元素；即可得到这个矩形所关联覆盖的所有网格集合；2, 遍历这个网格集合中的元素, 取到每个网格元素List中所记录的图元；3, 画出这些图元即可。（当然整个过程涉及到两点：1, 屏幕坐标和地图坐标的互相变换；2,窗口裁减 ,也可以不裁减）二、 包含判断 , 给出一个点point和一个多边形polygon, 判断点是否在面内, 首先判断这个点所在的网格 , 是否同时关联这个polygon, 如果不是 , 表明点不在面内, 如果是 , 可以下一步的精确解析几何判断, 或者精度允许的情况下,即判断 polygon

7、 是包含 point的。另外 ,Google Map 应该也是采用地理网格的方式, 对地图图象进行索引的, 可见一斑 , 网格索引在图形显示 , 选择 , 拓扑判断上的广泛应用。但同时也存在很严重的缺陷：当被索引的图元对象是线 , 或者多边形的时候, 存在索引的冗余, 即一个线或者多边形的引用在多个网格中都有记录。随着冗余量的增大, 效率明显下降。所以, 很多学者提出了各种方法来改进网格索引 , 这个将在下面的章节中介绍。而点图元非常适合网格索引, 不存在冗余问题。四叉树索引（Quadtree ）类似于前面介绍的网格索引, 也是对地理空间进行网格划分, 对地理空间递归进行四分来构建四叉树 ,本

8、文将在普通四叉树的基础上, 介绍一种改进的四叉树索引结构。首先 , 先介绍一个 GIS（ Geographic Information System）或者计算机图形学上非常重要的概念最小外包矩形 (MBR-Minimum Bounding Rectangle)：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 最小外包矩形MBR 就是包围图元,且平行于X,Y 轴的最小外接矩形。MBR 到底有什么用处呢 , 为什么要引入这个概念呢

9、？因为, 图元的形状是不规则的, 而 MBR是平行于 X,Y 轴的规则图形 ,设想一下 , 如果所有的图元都是平行于X,Y 轴的矩形 , 那针对这样的矩形进行几何上的任何判断 , 是不是要简单很多呢？不管我们人自己写公式算法或者编写程序运行, 是不是都要比原本复杂的图形几何运算要简洁很多呢？答案很显然。然后 , 我们再介绍一下GIS 空间操作的步骤（这个步骤, 在前面忘记向大家说明了,在这里补充一下）可见 , 过滤阶段 , 通过空间索引可以排除掉一些明显不符合条件的图元, 得到后选集合,然后对后选图元集合进行精确几何运算,得到最终结果。大家可能会有这样的疑问 , 这样有必要吗？是不是反而把问题

10、复杂化了？合适的空间索引只会提高计算机的效率, 没有空间索引, 我们无疑要对集合中的每个图元进行精确几何运算, 而这样的运算是复杂的, 是非常占用 CPU的,所以需要空间索引, 采取少量的内存和简单的CUP运算 , 来尽量减少那种高耗CUP名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 的精确运算的次数,这样做是完全值得的。至于精确的几何运算到底复杂在哪里, 该如何进行精确的几何运算,将在下面的章节中详细描述,这里主要介绍过滤

11、阶段的空间索引。现在 , 让我们来具体了解一下“四叉树索引”。四叉树索引就是递归地对地理空间进行四分, 直到自行设定的终止条件（比如每个节点关联图元的个数不超过3 个, 超过 3 个, 就再 四分） , 最终形成一颗有层次的四叉树。图中有数字标识的矩形是每个图元的MBR, 每个叶子节点存储了本区域所关联的图元标识列表和本区域地理范围 ,非叶子节点仅存储了区域的地理范围。大家可以发现, 同样存在一个图元标识被多个区域所关联, 相应地存储在多个叶子节点上,比如“ 6“所代表的图元, 分别存储在四个分枝上。 这样 , 就存在索引的冗余,与网格索引存在同样的弊端。下面我们介绍一种改进的四叉树索引 ,或

12、者说是分层的网格索引。改进的四叉树索引, 就是为了避免这种空间索引的冗余, 基本改进思路是：让每个图元的 MBR 被一个最小区域完全包含 。可以看出 ,3 和 13 分别都跨越了两个区域, 要被一个最小区域完全包含, 就只能是根节点所代表的区域 ,2,5 跨越了两个区域,6 跨越了四个区域, 要被一个最小区域完全包含, 就只能是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - NW 区域。怎么判断一个图元被哪个最小区域完全包含呢

13、？从直观上看, 递归地对地理空间进行四分 , 如果图元与一个区域四分的划分线相交 , 则这个图元就归属于这个区域, 或者直到不再划分了 , 那就属于这个不再划分的区域。呵呵。可能有点绕口, 看图 , 结合“最小”“完全包含”这两个字眼 , 您就明白了。这颗四叉树中, 图元的标识不再仅仅存储在叶子节点上 , 而是每个节点都有可能存储, 这样也就避免了索引冗余。同时每个节点存储本节点所在的地理范围。有了四叉树索引, 下面又该如何利用这颗树来帮助检索查找呢？还是矩形选择为例吧！（为什么我总是拿这个例子来说事呢？因为这个例子简单, 容易理解 , 有代表性！）我们在地图上画一个矩形 , 判断地图上哪些图

14、元落在这个矩形里或者和这个所画矩形相交。方法很多,这里介绍一种简单的检索步骤, 如下：1, 首先 , 从四叉树的根节点开始, 把根节点所关联的图元标识都加到一个List里；2, 比较此矩形范围与根节点的四个子节点（或者叫子区域）是否有交集（相交或者包含）,如果有 , 则把相应的区域所关联的图元标识加到List集合中 , 如果没有 , 则以下这颗子树都不再考虑。3, 以上过程的递归,直到树的叶子节点终止, 返回 List 。4, 从 List集合中根据标识一一取出图元, 先判断图元MBR 与矩形有无交集, 如果有 , 则进行下面的精确几何判断,如果没有 , 则不再考虑此图元。 （当然 , 这里只

15、说了一个基本思路,其实还有其他一些不同的方法, 比如 , 结合空间数据磁盘的物理存储会有一些调整）总结：改进的四叉树索引解决了线, 面对象的索引冗余, 具有较好的性能, 而被大型空间数据库引擎所采用 , 如 ArcSDE,Oracle Spatial等, 同时这种结构也适用于空间数据的磁盘索引,配合空间排序聚类,基于分形的Hilbert算法数据组织, 将在空间数据格式的定义中发挥重要作用。二、R-Tree 空间索引算法的研究历程和最新进展分析摘要： 本文介绍了空间索引的概念、R-Tree 数据结构和R-Tree 空间索引的算法描述，并从R-Tree索引技术的优缺点对R-Tree 的改进结构变种

16、R-Tree 进行了论述。 最后，对 R-Tree 的最新研究进展进行了分析。关键词： 空间索引技术； R-Tree；研究历程；最新进展当前数据搜索的一个关键问题是速度。提高速度的核心技术是空间索引。空间索引是由空间位置到空间对象的映射关系。当前的一些大型数据库都有空间索引能力，像 Oracle ，DB2 。空间索引技术并不单是为了提高显示速度，显示速度仅仅是它所要解决的一个问题。空间索引是为空间搜索提供一种合适的数据结构，以提高搜索速度。空间索引技术的核心是：根据搜索条件，比如一个矩形，迅速找到与该矩形相交的所有空间对象集合。 当数据量巨大， 矩形框相对于全图很小时， 这个集合相对于全图数据

17、集大为缩小， 在这个缩小的集合上再处理各种复杂的搜索，效率就会大大提高。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 所谓空间 索引，就是指依据空间实体的位置和形状或空间实体之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间实体的概要信息如对象的标识、外接矩形及指向空间实体数据的指针。简单的说，就是将空间对象按某种空间关系进行划分，以后对空间对象的存取都基于划分块进行。1 引言空间索引是对存储在介质上的数据位置信

18、息的描述，用来提高系统对数据获取的效率。空间索引的提出是由两方面决定的：其一是由于计算机的体系结构将存贮器分为内存、外存两种，访问这两种存储器一次所花费的时间一般为3040ns， 810ms， 可以看出两者相差十万 倍以上，尽管现在有“内存数据库”的说法，但绝大多数数据是存储在外存磁盘上的，如果对磁盘上数据的位置不加以记录和组织，每查询一个数据项就要扫描整个数据文件，这种访问磁盘的代价就会严重影响系统的效率， 因此系统的设计者必须将数据在磁盘上的位置加以记录和组织，通过在内存中的一些计算来取代对磁盘漫无目的的访问，才能提高系统的效率，尤其是GIS 涉及的是各种海量的复杂数据，索引对于处理的效率

19、是至关重要的。其二是GIS 所表现的地理数据多维性使得传统的B 树索引并不适用，因为 B 树所针对的字符、数字等传统数据类型是在一个良序集之中，即都是在一个维度上， 集合中任给两个元素， 都可以在这个维度上确定其关系只可能是大于、小于、等于三种，若对多个字段进行索引，必须指定各个字段的优先级形成一个组合字段， 而地理数据的多维性， 在任何方向上并不存在优先级问题，因此 B 树并不能对地理数据进行有效的索引，所以需要研究特殊的能适应多维特性的空间索引方式。1984 年 Guttman 发表了 R树: 一种空间查询的动态索引结构，它是一种高度平衡的树， 由中间节点和页节点组成， 实际数据对象的最小

20、外接矩形存储在页节点中，中间节点通过聚集其低层节点的外接矩形形成，包含所有这些外接矩形。其后，人们在此基础上针对不同空间运算提出了不同改进，才形成了一个繁荣的索引树族，是目前流行的空间索引。R树是 B树 向多维空间发展的另一种形式， 它将空间对象按范围划分， 每个结点都对应一个区域和一个磁盘页， 非叶结点的磁盘页中存储其所有子结点的区域范围，非叶结点的所有子结点的区域都落在它的区域范围之内；叶结点的磁盘页中存储其区域范围之内的所有空间对象的外接矩形。每个结点所能拥有的子结点数目有上、下限，下限保证对磁盘空间的有效利用，上限保证每个结点对应一个磁盘页， 当插入新的结点导致某结点要求的空间大于一个

21、磁盘页时，该结点一分为二。 R树是一种动态索引结构， 即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。2 R-Tree 数据结构R-Tree 是一种空间索引数据结构，下面做简要介绍：（1）R-Tree 是 n 叉树， n 称为 R-Tree 的扇（ fan ）。（2）每个结点对应一个矩形。（3）叶子结点上包含了小于等于n 的对象，其对应的矩为所有对象的外包矩形。（4）非叶结点的矩形为所有子结点矩形的外包矩形。R-Tree 的定义很宽泛，同一套数据构造R-Tree，不同方可以得到差别很大名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

22、 - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 的结构。什么样的结构比较优呢？有两标准：（1）位置上相邻的结点尽量在树中聚集为一个父结点。（2）同一层中各兄弟结点相交部分比例尽量小。R树是一种用于处理多维数据的数据结构，用来访问二维或者更高维区域对象组成的空间数据 .R 树是一棵平衡树。树上有两类结点：叶子结点和非叶子结点。每一个结点由若干个索引项构成。对于叶子结点，索引项形如(Index ，Obj_ID) 。其中， Index 表示包围空间数据对象的最小外接矩形MBR ，Obj_ID 标识一个空间数据对象。

23、对于一个非叶子结点，它的索引项形如(Index ，Child_Pointer)。 Child_Pointer 指向该结点的子结点。 Index 仍指一个矩形区域，该矩形区域包围了子结点上所有索引项MBR 的最小矩形区域。 一棵 R树的示例如图所示：3 R-Tree 算法描述算法描述如下：对象数为 n，扇区大小定为 fan 。（1）估计叶结点数 k=n/fan 。（2）将所有几何对象按照其矩形外框中心点的x 值排序。（3）将排序后的对象分组，每组大小为 *fan ，最后一组可能不满员。（4）上述每一分组内按照几何对象矩形外框中心点的y 值排序。（5）排序后每一分组内再分组，每组大小为fan。（6

24、）每一小组成为叶结点，叶子结点数为nn。（7）N=nn ，返回 1。4 R-Tree 空间索引算法的研究历程1 R-Tree 多维索引技术的历史可以追溯到20 世纪 70年代中期。就在那个时候，诸如Cell 算法、四叉树和k-d 树等各种索引技术纷纷问世，但它们的效果都不尽人意。在 GIS和 CAD系统对空间索引技术的需求推动下，Guttman于 1984年提出了 R树索引结构，发表了 R树: 一种空间查询的动态索引结构，它是一种高度平衡的树， 由中间节点和页节点组成， 实际数据对象的最小外接矩形存储在页节点中， 中间节点通过聚集其低层节点的外接矩形形成，包含所有这些外接矩形。其后，人们在此基

25、础上针对不同空间运算提出了不同改进，才形成了一个繁荣的索引树族，是目前流行的空间索引。2 R+树在 Guttman的工作的基础上，许多R树的变种被开发出来， Sellis等提出了 R+ 树，R+ 树与 R树类似，主要区别在于R+ 树中兄弟结点对应的空间区域无重叠，这样划分空间消除了R树因允许结点间的重叠而产生的“死区域”（一个结点内不含本结点数据的空白区域），减少了无效查询数， 从而大大提高空间索引名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - -

26、- - - - - 的效率，但对于插入、 删除空间对象的操作， 则由于操作要保证空间区域无重叠而效率降低。同时R+ 树对跨区域的空间物体的数据的存储是有冗余的，而且随着数据库中数据的增多，冗余信息会不断增长。Greene也提出了他的 R树的变种。3 R*树在 1990年，Beckman和 Kriegel提出了最佳动态 R树的变种 R*树。R*树和 R树一样允许矩形的重叠，但在构造算法R*树不仅考虑了索引空间的“面积”，而且还考虑了索引空间的重叠。该方法对结点的插入、 分裂算法进行了改进，并采用“强制重新插入”的方法使树的结构得到优化。但 R*树算法仍然不能有效地降低空间的重叠程度， 尤其是在数

27、据量较大、 空间维数增加时表现的更为明显。 R*树无法处理维数高于20 的情况。4 QR树QR树利用四叉树将空间划分成一些子空间，在各子空间内使用许多R树索引，从而改良索引空间的重叠。QR 树结合了四叉树与R树的优势，是二者的综合应用。实验证明：与R树相比， QR树以略大（有时甚至略小）的空间开销代价，换取了更高的性能，且索引目标数越多，QR 树的整体性能越好。5 SS 树SS树对 R*树进行了改进， 通过以下措施提高了最邻近查询的性能：用最小边界圆代替最小边界矩形表示区域的形状，增强了最邻近查询的性能， 减少将近一半存储空间； SS树改进了 R*树的强制重插机制。 当维数增加到 5 是，R树

28、及其变种中的边界矩形的重叠将达到90，因此在高维情况（ 5）下，其性能将变的很差，甚至不如顺序扫描。6 X 树X树是线性数组和层状的R树的杂合体，通过引入超级结点，大大地减少了最小边界矩形之间的重叠，提高了查询效率。X树用边界圆进行索引，边界矩形的直径（对角线）比边界圆大，SS树将点分到小直径区域。由于区域的直径对最邻近查询性能的影响较大，因此SS树的最邻近查询性能优于R*树；边界矩形的平均容积比边界圆小， R*树将点分到小容积区域；由于大的容积会产生较多的覆盖， 因此边界矩形在容积方面要优于边界圆。SR树既采用了最小边界圆 （MBS ） ，也采用了最小边界矩形（ MBR ），相对于 SS树，

29、减小了区域的面积，提高了区域之间的分离性，相对于R*树，提高了邻近查询的性能。5 R-Tree 空间索引算法的最新研究信息的膨胀使数据库检索需要面对的问题越来越多。在构建索引方面，最主要面临的则是如何构造高效的索引算法来支持各种数据库系统（比如：多媒体数据库、空间数据库等） ，特别是如何有效的利用算法来实现加速检索。概括地说，R-Tree 空间索引算法的研究要做到：支持高维数据空间；有效分割数据空间，来适应索引的组织；高效的实现多种查询方式系统中的统一。R-Tree 的索引结构最新研究不能是单纯为了加速某种查询方式或提高某个方面的性能，忽略其他方面的效果，这样可能会造成更多不必要的性能消耗。X

30、ML作为可扩展的标记语言， 其索引方法就是基于传统的R-Tree 索引技术的XR-Tree 索引方法。该方法构造了适合于XML 数据的索引结构。 XR-Tree 索引方法是一种动态扩充内存的索引数据结构，针对XISS（XML Indexing and Storage System：XML索引和存储体系） 中结构连接中的问题， 设计了基于 XR-Tree 索 引名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 树有效地跳过不参与匹配的元素的连接算法。但这种索引方法在进行路径的连接运算中仍然存储大量的中间匹配结果，为此一种基于整体查询模式的基于索引的路 径连接算法提出，即利用堆栈链表来临时压栈存储产生的部分匹配结果，并且随着匹配的动态进行出栈操作。这样在查询连接处理完成以后， 直接输出最终结果，既节省了存储空间又提高了操作效率。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -