空间索引-read.pptVIP

§6.6 空间索引 * 地理信息系统基础 §6.6 空间索引 提出一个问题： 当工作区数据量较大，特别是用无缝的空间数据库管理整个工程的空间数据时，要查询鼠标到底圈选了哪些地物？ 地理信息系统基础 §6.6 空间索引 空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。 常见的空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，比较有代表性的包括四叉树、对象范围、R树、R+ 树和CELL树等。此外，结构较为简单的索引文件、格网索引广泛应用。 地理信息系统基础 §6.6 空间索引 地理信息系统基础 §6.6 空间索引 地理信息系统基础 §6.6 空间索引 地理信息系统基础 §6.6 空间索引 三、 四叉树空间索引 四叉树有两种，一种是线性四又树，一种是层次四叉树。这两种四叉树都可以用来进行空间索引，即线性四叉树空间索引和层次四叉树空间索引。 地理信息系统基础 §6.6 空间索引 三、 四叉树空间索引 1、线性四叉树空间索引 对于线性四叉树而言，先采用Morton编码（Peano键），然后，根据空间对象覆盖的范围，进行四叉树的分割。 线性四叉树空间索引 地理信息系统基础 §6.6 空间索引 三、 四叉树空间索引 2、层次四叉树空间索引 层次四叉树的空间索引与线性四叉树基本类似。只是它需要记录中间节点和父节点到子节点之间的指针。 层次四叉树空间索引 地理信息系统基础 §6.6 空间索引 四、对象范围索引 在记录每个空间对象的坐标时，记录每个空间对象最大最小坐标。这样，在检索空间对象时，根据空间对象的最大最小范围，预先排除那些没有落入检索窗口内的空间对象，仅对那些最大最小范围落在检索窗口的空间对象进行进一步的判断，最后检索出那些真正落入窗口内的空间对象。如下图所示。 对象范围索引 地理信息系统基础 §6.6 空间索引 五、R 树空间索引 刚才所述的空间索引方法可以看成是最原始的R树索引方法。每个目标都建立了一个范围，检索空间对象，仅检索范围与检索窗口有重叠的内容。R树空间索引方法是把这一概念进一步引申，设计一些虚拟的矩形目标，将一些空间位置相近的目标，包含在这个矩形内，这些虚拟的矩形作为空间索引，它含有所包含的空间对象的指针。 该矩形的数据结构为： RECT（Rectangte－ID，Type，Min－X，Max-X，Min-Y，Max-Y）矩形也有对象标识，Type表示为该矩形是虚拟空间对象还是实际的空间对象，Min-X，Max-X，Min-Y，Max-Y表示最大最小范围。 地理信息系统基础 §6.6 空间索引 五、R 树空间索引 在构造虚拟矩形时，应遵循以下原则，尽可能包含多的目标；矩形之间尽可能少的重叠。 五、R 树空间索引 虚拟矩形还可以进一步细分，即可以再套虚拟矩形形成多级空间索引。 *