一、基础概念：什么是 B 树？

1. 定义

B 树全称多路平衡查找树，是一种自平衡的多叉搜索树，专门为磁盘 IO 场景设计（数据库、文件系统底层索引）。 二叉搜索树一次只能二分，磁盘 IO 次数高；B 树一个节点存多条索引，大幅减少磁盘读写次数。

2. 阶数 m 的核心定义（最关键）

一棵 m 阶 B 树，满足硬性规则：

1. 每个节点最多 m 个子节点，最多 m-1 个关键字（key）；
2. 除根节点外，所有非叶子节点最少 ⌈m/2⌉ 个子节点，最少 ⌈m/2⌉ -1 个关键字；
3. 根节点特殊：最少可以只有 2 个子节点（树高度 > 1 时），若整棵树只有根，允许 0 个子节点；
4. 所有叶子节点全部在同一层（绝对平衡，不会出现左右高度差）；
5. 关键字有序：节点内关键字从小到大排列； 若节点关键字为 k₁ < k₂ < ... < kₙ，则：
   • 第 0 个子树：全部值 < k₁
   • 第 i 个子树：kᵢ < 全部值 < kᵢ₊₁
   • 最后一个子树：全部值 > kₙ

3. 通俗举例：4 阶 B 树（最常用，m=4，2-3-4 树）

m=4，最多 4 子树、3 关键字；最少⌈4/2⌉=2 子树、1 关键字。

• 节点可存 1/2/3 个 key，对应 2/3/4 个子节点；
• 超过 3 个 key 触发节点分裂；
• 少于 1 个 key 触发节点合并 / 借值。

二、B 树节点结构拆解

节点内部存储结构（磁盘页标准格式）

[子树指针0][key₀][子树指针1][key₁][子树指针2]...[keyₙ₋₁][子树指针n]

1. Key：索引关键字（如主键 ID、数字），附带数据地址（磁盘记录偏移）；
2. 子树指针：指向下层磁盘页（子节点）；
3. 叶子节点：子树指针全部为空，key 直接绑定完整数据；
4. 非叶子节点：仅存索引 key，不存完整数据，只用来路由查找。

和二叉搜索树对比

特性	二叉搜索树 BST	m 阶 B 树
分支数	最多 2 叉	最多 m 叉
磁盘 IO	树高很高，IO 频繁	树高极小，IO 极少
平衡特性	普通 BST 会退化链表，AVL 平衡但维护复杂	天然全局平衡，所有叶子同层
适用场景	内存小规模数据	磁盘数据库、文件索引

三、B 树核心四大操作：查找 / 插入 / 删除 / 分裂 / 合并

（1）查找操作（递归逻辑）

流程

1. 从根节点进入，遍历当前节点有序 key 数组；
2. 找到等于目标 key：直接返回该节点数据；
3. 找到第一个大于目标的 key，走它左侧子树；
4. 所有 key 都小于目标，走最后一个子树；
5. 走到叶子节点仍未匹配：查找失败。

示例（4 阶 B 树）

节点 key：[10,30,50]，查找 25

1. 10 < 25 < 30 → 进入 10 和 30 中间的子树递归查找；
2. 直到叶子节点判断有无 25。

复杂度

树高 h ≤ log⌈m/2⌉(N+1)/2，N 为总数据量；

每一层仅 1 次磁盘 IO，数据库百万级数据仅 3~4 次 IO 即可完成查找。

（2）插入操作

整体规则

1. 插入永远先找到对应叶子节点，不会插入非叶子；
2. 叶子插入 key 后，若 key 数量 ≤ m-1：直接结束；
3. 若 key 数量 == m（溢出）：执行分裂操作。

分裂完整步骤（m 阶通用）

1. 把当前满节点全部 key + 新 key 合并为有序数组；
2. 取中间位置 mid = floor(m/2) 的 key，提升到父节点；
3. mid 左侧所有 key、子树留在原节点；
4. mid 右侧所有 key、子树新建右侧兄弟节点；
5. 父节点插入上升的 mid 关键字，若父节点也溢出，递归向上分裂；
6. 若一直分裂到根节点：新建根节点，树高度 + 1。

实操演示：4 阶 B 树（m=4，最多 3key）

采用工业 0 下标（Base-0），现有叶子节点 [12,24,36]（已满 3 个），插入 28：

