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

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

B-树是一种平衡的 M 路（M>=2）查找树，其核心设计目标是减少磁盘 I/O 次数。相比二叉搜索树，B-树通过增加每个节点的子节点数量来降低树的高度，从而在海量数据存储场景中表现优异。

定义与特性

1. 根节点至少有两个孩子；
2. 每个非根节点至少有 M/2(上取整) 个关键字，至多有 M-1 个关键字，且升序排列；
3. 每个非根节点至少有 M/2(上取整) 个孩子，至多有 M 个孩子；
4. key[i] 和 key[i+1] 之间的孩子节点的值介于两者之间；
5. 所有叶子节点位于同一层。

插入分析

以 M=3 为例，每个节点最多存储两个数据。为了简化分裂逻辑，我们允许节点暂时容纳三个关键字，插入第三个后再触发分裂。

下面以序列【53, 139, 75, 49, 145, 36, 101】构建 B 树的过程演示：

插入总结：

1. 若树为空，直接创建根节点。
2. 若非空，定位到叶子节点位置。
3. 检查元素是否已存在，避免重复插入。
4. 按排序插入后，若节点满（达到 M），则执行分裂操作。
5. 分裂可能向上传播，直至根节点或不再需要分裂。

模拟实现

基本结构

我们需要一个节点类 BTRNode，包含关键字数组、子节点指针、父节点指针以及当前有效关键字数量。同时需要一个辅助类 Pair 来返回查找结果。

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

寻找插入位置

这里返回 Pair<BTRNode, Integer> 很有必要。因为我们需要区分两种情况：一是找到了相同的 Key（不插入），二是找到了插入位置（叶子节点）。仅返回节点无法区分是否存在该 Key，仅返回下标无法知道插入点。

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

删除操作

删除逻辑比插入复杂，主要涉及借位和合并。

1. 若待删 Key 在非叶子节点，用后继 Key 覆盖，转为删除叶子节点的后继 Key。
2. 若删除后节点 Key 数不足下限（ceil(M/2)-1），尝试从兄弟节点借位。
3. 若兄弟节点也无多余 Key，则与兄弟节点及父节点 Key 合并。

B+ 树与 B* 树

B+ 树是 B-树的变体，所有关键字都存储在叶子节点，并通过链表连接。这使得范围查询效率更高，更适合文件系统和数据库索引。

*B 树**进一步提高了节点利用率，非叶子节点的关键字使用率至少为 2/3，减少了分裂频率。

总结

B-树及其变种是现代数据存储系统的基石。理解其插入分裂机制和内存布局，对于优化数据库性能至关重要。上述 Java 实现展示了核心逻辑，实际工程中还需考虑并发控制与持久化策略。