一站式学习数据结构：B树
相关代码下载：https://github.com/guoyixing/datastructure
一、为什么有二叉搜索树还需要b树
本质上二叉搜索树和b树都是为了快速的搜寻数据而存在，那么b树与Avl等其他搜索树有什么区别，或者说有什么优势？
这个问题还需要从现在的数据库规模和内存容量说起，随着互联网的高速发展，今天典型的数据集都需要以TB单位度量，数据库规模与内存容量的比值也在逐年变小，亦相对而言下内存的容量是在不断的减小。
物理上，存储器的容量越大，访问的速度相对越慢。不同形式的存储器，访问速度差异也是悬殊巨大。以磁盘与内存为例：磁盘速度是ms（毫秒）级别的/内存速度是ns（ 纳秒/毫微秒,十亿分之一秒）级别的，ms/ns>10^5，两者差距可见一斑。做个形象却毫不夸张的比喻，若是内存访问需要一秒钟，则一次外存的访问就相当于要一天，为了避免这1次外存的访问，我们宁愿做100次的内存的访问。
从磁盘中批量的获取数据，可以使我们的访问速度有效的提高，读写1b的数据，和读写1kb的数据几乎没有差别。B树便是通过这种特性来提高对数据的访问速度。
二、B Tree的结构
上图是一张平衡二叉搜索树，我们将蓝色的部分进行适当合并，得到“超级节点”没两代合并成4路，当然也可以每3代合并成8路。如下图所示
每d代的合并，就会生成m=2^d路，m-1个关键码。形成了一个平衡的多路搜索树
逻辑上来看BBST（二叉搜索树）完全等价，但是多级存储系统中使用B树，可以针对外部的查找，大大减少I/O的次数。
所谓的m阶的B树，即m路的平衡搜索树（此时m必须大于等于2），B树的外部节点的深度相等，所有叶子节点的深度也相等。树高h = 外部节点的深度，也就是说和其他树不同B树的高度取决于外部节点，而不是叶子节点。每个内部节点各有不超过m-1个关键码，不超过m个分支。内部结点的分支树也不可以过少，具体的情况如下：树根节点最少要有两个分支，一个关键码，其余的节点只要有m/2的分支和m/2-1个关键码。所以也可称作（[m/2],m）树。
当m=3的时候，称作（2,3）树也是最简单的树，每个节点的分支树，可能有2个或者3个，对应的每个节点的关键码数目可能是1个或者2个。节点的两种形式如下图
当m=4的时候，称作（2,4）树，各节点的分支树，可能是2、3、4个，每个节点的关键码数目可能是1、2、3个。比起（2,3）树就多了一种节点形态。
现在来看1棵B树实例，有些直观上的理解，下面的三个图是同一个B树的三种表示形式，我们通常用c的表示方式。
三、通过代码实现B树结构
代码中B树分成两部分，B树本身与B树节点
B树节点：关键码和分支的引用我们可以通过用两个动态数组快速实现（动态数组的代码在github上）
public class BTNode<T> {
/**
* 父级对象
*/
BTNode<T> parent;
/**
* 当前节点存放的数据
*/
MyVector<T> key = new MyVector<>();
/**
* 所有的子集节点
*/
MyVector<BTNode<T>> child = new MyVector<>();
BTNode() {
this.parent = null;
child.insert(0, null);
}
BTNode(T t, BTNode<T> lc, BTNode<T> rc) {
this.parent = null;
key.insert(0, t);
child.insert(0, lc);
child.insert(1, rc);
if (lc != null) {
lc.parent = this;
}
if (rc != null) {
rc.parent = this;
}
}
}B树：这里是个4阶的B树，如果有需要可以通过构造函数初始化阶次，order便是上文中提到的m
public class BTree<T> {
/**
* 关键码总数
*/
protected int size;
/**
* 阶次
*/
protected int order = 4;
/**
* 根节点
*/
protected BTNode<T> root = new BTNode<>();
/**
* 最后访问节点
*/
protected BTNode<T> hot;
}四、B树的查询
将根节点，作为当前节点，只要是当前节点非外部节点，便在当前节点中顺序查找，如果找到目标的关键码，则返回查找成功，否则沿着引用，转到对应子树将其根节点读入内存,直至最后都无法找到返回查询失败。
根据约定，根节点是常住在RAM中的，我们时间复杂度的时候，几乎可以忽略内存中的查找，主要运行时间来自于I/O的次数。每次深入一阶至多读取一次I/O，所以运行时间=O(h) ，h取决于搜索的层数。
通过简单的观察，不难发现查询时间与树的高度有着密切的关系。我们简单的研究一下当含有N个节点的时候m阶的B树，最大的高度和最小的高度。
最大树高：
为了达到最大树高，每个内部节点都应当足够的“瘦”，也就是说每层的节点和分支数应该保持最小值。各层的节点数依次为：
n0（第一层）：1
n1（第二层）：2
n2：2（m/2） m表示这棵树是几路的，也就是最大的分支数
.....
nk：2x[m/2]^(k-1)
查询外部节点所在的位置，外部节点在数的最底层nh处，N+1=nh>=2x[m/2]^(h-1)，其搜索的时间复杂度为O(logm底N)，如果m=256的时候，I/O的次数（树高）比同节点数的二叉搜索树下降至1/7
最小树高：
同样的为了达到最小树高，每个每个内部节点都应该尽可能的胖，各层节点数一次为
n0:1
n1：m
n2：m^2
......
n(h-1)：m^(h-1)
nh=m^h
查询外部节点所在位置，所需的时间大致为 Ω(logm底N)，如果m=256的时候，I/O的次数（树高）比同节点数的二叉搜索树下降至1/8
可以发现在最大树高和最小树高的时候查询的所需的时间并没有太过明显的变换。
查询方法的具体实现如下：
/**
* b树的搜索方法
* 借用向量的搜索方法可以快速实现
*
* @param t 查询的节点
*/
public BTNode<T> search(T t) {
//从根节点出发
BTNode<T> v = this.root;
this.hot = null;
//循环每个节点
while (v != null) {
//通过向量的搜索方法查询节点内容
int r = v.key.search(t);
//命中则返回节点
if (0 <= r && t.equals(v.key.get(r))) {
return v;
}
//并且将热点执行访问过的节点
this.hot = v;
//没就继续访问下一个子节点
v = v.child.get(r + 1);
}
return null;
}
五、B树的插入
b树的插入算法：
/**
* 插入算法
*
* @param t 插入的节点
*/
public boolean insert(T t) {
//通过搜索算法 查询是否已经存在
BTNode<T> v = search(t);
if (v != null) {
return false;
}
//找到之前访问热点的位置 便是最适合插入的位置
int r = this.hot.key.search(t);
//热点节点末端加入新节点
this.hot.key.insert(r + 1, t);
this.hot.child.insert(r + 2, null);
this.size++;
//判断是否上溢
solveOverflow(this.hot);
return true;
}b树的插入算法十分简单，但是要注意在插入的过程中节点的关键码有可能已经饱和，这时候就会发生上溢，设发生上溢节点中的关键码依次为k0，k1，....，k(m-1)，取中位数s=m/2，以关键码ks为分界线划分为k0~k(s-1),ks,k(s+1)~k(m-1)
将关键码上移一层，并分裂发生上溢的节点k0~k(s-1)做左子节点，,k(s+1)~k(m-1)做右子节点，分裂后左右子节点所含关键码数依旧符合m阶B树的条件。
当然还有更坏的情况，若上溢的父节点本身已经饱和，则在接纳被提升上来的关键码之后，也会发生上溢，此时我们可以沿用之前的方法，继续分裂。上溢依旧有可能继续发生，并逐层向上传播，最坏的情况下不过是到树根，如果找到抵达树根，可让被提升的关键码自成节点作为树根，总执行时间不过线性正比于分裂次数，不超过O(h)
具体代码实现如下：
/**
* 上溢修复
* 当节点的子集超过 规定的个数就会发生上溢
* 节点的个数应当是磁盘单元空间/单条数据大小 并且不小于2
*
* @param v 需要处理上溢的节点
*/
private void solveOverflow(BTNode<T> v) {
if (this.order >= v.child.getSize()) {
//递归基 停止继续往上层修复
return;
}
//获取中间节点位置
int s = order / 2;
//创建新的分裂节点
BTNode<T> u = new BTNode<>();
//将做中间节点右侧的节点复制到 分裂出的新节点上 子节点永远比key要多出1 所以会剩下一个子节点
for (int j = 0; j < this.order - s - 1; j++) {
u.child.insert(j, v.child.remove(s + 1));
u.key.insert(j, v.key.remove(s + 1));
}
//单独处理剩下的这个最右侧的子节点
u.child.replace(this.order - s - 1, v.child.remove(s + 1));
//如果子节点存在数值则 重新定位这些节点的父节点
if (u.child.get(0) != null) {
for (int j = 0; j < this.order - s; j++) {
u.child.get(j).parent = u;
}
}
//如果父节点为空 说明已经上溢到顶层 需要生成新的父节点
BTNode<T> p = v.parent;
if (p == null) {
this.root = p = new BTNode<>();
p.child.replace(0, v);
v.parent = p;
}
int r = 1 + p.key.search(v.key.get(0));
//将节点上移到新的根节点
p.key.insert(r, v.key.remove(s));
p.child.insert(r + 1, u);
//建立关系
u.parent = p;
//递归上溢
solveOverflow(p);
}六、B树的删除
/**
* 删除算法
*
* @param t 需要删除的节点
*/
public boolean remove(T t) {
//查找节点是否存在 不存在返回删除失败
BTNode<T> v = search(t);
if (v == null) {
return false;
}
//存在则通过向量的查询算法 找到节点的地址
int r = v.key.search(t);
//如果v不是叶子节点
if (v.child.get(0) != null) {
//右子树一直左走
BTNode<T> u = v.child.get(r + 1);
//直到走到叶子节点上
while (u.child.get(0) != null) {
u = u.child.get(0);
}
//将v与获取到的子节点替换 u便是在v中最大的子节点
v.key.replace(r, u.key.get(0));
v = u;
r = 0;
}
//此时v一定是底层 并且r就是要删除掉的节点
v.key.remove(r);
v.child.remove(r + 1);
this.size--;
//判断是否要下溢修复
if (this.size != 0) {
solveUnderflow(v);
}
return true;
}同样的当B树删除的时候，有可能发生下溢，可以想到上溢的时候我们采用分裂的策略处理，下溢的时候必然可以采用合并策略处理，但在此之前我们不妨思考一下是否有更好的处理方案呢
当节点V出现下溢的时候，必然恰好包含m/2-2个关键码和m/2-1个分支，视其左、右兄弟L，R所含关键码个数可以分成3种情况处理。
1、若L存在，至少包含m/2个关键码，将关键码y从P移到V中（作为最小的关键码），将x从L中移至P中（取代之前的关键码y），如此之后便完成了一次旋转，下溢的情况便被修复
2、若R存在，至少包含[m/2]个关键码，与1的操作完全对称
3、L或R不存在，或者所包含的关键码不足m/2个，需要注意的是L和R必然有一个存在，但是恰好含油m/2-1个关键码，这时从P中抽出介于L和V之间的关键码y，通过y合并，以L和V合并成一个节点，并同时此前y的子节点的引用，合并之后，下溢便被修复，与上溢的情况一样，父节点P被接走一个节点的时候有可能也会发生下溢，下溢持续发生，并逐层传播，直至根节点，至多不超过h次。
下图是下溢发生是实例的步骤。
给出下溢修复代码：
/**
* 下溢修复
* 当节点的子集达不到最小要求数目的时候 节点就向着父节点接一个节点会发生合并
* 或者想左右兄弟节点借一个节点发生旋转
*
* @param v 需要处理下溢的节点
*/
private void solveUnderflow(BTNode<T> v) {
if ((this.order + 1) / 2 <= v.child.getSize()) {
return;
}
BTNode<T> p = v.parent;
//当父节点不存在的时候 也就是最顶层 说明树的层数减少了一层
if (p == null) {
this.root = v.child.get(0);
return;
}
int r = 0;
//获取节点所在位置
while (!p.child.get(r).equals(v)) {
r++;
}
if (0 < r) {
//当节点不在最左边的时候 一定会有左兄弟
BTNode<T> ls = p.child.get(r - 1);
//判断左兄弟能否借出一个节点给他 如果可以变将借出的节点放置父节点的位置 父节点下移到当前节点的最左边 以此整棵树依旧保持中序意义上的顺序
//顺时针旋转
if ((this.order + 1) / 2 < ls.child.getSize()) {
//将父节点的key转移过来
v.key.insert(0, p.key.get(r - 1));
//将父节点与借出节点交换
p.key.replace(r - 1, ls.key.remove(ls.key.getSize() - 1));
//将的借出节点的子节点转移到 需要修复的节点下
v.child.insert(0, ls.child.remove(ls.child.getSize() - 1));
//修改父节点连接
if (v.child.get(0) != null) {
v.child.get(0).parent = v;
}
return;
}
}
if (p.child.getSize() - 1 > r) {
//当节点不在最右边的时候 一定存在右兄弟 与左兄弟的处理方式对称
BTNode<T> rs = p.child.get(r);
if ((this.order + 1) / 2 < rs.child.getSize()) {
v.key.insert(v.key.getSize(), p.key.get(r));
p.key.replace(r, rs.key.remove(0));
v.child.insert(v.child.getSize(), rs.child.remove(0));
if (v.child.get(v.child.getSize() - 1) != null) {
v.child.get(v.child.getSize() - 1).parent = v;
}
return;
}
}
if (0 < r) {
//获取左边节点的孩子
BTNode<T> ls = p.child.get(r - 1);
//将需要修复的对象的父节点移到 父节点左边节点的孩子的最后的位置上
ls.key.insert(ls.key.getSize(), p.key.remove(r - 1));
//v已经不是p的孩子 这里删除r位置上的元素便是v
p.child.remove(r);
//将需要修复的节点的首位 移至左节点的孩子的末尾
ls.child.insert(ls.child.getSize(), v.child.remove(0));
//如果这个孩子不是一个空的
if (ls.child.get(ls.child.getSize() - 1) != null) {
//将这个孩子的父对象 指向当前的左节点
ls.child.get(ls.child.getSize() - 1).parent = ls;
}
//如果v中依旧有元素存在
while (v.key.getSize() != 0) {
//继续吧元素逐一的移到左节点的末尾
ls.key.insert(ls.key.getSize(), v.key.remove(0));
ls.child.insert(ls.child.getSize(), v.child.remove(0));
if (ls.child.get(ls.child.getSize() - 1) != null) {
ls.child.get(ls.child.getSize() - 1).parent = ls;
}
}
} else {
//与之前的处理完全对称
BTNode<T> rs = p.child.get(r + 1);
rs.key.insert(0, p.key.remove(0));
p.child.remove(r);
rs.child.insert(0, v.child.remove(r));
if (rs.child.get(0) != null) {
rs.child.get(0).parent = rs;
}
while (v.key.getSize() != 0) {
rs.key.insert(0, v.key.remove(r));
rs.child.insert(0, v.child.remove(r));
if (rs.child.get(0) != null) {
rs.child.get(0).parent = rs;
}
}
}
solveUnderflow(p);
return;
}
如果有不懂的欢迎大家留言提问