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

《第六讲-空间数据索引技术与空间查询语言(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七讲空间数据索引技术与空间查询语言Ø空间数据索引技术Ø空间查询语言空间索引技术一、空间索引技术二、简单格网空间索引三、KD树索引（二叉树索引）四、B树索引五、四叉树索引六、可扩展的哈希索引七、空间填充曲线五、四叉树索引1)点四叉树索引n点四叉树是QuadTree的一个变种，主要是针对空间点的存储表达与索引，与KD树相似，两者的差别是在点四叉树中，空间被分割成四个矩形，四个不同的多边形对应于SW、NW、SE、NE四个象限。n点四叉树的每个结点存储了一个空间点的信息及孩子结点的指针。(0,100)(100,100)AD(30,90)NWNEB(10,75)SWSEF(80,70)FBCEA(

2、45,45)C(25,15)DE(70,20)(0,0)(100,0)（a）平面图（b）结构图图5-22一颗二维的点四叉树结构n点四叉树的结构简单，对于精确匹配的点查找性能较高，查找路径只有一条。n但对区域查找，查找路径有多条，查找性能较差。n其搜索过程和KD树相似，如果想从PointQuadTree中删除一个点的话，则会引起相应的子树的重建，一个简单的方法是将所有子树上的数据重新插入。2)PR四叉树nPR四叉树是点四叉树的一个变种，它不使用数据集中的点来分割空间。在PR四叉树中，每次分割空间时，都是将一个正方形分成四个相等的子正方形，依次进行，直到每个正方形的内容不超过所给定的桶量（比如

3、一个对象）为止。nPR四叉树叶子结点可能不在树的同一层次；叶子结点的黑结点或空结点分别表示数据空间某一位置空间点的存在与否。HGNENWSWSEEBFGHABCDIDCFI图5-24PR四叉树的索引结构3)CIF四叉树索引n它的组织方式与区域四叉树相似，数据空间被递归地细分直至产生的子象限不再包含任何矩形。n在分解的过程中，与任一划分线相交的矩形与该划分线对应的象限相关联，矩形只属于完全包围它的最小象限。图5-25是二维空间一颗CIF树的例子（这里假设数据桶的容量为3个矩形）。（a）平面图（b）结构图（c）桶表图5-25二维空间CIF四叉树的一个例子4)基于固定网格划分的四叉树索引n在基于

4、固定网格空间划分的四叉树空间索引机制中，二维空间范围被划分为一系列大小相等的棋盘状矩形，即将地理空间的长和宽在X和Y方向上进行2N等分，形成2N×2N的网格，并以此建立N级四叉树。n在四叉树中，空间要素标识记录在其外包络矩形所覆盖的每一个叶结点中。¨但当同一父亲的四个兄弟结点都要记录该空间要素标识时，则只将该空间要素标识记录在该父亲结点上，并按这一规则向上层推进。有效减少了大的空间要素（跨越多个网格）在结点中的重复记录。六、可扩展的哈希索引网格文件n网格文件是一种典型的基于哈希的存取方式，它是由包含着很多与数据桶相联系的单元的网格目录来实现n对于二维空间为平行于x或y轴的直线，这一超平面将

5、数据空间划分为两个子空间。所有的边界一起将整个数据空间划分成许多k维的矩形子空间，这些矩形子空间称为网格目录，由一个k维的数组表示。图5-28网格文件的结构六、可扩展的哈希索引n目录项（即网格目录数组的元素）和网格单元之间具有一对一的关系。网格目录的每一网格单元包含一个外存页的地址，对应着一个数据桶，一般一个数据桶为硬盘上一个磁盘页，这一外存页存储了包含了网格单元的数据目标，称为数据页。n数据页所对应的一个或多个网格单元称之为存储区域存储区域两两不相交。每个数据桶往往可以包含着几个相邻的单元，存储多个网格单元的目标，只要这几个网格单元一起形成一矩形的区域。D5D4D6网格文件插入目录示意图

6、七、空间填充曲线n空间填充曲线是一种重要的近似表示方法，将数据空间划分成大小相同的网格，再根据一定的方法将这些网格编码，每个格指定一个唯一的编码，并在一定程度上保持空间邻近性，即相邻的网格的标号也相邻，一个空间对象由一组网格组成。这样可以将多维的空间数据降维表示到一维空间当中。n理想的空间映射方法是：在多维空间中聚集的空间实体，经过填充曲线编码以后，在一维空间中仍然是聚集的。（a）行排序（b）Hilbert排序（c）Z排序图5-30几种常用的空间填充编码方法1)Z-ordering曲线（peano曲线）lZ-排序（Z-ordering）技术将数据空间循环分解到更小的子空间（被称为Peano

7、Cell），每个子空间根据分解步骤依次得到一组数字，称为该子空间的Z-排序值。l子空间有不同的大小，Z-排序有不同的长度，显然，子空间越大，相应的Z-排序值越短。这里，分辨率（resolution）是指最大的分解层次，它决定了Z-排序值的最大长度。2n×2n个分区，编号为0~2n×2n-1图5-31Z-排序示例2)Hilbert曲线n与Z-排序类似，Hilbert曲线也是一种空间填充曲线，它利用一个线性序列来填充空间，其