搜索
第6章空间索引与查询6.1空间索引一、空间索引技术二、简单格网空间索引三、四叉树索引四、R树索引五、空间填充曲线对一个数据集做“索引”，是为了提高对这个数据集检索的效率。索引是用来提供快速、有选择性的存取数据库的一种机制。相当于一个映射机构，将属性的值转换为相应的地址或地址集。对于空间数据，其存储主要依赖于空间对象之间的位置关系而非属性值。鉴于空间数据的特点，我们需要寻找适用的空间索引机制。一、空间索引1.空间索引的定义空间索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，一般包括空间要素标识，外包络矩形以及指向空间要素的指针。2.空间索引的作用为了GIS系统中快速定位到所选中的空间要素，从而提高空间操作的速度和效率。空间索引的技术和方法是GIS关键技术之一，是快速高效的查询、检索和显示地理空间数据的重要指标，他的优劣直接影响空间数据库和GIS系统的整体性能。3.空间索引的分类按照搜索分割对象不同,可将空间索引分为3类,即基于点区域划分的索引方法、基于面区域划分的索引方法和基于三维体区域划分的索引方法。B树是常见的基于点区域划分的索引。常见的空间索引常见空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，比较有代表性的包括BSP树、R树、R+树和CELL树等。此外，结构较为简单的格网型空间索引有着广泛的应用。二、简单格网空间索引基本思想是将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。为了便于建立空间索引的线性表,每个格网按一定规律进行编码，建立码与空间实体的关系,该关系表就成为格网索引文件。每个要素在一个或者多个网格中,每个网格可以包含多个要素。21232931535561632022283052546062171925274951575916182426485056585713153739454746121436384446139113335414302810323440422123293153556163202228305254606217192527495157591618242648505658571315373945474612143638444613911333541430281032344042空间索引对象索引Peano键空间对象空间对象Peano键集7BA25-2514EB7-715EC54-5525AC60-6026ED32-3332DD35-3533DD38-3835D.FE14-1537EE26-2638DE37-3739EE39-3948EE48-4850EE50-5054CF35-3555C60CABCEDF每个要素在一个或者多个网格中,每个网格可以包含多个要素,要素不是真正被分割。由此建立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不为空，所以继续往下查找，得到B的NE象限为空，因此，D作为B的NE孩子结点。（4）同理，空间点E、F，分别为A的SE、NE孩子节点。缺点：（1）尽管点四叉树构造简单，但是删除一个节点时，该节点对应的所有子树节点必须重新插入四叉树中，效率很差。（2）对于精确匹配的点查找，效率很高，但是对于区域查找，查找路径有多条，效率较差。（3）树的动态性差，树的结构完全由点的插入顺序决定。树的平衡难以保证。区域四叉树(Region-BasedQuadtree)是以区域目标为循环分解对象的四叉树,分解过程既可以按照区域边界,也可以按照区域内部对二维空间进行划分。如果区域四叉树中的结点覆盖的区域中所有数组元素的值都相同，则该结点是叶子结点。否则，该结点是内部结点，被进一步划分为四个等大小的子结点。主要有MX四叉树与PR四叉树。避免了点四叉树的动态性差、结构完全由点的插入顺序决定的功能缺点。2.区域四叉树MX四叉树MX四叉树将每个空间点看成是区域四叉树中的一个黑象素，或当成一个方阵（SquareMatrix）中的非零元素，因此称为MX四叉树。利用叶子节点为黑节点或空闲点表示数据空间某一位置空间点的存在与否。树的构造过程即是对整个数据空间重复地进行2k次等分，直到每一空间点都位于某一象限的最左下角的过程。MX四叉树特点：空间中每一个点都属于某一象限且位于该象限的最左下角，每一象限只与一个空间点相关联。尽管D同时是两个大小不等的象限的最左下角，但其应属于最下一级象限（即最后一次空间划分所产生的子象限）。这就决定了所有空间点均位于叶子节点。缺点：插入（或删除）一个点可能导致树的深度增加（或减少）一层或多层，所有的叶子节点都必须重新定位。树的深度往往很大，这会影响查找效率。PR（PointRegion）四叉树叶子节点或者为空，或者包含唯一数据点。PR四叉树PR四叉树与MX四叉树的构造过程类似，不同的是，当分解到一个象限只包含一个点时，不需要继续分解使该点位于某一子象限的最左下角。另外，插入或删除一个点也不会影响到其他的分支，操作比较简单。PR四叉树与MX四叉树的区别：（1）数据点位于象限内，不要求位于左下角。（2）叶子节点可能不在树的同一层次。（3）PR四叉树的叶子结点数及树的深度都小于MX四叉树，因此PR四叉树效率高。CIF四叉树CIF四叉树是为了表示VLSI（VeryLargeScaleIntegration)应用中的小矩形而提出的。它可以用于索引空间矩形及其他形体。表示方式与区域四叉树类似，数据空间被递归的细分，直至产生的子象限不再包含任何矩形。在分解过程中，所有与任一划分线相交的矩形与该划分线对应的象限相关联。0数据桶的容量设为3。相交查询：从根节点开始，首先检查与之关联的所有矩形是否为查找结果；接下来检查象限空间与查询区域相交的孩子结点….直到叶子节点。插入矩形：首先检查根节点，如果与根节点的划分线相交，则插入到根节点对应的桶链表中；否则检查包含该矩形的子象限的孩子结点…；如果检查到某一没有孩子的象限，而且该矩形依旧没有插入到对应的位置，那么该象限必须再次细分直到为该矩形找到对应的子象限。删除矩形：找到矩形所在结点，从数据桶中删除。如果删完后桶为空，且该节点没有孩子结点，则可以删除该节点。CIF四叉树可以用于索引矩形以及任何其他形体的空间目标而不需要经过目标近似与空间目标映射，因此对于区与查询，效率相对MX、PR四叉树要高些。但是区域查询往往需要访问多个节点对应的存储桶，尤其当索引量增大，大区域节点所包含较多数据矩形时，外存I/O开销很大。四叉树索引优点：结构清晰，容易建立。它同时具有聚集空间目标的能力（在栅格数据存储中发挥突出作用），提高了检索效率，得到广泛应用。有很多改进的方法被提出：（1）一体化索引，进行了索引空间的三级划分，包括索引块、基本格网、细分格网，并采用行次序法对各级区域进行了编码。（2）CELLQTREE，叶子节点索引点对象，中间节点索引线和面对象，较好的解决了大区域对象的标示符在子空间结点中的多次重复存储问题。四叉树索引的缺点：当索引数据量较大时，如果四叉树层次过小，将导致查找性能下降；如果四叉树层次过大，将导致重复存储的增加，从而增加空间开销，这同时又会影响查找性能。四.R树空间索引1.R树1984年Guttman发表了《R树:一种空间查询的动态索引结构》，首次提出了R树空间索引结构。其后，人们在此基础上针对不同空间运算提出了不同改进，才形成了一个繁荣的索引树族，是目前流行的空间索引。R树是一种高度平衡的树，由中间节点和页节点组成，实际数据对象的最小外接矩形存储在页节点中，中间节点通过聚集其低层节点的外接矩形形成，包含所有这些外接矩形。R树是一种动态索引结构，即：它的查询可与插入或删除同时进行，而且不需要定期地对树结构进行重新组织。R树示例图五、空间填充曲线空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编码，并在一定程度上保持空间邻近性，即相邻的网格的标号也相邻，一个空间对象由一组网格组成。这样可以将多维的空间数据降维表示到一维空间当中。理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码以后，在一维空间中仍然是聚集的。（a）行排序（b）Hilbert排序（c）Z排序图5-30几种常用的空间填充编码方法1)Z-ordering曲线（peano曲线）Z-排序（Z-ordering）技术将数据空间循环分解到更小的子空间（被称为PeanoCell），每个子空间根据分解步骤依次得到一组数字，称为该子空间的Z-排序值。子空间有不同的大小，Z-排序有不同的长度，显然，子空间越大，相应的Z-排序值越短。这里，分辨率（resolution）是指最大的分解层次，它决定了Z-排序值的最大长度。图5-31Z-排序示例n=0n=1n=2n=32n×2n个分区，编号为0~2n×2n-12)Hilbert曲线与Z-排序类似，Hilbert曲线也是一种空间填充曲线，它利用一个线性序列来填充空间，其构造过程如图5-33所示。实验证明，Hi1bert曲线的方法比Z-排序好一些，因为它没有斜线。不过Hilbert曲线算法的计算量要比Z-排序复杂。图5-33Hilbert曲线示例n=0n=1n=2n=36.2空间查询一.空间信息与空间信息查询二.空间查询方式三.空间信息查询语言一.空间信息与空间信息查询空间位置和形态•对象所在的地理区域，对象的几何和属性特征。空间关系和关联•空间对象间的拓扑关系。空间分布规律•特定类别地物分布在特定的区域，如电子市场、娱乐场所、饮食街等。时空演化•通过时间空间数据分析，可以研究和揭示事物发展演化的规律。空间信息分类空间信息查询查询什么•空间查询的一般问题是“有没有？”、“是什么？”、“在什么地方？”、“怎样（到达）？”查询对象图形中的信息属性表中的信息其它信息•一般问题是“某图元代表什么实体，有什么属性”、“处于什么位置、距离、路径”、“一定范围内包含的地物，地物之间的关系等”。查询的意义信息管理•通过查询可以获取特定数据，进行信息管理和数据更新。特定信息提取•通过查询提取需要的信息，据弃无关的信息，便于使用。空间分析基础•查询结果一般是对所需查找的信息及数据的报告，研究需要对这些数据单独提出进行相关分析。1、图查文(图形查询属性)2、文查图(属性查询图形)2、空间关系的查询(面—点、面—线、面—面、线—点、线—线查询)4、逻辑查询(SQL查询)二.空间查询方式图文互查是GIS中最常用的查询。如：在中国行政区图查人口4000万的省。1）和一般SQL查询类似，构建SQL查询语句进行查询。2）查询到结果后，利用图形和属性的对应关系，再图上表示出结果。1、图查文图查文图查文2、文查图一般GIS软件提供“INFO”工具。用点选、区域圈选、多边形选择、矩形选择的方式选中地物，并显示出查询对象的属性列表。1）利用空间索引，在数据库中快速检索被选空间实体。2）根据实体和属性的连接关系得到所查询实体的属性列表。文查图文查图MapInfo软件中点目标的几何参数查询MapInfo软件中线目标的几何参数查询Mapinfo软件中面状目标的几何参数查询是指给定一个点或一个几何图形，检索出该图形范围内的空间对象以及相应的属性。这种查询方式又称为图形查询属性的方式。MapInfo软件中图形查属性的表达方式ArcView软件中图形查属性的表达方