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

三、B-树插入算法总结

1. 若树为空，直接创建根节点并插入关键字。
2. 若树非空，查找待插入关键字的位置（最终插入位置必为叶子节点）。
3. 若关键字已存在，则直接返回（假设关键字唯一）。
4. 将关键字按升序插入目标节点。
5. 检查节点关键字数量是否达到 M。若未达到，插入完成。
6. 若节点已满（关键字数等于 M），则执行分裂：
   • 申请新节点。
   • 取中间位置关键字，将其右侧关键字及对应子节点移至新节点。
   • 将中间关键字及新节点指针插入父节点，并递归检查父节点是否满足性质。
7. 若分裂传播至根节点，则创建新根，树高增加 1。

四、Java模拟实现

1. 辅助类 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; }
}

2. B-树节点结构

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

3. 查找插入位置

返回 Pair<BTRNode, Integer> 的原因：

• 若仅返回节点，无法区分'关键字已存在'与'找到插入位置'。
• 若仅返回索引，无法定位具体节点。
• 使用 Pair 可同时返回目标节点及关键字下标（若已存在则返回对应下标，否则返回 -1 表示应插入该节点）。

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

4. 插入元素

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

5. 节点分裂

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

6. 中序遍历

private void inorder(BTRNode node) {
    if (node == null) return;
    for (int i = 0; i < node.usedSize; ++i) {
        inorder(node.subs[i]);
        System.out.println(node.keys[i]);
    }
    inorder(node.subs[node.usedSize]);
}

7. 完整代码与测试

public class MyBTree {
    // 包含上述所有内部类与方法
    public static void main(String[] args) {
        MyBTree tree = new MyBTree();
        int[] array = {53, 139, 75, 49, 145, 36, 101};
        for (int k : array) {
            tree.insert(k);
        }
        tree.inorder(tree.root);
    }
}

运行结果将按升序输出所有关键字。

五、B-树的删除操作

删除操作需保证删除后节点关键字数仍满足 ≥ ⌈M/2⌉ - 1。

1. 定位关键字：若关键字位于非叶子节点，用其后继关键字（必在叶子节点）替换，然后转为删除叶子节点中的该后继关键字。
2. 检查节点容量：若删除后节点关键字数 ≥ ⌈M/2⌉ - 1，删除结束。
3. 向兄弟借位：若兄弟节点关键字数 > ⌈M/2⌉ - 1，则将父节点对应关键字下移至当前节点，兄弟节点的一个关键字上移至父节点。
4. 节点合并：若兄弟节点也不满足借位条件，则将父节点关键字下移，与当前节点及兄弟节点合并为一个新节点。合并后，若父节点关键字数不足，则递归向上处理。

(注：删除过程涉及多次节点形态变化，可参考原图演示步骤 a~e)

六、B-树的优点与应用场景

优点

• 减少磁盘 I/O：多路结构大幅降低树高，减少磁盘访问次数。
• 自平衡性：插入/删除自动分裂/合并，保证查找、插入、删除的高效性。
• 支持海量数据：通过增加分支因子有效管理大规模数据集。

应用场景

• 数据库索引：MySQL、PostgreSQL 等广泛采用 B-树或其变种。
• 文件系统：如 Unix 的 Inode 结构。
• GIS 空间索引：用于空间数据的快速检索。
• 网络路由表：快速定位目标地址。

七、B+树

B+树是 B-树的变种，主要区别如下：

1. 非叶子节点的子树指针数与关键字数相同。
2. 非叶子节点仅作为索引，不存储实际数据记录。
3. 所有关键字及数据记录均存储在叶子节点中。
4. 叶子节点通过指针相连，形成有序链表。

B+树的优势

• 更低的 I/O 次数：内部节点仅存索引，单页可容纳更多关键字，树高更低。
• 高效的范围查询：叶子节点链表结构天然支持顺序遍历。
• 查询性能稳定：所有查询必达叶子节点，路径长度一致。

应用场景

关系型数据库索引（如 InnoDB）、文件系统目录管理、缓存系统等。

八、B*树

B*树是 B+树的进一步优化：

• 节点结构：非根/非叶子节点增加指向兄弟节点的指针。
• 空间利用率：节点最低使用率提升至 2/3（B+树为 1/2），减少分裂频率。
• 分裂策略：节点满时，优先尝试与兄弟节点共享空间，均满时才分裂。

优势

更高的空间利用率、更好的平衡性、更少的磁盘 I/O。

九、总结

B-树及其变种（B+树、B*树）通过多路平衡结构，完美契合磁盘存储特性，是现代数据库与文件系统的核心基石。理解其分裂、合并与索引机制，对系统设计与性能调优具有重要意义。