《空间数据库》第6章 空间数据索引-教学课件（非AI生成）.ppt

R+-Tree结构的操作选择进行分配的矩形：[计算各矩形的与值]——对于矩形集中其余矩形，分别计算并进行分配，各类MBR的面积增长与的值。[选取矩形]——选取与相差最大的矩形作为要分配的矩形。***空间码是比对象本身更简单的几何对象第6章空间数据索引*概述索引通常是描述从空间数据库中获得数据的有效方法空间存储结构的目标是方便空间选取和连接查询索引结构按照一个或多个空间码来管理空间查询过程采取过滤和精炼两步走策略*空间索引职责插入删除成员查询点查询范围查询最近邻居距离扫描相交查询包含查询空间连接查询*课程内容B-TreeR-TreeR+-Tree*外部字典的索引顺序访问方法(indexedsequentialaccessmethod,ISAM)在ISAM方法中，可用的磁盘空间被划分为很多块，块是磁盘空间的最小单位，被用来作为输入和输出。块一般具有与磁道同样的长度，且可以用单个有哪些信誉好的足球投注网站和很小的延迟进行输入输出。字典元素以升序存储在块中。在顺序访问时，依次输入各个块，在每个块中按升序有哪些信誉好的足球投注网站元素。要支持随机访问，索引是不可缺少的。索引中包括每个块中的最大关键值。由于索引中所包含的关键值数量仅与块数相同，并且每个块一般都能贮存很多元素（m值通常较大），因此索引足以驻留在内存中。对关键值为k的元素作一次随机访问，首先只要寻找包含相应元素的块的索引，然后将相应的块从磁盘中取出并在其中寻找需要的元素。这样，执行一次随机访问只需要一次磁盘访问就足够了。*B-Tree定义定义：[m序B-树]m序B-树（B-Treeoforderm）是一棵m叉有哪些信誉好的足球投注网站树，如果B-树非空，那么相应的扩充树满足下列特征：1)树中每个结点至多有M棵子树；2)若根结点不是叶子结点，则至少有两个子树；3)除根之外的所有非终端结点至少有int(M/2)棵子树；4)所有的非终端结点中包含下列数据*B-Tree定义*B-Tree定义5)所有的叶子结点都出现在同一层次上，并且不带数据（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）*B-Tree定义*MBR(Envelope)

(minimumboundingrectangles)包含空间实体边界与坐标轴平行的最小矩形。*R-Tree结构*R-Tree结构*R-Tree定义R-tree是一种类似于B树的动态平衡树（见图2-2A）。R-tree的结点由若干个结构为(I，PointerToChild)的单元组成。在上式中，n是空间对象的空间维数，则代表第i维上的坐标范围[a,b]，为一闭区间。在非叶子结点中，I是包含其所有子结点的最小包含矩形（MBR）。而在叶子结点中，I是空间对象的MBR。*R-Tree定义每个叶子结点包含的单元个数介于m与M之间，除非它同时是根结点。每个叶子结点中的单元（I，SpatialObjectID）中，I是包含该n维空间对象的MBR，SpatialObjectID是该空间对象的ID。每个非叶子结点的孩子结点数介于m和M之间，除非它是根结点。每个非叶子结点的单元（I，PointerToChild）中，I是包含孩子结点的MBR，PointerToChild是指向子结点的指针。通过该指针能访问到子结点。根结点最少有两个孩子，除非它同时是叶子结点。所有的叶子结点都处于树的同一层上。*R-Tree结构的效率分析Coverage：每一层所有结点对应的矩形面积总和Overlap：一对或多个结点相关联矩形交迭的面积总和*R-Tree结构的效率分析*R-Tree结构的效率分析Coverage和Overlap面积最小Coverage面积最小意味着DeadSpace面积会减少Overlap面积最小比Coverage面积最小，对R-Tree结构的效率影响更大在动态分割或更新过程中控制R-Trees的结构及其对效率的影响*R+-Tree结构*R+-Tree结构*R+-Tree结构的描述叶结点（oid，Rect）oid表示实体标识Rect可以用（Xlow，Xhigh，Ylow，Yhigh）表示结点（p，Rect）p是一个指向下一层结点的指针*R+-Tree结构的操作有哪些信誉好的足球投注网站算法类似于其它树的有哪些信誉好的足球投注网站算法，R-tree的有哪些信誉好的足球投注网站算法也是一个递归过程。设有哪些信誉好的足球投注网站区域为S，则有哪些信誉好的足球投注网站区域S内空间对象的过程如下：[子树的有哪些信誉好的足球投注网站]——从R-tree的根结点T开始，如果T结点不是叶子结点，则依次判断该结点中各单元的