# 1. B树概述
B树也是平衡树的一种实现, 相比AVL,红黑树 适合在内存中进行操作, 而B树适合在磁盘中进行操作.
同样是100万的数据, 使用AVL树来存储, 数高大约是20 ,平均一次磁盘操作是几十ms, 那么20次的操作, 总耗时就会明显的很慢, 而内存的读写操作则是ns级别, 即便是ns级别,对人的感知也不是很大.
100万的数据, 使用B树(假设最小度数为500)来存储, 树高大约是3. 因此对于磁盘的文件存储通常采用B树等数据结构.
# 2. B树的特性
- 度: degree 指的是树中某一个节点,它的孩子的个数.
- 阶: order 指的是所有节点中孩子数的最大值.
- 每个节点最多有m个孩子,其中m称为B-树的阶
- 除了根节点和叶子结点外,其他每个节点至少有ceil(m/2)个孩子.
- 若根节点不是叶子节点, 则至少有两个孩子.
- 所有的叶子节点都是在同一层,即高度相同.
- 每个非叶子结点由n个关键字和n+1个指针组成(也就是n+1个孩子), 也就是说节点中的关键字数量是孩子数减1, 公式: ceil(m/2) - 1 <= n <= m - 1
- 节点中的关键字按照非降序排列,即节点中的第i个关键字大于等于第i-1个关键字.
- 指针P[i]指向关键字值位于第i个关键字和第i+1个关键字之间的子树.
孩子数: ceil(m/2) ~ m 关键字个数: ceil(m/2)-1 ~ m-1
# 3. 编写一个B树
# 3.1 Node节点定义
//这个节点类应该少了, 对应的value的对象
public static class Node{
//关键字数组
public int[] keys;
//孩子Node数组
public Node[] children;
//关键字的实际数量
public int keyNumber;
//是否为叶子结点
public boolean isLeaf = true;
//最小度数, 最小孩子数
int t;
public Node(int t){
this.t = t;
//孩子数的最大树是 最小度数的两倍, 例子 最多允许6个孩子, 那么它的最小度数为ceil(6/2) = 3, 而当最多允许5个孩子时, 最小度数也是3
//也就是说2*t 就是在当前最小度数下, 最多可能有的孩子数.
this.children = new Node[2 * t];
//关键字的数组, 因为孩子最多是2t, 而关键字则少1, 则是2t-1
this.keys = new int[2 * t - 1];
}
public Node(int[] src,int t){
this(t);
System.arraycopy(src,0,keys,0,src.length);
this.keyNumber = src.length;
}
//输出这个节点有有效的关键字
@Override
public String toString() {
return Arrays.toString(Arrays.copyOfRange(keys,0,keyNumber));
}
/**
* <h1 style='color:white;'>多路查找,在一个结点的多个关键字对应的范围查找.</h1>
* <p>
* 依次遍历所有的有效关键字, 如果查找的关键字等于这个关键字, 则返回这个Node,
* 否则判断下一个关键字, 直到当前关键字大于了待查找关键字, 或者说已经查找完了所有的关键字.
* 对于后两种情况, 遍历结束后的 i指针 都正好指向了, 我们需要继续去查找的节点, 我们只需要对在这个节点中继续查找即可
* </p>
*
*
* @param key
* @return
*/
public Node get(int key){
int i = 0;
while(i < keyNumber){
//当前关键字就是目标
if(keys[i] == key){
return this;
}else if(keys[i] > key){
break;
}
i++;
}
//此时i对应的child 可能需要的结点
return children[i].get(key);
}
//编写一个方法, 用于插入新的key在keys中
public void insertKey(int index,int key){
//1.首先移动index位置以及后面的元素, 向后平移一位
System.arraycopy(keys,index,keys,index+1,keyNumber-index);
//2.在空出的位置插入
keys[index] = key;
//3.关键字数量+1
keyNumber++;
}
//编写一个方法, 用于插入新的Node在children中.
public void insertChild(int index,Node child){
//1.首先移动index位置以及后面的元素, 向后平移一位
System.arraycopy(children,index,children,index+1,keyNumber-index);
//2.在空出的位置插入
children[index] = child;
//3.孩子的数量由我们在插入时,维护.
}
}
# 3.2 编写BTree类
设计几个属性
int t: 这颗树的最小度数final int MAX_KEY_NUMBER: 这颗树的中最大Key的 数量final int MIN_KEY_NUMBER: 最小key的数量Node root: 根节点
设计构造函数
//无参构造, 默认的树的最小度数为2, 即一颗二叉树.
public BTree() {
this(2);
}
//有参构造
public BTree(int t) {
this.t = t;
//创建根节点
root = new Node(t);
//最大key的数量, 是最大的孩子数-1, 这个值一定是奇数
this.MAX_KEY_NUMBER = 2 * t - 1;
//最小key的数量, 是最小的孩子数-1
this.MIN_KEY_NUMBER = t - 1;
}
准备一些方法
- contains方法
//判断b树中是否包含某个结点
public boolean contains(int key){
return root.get(key) != null;
}
# 3.3 核心方法
1. 向树中添加节点(put和doPut)
添加节点我们使用put和doPut, put仅仅只是一个递归的入口.而实际进行添加操作的是doPut方法.
doPut的逻辑:
- 找到应该插入节点的位置 i
- 判断当前node是否是叶子节点.
- 是叶子: 在i位置插入.
- 不是叶子(有孩子): 递归的从孩子节点查找插入位置
- 判断插入后是否分裂, 如果当前结点key的数量已经达到了最大的key的数量(MAX_KEY_NUMBER), 则调用split方法进行分裂
实际代码:
//新增/修改节点, 因为图方便, 没有设置value
public void put(int key){
doPut(root,key,null,0);
}
private void doPut(Node root, int key,Node parent, int index) {
int[] keys = root.keys;
int i = 0;
while (i < keys.length) {
if(keys[i] == key){
//执行更新操作
return;
}else if(keys[i] > key){
break;
}
i++;
}
//两种情况: 当前结点是叶子结点, 则我们之间在当前位置插入
if(root.isLeaf){
root.insertKey(i,key);
//可能出现分裂
}else{
//当前结点不是叶子节点, 它有自己的孩子, 那么我们还需要进一步的在孩子节点中查找
doPut(root.children[i],key,root,i);
//可能出现分裂
}
//考虑插入后, 可能导致的分裂问题
if(root.keyNumber == MAX_KEY_NUMBER){
split(root,parent,index);
}
}
2. split 分裂方法
当我们同过put方法添加了新的key后, 如果key的数量达到了最大的key的数量就会触发分裂.
方法声明:
public void split(Node left,Node parent, int index)
分裂时需要对两种额外情况进行处理:
- 分裂的是根节点, 此时方法参数的parent为null,index为0
因为分裂的节点,需要将中间的key, 添加到它的父节点中对应的位置, 而根节点没有parent, 所以我们在进行分裂前需要进行创建父节点, 再将各种引用设置正确.
![img]()
- 分裂的结点包含孩子, 也就是说分裂的结点不是叶子节点.
对于这种情况, 我们不仅仅要拷贝一半的key到新的结点里面, 还要拷贝一半的孩子节点的引用到新的结点里面.
正常的处理流程:
- 创建一个节点right, 存储分裂出来的内容.
- 将分裂节点left的右一半的key,拷贝到right的keys里.
- 如果分类节点不是叶子节点,还有孩子,则将孩子节点也拷贝到right的children里面, 并将left里面被拷贝走的child的引用设置为null.
- 重新设置left里面key的数量,即设置keyNumber. 我们不需要设置children的有效数量, 因为children的有效数量, 隐含在keyNumber, 即 children有效数量 = keyNumber + 1;
- 将分裂结点的 中间key, 添加到父节点.
- 将新创建的right孩子, 添加到父节点的children中对应的位置.
实际代码:
public void split(Node left,Node parent, int index){
//考虑特殊情况2: 需要分裂的节点是根节点. 判断分裂节点是根节点有两种: 1.left == this.root 2. parent == null
//对于这种情况, 我们需要先将新的根节点创建出来
if(parent == null){
Node newRoot = new Node(t);
//根节点肯定是有孩子的, 即不是叶子节点.
newRoot.isLeaf = false;
//设置原来要分裂的结点为第一个孩子.
newRoot.insertChild(0,left);
//设置root指向
this.root = newRoot;
//为了下面的分裂处理, 将parent 设置为新的根节点.
parent = newRoot;
}
//1.keys的后半部分移动到一个新的结点( 把t以后的key和child都拷贝过去)
Node right = new Node(t);
//设置是否为叶子节点, 如果left是叶子结点, 就说明right也是叶子结点
right.isLeaf = left.isLeaf;
//拷贝keys, 移动的数量是t-1个, t-1 正好是一半.
System.arraycopy(left.keys,t,right.keys,0,t-1);
//考虑特殊情况1: 待分类节点不是叶子结点, 说明它有孩子, 那我们在分裂节点时, 应该也将对应的孩子也进行移动到新节点
if(!right.isLeaf){
//从源数组的t开始拷贝, 拷贝 t个元素, 也就是比key多拷贝一个
//比如说t = 2, 那么最大孩子数为 4, 最大的key数为3, 当key达到3时触发分裂, 这个时候 t就是keys数组的 右边一半的开始索引,
//而对于 children来说,t = 2时 children数组的右半部分的开始索引. 且需要移动的child个数比key的个数大1.
System.arraycopy(left.children,t,right.children,0,t);
//将后面的元素置为null, 孩子与key的数量关系是: 孩子数量 = key + 1;
for (int i = t; i <= left.keyNumber; i++) {
left.children[i] = null;
}
}
//设置 各个节点的keyNumber
right.keyNumber = t - 1; //新增了一半
left.keyNumber = t - 1; //移走了一半, 然后又将中间的key移动给了父节点.
//2.将分裂节点的t-1位置的key, 插入到parent的index处,index就是left作为孩子时的索引
parent.insertKey(index,left.keys[t-1]);
//3.right节点作为parent的孩子节点,插入到index+1处
parent.insertChild(index+1,right);
}