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

寻找插入位置

这里返回 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 实现展示了核心逻辑，实际工程中还需考虑并发控制与持久化策略。