空间索引结构(讲稿).pptVIP

空间索引结构 空间索引结构 空间索引结构 空间索引结构 空间索引 空间索引分类（非空间索引结构） 空间索引分类（非空间索引结构） 空间索引分类（非空间索引操作） 空间索引分类 空间索引分类 空间索引分类 空间索引分类 空间索引分类 空间索引分类(线性索引) 空间索引分类（非线性索引） 空间驱动的索引结构 空间驱动的索引结构（网格索引） 空间驱动的索引结构（均匀网格） 空间驱动的索引结构（均匀网格） 空间驱动的索引结构（均匀网格） 空间驱动的索引结构（均匀网格） 空间驱动的索引结构（均匀网格） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 空间驱动的索引结构（网格文件） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树7） 数据驱动的索引结构（R树7） 数据驱动的索引结构（R树7） 数据驱动的索引结构（R树9） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 数据驱动的索引结构（R树） 2、例子：图7-10为一个格网文件点查询的例子。点P位于DIR[3，2]范围之内，对应的磁盘页p4中含有4个索引项。将p4页调入内存，对其包含的4个mbb分别进行测试，其中8和12的mbb中包含了点P。根据对象标识8和12取出各自的几何边界数据，精确测试对象8和12，求出包含点P的对象12。 图7-10 基于网格文件的点查询 （三）窗口查询算法 工作过程如下： 第一步：计算所有覆盖窗口的索引单元。 第二步：扫描每一个索引单元，调入相应的磁盘页。读入每个磁盘页中的对象，排序并去掉重复对象。求出那些落入窗口中，或与窗口相交的mbb。 第三步：根据各自的对象标识取出这些mbb对应的几何边界，精确检测每个对象是否位于窗口中或与窗口相交。 （四）总结 用网格文件索引MBB，大多数情况下比较理想，但也存在很多问题： 1、对象的多重索引增加了索引表的容量，数据集越大越严重，索引单元接近MBB大小时，情况就更严重。 2、索引表容量越大，查询重复项的代价越高。 3、算法的效率依赖于索引表位于内存中的假设，如果索引表很大，一部分要存入磁盘，管理将变得复杂，效率会受影响。 Back 空间驱动的索引结构将整个空间划分成小区域，每个小区域定义为一个索引单元，直接索引其中的空间对象或索引对象的MBB。 数据驱动的索引结构则按照空间对象的位置、范围和分布，来确定索引单元的位置和范围，索引单元的全集不一定覆盖整个空间。这里主要介绍R树。 R树是一种数据驱动的索引结构，是B树的扩展。与B树相比，R树是一棵由多层嵌套的外接矩形构成的平衡树，即R树的每个结点以范围矩形mbb或目录矩形dr的形式表示一个空间范围，它界定了一个空间索引区域，定义为一个空间索引单元。 R树的每个结点都是一个空间索引单元，非叶结点包含其多颗子树的索引项，叶结点包含多个数据对象的索引项，本结点的范围矩形作为自身索引项的一部分存储在它的上层结点中。 R树的每个结点对应一个物理页，每个结点只能包含k个索引项，m＜k＜M，M是R树结点中包含索引项的最大数目，m是R树结点中包含索引项的最小数目，并限制2 ? m ? M/2。 一、原始的R树 R树的基本结构是一棵多层嵌套的、由外接矩形构成的平衡树。每个结点的索引区域表示成一个范围矩形，每个结点为一个空间索引单元，每个索引单元有k个索引项。 叶结点的范围矩形为其内部多个数据对象mbb的最小外接矩形，非叶结点的范围矩形为其多个子结点范围矩形mbb的最小外接矩形。 叶结点中存放多个数据对象的索引项，每个索引项的形式为[ptr，mbb，oid]，其中oid是数据对象的标识，mbb是数据对象的外接矩形，ptr指向存储该对象几何形状数据的磁盘位置。 非叶结点中存放多个子结点索引项，每个索引项的形式为[ptr，mbb，nodeid]，其中nodeid是指向子结点的指针，mbb为子树的目录矩形dr，ptr是子结点对应的磁盘页地址。 （一）R树的性质 1、根结点至少有两个子结点； 2、所有的叶结点都处于同一层； 3、除根结点外，R树中所有结点包含的索引项数目均在[m，M]之间，并限制2 ?m?M/2。 图7-26显示一棵m=2，M=4的R树。M