B-树模拟实现详解

核心节点类 BTRNode 包含关键字数组、孩子指针数组、父节点指针以及当前使用的关键字数量：

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];
    }
    // 未找到，返回父节点和 -1 表示插入位置
    return new Pair<>(parent, -1);
}

插入元素逻辑

插入流程如下：

1. 若根节点为空，直接创建并赋值。
2. 若不为空，先调用 find 检查是否存在重复 key。
3. 若不存在，在找到的叶子节点中按顺序插入。
4. 检查节点是否已满（usedSize >= M），若满则触发分裂。

public boolean insert(int key) {
    // 1. 树为空的情况
    if (root == null) {
        root = new BTRNode();
        root.keys[0] = key;
        root.usedSize++;
        return true;
    }

    // 2. 检查是否存在
    Pair<BTRNode, Integer> pair = find(key);
    if (pair.getVal() != -1) {
        return false; // 已存在
    }

    // 3. 执行插入
    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-树保持平衡的关键。主要步骤包括：

1. 记录当前节点及其父节点，创建新节点。
2. 计算中间位置，将右半部分的数据和孩子拷贝到新节点。
3. 更新新节点的有效大小，并修正被移动孩子的父指针。
4. 将中间元素提升到父节点。
5. 若父节点也满了，递归分裂父节点。

private void split(BTRNode cur) {
    BTRNode newNode = new BTRNode();
    BTRNode parent = cur.parent;

    // 1. 计算中间位置
    int mid = cur.usedSize >> 1;
    int i = mid + 1;
    int j = 0;

    // 2. 挪动数据和指针
    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;
    }

    // 3. 更新有效大小
    newNode.usedSize = j;
    cur.usedSize = cur.usedSize - j - 1;

    // 4. 特殊处理根节点
    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;
    }

    // 5. 更新父节点
    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++;

    // 6. 递归分裂父节点
    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]);
}

完整代码与测试

以下是整合后的完整代码，包含主方法测试：

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);
    }
}

运行上述代码，控制台将输出有序序列，验证了 B-树的中序遍历结果正确性。

B-树的删除

删除操作相对复杂，主要分为三种情况：

1. 非叶子节点删除：用后继 key 覆盖要删除的 key，然后在后继 key 所在的子支中删除该后继 key（此时后继 key 一定位于叶子节点）。
2. 叶子节点 key 数不足：若删除后节点 key 个数小于 ceil(m/2)-1，尝试从兄弟节点借取 key。
3. 合并节点：若兄弟节点也无多余 key，则将父节点 key 下移，与当前节点及兄弟节点合并。

以 5 阶 B 树为例，节点最多有 4 个 key，最少有 2 个 key。删除过程中可能涉及多次旋转或合并，直至满足平衡条件。

B-树的优点与应用

核心优势

1. 减少磁盘 I/O：设计目标是减少磁盘访问次数，提高存取速度。
2. 自平衡性：插入和删除时自动分裂合并，确保操作高效。
3. 支持海量数据：通过增加子节点数量降低树高，减少遍历节点数。

应用场景

• 数据库索引：MySQL、PostgreSQL 等基于 B-树变种实现索引。
• 文件系统：管理目录和文件，如 Unix Inode。
• GIS 系统：空间数据索引。
• 路由表：快速定位目标地址。

B+ 树与 B* 树简介

B+ 树

B+ 树是 B-树的变形，主要区别在于：

• 所有关键字都出现在叶子节点的链表中。
• 非叶子节点仅作为索引，不包含数据。
• 叶子节点之间有指针相连，适合范围查询。

优势：降低磁盘 I/O，范围查询效率高，更适合文件系统和数据库索引。

B* 树

B* 树在 B+ 树基础上进一步优化：

• 非根和非叶子节点增加指向兄弟的指针。
• 块最低使用率为 2/3，比 B+ 树的 1/2 更高。
• 分裂概率更低，空间利用率更高。

总结

B-树及其变种是现代数据存储系统的基石。理解其插入分裂、删除合并的底层逻辑，对于优化数据库性能和设计高效数据结构至关重要。