B-树原理及 Java 模拟实现

查找与插入

查找函数需要返回 Pair<BTRNode, Integer>。如果 val 不为 -1，说明元素已存在；若为 -1，则 getKey() 返回的是应插入位置的父节点。

插入时，先判断是否为空树。若非空，调用 find 确认是否存在。若不存在，在叶子节点中腾出空间插入。一旦 usedSize 达到 M，立即触发 split 方法。

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) {
    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;
    split(parent);
    return true;
}

节点分裂

分裂是 B-树保持平衡的关键。当节点满时，取中间位置，将右半部分及其子指针复制到新节点，中间元素上提。特别注意更新子节点的父指针，以及处理根节点分裂的特殊情况（创建新根）。

private void split(BTRNode cur) {
    BTRNode newNode = new BTRNode();
    BTRNode parent = cur.parent;
    int mid = cur.usedSize >> 1;
    int i = mid + 1, 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);
}

完整实现

将上述逻辑整合，包含中序遍历验证：

public class MyBtree {
    static class BTRNode {
        public int[] keys;
        public BTRNode[] subs;
        public BTRNode parent;
        public int usedSize;
        public static final int M = 3;

        public BTRNode() {
            this.keys = new int[M];
            this.subs = new BTRNode[M + 1];
        }
    }

    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;
        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, 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）覆盖，然后在后继所在的子树中递归删除。这样保证实际删除发生在叶子节点。
2. 节点平衡调整：
   • 借位：若兄弟节点关键字数大于下限，父节点 Key 下移，兄弟节点 Key 上移。
   • 合并：若兄弟节点也不足，将父节点 Key 下移，与当前节点及兄弟节点合并为新节点。原父节点的两个子指针变为一个。

以下图 5 阶 B-树为例，展示删除过程中的借位与合并逻辑。

B-树的优势与应用

• 减少 I/O：多路平衡设计大幅降低树高，减少磁盘访问次数。
• 自平衡：插入删除自动维护平衡，无需额外旋转操作。
• 适用场景：数据库索引（MySQL/PostgreSQL）、文件系统（Inode）、GIS 空间索引等。

变种对比：B+ 树与 B* 树

B+ 树

B+ 树是 B-树的常见变体，主要区别在于：

• 所有关键字都存储在叶子节点，非叶子节点仅存索引。
• 叶子节点通过链表连接，支持高效范围查询。
• 更适合文件系统和数据库索引。

B* 树

B* 树进一步优化了节点利用率：

• 非根非叶子节点关键字数至少为 (2/3)M，空间利用率更高。
• 增加指向兄弟节点的指针，分裂时尽量不分配新节点，而是与兄弟共享。