空间数据索引技术空间数据索引技术与空间查询语言与空间查询语言第七讲2021/8/141 Ø 空间数据索引技术Ø 空间查询语言2021/8/142 空间索引技术空间索引技术一、 空间索引技术二、 简单格网空间索引三、 KD树索引（二叉树索引）四、 B树索引五、 四叉树索引六、 可扩展的哈希索引七、 空间填充曲线2021/8/143 1)点四叉树索引n点四叉树是点四叉树是QuadTreeQuadTree的一个变种，主要是针的一个变种，主要是针对空间点的存储表达与索引，与对空间点的存储表达与索引，与KDKD树相似，树相似，两者的差别是在点四叉树中，空间被分割成两者的差别是在点四叉树中，空间被分割成四个矩形，四个不同的多边形对应于四个矩形，四个不同的多边形对应于SWSW、、NWNW、、SESE、、NENE四个象限四个象限n点四叉树的每个结点存储了一个空间点的信点四叉树的每个结点存储了一个空间点的信息及孩子结点的指针息及孩子结点的指针五、四叉树索引2021/8/144 （（a a）平面图）平面图 （（b b）结构图）结构图 图图5-22 5-22 一颗二维的点四叉树结构一颗二维的点四叉树结构2021/8/145 n点四叉树的结构简单，对于精确匹配的点查点四叉树的结构简单，对于精确匹配的点查找性能较高，查找路径只有一条。
找性能较高，查找路径只有一条n但对区域查找，查找路径有多条，查找性能但对区域查找，查找路径有多条，查找性能较差n其搜索过程和其搜索过程和KDKD树相似，如果想从树相似，如果想从Point Point QuadTreeQuadTree中删除一个点的话，则会引起相应中删除一个点的话，则会引起相应的子树的重建，一个简单的方法是将所有子的子树的重建，一个简单的方法是将所有子树上的数据重新插入树上的数据重新插入2021/8/146 2) PR四叉树nPRPR四叉树是点四叉树的一个变种，它不使用数据集四叉树是点四叉树的一个变种，它不使用数据集中的点来分割空间在中的点来分割空间在PRPR四叉树中，每次分割空间四叉树中，每次分割空间时，都是将一个正方形分成四个相等的子正方形，时，都是将一个正方形分成四个相等的子正方形，依次进行，直到每个正方形的内容不超过所给定的依次进行，直到每个正方形的内容不超过所给定的桶量（比如一个对象）为止桶量（比如一个对象）为止 nPRPR四叉树叶子结点可能不在树的同一层次；叶子结四叉树叶子结点可能不在树的同一层次；叶子结点的黑结点或空结点分别表示数据空间某一位置空点的黑结点或空结点分别表示数据空间某一位置空间点的存在与否。
间点的存在与否2021/8/147 图图5-24 PR5-24 PR四叉树的索引结构四叉树的索引结构2021/8/148 3) CIF四叉树索引n它的组织方式与区域四叉树相似，数据空间它的组织方式与区域四叉树相似，数据空间被递归地细分直至产生的子象限不再包含任被递归地细分直至产生的子象限不再包含任何矩形n在分解的过程中，与任一划分线相交的矩形在分解的过程中，与任一划分线相交的矩形与该划分线对应的象限相关联，与该划分线对应的象限相关联，矩形只属于矩形只属于完全包围它的最小象限完全包围它的最小象限图5-255-25是二维空间是二维空间一颗一颗CIFCIF树的例子（这里假设数据桶的容量树的例子（这里假设数据桶的容量为为3 3个矩形）个矩形） 2021/8/149 （（a a）平面图）平面图 （（b b）结构图）结构图 （（c c）桶表）桶表 图图5-25 5-25 二维空间二维空间CIFCIF四叉树的一个例子四叉树的一个例子2021/8/1410 4) 基于固定网格划分的四叉树索引n在基于固定网格空间划分的四叉树空间索引机制在基于固定网格空间划分的四叉树空间索引机制中，二维空间范围被划分为一系列大小相等的棋中，二维空间范围被划分为一系列大小相等的棋盘状矩形，即将地理空间的长和宽在盘状矩形，即将地理空间的长和宽在X X和和Y Y方向上方向上进行进行2 2N N等分，形成等分，形成2 2N N×2×2N N的网格，并以此建立的网格，并以此建立N N级级四叉树。
四叉树n在四叉树中，空间要素标识记录在其外包络矩形在四叉树中，空间要素标识记录在其外包络矩形所覆盖的每一个叶结点中所覆盖的每一个叶结点中¨但当同一父亲的四个兄弟结点都要记录该空间要素标但当同一父亲的四个兄弟结点都要记录该空间要素标识时，则只将该空间要素标识记录在该父亲结点上，识时，则只将该空间要素标识记录在该父亲结点上，并按这一规则向上层推进并按这一规则向上层推进2021/8/1411 有效减少了大的空间要有效减少了大的空间要素（跨越多个网格）在素（跨越多个网格）在结点中的重复记录结点中的重复记录2021/8/1412 网格文件n网格文件是一种典型的基于哈希的存取方式，网格文件是一种典型的基于哈希的存取方式，它是由包含着很多与数据桶相联系的单元的它是由包含着很多与数据桶相联系的单元的网格目录来实现网格目录来实现n对于二维空间为平行于对于二维空间为平行于x x或或y y轴的直线，这一轴的直线，这一超平面将数据空间划分为两个子空间所有超平面将数据空间划分为两个子空间所有的边界一起将整个数据空间划分成许多的边界一起将整个数据空间划分成许多k k维维的矩形子空间，这些矩形子空间称为网格目的矩形子空间，这些矩形子空间称为网格目录，由一个录，由一个k k维的数组表示。
维的数组表示六、可扩展的哈希索引2021/8/1413 图图5-28 5-28 网格文件的结构网格文件的结构2021/8/1414 n目录项（即网格目录数组的元素）和网格单目录项（即网格目录数组的元素）和网格单元之间具有一对一的关系网格目录的每一元之间具有一对一的关系网格目录的每一网格单元包含一个外存页的地址，对应着一网格单元包含一个外存页的地址，对应着一个数据桶，一般一个数据桶为硬盘上一个磁个数据桶，一般一个数据桶为硬盘上一个磁盘页，这一外存页存储了包含了网格单元的盘页，这一外存页存储了包含了网格单元的数据目标，称为数据页数据目标，称为数据页n数据页所对应的一个或多个网格单元称之为数据页所对应的一个或多个网格单元称之为存储区域存储区域两两不相交每个数据桶存储区域存储区域两两不相交每个数据桶往往可以包含着几个相邻的单元，存储多个往往可以包含着几个相邻的单元，存储多个网格单元的目标，只要这几个网格单元一起网格单元的目标，只要这几个网格单元一起形成一矩形的区域形成一矩形的区域 六、可扩展的哈希索引2021/8/1415 D5D4D6网格文件插入目录示意图网格文件插入目录示意图2021/8/1416 七、空间填充曲线n空间填充曲线是一种重要的近似表示方法，将数空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网格，再根据一定的方据空间划分成大小相同的网格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编码，法将这些网格编码，每个格指定一个唯一的编码，并在一定程度上保持并在一定程度上保持空间邻近性空间邻近性，即，即相邻的网格相邻的网格的标号也相邻，的标号也相邻，一个空间对象由一组网格组成。
一个空间对象由一组网格组成这样可以将多维的空间数据降维表示到一维空间这样可以将多维的空间数据降维表示到一维空间当中n理想的空间映射方法是：在多维空间中聚集的空理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码以后，在一维空间中间实体，经过填充曲线编码以后，在一维空间中仍然是聚集的仍然是聚集的 2021/8/1417 （（a a）行排序）行排序 （（b b））HilbertHilbert排序排序 （（c c））Z Z排序排序 图图5-30 5-30 几种常用的空间填充编码方法几种常用的空间填充编码方法2021/8/1418 1) Z-ordering曲线（peano曲线）lZ-排序（Z-ordering）技术将数据空间循环分解到更小的子空间（被称为Peano Cell），每个子空间根据分解步骤依次得到一组数字，称为该子空间的Z-排序值l子空间有不同的大小，Z-排序有不同的长度，显然，子空间越大，相应的Z-排序值越短。
这里，分辨率（resolution）是指最大的分解层次，它决定了Z-排序值的最大长度 2021/8/1419 图图5-31 Z-5-31 Z-排序示例排序示例2n ×2n个分区， 编号为0~2n ×2n-12021/8/1420 2) Hilbert曲线n与与Z-Z-排序类似，排序类似，HilbertHilbert曲线也是一种曲线也是一种空间填充曲线，它利用一个线性序列来空间填充曲线，它利用一个线性序列来填充空间，其构造过程如图填充空间，其构造过程如图5-335-33所示n实验证明，实验证明，Hi1bertHi1bert曲线的方法比曲线的方法比Z-Z-排排序好一些，因为它没有斜线不过序好一些，因为它没有斜线不过HilbertHilbert曲线算法的计算量要比曲线算法的计算量要比Z-Z-排序排序复杂2021/8/1421 图图5-33 Hilbert5-33 Hilbert曲线示例曲线示例2021/8/1422 空间查询语言空间查询语言一、扩展一、扩展SQLSQL以处理空间数据以处理空间数据二、对象二、对象——关系查询语言关系查询语言三、强调空间的查询示例三、强调空间的查询示例四、空间查询处理四、空间查询处理 2021/8/1423 n突破关系模型中关系必须是第一范式的限制，突破关系模型中关系必须是第一范式的限制，允许定义层次关系和嵌套关系。
允许定义层次关系和嵌套关系n增加抽象数据类型，如点、线、面、栅格、图增加抽象数据类型，如点、线、面、栅格、图像等n增加空间谓词如表示空间关系的，包含、相增加空间谓词如表示空间关系的，包含、相交等，表示空间操作的，叠加、缓冲区等交等，表示空间操作的，叠加、缓冲区等n增加适合空间数据索引的方法，如增加适合空间数据索引的方法，如R数、四叉数、四叉树等一、扩展一、扩展SQLSQL以处理空间数据以处理空间数据在在SQL的基础上进行扩展将是管理和分析空间的基础上进行扩展将是管理和分析空间数据的一个趋势扩展关系模型主要表现在：数据的一个趋势扩展关系模型主要表现在：2021/8/1424 2021/8/1425 定义的空间操作算子包括基本操作、空间关系运定义的空间操作算子包括基本操作、空间关系运算和空间分析操作算和空间分析操作2021/8/1426 2021/8/1427 2021/8/1428 1 1））SQL3SQL3（（ SQL99 SQL99）概览）概览Ø它详细地描述了空间数据类型点、线、面在数据它详细地描述了空间数据类型点、线、面在数据库中的存储方式，并能够定义操作于空间数据的库中的存储方式，并能够定义操作于空间数据的空间运算符。
空间运算符Ø支持抽象数据类型（支持抽象数据类型（Abstract Data Type, ADT Abstract Data Type, ADT ) ) 并且包括了指定拓扑操作和空间分析操作并且包括了指定拓扑操作和空间分析操作Ø可以使用可以使用CREATE TYPECREATE TYPE语句来定义语句来定义ADT, ADTADT, ADT由一由一组属性和访问这些属性的方法组成组属性和访问这些属性的方法组成ADTADT可以作可以作为关系模式中某一列的类型为关系模式中某一列的类型二、对象二、对象——关系查询语言（关系查询语言（OR-SQLOR-SQL）） 2021/8/1429 扩展方案扩展方案ADT ADT ：：二、对象二、对象——关系查询语言（关系查询语言（OR-SQLOR-SQL）） 2021/8/1430 三、强调空间的查询示例三、强调空间的查询示例2021/8/1431 ① ① 查询：列出查询：列出countrycountry表中所有与美国表中所有与美国(USA)(USA)相邻的国相邻的国家名字② ② 查询：找出查询：找出RiverRiver表中所列出的河流流经的国家。
表中所列出的河流流经的国家2021/8/1432 ③ ③ 查询：对于查询：对于RiverRiver表中列出的河流，在表中列出的河流，在CityCity表中找表中找到距离其最近的城市到距离其最近的城市④ ④ 查询：圣劳伦斯河能为方圆查询：圣劳伦斯河能为方圆300300公里以内的城市供公里以内的城市供水，列出能从该河获得供水的城市水，列出能从该河获得供水的城市 2021/8/1433 ⑤⑤查询：求出河流在流经的各国境内的长度查询：求出河流在流经的各国境内的长度⑥⑥查询：按其邻国数目的多少列出所有国家查询：按其邻国数目的多少列出所有国家2021/8/1434 n过滤筛选步骤（过滤筛选步骤（Filter）：）：n细化步骤（细化步骤（Refine）：）：n用一个不精确的大致范围来进行查询，产生用一个不精确的大致范围来进行查询，产生一个满足条件的较小候选集合对候选集合一个满足条件的较小候选集合对候选集合中的对象进行精确的筛选，产生最终的查询中的对象进行精确的筛选，产生最终的查询结果四、空间查询处理四、空间查询处理2021/8/1435 2021/8/1436 2021/8/1437 本讲重点内容本讲重点内容Ø 空间索引的定义Ø 各种空间索引方法Ø 主要的空间操作算子 Ø 空间查询的处理步骤2021/8/1438 部分资料从网络收集整理而来，供大家参考，感谢您的关注！ 。