B-树原理详解及 Java 模拟实现

插入 101，引发连锁分裂。

最终导致根节点分裂。

插入总结

1. 如果树为空，直接插入新节点中，该节点为树的根节点。
2. 树非空，找待插入元素在树中的插入位置（注意：找到的插入节点位置一定在叶子节点中）。
3. 检测是否找到插入位置（假设树中的 key 唯一，即该元素已经存在时则不插入）。
4. 按照插入排序的思想将该元素插入到找到的节点中。
5. 检测该节点是否满足 B-树的性质：即该节点中的元素个数是否等于 M，如果小于则满足。
6. 如果插入后节点不满足 B 树的性质，需要对该节点进行分裂：申请新节点，找到该节点的中间位置，将该节点中间位置右侧的元素以及其孩子搬移到新节点中，将中间位置元素以及新节点往该节点的双亲节点中插入，即递归执行上述步骤。
7. 如果向上已经分裂到根节点的位置，插入结束。

Java 模拟实现

基本结构

我们需要定义一个节点类 BTRNode，包含关键字数组、孩子指针数组、父节点指针以及当前已用大小。为了便于分裂操作，数组容量通常比最大关键字数多 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 class MyBtree { 
    static class BTRNode { 
        public int[] keys;//关键字 
        public BTRNode[] subs;//孩子 
        public BTRNode parent;//存储当前孩子节点的父亲节点 
        public int usedSize;//记录当前节点中关键字的数量 
        public BTRNode () { 
            //说明一下：这里多给一个 是为了好进行分裂 
            this.keys = new int[M]; 
            this.subs = new BTRNode[M+1]; 
        } 
    } 
    public static final int M = 3; 
    public BTRNode root;//当前 B 树的根节点 
}

寻找插入位置

为什么要返回 Pair<BTRNode,Integer>？因为 find 函数需要同时完成两个任务：一是检查 B-树中是否存在要插入的元素，二是确定插入的具体位置。如果只返回节点，无法区分是找到了相同元素还是仅仅定位到了父节点；如果只返回索引，又不知道具体在哪个节点。使用 Pair 可以同时携带节点引用和在该节点内的下标信息。

private Pair<BTRNode,Integer> find(int key) { 
    BTRNode cur = root; 
    BTRNode parent = 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) { 
                i++; 
            }else { 
                break; 
            } 
        } 
        parent = cur; 
        cur = cur.subs[i]; 
    } 
    return new Pair<>(parent,-1); 
}

插入元素

插入逻辑主要分三步：判断是否为空、检查重复、执行插入并可能分裂。

public boolean insert(int key) { 
    //1、如果 B 树为空的时候 
    if(root == null) { 
        root = new BTRNode(); 
        root.keys[0] = key; 
        root.usedSize++; 
        return true; 
    } 
    //2、当 B 树不为空的时候，我们需要查看当前 B 树当中 是否存在我的 Key 
    Pair<BTRNode,Integer> pair = find(key); 
    //判断 这里获取到的 val 值 是不是 -1 来确定 当前是否存在该 key 
    if(pair.getVal() != -1) { 
        return false; 
    } 
    //3、说明不存在这个 key 我们要进行插入 
    BTRNode parent = pair.getKey(); 
    int index = parent.usedSize-1; 
    for (; index >= 0;index--) { 
        if(parent.keys[index] >= key) { 
            parent.keys[index+1] = parent.keys[index]; 
        }else { 
            break; 
        } 
    } 
    parent.keys[index+1] = key; 
    parent.usedSize++; 
    //为什么不处理 孩子呢 因为你每次插入都是再叶子节点，所以叶子节点都是 null 
    if(parent.usedSize < M) { 
        //没有满 
        return true; 
    }else { 
        //满了-》分裂 
        split(parent); 
        return true; 
    } 
}

分裂节点

分裂是 B-树保持平衡的关键。当节点满时，需要将中间元素提升给父节点，剩余元素拆分到新节点。这里要注意更新新节点的孩子指针的父节点引用。

