空间数据组织与管理课件

1、姓名：马孟 学号：2016127012 空间查询与索引 空间索引定义 空间索引是指依据空间实体的位置和形状或空间实体之间的某种 空间关系，按一定顺序排列的一种数据结构，其中包含空间实体 的概要信息如对象的标识、最小边界矩形及指向空间实体数据的 指针。 内容内容 01 三个基本知识 02 网络索引 03 四叉树索引 目录目录 R树索引 04 空间查询 05 1 最小边界矩形 三个基本知识三个基本知识 2 空间填充曲线 3 空间查询执行过程与索引 最小边界矩形：（minimum bounding rectangle,MBR）是GIS或 计算机图形学上非常重要的概念。 几何对象的MBR是该几何对象的

2、最小外接矩形，但该几何的边 必须平行于X,Y轴。由于MBR是平行于X，Y轴的规则图形，故对 空间几何对象MBR的几何运算，要比原本复杂几何对象的运算简 单得多。 Z曲线 1 Hilbert曲线 2 空间填充曲线 空间填充曲线（space-filling curve）是一种降低空间维度的方法。它是一条 连续曲线，自身没有任何交叉，可以通过访问所有网络单元来填充包含均匀 网络的四边形。常用的空间填充曲Z曲线、Hilbert曲线。 空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网 格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编码，并在 一定程度上保持空间邻近性，即相邻的

3、网格的标号也相邻，一个空间对象由 一组网格组成。这样可以将多维的空间数据降维表示到一维空间当中。 理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码 以后，在一维空间中仍然是聚集的 Z曲线曲线 Z曲线沿着一条“Z”字形路径来填充数据空间。 Z-排序（Z-ordering）技术将数据空间循环分解到更小的子空间，每个子空间根据分解 步骤依次得到一组数字，称为该子空间的Z-排序值。 数据空间经Z曲线填充后，按照Z曲线经过的顺序，每个网格空间都会被赋予一定得值。 通常来说，Z值邻近网络空间位置也相对邻近。 8空间数据组织与管理 Hilbert曲线沿着一条“”字形路径来填充数据空间 数据

4、空间经Hilbert曲线填充后，按照Hilbert曲线经过的顺序，每个网格空间也会被赋予一定 的值。通常来说，Hilbert值邻近网络空间位置也相对邻近。 相比之下，Hilbert曲线的数据聚集特性更优，即Hilbert值邻近网络空间位置的邻近性更好； 而Z曲线聚集特性较差。但是，Hilbert曲线的映射过程较复杂，Z曲线的映射过程较简单 9空间数据组织与管理 空间查询 候选集 精确几何的输入 实际几何对象精确检测 匹配不匹配 查询结果 过滤步精炼步 空间索引 10空间数据组织与管理 网络索引 网格索引思路比较简单。基本思想是将研究的网格索引思路比较简单。基本思想是将研究的N维空间区域用横竖划

5、分维空间区域用横竖划分 为大小相等的网格，用一个为大小相等的网格，用一个N维数据来记录每一个网格所包含的空间要素。维数据来记录每一个网格所包含的空间要素。 当用户进行空间查询时，首先计算出查询空间要素所在的网格，然后通过该当用户进行空间查询时，首先计算出查询空间要素所在的网格，然后通过该 网格快速定位到所选择的空间要素。通常是把整个数据库数值空间划分成网格快速定位到所选择的空间要素。通常是把整个数据库数值空间划分成 3232（或（或6464）的正方形网格，建立另一个倒排文件）的正方形网格，建立另一个倒排文件栅格索引。每栅格索引。每 一个网格在栅格索引中有一个索引条目一个网格在栅格索引中有一个索

6、引条目(记录记录)，在这个记录中登记所有位于，在这个记录中登记所有位于 或穿过该网格的物体的关键字，可用变长指针法或位图法实现或穿过该网格的物体的关键字，可用变长指针法或位图法实现 在下图中有三个制图物体：一条河流、一个湖泊和一条省界，它们的关键字在下图中有三个制图物体：一条河流、一个湖泊和一条省界，它们的关键字 分别为分别为5，11和和23。河流穿过的栅格为。河流穿过的栅格为2，34，35，67，68；湖泊覆盖的栅格；湖泊覆盖的栅格 为为68，69，100，101；省界所通过的栅格为；省界所通过的栅格为5，37，36，35，67，99，98，97。 这种物体与栅格的关系可用位图法来表示。由图

7、看出，一个栅格中包含的物这种物体与栅格的关系可用位图法来表示。由图看出，一个栅格中包含的物 体个数就是该栅格在栅格索引的对应记录中存贮的比特体个数就是该栅格在栅格索引的对应记录中存贮的比特“1”的个数。这是定的个数。这是定 位位(开窗开窗)检索的基本工具。此外，物体与栅格的关系亦可用变长指针法表示，检索的基本工具。此外，物体与栅格的关系亦可用变长指针法表示， 如图所示如图所示 网络索引 3254321 643736353433 966968676665 (5) (11) (23) 13空间数据组织与管理 14空间数据组织与管理 网络索引 网络索引最大的优点就是简单，易于实现。其次，网络索引具有

