《空间数据组织与管理》由会员分享，可在线阅读，更多相关《空间数据组织与管理（31页珍藏版）》请在金锄头文库上搜索。
1、姓名：马孟学号：2016127012空间查询与索引空间索引定义空间索引是指依据空间实体的位置和形状或空间实体之间的某种 空间关系，按一定顺序排列的一种数据结构，其中包含空间实体 的概要信息如对象的标识、最小边界矩形及指向空间实体数据的 指针。内容01三个基本知识02网络索引03四叉树索引目录R树索引04空间查询051最小边界矩形三个基本知识2空间填充曲线3空间查询执行过程与索引最小边界矩形：（minimum bounding rectangle,MBR）是GIS或 计算机图形学上非常重要的概念。几何对象的MBR是该几何对象的最小外接矩形，但该几何的边 必须平行于X,Y轴。由于MBR是平行于X，
2、Y轴的规则图形，故对 空间几何对象MBR的几何运算，要比原本复杂几何对象的运算简 单得多。Z曲线1Hilbert曲线2空间填充曲线空间填充曲线（space-filling curve）是一种降低空间维度的方法。它是一条 连续曲线，自身没有任何交叉，可以通过访问所有网络单元来填充包含均匀 网络的四边形。常用的空间填充曲Z曲线、Hilbert曲线。空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网 格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编码，并在 一定程度上保持空间邻近性，即相邻的网格的标号也相邻，一个空间对象由 一组网格组成。这样可以将多维的空间数据降维表示到一
3、维空间当中。理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码 以后，在一维空间中仍然是聚集的Z曲线Z曲线沿着一条“Z”字形路径来填充数据空间。 Z-排序（Z-ordering）技术将数据空间循环分解到更小的子空间，每个子空间根据分解 步骤依次得到一组数字，称为该子空间的Z-排序值。 数据空间经Z曲线填充后，按照Z曲线经过的顺序，每个网格空间都会被赋予一定得值。 通常来说，Z值邻近网络空间位置也相对邻近。Z曲线示例图Hilbert曲线Hilbert曲线沿着一条“”字形路径来填充数据空间 数据空间经Hilbert曲线填充后，按照Hilbert曲线经过的顺序，每个网格空间也会被赋予
4、一定 的值。通常来说，Hilbert值邻近网络空间位置也相对邻近。 相比之下，Hilbert曲线的数据聚集特性更优，即Hilbert值邻近网络空间位置的邻近性更好； 而Z曲线聚集特性较差。但是，Hilbert曲线的映射过程较复杂，Z曲线的映射过程较简单Hilbert曲线示例图空间查询执行过程与空间索引空间查询候选集精确几何的输入实际几何对象精确检测匹配不匹配查询结果过滤步精炼步空间索引空间查询执行过程空间数据库中空间查询操作一般分为过滤和精炼两步执行，过滤步是利 用空间对象索引编目信息以及空间对象的近似形状，检索出可能满足该空间 查询条件的对象候选集；精炼步是对候选集中的空间对象按查询要求进行
5、精 确的计算处理，以获得满足查询条件的最终结果。网络索引网格索引思路比较简单。基本思想是将研究的N维空间区域用横竖划分 为大小相等的网格，用一个N维数据来记录每一个网格所包含的空间要素。 当用户进行空间查询时，首先计算出查询空间要素所在的网格，然后通过该 网格快速定位到所选择的空间要素。通常是把整个数据库数值空间划分成 3232（或6464）的正方形网格，建立另一个倒排文件栅格索引。每一 个网格在栅格索引中有一个索引条目(记录)，在这个记录中登记所有位于或 穿过该网格的物体的关键字，可用变长指针法或位图法实现在下图中有三个制图物体：一条河流、一个湖泊和一条省界，它们的关键字 分别为5，11和2
6、3。河流穿过的栅格为2，34，35，67，68；湖泊覆盖的栅格 为68，69，100，101；省界所通过的栅格为5，37，36，35，67，99，98，97 。这种物体与栅格的关系可用位图法来表示。由图看出，一个栅格中包含的 物体个数就是该栅格在栅格索引的对应记录中存贮的比特“1”的个数。这是定 位(开窗)检索的基本工具。此外，物体与栅格的关系亦可用变长指针法表示， 如图所示网络索引3254321643736353433966968676665(5)(11)(23)网络索引网络索引网络索引网络索引最大的优点就是简单，易于实现。其次，网络索引具有良好的可扩 展性。网络化可以通过网络编号向正负方向
7、上不断延展以反映整个二维空间 的情况。可以看出：网络索引在追加新要素记录时，无论在扩展网络范围， 还是增加网格记录项上都有很好的可扩展性。网络范围的可扩展性是四叉树 索引所不可比拟的。四叉树索引四叉树索引就是为了实现要素真正被网络分割、同时保证桶内要素不超过某 一个量而提出的一种空间索引方法。四叉树索引首先将整个数据空间分割成为四个相等的矩形，四个不同的矩形 分别对应西北（NW）、东北（NE）、西南（SW）、东南（SE）四个象限 ；若每个象限内包含的要素不超过给定的桶量则停止，否则对超过的桶量的 矩形再按同样的方法进行划分，直到桶量满足要求或不会再减少为止，最终 形成一颗有层次的四叉树。四叉树
8、索引四叉树索引四叉树索引在一定程度上实现了地理要素真正被网络分割，保证了桶内要素不超过某一个量，提高 了检索效率。但是对于海量空间数据，四叉树索引的性能有可能并不十分理想。因为当空间数据量较大 时，四叉树的树根往往很深，这无疑会影响查询效率；但如果压缩四叉树深度，又将导致划分到同一个 区域的对象数过多，从而影响检索性能。此外，四叉树的可扩展性不如网络索引。若是扩大空间区域， 则必须重新划分空间区域，重建四叉树；若是增加（删除）一个空间对象，则可能导致树的深度增加（ 减少）一层或多层，相关的叶子结点都必须重新定位。R树索引R树用空间对象的最小边界矩形（MBR）来逼近其几何形状，采用空间聚集的方式
9、把相邻近的空间实体划分到一起，组成更高一级的节点；在更高 一级又根据这些节点的最小外包矩形进行聚集，划分形成更高一级的节点， 直到所有的实体组成一个根节点。R树索引R树索引特点：除根结点外，每个叶节点包含mM条索引记录（其中mM/2）;每个叶结点上记录了空间对象的MBR和元组标识符；除根结点外，每个中间结点至多有M个子结点，至少有m个子结点；每个非叶结点上记录了（MBR，子结点指针），其MBR为空间上包含其 子结点中矩形的最小外包矩形；若根结点不是叶结点，则至少包含2个子结点；所有的叶结点出现在同一层中；所有MBR的边与一个全局坐标系的坐标轴平行；R树索引优点采用空间聚类的方法对数据进行分区，
10、提高了空间分区节点的利用效率；R树作为一棵平衡树，也降低了树的深度，提高了R树的检索效率；缺点由于R树非叶结点的MBR允许重叠，这样会导致同一空间查询出现多条查 询路径情况R树索引要想得到一棵高效的R树，需尽量追求以下几点：非叶结点MBR的面积尽可能小，其中不被其下级节点覆盖的面积尽可能 小。这样，查找分支的决策可以在树的更高层进行，从而改进查询性能。各非叶结点MBR的重叠尽可能小，这样可以减少查找路径的数目。非叶结点MBR的周长可能小。尽可能提高每个节点的子结点的数目，提高空间利用率，降低树的深度。空间查询01定义02空间几何查询03空间定位查询04空间关系查询05SQL（结构化查询语言）查
11、询目录空间查询定义：根据空间特征本身的特性及与其他特征之间的空间关系，用一定方式 查询满足条件的特征。空间几何查询应用GIS本身具有的几何量算的功能，查询空间特征的几何参数。点：坐标，两点间的距离。线：长度，点到线的距离。面：面积，周长。空间查询空间定位查询图形的定位（选择）有多种形式：（1）点查询：查询一个对象；（2）矩形查询；（3）圆查询；（4）多边形查询。后三者都是查询一组对象。例如查询落入某行政区内的道路、景点等。空间查询空间关系查询邻接查询邻接关系包含查询包含关系穿越查询线面相交关系落入查询包含关系缓冲区查询包含关系反向查询例如：A包含B，若由A查询B则为包含查询；反 之，若由B查询
12、A则为落入查询。空间查询SQL（结构化查询语言查询）由属性条件查询相应的图形。用SQL语言构造条件语句，查询满足条件的图 形。例如：查询人口50万的县或市。Select 人口（属性项）From 县或市（属性表）Where 县或市人口 50万（条件）一般的GIS软件都设计了比较好的用户界面，交互式选择和输入有关语句 的内容，代替键入完整的查询条件语句。另外， SQL属性条件和空间关系的图形条件组合在一起，形成扩展的SQL 查询语言空间查询在某些复杂的应用中，还可以构造一些嵌套查询和集合查询。下面给出了复杂 查询的示例。其中，前两个示例为嵌套查询，后一个示例为集合查询。找出距离Stream中河流中
13、心线最近的一个区域。SELECT Z1.name,S1.NameFROM Zone Z1,Streams S1WHERE ST_Distance(Z1.Boundary,S1.Centerline)Z2.name)空间查询找出中心线长度超过“主街”的所有路段SELECT RS1，name FROM Road_Segments RS1WHERE ST_Length(RS1.Centerline)ANY(SELECT ST_Length(RS2.Centerline)FROM Road_Segments RS2WHERE RS2.Name主街)空间查询列出数据库中所有池塘和湖泊的名字和形状SELECT Name,ShoresFROM PondsUNIONSELECT Name,ShoreFROM Lakes谢谢观赏谢谢观赏谢谢观赏
