18143453325 在线咨询 在线咨询
18143453325 在线咨询
所在位置: 首页 > 营销资讯 > 信息时代 > 空间索引(数据库)

空间索引(数据库)

时间:2022-10-31 04:30:01 | 来源:信息时代

时间:2022-10-31 04:30:01 来源:信息时代

    空间索引 : 在存储空间数据时依据空间对象的位置和形状或空间对象之间的某种空间关系,按一定顺序排列的一种数据结构。其中包含空间对象的概要信息,如对象的标识、外接矩形以及指向空间对象实体的指针。
1. R-树(R-tree)
R-树是B-树在多维空间的扩展,它由Guttman于1984年提出。一棵R-树包括叶子结点和索引结点两类结点。对于一棵具有.M个扇出(即M阶)的R-树来说,其结点结构可描述如下:
叶子结点: (Count,Level,<OI1,MBR1>,<OI2,MBR2>,…,<OIM,MBRM>);
索引结点: (Count,Level,<P1,MBR1>,<P2,MBR2>,…,<PM,MBRM>); 其中,<OIi,MBRi>称为数据项,OIi为空间对象的标识,MBRi为该空间对象在k维空间中的最小包围矩形。<Pi,MBRi>称为索引项,Pi是指向下一层子树根结点的指针,MBRi代表其索引的子树空间,是包络其子树根结点中所有数据项或索引项的最小包围矩形。Count代表每个结点中含有的索引项或数据项个数(即该结点的“孩子结点”个数),并且Count≤M。Level表示该结点在树中的层数。令m为结点包含索引项或数据项的最小数目,且m满足2≤m≤M/2。如果结点所包含的索引项个数或数据项个数小于m,则会产生下溢(underflow); 反之,如果结点所包含的索引项个数或数据项个数大于M,则会发生上溢(overflow)。
一棵R-树必须满足性质:①若根结点不是叶子结点,则至少有两棵子树; ②除根结点以外的所有索引结点至多有M棵子树,至少有m棵子树;③每个叶子结点均包含m至M个数据项;④所有的叶子结点都出现在同一层上; ⑤所有结点都需要相同的存储空间(通常为一个磁盘页面)。
此外,R-树还具有特点: ①叶子结点中的数据项所包围的空间可能重叠; ②索引结点中的索引项所包围的空间也可能重叠: ③由于上述重叠性的存在,因此,即使对于精确匹配查找,也会存在多条查找路径。
图1描述了对应空间对象分布的一棵R-树,空间对象的分布则如图2所示。在图1中,实线矩形框表示空间对象的MBR,即数据矩形;虚线矩形框表示索引结点中索引项对应的索引空间,即索引矩形或索引MBR。从图1中可以看出,索引矩形允许重复。


图1 空间对象分布的R-树


为找到与查找区域相交的所有空间对象,查找必须从根结点进入,然后递归遍历所有索引空间与查找区域相交的子树,直至到达叶子结点。这时,检测叶子结点中数据项的MBR与查找区域,如果相交,就提取对应的对象的几何信息进行计算。R-树适用的维数并不高,通常为2~5维,而且子树的矩形区域可以有重叠,因此往往存在多条查找路径,而其中的某些查找路径往往不包含查找结果,这无疑增加了不必要的查询响应时间。


图2 空间对象的分布


2. R+-树(R+-tree)
R+-树是R-树的一种变体,主要是针对R-树中兄弟结点的MBR重叠后,导致空间搜索性能较差的特点提出的。其改进的主要思想是: 如果裁减数据矩形,那么可以获得中间结点索引矩形的零重叠,因此,对于点查询,查找路径可以有一条; 对于区域查询,查找性能也可以得到提高。R+-树中,兄弟结点之间的MBR不允许重叠,这使得空间搜索的性能较好,但由于在插入和删除时需保证兄弟结点之间的MBR不能重叠,因此插入和删除操作的效率较低。
R+-树具有特点:①对于索引结点中的任意一个索引项〈Pi,MBRi〉,我们说Pi指向的子树包含索引矩形R,当且仅当R被MBRi所覆盖(cover); Pi指向的子树包含数据矩形D,当且仅当D与MBRi重叠(overlap)。②对于索引结点中的任意两个索引项〈Pi,MBRi〉和〈Pj,MBRj〉,MBRi和MBRj的重叠(overlap)为零。③叶子结点中的数据矩形允许并可能重叠。④根结点如果不是叶子结点,则至少有两个孩子。⑤所有的叶子结点都在同一层次上。
显然,R+-树与R-树的区别在于以下三点: ①R+-树中的结点对数据项和索引项的填充个数没有严格限制(R-树要求至少有m个)。②R+-树索引结点的索引矩形不允许重叠(R-树的索引矩形允许重叠)。③R+-树中空间对象标识可重复存储在多个叶子结点中(R-树空间对象无重复存储)。
R+-树上的查找操作与R-树相似。与R-树相比,对于范围查找,R+-树的查找路径应该可以减少,但仍然可能有多条;对于点查找,R+-树通过一条路径就可以得到查找结果。

74
73
25
news

版权所有© 亿企邦 1997-2022 保留一切法律许可权利。

为了最佳展示效果,本站不支持IE9及以下版本的浏览器,建议您使用谷歌Chrome浏览器。 点击下载Chrome浏览器
关闭