1. 合并数组 [12,24,28,36]；
2. mid=2，中间值 28 提升到父节点；
3. 左节点：[12,24]，右节点：[36]；
4. 父节点新增 key=24，完成分裂； 若父节点插入后也满，重复分裂逻辑。

（3）删除操作（核心：借值 / 合并）

删除分两种场景：删除叶子 key、删除非叶子 key。

场景 1：删除叶子节点关键字

1. 删除后 key 数量 ≥ 最小下限（⌈m/2⌉-1）：直接删除，结束；
2. 删除后 key 数量 < 最小下限（欠载）：两种补救方案
   • 方案 A：向左右兄弟借关键字（优先执行） 兄弟节点 key 数量 > 最小值 → 兄弟拿一个 key 上移到父节点，父节点 key 下沉到当前节点，平衡数量；
   • 方案 B：兄弟无多余 key，执行节点合并 当前节点 + 父节点分隔 key + 兄弟节点全部合并为一个节点； 父节点删除分隔 key，若父节点因此欠载，递归向上处理。

场景 2：删除非叶子节点关键字

非叶子 key 是分隔索引，不能直接删，替换规则：

1. 取左子树最大值（左分支最右下叶子 key），替换待删除 key；
2. 再去叶子节点删除这个最大值，转化为叶子删除逻辑； 等价方案：取右子树最小值替换。

举例（4 阶 B 树，最少 1 个 key）

叶子节点 [15]，删除 15 后无 key，欠载：

1. 看右兄弟 [25,35]（有多余 key）：借 35 的父分隔 key 下沉，兄弟给一个 key 过来；
2. 若兄弟只有 1 个 key，直接合并当前节点、父分隔 key、兄弟节点。

四、B-树（B树）的基本操作C++代码实现

本代码实现m 阶标准 B 树，完全采用工业 0 下标（Base-0）开发逻辑，包含完整增删查、四种遍历、最值、区间查询、节点分裂 / 借键 / 合并欠载修复全套逻辑。

（一）基础结构体与构造类

1. struct BNode 节点结构体

struct BNode {
    vector<int> keys;          // 当前节点存储的关键字数组，有序升序
    vector<BNode*> children;   // 子节点指针数组，长度恒等于 keys.size()+1
    bool leaf;                 // true=叶子节点（无下层子树），false=非叶子索引节点
    BNode(bool isLeaf = true) : leaf(isLeaf) {}
};

• 存储规则：keys[0] < keys[1] < ... < keys[n-1]
• 子树对应关系：

children[0] 全部值 < keys[0]

children[i] 区间 keys[i-1] < val < keys[i]

children.back() 全部值 > keys.back()

2. class BTree 树类成员变量

int m;         // B树阶数 m
int max_keys;  // 单个节点最多关键字 m-1
int min_keys;  // 非根节点最少关键字 ⌈m/2⌉ -1 = (m-1)/2
BNode* root;   // 根节点指针

构造函数 BTree(int order)：

BTree(int order) {
    m = order;
    max_keys = m - 1;
    min_keys = (m - 1) / 2;
    root = new BNode(true);
}

• 初始化阶数 m = order
• 计算节点容量上下限：max_keys = m-1，min_keys = (m-1)/2
• 创建初始空根节点，默认是叶子节点（空树）

（二）查询相关函数

1. bool search(int key) 等值查找

bool search(int key) {
    BNode* cur = root;
    while (true) {
        int i = lower_bound(cur->keys.begin(), cur->keys.end(), key) - cur->keys.begin();
        if ((size_t)i < cur->keys.size() && cur->keys[i] == key) return true;
        if (cur->leaf) return false;
        cur = cur->children[i];
    }
}

功能：从根向下遍历，判断关键字是否存在 执行流程：

1. cur = root 从根节点开始循环
2. lower_bound 在当前节点有序 keys 中找到第一个≥key 的下标i
3. 若下标不越界且cur->keys[i]==key，直接返回true（找到）
4. 如果当前是叶子节点，循环结束返回false（不存在）
5. 否则进入子树 cur = cur->children[i]，重复循环

示例：3 阶 B 树节点[22,47]，查找 30

lower_bound找到下标 1（47），进入children[1]子树继续查找。

2. int get_pred(BNode* node, int idx) 获取前驱最大值

