我要评论这篇文章我们来讲解一下数据结构中非常重要的b-树。
目录
1.b树的相关介绍
1.1、b树的介绍
在介绍b树之前，我们回顾一下我们学的树。
首先是二叉树，这个不用多说，然后为了查找的效率，我们提出了搜索二叉树（或者称为二叉搜索树），就是节点类加个key值，然后左边小右边大的那个。然后为了避免极端情况的出现，就是二叉搜索树节点集中在一侧的情况，我们提出了平衡二叉树，就是带自旋的，可以左旋或者右旋的，高度差小于1的那种，平衡二叉树里面有avl树和红黑树两种实现方式，注意，平衡二叉树是在二叉搜索树的基础上提出的，所以平衡二叉树也叫平衡二叉搜索树。
下面介绍一下b树。
b-树是一种自平衡的多路查找树，注意： b树就是b-树，"-"是个连字符号，不是减号 。
在大多数的平衡查找树（self-balancing search trees)，比如 avl树 和红黑树，都假设所有的数据放在主存当中。那为什么要使用 b-树呢（或者说为啥要有 b-树呢）？要解释清楚这一点，我们假设我们的数据量达到了亿级别，主存当中根本存储不下，我们只能以块的形式从磁盘读取数据，与主存的访问时间相比，磁盘的 i/o 操作相当耗时，而提出 b-树的主要目的就是减少磁盘的 i/o 操作。
大多数平衡树的操作（查找、插入、删除，最大值、最小值等等）需要 o(ℎ)次磁盘访问操作，其中 ℎ 是树的高度。但是对于 b-树 而言，树的高度将不再是log(n)（n为数中节点的个数），而是一个我们可控的高度 ℎ （通过调整 b-树中结点所包含的键【你也可以叫做数据库中的索引，本质上就是在磁盘上的一个位置信息】的数目，使得 b-树的高度保持一个较小的值）。一般而言，b-树的结点所包含的键的数目和磁盘块大小一样，从数个到数千个不等。由于b-树的高度 h 可控（一般远小于log(n)），所以与 avl 树和红黑树相比，b-树的磁盘访问时间将极大地降低。
我们之前谈过红黑树与avl树相比较，红黑树更好一些，这里我们将红黑树与b-树进行比较，并以一个例子对上面一段的内容进行解释。
假设我们现在有 838,8608 条记录，对于红黑树而言，树的高度 ℎ=log(838,8608)=23 ，也就是说树的高度为23，也就是说如果要查找到叶子结点需要 23 次磁盘 i/o 操作；但是 b-树，情况就不同了，假设每一个结点可以包含 8 个键（当然真实情况下没有这么平均，有的结点包含的键可能比8多一些，有些比 8 少一些），那么整颗树的高度将最多 8 （ log8(838,8608)=7.8 ) 层，也就意味着磁盘查找一个叶子结点上的键的磁盘访问时间只有 8 次，这就是 b-树提出来的原因所在。
1.2、b树的特点
下面讲一下b树的特点
在讲b树的特点之前，我们先来了解几个概念
度：degree 指树中节点的孩子数
阶：order 指所有节点中孩子数最大值
b树的特点：
- 每个节点最多有m个孩子，其中m称为b-树的阶；（孩子数目的上限）
- 除根节点和叶子节点外，其他节点至少有 ceil(m/2) （阶数除以2向上取整）个孩子，就是说b树中节点最大有m个孩子即阶个孩子，至少有 m/2（向上取整） 个孩子；（孩子数目的下限）
- 若根节点不是叶子节点，则至少有两个孩子；（根节点孩子数的下限）
- 所有叶子节点都在同一层；（b树是否平衡的前提条件）
- 每个非叶子节点由 n 个关键字（就是n个关键值，参考二叉搜索树中的关键值）和 n+1 个指针（就是n+1个孩子）组成，其中 ceil(m/2)-1 <= n <= m-1；
- 关键字按非降序排列（就是升序排列，和二叉树搜索相同），即节点中的第 i 个关键字大于等于第 i-1 个关键字；
- 指针p[ i ] 指向关键字值位于第 i 个关键字和第 i+1 个关键字之间的子树；
这些特性都要理解。看一下一个b树的实例：
2.b树的节点类
下面，我们来看一下b树的具体实现吧
package tree;
import java.util.arrays;
public class l5_btree {
//b数的节点类
static class node{
int[] keys; //关键字，即关键值，排序用的
node[] children; //孩子，存孩子用的节点类数组
int keynumber; //有效关键字数目（就是真正存了几个关键字）
boolean leaf = true; //是否是叶子节点
int t; //最小度数（最小孩子数）
//构造函数
public node(int t) { // t >= 2
this.t = t;//手动设置最小孩子数
this.children = new node[2 * t];//最大孩子数是最小孩子数的二倍
this.keys = new int[2 * t -1];//关键字的最大数量 是 最大孩子数-1
}
@override
public string tostring() {
return arrays.tostring(arrays.copyofrange(keys,0,keynumber));
}
//多路查找，就是我给你一个关键值，你返回这个关键值对应的节点
node get(int key){
int i = 0; //设置个变量i，方便用来循环遍历
while (i < keynumber){ //节点中有关键字
if (keys[i] == key){ //如果节点中的关键字 等于 我给出的关键字，那就返回这个关键字对应的节点
return this;
}
if (keys[i] > key){ //如果关键字中的最小值都比给出的大，那就直接退出这个节点的循环了
break;
}
i++; //变量i自增
}
//执行到这里，就是说当前节点的关键字一定比给出的大，或者说，超出索引了，即keys[i]>key 或 i == keynumber
if (leaf){ //如果是叶子节点，那就肯定没有孩子了
return null;
}
//这种情况就是 i == keynumber 了，就找这个节点所对应的孩子了（孩子数比节点关键值数多1）
return children[i].get(key);
}
//写一个方法，向 keys 指定索引 index 处插入 key
void insertkey(int key, int index){
for (int i = keynumber-1; i >= index ; i--) {
keys[i+1] = keys[i];
}
keys[index] = key;
keynumber++;
}
//写一个方法，向 children 指定索引 index 处插入 child
void insertchild(node child, int index){
system.arraycopy(children,index,children,index+1,keynumber);
children[index] = child;
}
//移除指定index处的key
int removekey(int index){
int t = keys[index];
system.arraycopy(keys,index+1,keys,index,--keynumber-index);
return t;
}
//移除最左边的key
int removeleftmostkey(){
return removekey(0);
}
//移除最右边的key
int removerightmostkey(){
return removekey(keynumber-1);
}
//移除指定index处的child
node removechild(int index){
node node = children[index];
children[index] = null;
return children[index];
}
//移除最左边的child
node removeleftmostchild(){return removechild(0);}
//移除最右边的child
node removerightmostchild(){return removechild(keynumber);}
//返回index孩子处左边的兄弟
node childleftsibling(int index){
return index > 0 ? children[index-1]:null;
}
//返回index孩子处右边的兄弟
node childrightsibling(int index){
return index == keynumber ? null : children[index+1];
}
//复制当前节点的所有key和child到target
void movetotarget(node target){
int start = target.keynumber;
if (!leaf){
for (int i = 0; i <= keynumber; i++) {
target.children[start+i] = children[i];
}
}
for (int i = 0; i < keynumber; i++) {
target.keys[target.keynumber++] = keys[i];
}
}
}
node root; //定义一个根节点
int t; //树中节点的最小度数（就是一个节点的最小孩子数，根节点叶子节点除外）
final int min_key_number;//最小关键字的数量
final int max_key_number;//最大关键字的数量
//无参构造，最小度数默认值为2
public l5_btree() {
this(2);
}
//有参构造
public l5_btree(int t) {
this.t = t;
root = new node(t);//new出根节点，并给出根节点最小度数
min_key_number = t-1;
max_key_number = 2*t-1;
}
//判断关键字中是否存在指定关键字对应的节点
public boolean contains(int key){
return root.get(key) != null;
}
//新增一个关键字
/**描述一下流程吧
* 你构造一颗b树，给定了最小度数，那么最小关键字数、最大关键字数、阶数也就都定了
* 你开始往节点中插入关键值，一开始没满，你继续插入
* 当插入的关键字数等于最大关键字数时，这个节点就要分裂了，即将自身的关键字分出去，变为孩子节点
* 然后你再插入，它就会按照关键字的顺序去选位置，
* 如果找到位置了，是叶子节点，那么就直接插入（当然超过max_key_number就分裂一下）
* 如果恰好发现一个非叶子节点里面也有位置，那么应该先搜索一下这个节点的孩子，然后再进行判断插在哪里
* 当某个节点的关键字数再满，那这个树就再分裂一次
* */
public void put(int key){
doput(root,key,null,0);
}
//递归的函数
private void doput(node node,int key,node parent,int index){
int i = 0;
while (i < node.keynumber){
if (node.keys[i] == key){
return; //更新逻辑
}
if (node.keys[i] > key){
break; //找到插入位置，记为i
}
i++;
}
if (node.leaf){
node.insertkey(key,i);
//可能到达上限
}else {
doput(node.children[i],key,node,i);
//可能到达上限
}
if (node.keynumber == max_key_number){
split(node,parent,index);
}
}
//分裂函数
/**
* left：要分裂的节点
* parent：分裂节点的父节点
* index：分裂节点是第几个孩子
* */
private void split(node left, node parent, int index){
if (parent == null){//分裂的是根节点
node newroot = new node(t);
newroot.leaf = false;
newroot.insertchild(left,0);
this.root = newroot;
parent = newroot;
}
//1.创建right节点，把left中t之后的key和child移动过去
node right = new node(t);
right.leaf = left.leaf;
system.arraycopy(left.keys,t,right.keys,0,t-1);
//分裂节点是非叶子节点的情况
if (!left.leaf){
system.arraycopy(left.children,t,right.children,0,t);
}
right.keynumber = t-1;
left.keynumber = t-1;
//2.中间的key（t-1处）插入到父节点中
int mid = left.keys[t-1];
parent.insertkey(mid,index);
//3.right节点作为父节点的孩子
parent.insertchild(right,index+1);
}
//删除一个关键字
public void remove(int key){doremove(null,root,0,key);}
private void doremove(node parent,node node,int index,int key){
int i = 0;
while (i < node.keynumber){
if (node.keys[i] >= key){
break;
}
i++;
}
//找到了，代表待删除key的索引
//没找到，表示到第 i 个孩子里面继续查找
if (node.leaf){
if(!found(node, key, i)){//case1
return;
}else {//case2
node.removekey(i);
}
}else {
if(!found(node, key, i)){//case3
doremove(node,node.children[i],i,key);
}else {//case4
node s = node.children[i+1];
while (!s.leaf){
s = s.children[0];
}
int skey = s.keys[0];
node.keys[i] = skey;
doremove(node,node.children[i+1],i+1,skey);
}
}
if (node.keynumber < min_key_number){
//调整平衡 case5 and case6
balance(parent,node,index);
}
}
private void balance(node parent, node x, int i){
//case6 根节点
if (x == root){
if (root.keynumber == 0 && root.children[0] != null){
root = root.children[0];
}
return;
}
node left = parent.childleftsibling(i);
node right = parent.childrightsibling(i);
if (left != null && left.keynumber > max_key_number){
//case5-1 左边富裕 右旋
//把父节点中前驱key旋转下来
x.insertkey(parent.keys[i-1],0);
if (!left.leaf){
//left中最大的孩子换爹
x.insertchild(left.removerightmostchild(),0);
}
//left中最大的key旋转上去
parent.keys[i-1] = left.removerightmostkey();
return;
}
if (right != null && right.keynumber > max_key_number){
//case5-2 右边富裕 左旋
//把父节点中后继key旋转下来
x.insertkey(parent.keys[i],x.keynumber);
//right中最小的孩子换爹
if (!right.leaf){
x.insertchild(right.removeleftmostchild(),x.keynumber+1);
}
//right中最小的key旋转上去
parent.keys[i] = right.removeleftmostkey();
return;
}
//case5-3 两边都不富裕 向左合并
if(left != null){
//向左兄弟合并
parent.removechild(i);
left.insertkey( parent.removekey(i-1), left.keynumber);
x.movetotarget(left);
}else {
//自己合并
parent.removechild(i+1);
x.insertkey(parent.removekey(i),x.keynumber );
right.movetotarget(x);
}
}
private boolean found(node node, int key, int i) {
return i < node.keynumber && node.keys[i] == key;
}
}
为了对应代码中插入和删除的逻辑思路，下面给出两张图来看一下。
节点中插入key值后的节点分裂展示图：
在节点中删除key的6种情况展示图（删除的是某个节点的key）：
3.小结
说实话，我感觉这东西挺难的，写完之后脑瓜子都嗡嗡的。没有在纸上画图，单靠脑子想，我是肯定写不出来的，所以我的建议是：一定一定一定要画图，一定一定一定要看着图对着代码来一步一步的走，一定一定一定要看图！
发表评论