第6章-空间索引与空间信息查询.ppt

《第6章-空间索引与空间信息查询.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章空间索引与查询6.1空间索引一、空间索引技术二、简单格网空间索引三、四叉树索引四、R树索引五、空间填充曲线对一个数据集做“索引”，是为了提高对这个数据集检索的效率。索引是用来提供快速、有选择性的存取数据库的一种机制。相当于一个映射机构，将属性的值转换为相应的地址或地址集。对于空间数据，其存储主要依赖于空间对象之间的位置关系而非属性值。鉴于空间数据的特点，我们需要寻找适用的空间索引机制。一、空间索引1.空间索引的定义空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。2.空间索

2、引的作用为了GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。空间索引的技术和方法是GIS关键技术之一，是快速高效的查询、检索和显示地理空间数据的重要指标，他的优劣直接影响空间数据库和GIS系统的整体性能。3.空间索引的分类按照搜索分割对象不同,可将空间索引分为3类,即基于点区域划分的索引方法、基于面区域划分的索引方法和基于三维体区域划分的索引方法。B树是常见的基于点区域划分的索引。常见的空间索引常见空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，比较有代表性的包括BSP树、R树、R+树和CELL树等。此外，结构较为简单的格网型空间索引有着广泛的应用。二

3、、简单格网空间索引基本思想是将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。为了便于建立空间索引的线性表,每个格网按一定规律进行编码，建立码与空间实体的关系,该关系表就成为格网索引文件。每个要素在一个或者多个网格中,每个网格可以包含多个要素。212329315355616320222830525460621719252749515759161824264850565857131537394547461214363844461

4、39113335414302810323440422123293153556163202228305254606217192527495157591618242648505658571315373945474612143638444613911333541430281032344042空间索引对象索引Peano键空间对象空间对象Peano键集7BA25-2514EB7-715EC54-5525AC60-6026ED32-3332DD35-3533DD38-3835D.FE14-1537EE26-2638DE37-3739EE39-3948EE48-4850EE50-5054CF35-3

5、555C60CABCEDF每个要素在一个或者多个网格中,每个网格可以包含多个要素,要素不是真正被分割。由此建立Peano键和空间对象的关系。三.四叉树检索点四叉树区域四叉树MX四叉树PR四叉树CIF四叉树1.点四叉树以空间点为划分点，将索引空间分为两两不相交的的2k个子空间，依次与它的2k个子结点相对应，对于位于某一子空间的点，则分配给对应的子树。点四叉树的构造过程：（1）输入空间点A，以A为根节点并进行划分空间。（2）输入空间点B，B落入A的NW象限，并且A的NW象限为空，则B直接放入A的NW象限孩子结点。同理，C是A的SW孩子结点。（3）输入D，由于D落入A的NW象限，但是NW不为

6、空，所以继续往下查找，得到B的NE象限为空，因此，D作为B的NE孩子结点。（4）同理，空间点E、F，分别为A的SE、NE孩子节点。缺点：（1）尽管点四叉树构造简单，但是删除一个节点时，该节点对应的所有子树节点必须重新插入四叉树中，效率很差。（2）对于精确匹配的点查找，效率很高，但是对于区域查找，查找路径有多条，效率较差。（3）树的动态性差，树的结构完全由点的插入顺序决定。树的平衡难以保证。区域四叉树(Region-BasedQuadtree)是以区域目标为循环分解对象的四叉树,分解过程既可以按照区域边界,也可以按照区域内部对二维空间进行划分。如果区域四叉树中的结点覆盖的区域中所有数组元

7、素的值都相同，则该结点是叶子结点。否则，该结点是内部结点，被进一步划分为四个等大小的子结点。主要有MX四叉树与PR四叉树。避免了点四叉树的动态性差、结构完全由点的插入顺序决定的功能缺点。2.区域四叉树MX四叉树MX四叉树将每个空间点看成是区域四叉树中的一个黑象素，或当成一个方阵（SquareMatrix）中的非零元素，因此称为MX四叉树。利用叶子节点为黑节点或空闲点表示数据空间某一位置空间点的存在与否。树的构造过程即是对整个数据空间重复地进行2