这篇文章我们来讲解一下数据结构中非常重要的B-树。
目录
1.B树的相关介绍
1.1、B树的介绍
1.2、B树的特点
2.B树的节点类
3.小结
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):
文章来源:https://www.toymoban.com/news/detail-851931.html
3.小结
说实话,我感觉这东西挺难的,写完之后脑瓜子都嗡嗡的。没有在纸上画图,单靠脑子想,我是肯定写不出来的,所以我的建议是:一定一定一定要画图,一定一定一定要看着图对着代码来一步一步的走,一定一定一定要看图!文章来源地址https://www.toymoban.com/news/detail-851931.html
到了这里,关于数据结构与算法——20.B-树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!