int get_pred(BNode* node, int idx) {
    BNode* cur = node->children[idx];
    while (!cur->leaf) cur = cur->children.back();
    return cur->keys.back();
}

功能：删除非叶子节点关键字时，取左子树最大值替换待删 key 执行流程：

1. 进入node->children[idx]左子树
2. 循环一直取最右侧子节点，直到抵达叶子
3. 返回叶子节点最后一个 key（该子树最大值）

3. get_min() / get_max() 全局最值

int get_min() {
    BNode* cur = root;
    while (!cur->leaf) cur = cur->children[0];
    return cur->keys[0];
}
int get_max() {
    BNode* cur = root;
    while (!cur->leaf) cur = cur->children.back();
    return cur->keys.back();
}

• get_min()：从根一直走最左子节点，直到叶子，返回叶子第一个 key（全局最小）
• get_max()：从根一直走最右子节点，直到叶子，返回叶子最后一个 key（全局最大）

4. range_query(int l, int r) 区间查询

void range_collect(BNode* n, int low, int high, vector<int>& res) {
    if (n->leaf) {
        for (int k : n->keys) if (k >= low && k <= high) res.push_back(k);
        return;
    }
    for (int i = 0; (size_t)i < n->keys.size(); i++) {
        range_collect(n->children[i], low, high, res);
        if (n->keys[i] >= low && n->keys[i] <= high) res.push_back(n->keys[i]);
    }
    range_collect(n->children.back(), low, high, res);
}
vector<int> range_query(int l, int r) {
    vector<int> res;
    range_collect(root, l, r, res);
    return res;
}

递归函数range_collect实现：

1. 若当前是叶子节点：遍历所有 key，把[l,r]范围内的值存入结果数组
2. 若非叶子：
   • 依次递归每一个子树
   • 若当前分界 key 落在区间内，存入结果
   • 最后递归最右侧子树 返回有序区间内全部关键字。

（三）插入模块：split_child + insert

1. void split_child(BNode* parent, int idx) 节点分裂核心函数

void split_child(BNode* parent, int idx) {
    BNode* node = parent->children[idx];
    BNode* right = new BNode(node->leaf);
    int mid = (int)node->keys.size() / 2;
    int mid_key = node->keys[mid];

    right->keys.assign(node->keys.begin() + mid + 1, node->keys.end());
    node->keys.resize((size_t)mid);

    if (!node->leaf) {
        right->children.assign(node->children.begin() + mid + 1, node->children.end());
        node->children.resize((size_t)(mid + 1));
    }

    parent->keys.insert(parent->keys.begin() + idx, mid_key);
    parent->children.insert(parent->children.begin() + idx + 1, right);
}

触发条件：子节点关键字数量达到max_keys（溢出），二分拆分节点 执行步骤：

1. node = parent->children[idx] 取出满的溢出节点
2. 新建空右兄弟节点right，叶子属性和原节点一致
3. 取中间下标mid = node->keys.size()/2，中间值mid_key要提升到父节点
4. 拆分关键字：
   • 右节点拷贝mid+1到末尾所有 key
   • 原节点只保留前mid个 key
5. 拆分子树指针（非叶子节点才执行）：
   • 右节点拷贝mid+1之后所有子指针
   • 原节点只保留前mid+1个子指针
6. 更新父节点：
   • 父节点 keys 插入mid_key作为新分界
   • 父节点 children 插入新右兄弟节点

示例：3 阶节点[22,47,60]溢出，mid=1，mid_key=47 原节点保留[22]，新右节点[60]，47 提升到父节点。

2. void insert(int key) 完整插入流程

void insert(int key) {
    BNode* cur = root;
    vector<pair<BNode*, int>> stack;
    while (!cur->leaf) {
        int i = lower_bound(cur->keys.begin(), cur->keys.end(), key) - cur->keys.begin();
        if ((size_t)i < cur->keys.size() && cur->keys[i] == key) {
            cout << "键已存在\n";
            return;
        }
        stack.emplace_back(cur, i);
        cur = cur->children[i];
    }
    int pos = lower_bound(cur->keys.begin(), cur->keys.end(), key) - cur->keys.begin();
    if ((size_t)pos < cur->keys.size() && cur->keys[pos] == key) {
        cout << "键已存在\n";
        return;
    }
    cur->keys.insert(cur->keys.begin() + pos, key);

    while ((int)cur->keys.size() > max_keys) {
        if (stack.empty()) {
            BNode* new_root = new BNode(false);
            new_root->children.push_back(cur);
            split_child(new_root, 0);
            root = new_root;
            break;
        }
        pair<BNode*, int> item = stack.back();
        stack.pop_back();
        BNode* p = item.first;
        int idx = item.second;
        split_child(p, idx);
        cur = p;
    }
}

