时间: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-树
图2 空间对象的分布