当前位置：首页 > news >正文

JavaDS —— B树

news 2024/11/20 21:42:22

前言

本章节将带领大家进入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] 之间的】
所有叶子节点通过双向链表进行连接
所有关键字都在叶子节点出现