(1984 R树) r-trees: a dynamic index structure for spatial searching
B树
B树是一棵多叉平衡树,基本思想类似于先找一个大的空间,再逐步缩小所要查找的空间,最终在一个自己设定的最小不可分空间内找出满足要求的解。一个实例图如下:
例如从区间[3,99]中找79,先从根结点判断79>35,把区间缩小为[35,99],然后在子节点中判断65<79<87,把区间缩小为[65,87],最后在中间的叶节点[75,79]中遍历,得到79
R树
B树适用于一维数据,对于多维数据需要用到R树。R树类似于B树在k维空间上的自然扩展,也是采用将空间进行划分的思想。
有些类似于地图查询
叶节点结构
假设空间数据库由一系列元组(tuple)构成,每个元组代表一个空间对象,并且每个元组都有一个唯一的标识符(tuple-identifier)
叶节点中叶节点中每条索引记录可表示为(I, tuple-identifier),其中I = (I0 , I1 ,……, In-1)
这里n是数据的维度, Ii 是一个闭区间[a,b], 用于描述I在该维度上的范围 (Here n is the number of dimensions and Ii is a closed bounded interval [a,b] describing the extent of the object along dimension i)
非叶节点结构
非叶节点中每个条目可表示为(I, child-pointer), child-pointer是指向子节点的指针, I 是能覆盖所有子节点对应矩形的矩形(where child-pointer is the address of a lower node in the R-tree and I covers all rectangles in the lower node's entries)
即非叶节点中不保存具体的数据元组, 而是记录子节点地址信息, 子节点中保存具体数据元组的信息
R树结构实例
R树缺点分析
最主要的缺点在于R树允许兄弟结点之间的相互重叠, 而R树在查询中是判断当前结点的MBR与给定的查询范围间有没有重叠(overlap), 因此对于精确匹配查询R树不能保证唯一的搜索路径, 有时候可能会有很多无用的查询
对于上图组成的R树,若查询区间W如下:
由于A与W有重叠, 因此会继续判断D、E、F、G,发现都不是, 然后再查询B, 得到结果H. 其中对于A的查询都是不必要的
R树的操作
搜索算法:记根节点为T,一个索引条目为E,包括该条目的矩形为EI,子节点指针或元组标识符均为EP
输入:一个搜索矩形S
输出:所有与S有重叠(overlap即可)的索引记录
S1:若T不是叶节点,则检查其中的每一个条目E,如果EI与S相交,则对Ep所指向的那个子树根节点调用Search算法
S2:若T是一个叶节点,则检查其中的每个条目E,如果EI与S相交,则E就是需要返回的检索结果之一。
插入算法:向R树中插入新条目E
I1:[为新记录寻找位置] 调用ChooseLeaf方法去选择一个叶节点L来存放E
I2:[向叶节点添加新记录] 如果叶节点L有空间存放,则添加E。否则调用SplitNpde方法分裂原节点得到L和LL两个新节点,它们包含了原节点中的所有条目以及新插入的记录
I3:[向上传播更改] 对L调用AdjustTree方法,如果在I2中产生分裂,还需要对LL进行相同操作
I4:[增加树高] 如果节点的分裂传播导致根节点产生分裂,则新建一个根节点,它的两个子节点就是旧根节点分裂后形成的两个节点
辅助函数ChooseLeaf:选择一个叶节点来存放新记录E
CL1:设根节点为N
CL2:如果N为叶节点,则返回
CL3:如果N不是叶子结点,则从N中所有的条目中选出一个最佳的条目F,选择的标准是:如果E加入F后,F的外廓矩形FI扩张最小,则F就是最佳的条目。并且如果存在多个这样的条目,则选择面积最小的那个
CL4:[向下查找直到叶节点] 记CL3中找到的Fp指向的子节点为N,然后返回步骤CL2循环运算,直至查找到叶节点
辅助函数AdjustTree:由叶节点L向上运算直至根节点,目的是调整外廓矩形,并将节点分裂的结果向上传递
AT1:将L记为N。如果L已经被分裂成为了L和LL,则将LL记为NN。
AT2:如果N是根节点,算法中止。
AT3:[调整父节点中的外廓矩形] 记P是N的父节点,记En是P里指向N的那个条目。调整EN.I使得所有在N中的矩形都被恰好包围
AT4:[向上传递节点分裂的结果] 如果由于节点分裂产生了一个新的节点NN,则新建一个条目Enn,其中的Enn.p指向NN,Enn.I是NN的最小外廓矩形。如果P有空间容纳Enn,则将Enn加入P当中。如果节点P已满,则对节点P执行算法SplitNode,生成新的P和PP,P和PP包括旧的P中的所有条目和条目Enn。
AT5:[上移] 如果P发生了分裂,则令N=P,令NN=PP,然后返回步骤AT2重新开始运算。
删除算法:从R树中删除记录E
D1:[找到含有记录的叶子结点] 使用FindLeaf方法找到包含有记录E的叶子结点L。如果搜索失败,则直接终止。
D2:[删除记录] 将E从L中删除。
D3:[传递记录] 对L使用CondenseTree操作
D4:[缩减树] 当经过以上调整后,如果根结点只包含有一个孩子结点,则将这个唯一的孩子结点设为根结点。
辅助函数FindLeaf:设R树的根节点为T,查找包含索引条目E的叶节点
FL1:如果T不是叶节点,则逐个检查T中的每个条目F,看FI是否与EI相交。若相交,则对Fp指向的子树根节点调用算法FindLeaf。
FL2:如果T是叶节点,那么检查每一个条目是否有E存在,如果有则返回T
辅助函数CondenseTree:叶节点L中刚刚删除了一个条目。现在要评估这个节点的条目数是否太少,如果太少,应将这些条目移到其他节点中。如果有必要,要逐级向上进行这种评估。调整向上传递的路径上的所有外廓矩形,使其变小
CT1: 记N=L,定义Q为需要评估的节点数组,初始化的时候将此数组置空
CT2: 如果N是根节点,转到步骤CT6。如果N不是根节点,记P为N的父节点,并记En为P中代表N的那个条目
CT3: 如果N中的条目数小于m,将En从P中移除,并将N加入Q
CT4: 如果N没有被删除,则调整EN.I使得其对应矩形能够恰好覆盖N中的所有条目
CT5: 令N=P,返回步骤CT2重新执行
CT6:对Q中所有节点的所有条目执行重新插入。叶节点中的条目使用算法Insert重新插入到树的叶节点中,而较高层节点中的条目必须插入到树的较高位置上,以确保它们所指向的子树还处于相同的层节点分裂
因为判断是否访问一个结点取决于该结点的MBR是否与查询区域有重叠,因此分裂应该使得两个分裂结点的MBR和最小 (Since the decision whether to visit a node depends on whether its covering rectangle overlaps the search area, the total area of the two covering rectangles after a split should be minimized)