前言
本章节将带领大家进入B树的学习,主要介绍B树的概念和B树的插入代码的实现,删除代码不做讲解,最后简单介绍B+树和B*树。
B树的概念
1970年,R.Bayer和E.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树,称为B树(有些地方写的是B-树,注意不要误读成"B减树")。
如果B树是一颗三叉平衡树的话,上面一层是关键字区域,下面一层存放的是孩子结点:
我们来直观感受一下插入的过程:
B树的插入过程
一棵M阶(M>2)的B树,是一棵平衡的M路平衡搜索树,可以是空树或者满足一下性质:
- 根节点至少有两个孩子
- 每个非根节点至少有 【M/2(向上取整) - 1】 个关键字,至多有M-1个关键字,并且以升序排列
- 每个非根节点至少有【M/2(向上取整)】个孩子,至多有M个孩子
- key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
- 所有的叶子节点都在同一层
B树的实现
这里实现B树的插入代码。
结点定义
这里以三叉树为演示例子,定义 M 为 3,在结点初始化的时候,我们分别在keys 和 subs 域都增加一个空间,这样会方便我们后续的结点分裂。
public static final int M = 3;public Node root;static class Node {public int[] keys;//关键字public Node[] subs;//孩子结点public Node parent;//双亲结点public int usedSize;//使用的空间个数public Node() {//多分配一个空间是为了后面便于我们分裂结点this.keys = new int[M];this.subs = new Node[M+1];}}
插入分析
首先如果根节点为空的话,直接插入即可:
//根节点为空,直接插入if(root == null) {root = new Node();root.keys[0] = key;root.usedSize = 1;return;}
然后这里我们实现的B树是不能插入相同的数据的,所以我们需要先查找是否已经存在过 key 值,先写一个查找代码:
当遇到和key 值是一样的情况下,我们直接返回即可,如果没有遇到,我们需要继续查找下去。
结点的 keys 是连续的数组,我们需要遍历这个数组:
如果发现 key 大于数组元素,需要继续向后遍历,如果发现 key 小于数组元素,我们则需要进入到对应的孩子结点继续寻找 key 。
最后我们要考虑返回值,我们应该返回什么样的数据?
如果至少单纯判断是否存在,也就是返回布尔值,如果存在某个数据就是返回true,这时候是不需要进行插入操作的,但是如果不存在,你返回的是 false ,那我们应该从哪个结点进行插入操作,所以我们需要获得具体的结点,这时候就需要在查找的循环过程中保存上一个 cur 结点,当cur 走到空的时候,cur 的上一个结点就是我们需要插入数据的结点了。
但是如果返回结点,那就意味着最后的返回值不可能为空,那就无法判断是否存在了 key,所以我们需要接收两个返回值,这时候我们可以定义一个泛型类,用来创建对象保存两个数据,一个是结点,一个是下标,当不存在的时候直接返回 -1。
public class Pair<K, V> {private K key;private V val;public Pair(K key, V val) {this.key = key;this.val = val;}public K getKey() {return key;}public void setKey(K key) {this.key = key;}public V getVal() {return val;}public void setVal(V val) {this.val = val;}
}
//查找public Pair<Node,Integer> find(int key) {Node cur = root;Node prev = null;while(cur != null) {int i = 0;while(i < cur.usedSize) {if(cur.keys[i] == key) {//存在该节点return new Pair<>(cur,i);} else if(cur.keys[i] > key) {//需要进入孩子结点继续查找break;} else {//继续查找i++;}}prev = cur;cur = cur.subs[i];}//找不到,返回双亲结点return new Pair<>(prev,-1);}
如果不存在,我们就需要插入key ,在获取到的 prev 上进行直接插入,最后我们就要考虑是否超过了M,如果超过了M,就需要进行结点的分裂:
这里要注意的是,我们插入过程都是在叶子结点上进行的,所以不需要进行孩子域 subs 的调整。
//不存在,需要进行插入Node cur = find.getKey();//插入是在叶子结点进行的,不需要调整孩子结点int i = cur.usedSize - 1;for (; i >= 0; i--) {if(cur.keys[i] > key) {cur.keys[i+1] = cur.keys[i];} else {break;}}cur.keys[i+1] = key;cur.usedSize++;//是否需要进行分裂if(cur.usedSize == M) {split(cur);}
分裂分析
我们来看一下非根结点的分裂过程:
我们需要获取中间的关键字,然后从中间的关键字的下一个开始拷贝到新结点上,然后中间的关键字需要提取到上面去,也就是需要调整 双亲结点将 中间值插入进去,最后调整三个结点即可。
由于你往双亲结点上插入了一个数据,所以可能导致双亲结点超过容量,所以最后还需要查看双亲结点是否需要进行分裂
Node newNode = new Node();Node parent = cur.parent;//进行keys和孩子结点的拷贝int mid = M / 2;int i = 0;int j = mid + 1;for(; j < cur.usedSize; j++) {newNode.keys[i] = cur.keys[j];newNode.subs[i] = cur.subs[j];//如果拷贝过来的孩子结点不为空,需要修改孩子结点的双亲结点if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//usedSize 随之修改newNode.usedSize++;i++;}//还差一个孩子结点没有拷贝,再次拷贝孩子结点newNode.subs[i] = cur.subs[j];if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//新结点的双亲结点设置为 parentnewNode.parent = parent;//设置 cur 的 usedSize 数值cur.usedSize = mid;//需要提取的中间关键字int midVal = cur.keys[mid];//特殊情况:当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}//处理 parent 结点//将 cur 的中间关键值提到 parent;int end = parent.usedSize - 1;for(; end >= 0; end--) {if(parent.keys[end] > midVal) {parent.keys[end+1] = parent.keys[end];parent.subs[end+2] = parent.subs[end+1];} else {break;}}parent.keys[end+1] = midVal;parent.subs[end+2] = newNode;parent.usedSize++;//是否需要继续分裂if(parent.usedSize == M) {split(parent);}
如果分裂的是根节点的话,就有一点不一样了:我们需要为中间值创建一个新结点作为新的 根节点
//特殊情况:当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}
根节点的插入和非根结点的插入区别就在于中间值的处理,所以在前面拷贝的过程的代码可以保留,最后进行特殊情况的判断处理即可。
private void split(Node cur) {Node newNode = new Node();Node parent = cur.parent;//进行keys和孩子结点的拷贝int mid = M / 2;int i = 0;int j = mid + 1;for(; j < cur.usedSize; j++) {newNode.keys[i] = cur.keys[j];newNode.subs[i] = cur.subs[j];//如果拷贝过来的孩子结点不为空,需要修改孩子结点的双亲结点if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//usedSize 随之修改newNode.usedSize++;i++;}//还差一个孩子结点没有拷贝,再次拷贝孩子结点newNode.subs[i] = cur.subs[j];if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//新结点的双亲结点设置为 parentnewNode.parent = parent;//设置 cur 的 usedSize 数值cur.usedSize = mid;//需要提取的中间关键字int midVal = cur.keys[mid];//特殊情况:当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}//处理 parent 结点//将 cur 的中间关键值提到 parent;int end = parent.usedSize - 1;for(; end >= 0; end--) {if(parent.keys[end] > midVal) {parent.keys[end+1] = parent.keys[end];parent.subs[end+2] = parent.subs[end+1];} else {break;}}parent.keys[end+1] = midVal;parent.subs[end+2] = newNode;parent.usedSize++;//是否需要继续分裂if(parent.usedSize == M) {split(parent);}}
最终代码
package mybtree;public class Btree {public static final int M = 3;public Node root;static class Node {public int[] keys;//关键字public Node[] subs;//孩子结点public Node parent;//双亲结点public int usedSize;//使用的空间个数public Node() {//多分配一个空间是为了后面便于我们分裂结点this.keys = new int[M];this.subs = new Node[M+1];}}//插入public void insert(int key) {//根节点为空,直接插入if(root == null) {root = new Node();root.keys[0] = key;root.usedSize = 1;return;}//先查找是否存在keyPair<Node,Integer> find = find(key);//如果已经存在,直接返回if(find.getVal() != -1) {return;}//不存在,需要进行插入Node cur = find.getKey();//插入是在叶子结点进行的,不需要调整孩子结点int i = cur.usedSize - 1;for (; i >= 0; i--) {if(cur.keys[i] > key) {cur.keys[i+1] = cur.keys[i];} else {break;}}cur.keys[i+1] = key;cur.usedSize++;//是否需要进行分裂if(cur.usedSize == M) {split(cur);}}private void split(Node cur) {Node newNode = new Node();Node parent = cur.parent;//进行keys和孩子结点的拷贝int mid = M / 2;int i = 0;int j = mid + 1;for(; j < cur.usedSize; j++) {newNode.keys[i] = cur.keys[j];newNode.subs[i] = cur.subs[j];//如果拷贝过来的孩子结点不为空,需要修改孩子结点的双亲结点if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//usedSize 随之修改newNode.usedSize++;i++;}//还差一个孩子结点没有拷贝,再次拷贝孩子结点newNode.subs[i] = cur.subs[j];if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//新结点的双亲结点设置为 parentnewNode.parent = parent;//设置 cur 的 usedSize 数值cur.usedSize = mid;//需要提取的中间关键字int midVal = cur.keys[mid];//特殊情况:当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}//处理 parent 结点//将 cur 的中间关键值提到 parent;int end = parent.usedSize - 1;for(; end >= 0; end--) {if(parent.keys[end] > midVal) {parent.keys[end+1] = parent.keys[end];parent.subs[end+2] = parent.subs[end+1];} else {break;}}parent.keys[end+1] = midVal;parent.subs[end+2] = newNode;parent.usedSize++;//是否需要继续分裂if(parent.usedSize == M) {split(parent);}}//查找public Pair<Node,Integer> find(int key) {Node cur = root;Node prev = null;while(cur != null) {int i = 0;while(i < cur.usedSize) {if(cur.keys[i] == key) {//存在该节点return new Pair<>(cur,i);} else if(cur.keys[i] > key) {//需要进入孩子结点继续查找break;} else {//继续查找i++;}}prev = cur;cur = cur.subs[i];}//找不到,返回双亲结点return new Pair<>(prev,-1);}public void inorder(Node root){if(root == null)return;for(int i = 0; i < root.usedSize; ++i){inorder(root.subs[i]);System.out.println(root.keys[i]);}inorder(root.subs[root.usedSize]);}
}
B+树介绍
B+树是B-树的变形,也是一种多路搜索树:
其定义基本与B-树相同,除了:
- 非叶子节点的子树指针与关键字个数相同
- 非叶子节点的子树指针p[i],指向关键字值属于【k[i],k[i+1]】的子树【这句话的意思是B+树在B树的基础上只存在右子树,也就是说keys 数组第一个区域是不存在左孩子的,然后每一个孩子结点的范围是 k[i] 到 k[i+1] 之间的】
- 所有叶子节点通过双向链表进行连接
- 所有关键字都在叶子节点出现
B+树的应用:
在MySQL中使用B+树来对数据进行管理,在下一篇MySQL的索引中我会进行详细的讲解。
B* 树介绍
B*树是B+树的变形,在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
这样做的好处是可以节约存储空间,结点在进行分裂的时候,会优先先看看兄弟结点是否已满,如果没有满,会将数值插入到兄弟结点上。