核心规则：插入永远落到叶子节点，溢出后向上递归分裂 执行步骤：

1. 初始化栈stack，存储遍历路径（父节点 + 对应子树下标），用于向上分裂回溯
2. 向下遍历找到目标叶子节点：
   • 非叶子节点用lower_bound找到对应子树下标
   • 记录当前父节点与下标入栈，进入子树循环
3. 在叶子节点有序插入 key，重复值直接提示并退出
4. 向上循环处理溢出：
   • 如果当前节点 key 数量 > max_keys（溢出）
   • 栈为空 = 分裂到根节点：新建空根，把原根作为第一个子节点，调用split_child分裂，更新全局root
   • 栈不为空：取出父节点与子树下标，调用split_child分裂，切换当前节点为父节点继续循环判断溢出
5. 无溢出则插入完成。

（四）删除模块全套函数（欠载修复、借键、合并）

1. remove_from_leaf(BNode* node, int key) 叶子节点删除 key

void remove_from_leaf(BNode* node, int key) {
    auto it = lower_bound(node->keys.begin(), node->keys.end(), key);
    if (it != node->keys.end() && *it == key) node->keys.erase(it);
}

lower_bound定位 key，匹配成功直接 erase 删除，仅用于叶子节点。

2. borrow_left(BNode* parent, int idx) 向左兄弟借关键字

void borrow_left(BNode* parent, int idx) {
    BNode* cur = parent->children[idx];
    BNode* sib = parent->children[idx - 1];
    int sep = parent->keys[idx - 1];

    cur->keys.insert(cur->keys.begin(), sep);
    parent->keys[idx - 1] = sib->keys.back();
    sib->keys.pop_back();
    if (!cur->leaf) {
        cur->children.insert(cur->children.begin(), sib->children.back());
        sib->children.pop_back();
    }
}

当前节点下标idx，向左邻兄弟idx-1借 key：

1. 兄弟最后一个分界 key 下沉到当前节点头部
2. 父节点原分界值替换为兄弟最后一个 key
3. 兄弟删除末尾 key
4. 非叶子节点同步迁移兄弟最右侧子树到当前节点头部

3. borrow_right(BNode* parent, int idx) 向右兄弟借关键字

void borrow_right(BNode* parent, int idx) {
    BNode* cur = parent->children[idx];
    BNode* sib = parent->children[idx + 1];
    int sep = parent->keys[idx];

    cur->keys.push_back(sep);
    parent->keys[idx] = sib->keys[0];
    sib->keys.erase(sib->keys.begin());
    if (!cur->leaf) {
        cur->children.push_back(sib->children[0]);
        sib->children.erase(sib->children.begin());
    }
}

当前节点下标idx，向右邻兄弟idx+1借 key：

1. 兄弟第一个分界 key 下沉到当前节点尾部
2. 父节点原分界值替换为兄弟第一个 key
3. 兄弟删除头部 key
4. 非叶子节点同步迁移兄弟最左侧子树到当前节点尾部

4. merge(BNode* parent, int idx) 节点合并

void merge(BNode* parent, int idx) {
    BNode* left = parent->children[idx];
    BNode* right = parent->children[idx + 1];
    int sep = parent->keys[idx];

    left->keys.push_back(sep);
    left->keys.insert(left->keys.end(), right->keys.begin(), right->keys.end());
    if (!left->leaf) {
        left->children.insert(left->children.end(), right->children.begin(), right->children.end());
    }
    delete right;
    parent->keys.erase(parent->keys.begin() + idx);
    parent->children.erase(parent->children.begin() + idx + 1);
}

左右两个子节点容量都不足，无法借键，执行合并：