8、良好的可扩 展性。网络化可以通过网络编号向正负方向上不断延展以反映整个二维空间 的情况。可以看出：网络索引在追加新要素记录时，无论在扩展网络范围， 还是增加网格记录项上都有很好的可扩展性。网络范围的可扩展性是四叉树 索引所不可比拟的。 四叉树索引 四叉树索引就是为了实现要素真正被网络分割、同时保证桶内要素不超过某 一个量而提出的一种空间索引方法。 四叉树索引首先将整个数据空间分割成为四个相等的矩形，四个不同的矩形 分别对应西北（NW）、东北（NE）、西南（SW）、东南（SE）四个象限； 若每个象限内包含的要素不超过给定的桶量则停止，否则对超过的桶量的矩 形再按同样的方法进行划分，直到桶量满足要

9、求或不会再减少为止，最终形 成一颗有层次的四叉树。 NENWSWSE BCD D C B A G H FI E I F H G 17空间数据组织与管理 R树索引 R树用空间对象的最小边界矩形（MBR）来逼近其几何形状，采用空间 聚集的方式把相邻近的空间实体划分到一起，组成更高一级的节点；在更高 一级又根据这些节点的最小外包矩形进行聚集，划分形成更高一级的节点， 直到所有的实体组成一个根节点。 19空间数据组织与管理 R树索引 特点： 除根结点外，每个叶节点包含mM条索引记录（其中mM/2）; 每个叶结点上记录了空间对象的MBR和元组标识符； 除根结点外，每个中间结点至多有M个子结点，至少有m个

10、子结点； 每个非叶结点上记录了（MBR，子结点指针），其MBR为空间上包含其 子结点中矩形的最小外包矩形； 若根结点不是叶结点，则至少包含2个子结点； 所有的叶结点出现在同一层中； 所有MBR的边与一个全局坐标系的坐标轴平行； R树索引 优点 采用空间聚类的方法对数据进行分区，提高了空间分区节点的利用效率； R树作为一棵平衡树，也降低了树的深度，提高了R树的检索效率； 缺点 由于R树非叶结点的MBR允许重叠，这样会导致同一空间查询出现多条查 询路径情况 R树索引 要想得到一棵高效的R树，需尽量追求以下几点： 非叶结点MBR的面积尽可能小，其中不被其下级节点覆盖的面积尽可能小。 这样，查找分支的

11、决策可以在树的更高层进行，从而改进查询性能。 各非叶结点MBR的重叠尽可能小，这样可以减少查找路径的数目。 非叶结点MBR的周长可能小。 尽可能提高每个节点的子结点的数目，提高空间利用率，降低树的深度。 空间查询空间查询 01 定义 02 空间几何查询 03 空间定位查询 04 空间关系查询 05 SQL（结构化查询语言）查询 目录目录 空间查询 定义：根据空间特征本身的特性及与其他特征之间的空间关系，用一定方式 查询满足条件的特征。 空间几何查询 应用GIS本身具有的几何量算的功能，查询空间特征的几何参数。 点：坐标，两点间的距离。 线：长度，点到线的距离。 面：面积，周长。 空间查询 空间

12、定位查询 图形的定位（选择）有多种形式： （1）点查询：查询一个对象； （2）矩形查询； （3）圆查询； （4）多边形查询。 后三者都是查询一组对象。例如查询落入某行政区内的道路、景点等。 空间查询 空间关系查询 邻接查询 邻接关系 包含查询 包含关系 穿越查询 线面相交关系 落入查询 包含关系 缓冲区查询 包含关系 反向查询 例如：A包含B，若由A查询B则为包含查询；反 之，若由B查询A则为落入查询。 空间查询 SQL（结构化查询语言查询） 由属性条件查询相应的图形。用SQL语言构造条件语句，查询满足条件的图 形。例如：查询人口50万的县或市。 Select 人口（属性项） From 县或市

13、（属性表） Where县或市人口 50万（条件） 一般的GIS软件都设计了比较好的用户界面，交互式选择和输入有关语句 的内容，代替键入完整的查询条件语句。 另外， SQL属性条件和空间关系的图形条件组合在一起，形成扩展的SQL 查询语言 空间查询 在某些复杂的应用中，还可以构造一些嵌套查询和集合查询。下面给出了复杂 查询的示例。其中，前两个示例为嵌套查询，后一个示例为集合查询。 找出距离Stream中河流中心线最近的一个区域。 SELECT Z1.name,S1.Name FROM Zone Z1,Streams S1 WHERE ST_Distance(Z1.Boundary,S1.Centerline) ALL(SELECT ST_Distance(Z2.Boundary,S1.Centerline) FROM Zone Z2 WHERE Z1.NameZ2.name) 空间查询 找出中心线长度超过“主街”的所有路段 SELECT RS1，name FROM Road_