跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客我的书AI学习GitHub 精选镜像AI工具UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
Javajava算法

B-树模拟实现详解

B-树作为一种平衡多路查找树，通过节点分裂与合并维持高度平衡，有效降低磁盘I/O。详细解析了B-树的定义、插入分裂机制及核心代码实现，涵盖节点结构、查找定位、元素插入与节点分裂逻辑。同时对比了B+树与B*树的特点，探讨了其在数据库索引与文件系统中的应用场景，适合希望深入理解底层数据结构原理的开发者参考。

莫名其妙发布于 2026/3/14更新于 2026/10/22100 浏览
B-树模拟实现详解

B-树模拟实现详解

什么是 B-树

B-树是一种平衡的 M 路（M>=2）查找树。它可以是空树，每个节点拥有多个子节点，这种结构有效减少了树的高度，从而显著提高查找效率。

核心特性

  1. 根节点至少有两个孩子；
  2. 每个非根节点至少有 ceil(M/2)-1 个关键字，至多有 M-1 个关键字，且按升序排列；
  3. 每个非根节点至少有 ceil(M/2) 个孩子，至多有 M 个孩子；
  4. key[i] 和 key[i+1] 之间的孩子节点的值介于这两个关键字之间；
  5. B-树通过节点的分裂和合并操作来保持树的平衡，所有叶子节点都位于同一层。

插入机制分析

以 M=3 为例，每个节点存储两个数据时，可以将区间分割为三部分。为了方便处理分裂逻辑，我们通常假设每个节点最多有三个关键字、四个孩子，当插入第三个关键字后再进行分裂。

下面以插入序列【53, 139, 75, 49, 145, 36, 101】为例构建 B 树：

文章配图

步骤解析：

  1. 插入 53：树为空，直接作为根节点。
  2. 插入 139：添加到根节点。
  3. 插入 75：此时节点内已有两个元素，继续添加。
  4. 引发分裂：节点满后触发分裂，中间元素上移。
  5. 插入 49 和 145：分别落入不同分支。
  6. 插入 36：进入左子树。
  7. 再次分裂：子节点满，向上冒泡。
  8. 插入 101：最终调整完成。

文章配图

插入总结

  • 若树为空，新节点即为根节点。
  • 若树非空，需找到待插入元素在树中的位置（注意：插入位置一定在叶子节点中）。
  • 检测元素是否已存在（假设 key 唯一），若存在则不插入。
  • 按插入排序思想将元素放入节点。
  • 检查节点是否满足性质（元素个数 < M）。若不满足，执行分裂操作。
  • 分裂时申请新节点，将中间位置右侧元素及孩子搬移，并将中间元素及新节点插入父节点，递归处理直到不再分裂或到达根节点。

代码实现细节

基本结构设计

为了实现 B-树，我们需要定义节点结构和辅助类。这里使用 Java 语言演示。

首先是一个简单的键值对类 Pair，用于返回查找结果：

public class Pair<K,V> {
    private K key;
     V val;
      { 
        .key = key; 
        .val = val; 
    }
     K  {  key; }
       { .key = key; }
     V  {  val; }
       { .val = val; }
}
private
public
Pair
(K key, V val)
this
this
public
getKey
()
return
public
void
setKey
(K key)
this
public
getVal
()
return
public
void
setVal
(V val)
this

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

目录

  1. B-树模拟实现详解
  2. 什么是 B-树
  3. 核心特性
  4. 插入机制分析
  5. 插入总结
  6. 代码实现细节
  7. 基本结构设计
  8. 寻找插入位置
  9. 插入元素逻辑
  10. 节点分裂策略
  11. 中序遍历
  12. 完整代码与测试
  13. B-树的删除
  14. B-树的优点与应用
  15. 核心优势
  16. 应用场景
  17. B+ 树与 B* 树简介
  18. B+ 树
  19. B* 树
  20. 总结

更多推荐文章

查看全部
  • C++ 基础笔记：命名空间、IO、缺省参数及 Makefile
  • 基于 Rust 与大模型的智能 API Mock 生成器构建
  • 从零构建可扩展 Flutter 应用：v1.0 到 v2.0 架构演进详解
  • Java 环境配置与第一个 Hello World 程序实战
基于 LangChain 搭建本地知识库系统
  • 双指针算法进阶：从三角形到多数之和
  • LLaMA-Factory 大模型微调全流程实战
  • 当看到 Bug 背后的真相，我选择了沉默
  • AI 编程技能（Skill）详解与 Java 方法生成实战
  • C++ STL 核心基础：迭代器、auto 与范围循环
  • 产品经理 AI 学习地图：从入门到精通的完整指南
  • IBM DB2 常用命令与基础操作指南
  • C++ 多线程同步之原子操作（atomic）实战
  • 大模型基座训练的挑战与难点
  • Python 中 as 关键字的作用与用法
  • AI 时代创作者的核心身份与生存法则
  • 自然语言处理在金融领域的应用与实战
  • 网络安全挖洞实战指南：工具准备与漏洞提交流程
  • C++ STL 标准库算法详解与实战
  • 秋田中文离线地图 App 上线

    • 相关免费在线工具

    • Keycode 信息

      查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online

    • Escape 与 Native 编解码

      JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online

    • JavaScript / HTML 格式化

      使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online

    • JavaScript 压缩与混淆

      Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online

    • 加密/解密文本

      使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

    • Gemini 图片去水印

      基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online