《地理信息数据库原理及应用》第6讲 空间数据索引技术与空间查询语言（1）-教学课件（非AI生成）.ppt

4)G树索引G树是一种多层次的动态生长的格网结构。与KD树类似，G树也按照循环交替的方式分割空间，但是它是采取平均分割空间的方法。并且每个区域中不能超过2点。如果超过2点，继续循环交替分割空间，直至每个区域不超过2点为止。这种空间分割策略有3个特点：①区域的二进制编码是全序的；②分割所得的区域集合构成平面的一个划分；③区域的二进制编码的位数越多，则该区域越小。*初始情况又插入两点G树示例各区域的编码图b：二进制编码P：指针，页—数据*R树索引：R树是一种利用B树的某些本质特征来处理多维数据的数据结构。1.R树及其特点R树索引是一种高效的空间索引，它是B树在多维空间的扩展，也是平衡树。R树的结构类似于B+树的平衡树。R树中每个非叶子结点都由若干个（p，MBR）数据对组成。MBR为包含其对应孩子的最小边界矩形。这个最小外接矩形是个广义上的概念，二维上是矩形，三维空间上就是长方体MBV。以此类推到高维空间。p是指向其对应孩子结点的指针。四、B树索引*（a）空间实体分布（b）R树索引构造图图5-15R树索引数据结构示意图叶子结点则是由若干个（OI，MBR）组成，其中MBR为包含对应的空间对象的最小外接矩形。OI是空间对象的标号，通过该标号可以得到对应空间对象的详细的信息。*R树的其它特点除根结点外，每个结点包含m~M条索引记录（其中m﹤﹦M/2；除根结点外，每个中间结点至多M个子结点，至少有m个子结点；若根结点不是叶结点，则至少包含2个子结点；所有叶结点出现在同一层；所有MBR的边与一个全局坐标系的坐标轴平行；*图5-17一地图与其对应的R树结构图5-18图5-17地图中插入对象L后的R树结构*2)R+树索引1.R+树及其特点R+树索引的主要特征是在R+树中兄弟节点对应的空间区域没有重叠，这样划分空间可以使空间有哪些信誉好的足球投注网站的效率提高。R+树也是R树的一个变种，图5-20为一R+树对空间的划分及其索引对象的MBR组织。*图5-20R+树索引示意图xyzpqrabxyzpqrabR[1,2,5,6][3,4,7][14][8,11,12][12,13][8,9,10]12561411812133479101R+树的结点中数据个数没有严格限制，而R树至少有m个；2R+树中目录矩形不重叠；3R+树中空间目标标识重复存储在多个叶结点。*3)CELL树索引它在空间划分时不再采用矩形作为划分的基本单位，而是采用凸多边形来作为划分的基本单位，具体划分方法与BSP树有类似之处，子空间不再相互覆盖。CELL树的磁盘访问次数比R树和R+树少，由于磁盘访问次数是影响空间索引性能的关键指标，因此大大提高了有哪些信誉好的足球投注网站性能，故CELL树是比较优秀的空间索引方法。*图5-21CELL树*Z曲线：?读入x、y坐标的二进制值?隔行扫描二进制数字的比特到一个字符串?计算结果二进制串的十进制数空间数据文件结构—聚类*A、B、C对象的Z曲线空间数据文件结构—聚类*Hilbert曲线空间数据文件结构—聚类*Hilbert曲线：读入x、y坐标的二进制值将二进制形式的X、Y按位相互交叉,构成一个长度为2n的二进制串S将字符串自左至右分成2个比特长的串Si，i=1,2，……，n规定每2个比特的十进制值di，如“00”等于0，“01”等于1，“11”等于2，“10”等于3对于数组中每个数字j，如果j＝0，把后面的所有1变成3,3变成1；若j=3，则把后面的所有0变成2,2变成0将数组中每个值按上步换成二进制，自左至右连接所有串，并计算其十进制值。空间数据文件结构—聚类*Hilbert曲线空间数据文件结构—聚类*磁盘访问的度量：假定每个点都对应一个网格单元，曲线为每个单元指定一个整数值。对一个给定查询，这里采用聚类在给定查询代表的子空间中每个网格点的散列平均数。空间数据文件结构—聚类对于a)2~3,8~11两个散列单元对于b)