1. 左节点 = parent->children[idx]，右节点 = parent->children[idx+1]，分隔键sep = parent->keys[idx]
2. 左节点尾部追加分隔键 sep，再追加右节点全部 key
3. 非叶子节点同步合并右节点所有子指针到左节点
4. 删除右节点内存
5. 父节点删除分隔键，删除右子节点指针

5. fix_underflow(BNode* node, vector<pair<BNode*, int>>& stack) 欠载修复主逻辑

void fix_underflow(BNode* node, vector<pair<BNode*, int>>& stack) {
    while (node != root && (int)node->keys.size() < min_keys) {
        pair<BNode*, int> item = stack.back();
        stack.pop_back();
        BNode* parent = item.first;
        int idx = item.second;

        BNode* left_sib = (idx > 0) ? parent->children[idx - 1] : nullptr;
        BNode* right_sib = ((size_t)(idx + 1) < parent->children.size()) ? parent->children[idx + 1] : nullptr;

        bool left_ok = (left_sib != nullptr) && ((int)left_sib->keys.size() > min_keys);
        bool right_ok = (right_sib != nullptr) && ((int)right_sib->keys.size() > min_keys);

        if (left_ok) {
            borrow_left(parent, idx);
            break;
        } else if (right_ok) {
            borrow_right(parent, idx);
            break;
        } else if (left_sib) {
            merge(parent, idx - 1);
        } else {
            merge(parent, idx);
        }
        node = parent;
    }
    if (root->keys.empty() && !root->children.empty()) {
        BNode* new_root = root->children[0];
        delete root;
        root = new_root;
    }
}

删除后节点 key 数量 < min_keys 时调用，自下而上修复： 循环条件：当前节点不是根，且关键字不足下限

1. 取出栈内父节点与当前子树下标
2. 判断左右兄弟是否有富余 key（key 数量 > min_keys）
   • 左兄弟富余：borrow_left借键，修复完成退出循环
   • 右兄弟富余：borrow_right借键，修复完成退出循环
   • 两边都无富余：执行merge合并节点
3. 将父节点设为当前节点，继续循环判断上层是否欠载 循环结束后特殊处理根节点： 若根无关键字、但存在子节点，将第一个子节点设为新根，释放旧根内存。

6. void del(int key) 删除主函数

void del(int key) {
    vector<pair<BNode*, int>> stack;
    BNode* cur = root;
    int pos;
    while (true) {
        pos = lower_bound(cur->keys.begin(), cur->keys.end(), key) - cur->keys.begin();
        if ((size_t)pos < cur->keys.size() && cur->keys[pos] == key) break;
        if (cur->leaf) { cout << "不存在\n"; return; }
        stack.emplace_back(cur, pos);
        cur = cur->children[pos];
    }
    if (cur->leaf) {
        remove_from_leaf(cur, key);
    } else {
        int pred = get_pred(cur, pos);
        cur->keys[pos] = pred;
        stack.emplace_back(cur, pos);
        cur = cur->children[pos];
        remove_from_leaf(cur, pred);
    }
    fix_underflow(cur, stack);
}

执行完整流程：

1. 栈记录向下遍历路径，循环查找待删除 key 所在节点
2. 分两种删除场景：
   • 场景 1：key 在叶子节点：直接remove_from_leaf删除
   • 场景 2：key 在非叶子节点：取左子树最大值 pred 替换当前 key，再去叶子删除 pred
3. 调用fix_underflow自下而上修复节点欠载、借键、合并。

（五）四大遍历函数

1. 中序遍历 inorder(BNode* n, vector<int>& res)

void inorder(BNode* n, vector<int>& res) {
    if (!n) return;
    // 非叶子节点才递归子节点
    if (!n->leaf)
    {
        for (int i = 0; (size_t)i < n->keys.size(); i++)
        {
            inorder(n->children[i], res);
            res.push_back(n->keys[i]);
        }
        // 最后一个子节点
        inorder(n->children.back(), res);
    }
    else
    {
        // 叶子节点直接输出所有key，不访问children
        for (int k : n->keys)
            res.push_back(k);
    }
}
vector<int> traversal_in() {
    vector<int> r;
    inorder(root, r);
    return r;
}

B 树中序遍历结果严格升序（核心特性） 递归规则：

1. 非叶子节点： 依次递归子树 i → 存入 keys [i]，最后递归最右子树
2. 叶子节点：直接把所有 key 存入结果，无子树 输出：全局有序序列。

