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

B-树：解锁大数据存储和与快速存储的密码

article 2025/2/6 1:22:58

在我们学习数据结构的过程中，我们会学习到二叉搜索树、二叉平衡树、红黑树。

这些无一例外，是以一个二叉树展开的，那么对于我们寻找其中存在树中的数据，这个也是一个不错的方法。

但是，如若是遇到了非常大的数据容量进行存储的时候，此时呢，无法一次性加载到内存当中，那么此时，这样的二叉结构的树就显得力不从心了。

这是因为，我们二叉树中，一个节点只保存了一个数据域，此时遇到非常大数据量的时候，导致树高变得很高，进行遍历查询树的时候，需要遍历树较深的地方，当然，查询的数据如若是在较浅树层，那么查询的时间还好，如若是非常深，那么此时查询的时间就会变得很耗时。

所以我们干脆在一个节点中存储多个数值域，以达到减少树高，从而获得高效率的查询效率。

而我们数据结构中，正好有一种符合此特征的，那就是B-树

B-树

那么又是B-树？

定义：一种适合外查找的树，它是一种平衡的多叉树

那么它具有什么性质呢？

一颗M阶（M > 2）的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1.根节点至少有两个孩子

2.每个非根节点的关键字至少有M/2-1(向上取整），至多有M-1个关键字，并以升序排列

比如当M=4，至少有（4/2-1=1）个关键字，至多有（4-1=3）个关键字.

3.每个非根节点的孩子至少有（M/2）向上取整，至多有M个孩子

比如当M=4，至少有（4/2=2）个孩子，至多有4个孩子

4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间

5.所有叶子节点都在同一层

由此可得出，

孩子节点会比关键字多出一个。

值得注意的是，为了使其关键字和孩子访问速度较快，所以使用的是数组进行存储。

节点图例：

这里值得注意的是，上述节点图例，是一般情况下的，为了后续插入操作简易进行，所以节点内部会进行修改。后面的插入操作进行解释。

修改后的节点：

现在小编来分享下插入操作，以三叉树作为例子

插入

根据此修改后的插入节点图例，此节点定义代码如下：

 //这里约定以三叉树作为实现
    public static int BT=3;
    //定义节点
    static class Node{
       //keys关键字数组
        public int [] keys;
        //孩子数组
        public Node [] subs;
        //有效数据大小
        public int Usize;
        //父亲节点
        public Node parent;
        //提供一个构造方法
        public Node(){
            //多给一个节点，利于后续分裂
            this.keys=new int[BT];
            //孩子域会比父亲域多一个
            this.subs=new Node[BT+1];
        }
    }

插入操作其实是大致可说为，插入按照某个插入算法进行插入，满了就进行分裂。

假设我们有以下的插入数据

序列：53, 139, 75, 49, 145, 36, 101

那么初始插入，因为我们关键字数组是中是有序的序列，所以我们需要选用一个插入算法进行插入，这里选择的是直接插入排序

初始状态如下：

注意，我们是初始情况，即根节点是为空的

所以如何插入53的呢？

显然，先新建一个节点，然后直接放到keys[0]，Usize++即可。

代码实例：

//定义一个头节点
    public Node root;


    public boolean insert(int key){

        //如若根节点为空
        if(root==null){
            root=new Node();
            root.keys[0]=key;
            root.Usize++;
            return true;
        }

那么此时如若不为空呢？
即我们插入75的数据，那么此时我们先要找到75是否是存在于树中。

那么接下来说说，如何实现查找的

查找

我们以一个实例说明（值得注意的是，数据有序是因为以直接插入排序进行的）

假设我们要寻找的是54这个节点

显然我们在根节点是寻找不到的，那么此时该去哪个数值的子树去寻找呢？

因为我们的49是比54小的，那么接着去下一个数值去比较，即75

那么54和75比较，那么此时的是大于54的，所以就结束我们的比较

所以我们得去75的孩子节点数组去找，

那么此时就到了53这棵树这里，此时显然，54也是不在这里的，那么此时我们按照逻辑，还是得去子树再找，那么这里呢，没有子树了，所以导致我们寻找节点变为null了

这里要保存其父亲节点，进行后续的操作。

那么就有一个问题了

如若我们找到了，那我们一般也是返回当前的节点，如若我们找不到了，也是返回此时的保存下来的父亲节点，那么怎么区分他们是找到还是没有找到呢？

这里提供一个方案：

新建一个泛型类，存储下当前的节点以及一个整数值，通过整数值去判断是否是找到了

泛型类代码：

public class Pair<k,v> {
    public k key;
    public v val;
    public Pair(k key,v val){
        this.key=key;
        this.val=val;
    }

    public void setKey(k key) {
        this.key = key;
    }

    public void setVal(v val) {
        this.val = val;
    }

    public v getVal() {
        return val;
    }

    public k getKey() {
        return key;
    }
}

接下来是寻找节点代码

寻找节点代码：

private Pair<Node,Integer> findNode(int key) {
        Node cur=root;
        Node parent=null;
        while (cur!=null){
            int i=0;
            while (i<cur.Usize){
                if(cur.keys[i]==key){
                    return new Pair<>(cur,i);
                }else if(cur.keys[i]<key){
                    i++;
                }else {
                    break;
                }
            }
            parent=cur;
            cur=cur.subs[i];
        }
        return new Pair<>(parent,-1);
    }

此时，我们就可以判断返回值是不是负数即可。

  //当根节点不为空，那么此时找出这个key是否存在B树中
        Pair<Node,Integer> node=findNode(key);
        //根据返回值是否插入还是修改
        if(node.val!=-1){
            System.out.println("此key值已存在！");
            return false;
        }
       //没有找到，那么此时就要插入这个新节点，
        //此时的插入操作就是以直接插入方法进行
        Node parent=node.getKey();
        int i=parent.Usize-1;
        for (;i>=0;i--){
            if(parent.keys[i]>=key){
                parent.keys[i+1]=parent.keys[i];
            }else {
                break;
            }
        }
        //此时i变成负数，我们要把0下标的值放进去。
        parent.keys[i+1]=key;
        parent.Usize++;
        if(parent.Usize >= BT){
            //超出容量，此时进行分裂
            Split(parent);
            return true;
        }else {
            return true;
        }

    }

那么如若我们找不到的话，即这个数据是未曾插入的，所以我们要进行插入它。

那么插入的话选用了直接插入排序。

插入完成之后，我们还要判断下是否是大于了这个BT值，如若是大于了，此时我们就要进行分裂。

那么接下来就还有个分裂操作还没有分享。

分裂

这里的分裂分为根节点分裂，和孩子节点分裂

举例

根节点满时：

值得注意的是，我们把关键字移动的同时，也要把孩子数组对应到下标值，一一挪过去，挪过去的同时也要对subs[]数组中的值的父亲进行修改

然后呢，此时我们这里的举动是把同一层的孩子节点处理了，但是新出现的根节点

就比如现在的75，还没用进行处理，所以呢，我们要处理它，

比如keys[0]下标放的是75，subs[0]下标放的是53这个节点，sub[1]放的是139这个节点值

然后把53这个节点的父亲和139这个父亲，进行修改，然后还要修改对应的Usize。

  private void Split(Node cur) {
        Node parent=cur.parent;
        Node newNode=new Node();
        int mid=cur.Usize>>1;
        int j=0;
        int i=mid+1;
        for (;i<cur.Usize;i++){
            newNode.keys[j]=cur.keys[i];
            newNode.subs[j]=cur.subs[i];
            if(newNode.subs[i]!=null){
           //修改迁移过去的父亲节点
                newNode.subs[j].parent=newNode;
            }
            j++;
        }
        //由于分配多了一个节点，那么此时就要再次拷贝下孩子
        newNode.subs[j]=cur.subs[i];
        if(newNode.subs[i]!=null){
            newNode.subs[i].parent=newNode;
        }
        //此时进行修改Usize和新创建节点的父亲节点
        cur.Usize=cur.Usize-j-1;
        newNode.Usize=j;

        if(cur==root){
            root=new Node();
            root.keys[0]=cur.keys[mid];
            root.subs[0]=cur;
            root.subs[1]=newNode;
            root.Usize++;
            cur.parent=root;
            newNode.parent=root;
            return;
        }

        newNode.parent=parent;

这里是根节点的修改，还有孩子节点的分裂

孩子节点的分裂：

以下面例子举例：

显然，最左边的树，是满了，所以要进行分裂

孩子分裂出来的思路和刚刚根节点是差不多，

那么这里要说明的是下，对于孩子节点分裂完后，父亲节点的操作

即把49提到根节点后怎么操作。

插入49也是一个直接插入排序，所以不过多讲解。

如若我们定义一个endT=当前节点的.Usize-1，即是1-1=0，就是0下标。

那我们可以发现，没有分裂前，75这个节点subs[1]连接139这棵树。

那么如何把新增加53这棵树的节点插入到subs[1]呢？

显然，当我们把49和53排好序后，此时的endT=0

所以，subs[endT+2]的空间存储139这棵树节点即可。

等代码跳出循环后，再次把subs[1]的值赋值为53这棵树的节点值即可。

那么此时接着插入节点

可以注意到的是，101那边的这棵树也满了，继续分裂

再次注意到，出现了连续分裂，因为根节点这棵树也是满了，所以接着也要对根节点这棵树进行分裂，为了可以进行连续分裂，我们可以进行递归这样的方式

即判断下分裂完后，把139提到根节点后，当前的Usize值是否是满的，然后递归分裂

完整分裂代码：

 private void Split(Node cur) {
        Node parent=cur.parent;
        Node newNode=new Node();
        int mid=cur.Usize>>1;
        int j=0;
        int i=mid+1;
        for (;i<cur.Usize;i++){
            newNode.keys[j]=cur.keys[i];
            newNode.subs[j]=cur.subs[i];
            if(newNode.subs[i]!=null){
           //修改迁移过去的父亲节点
                newNode.subs[j].parent=newNode;
            }
            j++;
        }
        //由于分配多了一个节点，那么此时就要再次拷贝下孩子
        newNode.subs[j]=cur.subs[i];
        if(newNode.subs[i]!=null){
            newNode.subs[i].parent=newNode;
        }
        //此时进行修改Usize和新创建节点的父亲节点
        cur.Usize=cur.Usize-j-1;
        newNode.Usize=j;

        if(cur==root){
            root=new Node();
            root.keys[0]=cur.keys[mid];
            root.subs[0]=cur;
            root.subs[1]=newNode;
            root.Usize++;
            cur.parent=root;
            newNode.parent=root;
            return;
        }

        newNode.parent=parent;
        //此时开始对父亲节点开始操作
        int endT=parent.Usize-1;
        int midVal=cur.keys[mid];
        //采取的是直接插入
        for(;endT>=0;endT--){
            if (parent.keys[endT]>=midVal){
                parent.keys[endT+1]=parent.keys[endT];
                parent.subs[endT+2]=parent.subs[endT+1];
            }else {
                break;
            }
        }
        parent.keys[endT+1]=midVal;
        parent.subs[endT+2]=newNode;
        parent.Usize++;
        if(parent.Usize>=BT){
            Split(parent);
        }
    }

ok，B-树的整个插入操作就讲完啦

那么接下来的删除操作