第六讲 空间数据索引技术与空间查询语言(2)ppt课件

空间数据索引技术和空间查询语言，第7课，1课，空间数据索引技术空间查询语言，第2课，空间索引技术，1课，空间索引技术2，简单网格空间索引3，KD树索引(二叉树索引)4，b树索引5，四树索引6，可扩展散列索引7与KD树相似的空间点的存储表示和索引的主要区别在于，空间分为四个矩形，其他四个多边形对应于SW、NW、SE、NE四个象限。点quadtree中的每个节点均存储有关空间点的信息和指向点节点的指针。5，4，4，(a)平面(b)结构图5-22二维点四元树结构，5，点四元树结构简单精确匹配的点只有一个查找路径。但是，区域查询具有多个查询路径，并且查询性能很差。搜索过程类似于KD树，如果要从PointQuadTree中删除一个点，只需重新插入所有子树中的数据即可重建子树。6，2)PR四元树，即不使用数据集的点分割空间的点四元树的变体。PR quadtree每次拆分空间时，都会将矩形分为四个相同的子矩形，然后依次进行，直到每个矩形的内容不超过指定的桶数(例如对象)。PR quadtree子节点可能不在树的同一级别。叶节点的黑色或空节点分别表示数据空间中某个位置的空间点是否存在。7，图5-24PR四元树的索引结构，8，3)CIF四元树索引的配置类似于区域四元树，数据空间递归细分，直到结果子四元菜单不再包含矩形。在分解过程中，与任何分隔线相交的矩形与相应分隔线的象限相关联，矩形仅属于完全封闭的最小象限。图5-25是二维空间的CIF树的示例(此处假定数据存储桶的容量为3个矩形)。9，(a)平面(b)图表(c)桶形表5-25二维空间CIF四元树的示例，10，4)基于固定栅格分割的四元树索引在基于固定栅格空间的四元树空间索引机制中被划分为一系列二维空间范围类似的棋盘形矩形，即地理空间的长度和宽度在x和y方向为22在四元树中，空间要素标识外部包络矩形包围的每个叶节点上的记录。但是，如果要记录同一父的所有四个同级节点的空间要素id，则仅将相应的空间要素id记录在该父节点中，并按照此规则前进到父节点。11，有效减少节点内大型空间要素(跨多个栅格)的重复记录。12，网格文件，网格文件是典型的基于散列的访问方法，超平面是由包含连接到数据存储桶的大量单元的网格目录实现的二维空间与x或y轴平行的直线，将数据空间分为两个子空间。所有边界一起将整个数据空间划分为许多k维的矩形子空间(称为栅格目录)。这些矩形子空间显示为k维阵列。6、可扩展散列索引、13、图5-28网格文件的结构、14、目录项(网格目录数组中的元素)和网格单元格之间存在一对一关系。网格目录中的每个网格单元格都具有对应于数据存储桶的外部存储页面地址。硬盘上存储数据目标的磁盘页，数据目标包含网格单元，通常称为数据页。与数据页面对应的一个或多个网格单元格称为存储区域存储区域。每个数据存储桶通常包含多个相邻单元，这些单元存储多个栅格单元的目标，只要多个栅格单元一起形成矩形区域即可。，6，可扩展散列索引，15，D5，D4，D6，栅格文件插入目录图，16，7，空间填充曲线，空间填充曲线是将数据空间划分为相同大小栅格的重要近似值显示方法。然后，每个网格根据特定的方法指定唯一的编码，并保持一定程度的空间接近性。也就是说，相邻格线的标签也相邻，并且一个空间对象由一组格线组成。这将多维空间数据维度化为一维空间。理想的空间映射方法是在多维空间中聚集的空间图元，填充曲线编码后在一维空间中仍然聚集。17，(a)行对齐(b)希尔伯特对齐(c)Z对齐图5-30一些常用空间填充编码方法，18，1)Z-ordering曲线(peano曲线)，Z-对齐()子空间大小不同，Z对齐长度不同，显然子空间越大，相应的Z对齐值越短。其中，“分辨率”(resolution)表示确定Z对齐值最大长度的最大分解层次。19，图5-31Z-对齐示例，2n2n个分区，0到2n-1，20，2)类似于Z对齐的希尔伯特曲线，希尔伯特曲线也是用线性序列填充空间的空间填充曲线，如图5-33所示由于Hi1bert曲线没有斜线，因此实验证明，方法比Z对齐更好。希尔伯特曲线算法比Z对齐更复杂。21，图5-33希尔伯特曲线示例，22，空间查询语言1，用于空间数据处理的SQL扩展2，对象-关系查询语言3，强调空间的查询示例4，空间查询处理，23，可以打破关系模型中关系必须是第一范式的限制，定义层次关系和嵌套关系。添加抽象数据类型，例如点、直线、面、栅格、图像等。增加空间谓词。表示空间关系的、包含、交集等、空间操作、复盖、缓冲区等。增加空间数据索引的适当方法，例如r数、quadtree等。首先，扩展SQL以处理空间数据和基于SQL进行扩展是管理和分析空间数据的趋势。扩展关系模型主要表示在24，25中，定义的空间操作运算符包括基本操作、空间关系操作和空间分析操作。26，27，28，1)SQL3(SQL99)概述详细说明了空间数据类型点、直线和面在数据库中的存储方式，并允许定义用作空间数据的空间运算符。支持抽象数据类型(ADT)，包括指定的拓扑操作和空间分析操作。可以使用CREATETYPE语句定义ADT，ADT由一组属性及其访问方法组成。ADT可以是关系模式下的列类型。二、对象-关系查询语言(OR-SQL)、29、扩展架构ADT:二、对象-关系查询语言(OR-SQL)、30、三、突出空间的查询示例、31、查询：寻找河流表中列出的河流流向的国家。32，查找：对于River表中列出的河，在City表中查找最近的城市。查询：圣劳伦斯河向半径300公里以内的城市供水，列出了可以从这条河供水的城市。33，查询：流动国家的河流长度查询：所有国家根据其邻国的数量有多少。34，Filter step:R