private void split(BTRNode cur) { 
    BTRNode newNode = new BTRNode(); 
    //1. 先存储当前需要分裂节点的父节点 
    BTRNode parent = cur.parent; 
    //2. 开始挪数据 
    int mid = cur.usedSize >> 1; 
    int i = mid+1; 
    int j = 0; 
    for( ; i < cur.usedSize;i++) { 
        newNode.keys[j] = cur.keys[i]; 
        newNode.subs[j] = cur.subs[i]; 
        //处理刚刚拷贝过来的孩子节点的父亲节点 为新分裂的节点 
        if(newNode.subs[j]!=null) { 
            newNode.subs[j].parent = newNode; 
        } 
        j++; 
    } 
    //多拷贝一次孩子 
    newNode.subs[j] = cur.subs[i]; 
    if(newNode.subs[j]!=null) { 
        newNode.subs[j].parent = newNode; 
    } 
    //更新当前新节点的有效数据 
    newNode.usedSize = j; 
    //这里的 -1 指的是 将来要提到父亲节点的 key 
    cur.usedSize = cur.usedSize - j - 1; 
    //特殊：处理根节点的情况 
    if(cur == root) { 
        root = new BTRNode(); 
        root.keys[0] = cur.keys[mid]; 
        root.subs[0] = cur; 
        root.subs[1] = newNode; 
        root.usedSize = 1; 
        cur.parent = root; 
        newNode.parent = root; 
        return; 
    } 
    //更新当前新的节点的父亲节点 
    newNode.parent = parent; 
    //开始移动父亲节点 
    int endT = parent.usedSize-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; 
    //将当前父节点的孩子节点 新增为 newNode 
    parent.subs[endT+2] = newNode; 
    parent.usedSize++; 
    if(parent.usedSize >= M) { 
        split(parent); 
    } 
}

中序遍历

中序遍历可以验证 B-树的关键字是否有序。

private void inorder(BTRNode 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]); 
}

完整代码示例

将上述逻辑整合，完整的 MyBtree.java 如下：

public class MyBtree { 
    static class BTRNode { 
        public int[] keys;
        public BTRNode[] subs;
        public BTRNode parent;
        public int usedSize;
        public BTRNode () {
            this.keys = new int[M];
            this.subs = new BTRNode[M+1];
        }
    }
    public static final int M = 3;
    public BTRNode root;

    public boolean insert(int key) {
        if(root == null) {
            root = new BTRNode();
            root.keys[0] = key;
            root.usedSize++;
            return true;
        }
        Pair<BTRNode,Integer> pair = find(key);
        if(pair.getVal() != -1) {
            return false;
        }
        BTRNode parent = pair.getKey();
        int index = parent.usedSize-1;
        for (; index >= 0;index--) {
            if(parent.keys[index] >= key) {
                parent.keys[index+1] = parent.keys[index];
            }else {
                break;
            }
        }
        parent.keys[index+1] = key;
        parent.usedSize++;
        if(parent.usedSize < M) {
            return true;
        }else {
            split(parent);
            return true;
        }
    }

    private void split(BTRNode cur) {
        BTRNode newNode = new BTRNode();
        BTRNode parent = cur.parent;
        int mid = cur.usedSize >> 1;
        int i = mid+1;
        int j = 0;
        for( ; i < cur.usedSize;i++) {
            newNode.keys[j] = cur.keys[i];
            newNode.subs[j] = cur.subs[i];
            if(newNode.subs[j]!=null) {
                newNode.subs[j].parent = newNode;
            }
            j++;
        }
        newNode.subs[j] = cur.subs[i];
        if(newNode.subs[j]!=null) {
            newNode.subs[j].parent = newNode;
        }
        newNode.usedSize = j;
        cur.usedSize = cur.usedSize - j - 1;
        if(cur == root) {
            root = new BTRNode();
            root.keys[0] = cur.keys[mid];
            root.subs[0] = cur;
            root.subs[1] = newNode;
            root.usedSize = 1;
            cur.parent = root;
            newNode.parent = root;
            return;
        }
        newNode.parent = parent;
        int endT = parent.usedSize-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.usedSize++;
        if(parent.usedSize >= M) {
            split(parent);
        }
    }

