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 = (I₀ , I­₁ ,……, I_n-1)

这里n是数据的维度, I_i 是一个闭区间[a,b], 用于描述I在该维度上的范围 (Here n is the number of dimensions and I_i  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)