2. 前序遍历 preorder(BNode* n, vector<int>& res)

void preorder(BNode* n, vector<int>& res) {
    if (!n) return;
    res.insert(res.end(), n->keys.begin(), n->keys.end());
    for (auto c : n->children) preorder(c, res);
}
vector<int> traversal_pre() {
    vector<int> r; preorder(root, r); return r;
}

先访问当前节点全部 key，再依次递归所有子节点。

3. 后序遍历 postorder(BNode* n, vector<int>& res)

void postorder(BNode* n, vector<int>& res) {
    if (!n) return;
    for (auto c : n->children) postorder(c, res);
    res.insert(res.end(), n->keys.begin(), n->keys.end());
}
vector<int> traversal_post() {
    vector<int> r; postorder(root, r); return r;
}

先递归全部子节点，再存入当前节点所有 key。

4. 层序遍历 traversal_level()

vector<int> traversal_level() {
    vector<int> r;
    queue<BNode*> q; q.push(root);
    while (!q.empty()) {
        auto u = q.front(); q.pop();
        r.insert(r.end(), u->keys.begin(), u->keys.end());
        for (auto c : u->children) q.push(c);
    }
    return r;
}

使用队列queue<BNode*>实现广度优先：

1. 根节点入队
2. 循环取出队首节点，存入所有 key
3. 把该节点所有子节点依次入队 输出：从上到下、每层从左到右的节点关键字。

（六）C++完整代码参考地址与运行结果完整展示

1.参考地址

GitCode：B-Tree-Visualizer/btree.cpp-代码预览-B-Tree-Visualizer:基于 Python+Tkinter+Matplotlib 的 B-树/B+/B*树可视化工具项目 - AtomGit

GitHub：B-Tree-Visualizer/btree.cpp at main · hongyuxu0/B-Tree-Visualizer · GitHub

2.运行结果完整展示

五、B 树为什么适合做磁盘索引？（底层核心原理）

1. 减少磁盘 IO 次数 磁盘读写速度比内存慢上万倍，IO 是性能瓶颈；B 树单节点存大量索引，树高极低，百万数据仅 3~4 次磁盘读取。
2. 磁盘页对齐设计 操作系统磁盘按「页」读写（通常 4KB/8KB），B 树一个节点刚好占一页，一次 IO 读完一整组索引，无碎片读取。
3. 天然平衡，无退化风险 普通二叉树顺序插入会退化成链表，IO 暴增；B 树强制所有叶子同一高度，查询性能稳定无最坏情况。

六、完整实操示例：4 阶 Base-0 B 树 插入全过程

初始空树，依次插入：5,15,25,35,45,10

1.插入 5、15、25：根节点[5,15,25]（3key，4 阶上限）

2.插入 35：节点溢出，mid=25 上移，分裂： 根[25]，左叶子[5,15]，右叶子[35]

3.插入 45：右叶子[35,45]，未达上限，直接插入

4.插入 10：左叶子[5,10,15]，无溢出，稳定。最终树结构：

再插入 8，左叶子[5,8,10,15]满，分裂，mid=10 上移到根：

七、高频面试考点总结

1. m 阶 B 树叶子节点层数完全一致，绝对平衡；
2. 根节点子节点数特殊，其余节点有上下限；
3. 插入只在叶子，溢出向上递归分裂；
4. 删除欠载优先借 key，无 key 则合并，向上递归修正；
5. B 树每个 key 都带数据，B + 树只有叶子带数据；
6. 数据库不用 B 树而用 B + 树：范围查询、全表扫描效率碾压 B 树。

八、总结

本文系统介绍了B树的核心概念与实现原理。B树是一种多路平衡查找树，专为磁盘IO优化设计，通过节点存储多个索引大幅减少磁盘访问次数。文章详细解析了B树的阶数定义、节点结构、四大核心操作（查找/插入/删除/分裂合并）及其C++实现，包括基础结构体、查询函数、插入模块、删除模块和遍历函数。重点阐述了B树适合作为磁盘索引的底层原理：减少IO次数、磁盘页对齐设计和天然平衡特性。通过4阶B树的完整插入示例演示了实际操作过程，并总结了B树与B+树的区别及面试高频考点。B树凭借其稳定的查询性能和高效的磁盘利用率，成为数据库和文件系统索引的理想选择。