    private Pair<BTRNode,Integer> find(int key) {
        BTRNode cur = root;
        BTRNode parent = 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) {
                    i++;
                }else {
                    break;
                }
            }
            parent = cur;
            cur = cur.subs[i];
        }
        return new Pair<>(parent,-1);
    }

    private void inorder(BTRNode 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]);
    }

    public static void main(String[] args) {
        MyBtree myBtree = new MyBtree();
        int[] array = {53, 139, 75, 49, 145, 36,101};
        for (int i = 0; i < array.length; i++) {
            myBtree.insert(array[i]);
        }
        myBtree.inorder(myBtree.root);
    }
}

运行结果会按顺序输出所有关键字，验证树的有序性。

删除操作简述

删除操作相对复杂，主要涉及后继替换、借位和合并三种情况。

1. 若删除的 key 位于非叶子结点，用后继 key 覆盖，然后在后继 key 所在的子支中删除该后继 key（此时后继 key 一定位于叶子结点上）。
2. 若删除后结点 key 个数大于等于 Math.ceil(m/2)-1，结束删除操作。
3. 否则，若兄弟结点 key 个数足够，则父结点中的 key 下移，兄弟结点中的一个 key 上移。
4. 若兄弟结点也不够，则将父结点中的 key 下移与当前结点及它的兄弟结点中的 key 合并，形成一个新的结点，然后当前结点的指针指向父结点，重复上述步骤。

B+ 树对比

B+ 树是 B-树的变形，也是一种多路搜索树。其定义基本与 B-树相同，但有以下区别：

1. 非叶子节点的子树指针与关键字个数相同。
2. 非叶子节点的子树指针 p[i]，指向关键字值属于 [k[i], k[i+1]) 的子树。
3. 为所有叶子节点增加一个链指针。
4. 所有关键字都在叶子节点出现。

B+ 树的搜索与 B-树基本相同，区别是 B+ 树只有达到叶子节点才能命中，其性能也等价与在关键字全集做一次二分查找。

B+ 树的优势

1. 降低磁盘 I/O 次数：由于 B+ 树的非叶子节点不保存数据，且叶子节点之间通过指针相连，这使得在查找数据时，可以一次性加载更多的关键字到内存中。
2. 提高查询效率：B+ 树的叶子节点之间通过指针相连，形成了有序链表，这使得范围查询变得非常高效。
3. 适用于大数据集：B+ 树的高度较低，对于大数据集来说，可以减少查找、插入和删除操作所需的时间复杂度。

B+ 树的应用场景

1. 数据库索引：在关系型数据库中，B+ 树被广泛用于索引数据。
2. 文件系统：在文件系统中，B+ 树用于存储和管理文件和目录。
3. 缓存管理：在计算机系统中，B+ 树可用于管理缓存数据。

B* 树简介

B* 树是 B+ 树的一种变体，它在 B+ 树的基础上进行了优化。

特点

1. 节点结构：B* 树保留了 B+ 树的基本结构，但在非根和非叶子节点中增加了指向兄弟的指针。
2. 关键字数量：B* 树定义了非叶子节点关键字个数至少为 (2/3)M，即块的最低使用率为 2/3，这比 B+ 树的 1/2 更高。
3. 分裂与合并：当 B* 树的节点满时，会分配一个新的节点，并将数据根据一定的规则进行分裂。在分裂过程中，B* 树会尽量保持节点的平衡。

B* 树的优势

1. 更高的空间使用率：由于 B* 树定义了更高的块最低使用率，因此在相同条件下，B* 树能够存储更多的关键字。
2. 更好的平衡性：B* 树通过增加指向兄弟的指针和更严格的节点分裂与合并规则，使得树在插入和删除操作时能够更好地保持平衡。
3. 更低的磁盘 I/O 次数：由于 B* 树在存储结构上的优化，使得在进行大量数据的查询、插入和删除操作时，能够减少磁盘 I/O 次数。

总结

B-树及其变种（B+ 树、B* 树）是现代数据存储系统的基石。它们通过平衡树结构和多路查找机制，有效解决了海量数据下的检索效率问题。理解其插入、删除及分裂合并的底层逻辑，对于掌握数据库索引原理和文件系统设计至关重要。