【C++数据结构进阶】从磁盘 IO 到亿级检索：B - 树的设计精髓与实现全解析

前言

在数据结构的世界里，“搜索” 是永恒的核心命题。当我们面对几十条、几百条数据时，顺序查找的 O (N) 复杂度或许还能应付，但当数据量飙升到百万、亿级，甚至需要存储在磁盘等外部设备时，传统搜索结构就显得力不从心了。你是否好奇，数据库是如何在海量数据中实现毫秒级检索的？为什么平衡二叉树在磁盘场景下会 “水土不服”？今天，我们就来深入剖析一款专为外部存储优化的王者级数据结构 ——B - 树，带你从原理到代码，彻底搞懂它的设计哲学与实现细节。 在正式进入 B - 树的世界之前，我们先回顾一下常见的搜索结构，看看它们各自的优缺点，以及 B - 树是如何弥补这些缺陷的。下面就让我们正式开始吧！

一、常见的搜索结构：各有千秋却难承重任

在日常开发中，我们接触过多种搜索结构，它们在不同场景下各有表现，但在海量数据的磁盘存储场景中，都暴露出了明显的局限性。

1.1 顺序查找：最简单却最低效

顺序查找是最基础的搜索方式，对数据格式没有任何要求，只需从头到尾逐一比对目标元素。这种方式的时间复杂度是 O (N)，在数据量较小时（比如几十条数据），实现简单、开销小，但当数据量达到万级以上，效率就会急剧下降。想象一下，在一本没有目录的百万页书籍中找一个关键词，顺序查找的低效可想而知。

1.2 二分查找：有序数据的 “快刀”

二分查找要求数据必须是有序的，其核心思想是 “折半缩小范围”，时间复杂度优化到了 O (log₂N)。比如在 100 万条有序数据中查找目标，最多只需 20 次比对就能找到，效率远高于顺序查找。但二分查找的局限性也很明显：一是仅适用于有序数据，插入、删除操作会破坏有序性，维护成本高；二是依赖连续存储空间，无法应对数据量超过内存的场景 —— 当数据存储在磁盘时，二分查找的 “跳跃式访问” 会导致频繁的磁盘 IO，而磁盘 IO 的速度比内存访问慢数百倍，这会让其优势荡然无存。

1.3 二叉搜索树：动态数据的 “双刃剑”

二叉搜索树无需数据预先有序，插入、删除操作可以动态维护树结构，其查找、插入、删除的时间复杂度理论上是 O (log₂N)。但二叉搜索树有一个致命缺陷：结构不平衡。在最坏情况下（比如插入的数据完全有序），二叉搜索树会退化成单链表，此时所有操作的时间复杂度都会退化为 O (N)，性能甚至不如顺序查找。

1.4 平衡二叉树（AVL 树、红黑树）：追求平衡的 “努力家”

为了解决二叉搜索树的不平衡问题，平衡二叉树应运而生。AVL 树通过严格维护 “左右子树高度差不超过 1” 来保证平衡，红黑树则通过颜色规则（红节点的父节点必为黑节点、所有叶子节点到根节点的黑路径长度相同）来维持近似平衡。它们都能将时间复杂度稳定在 O (log₂N)，在内存中的表现十分优秀。

但当数据存储在磁盘时，平衡二叉树的缺陷就暴露无遗了：树的高度过高。平衡二叉树是二叉树，每个节点最多只有两个子节点，树的高度大约是 log₂N。对于 1 亿条数据，树的高度约为 27 层，这意味着一次查找需要进行 27 次磁盘 IO。要知道，磁盘 IO 是非常耗时的操作（一次机械硬盘 IO 约 10ms），27 次 IO 就需要 270ms，这对于追求高并发、低延迟的系统来说，是完全无法接受的。

1.5 哈希表：理想中的 “O (1)” 却暗藏危机

哈希表是一种基于 “键 - 值映射” 的结构，通过哈希函数将关键字映射到对应的存储位置，理想情况下查找、插入、删除的时间复杂度都是 O (1)，效率极高。但哈希表的局限性也不容忽视：

• 哈希冲突难以避免：即使采用优秀的哈希函数，也可能出现多个关键字映射到同一位置的情况，此时需要通过链表法、开放寻址法等方式解决冲突，极端情况下冲突会导致查找时间复杂度退化为 O (N)；
• 不支持范围查询：哈希表的存储是无序的，无法高效地进行 “查找大于 x 且小于 y 的所有数据” 这类范围查询操作；
• 依赖内存空间：哈希表需要连续的内存空间来存储数据，当数据量超过内存时，无法高效扩展。

1.6 痛点总结与 B - 树的诞生

通过对以上搜索结构的分析，我们可以总结出海量磁盘数据存储的核心痛点：

1. 树结构高度过高，导致磁盘 IO 次数过多；
2. 无法高效支持动态插入、删除和范围查询；
3. 极端场景下性能不稳定。

为了解决这些问题，1970 年，R.Bayer 和 E.mccreight 提出了一种适合外部查找的平衡多叉树 ——B 树（有些文献中写作 B - 树，注意不要误读为 “B 减树”）。B 树的核心设计思想是降低树的高度，通过 “多叉” 结构让每个节点存储多个关键字和子节点指针，从而大幅减少树的高度，进而减少磁盘 IO 次数。

对于 1 亿条数据，若采用 100 阶的 B 树，树的高度仅为 3 层（log₅₀1 亿≈3.6），只需 3 次磁盘 IO 就能完成查找，效率提升了近 10 倍！

二、B - 树概念：平衡多叉树的 “黄金法则”

2.1 什么是 B - 树？

B 树是一种平衡的多路搜索树，适用于外部存储设备（如磁盘）。它的 “平衡” 意味着所有叶子节点都在同一层，“多路” 意味着每个节点可以有多个子节点（超过两个）。

官方定义：一棵 m 阶（m>2，m 表示节点最多有 m 个子节点）的 B 树，可以是空树或者满足以下所有性质的树：

1. 根节点的特殊规则：根节点至少有两个子节点（如果树非空），最多有 m 个子节点；
2. 分支节点的结构：每个分支节点包含 k-1 个关键字和 k 个孩子，其中 ceil (m/2) ≤ k ≤ m（ceil 是向上取整函数）。例如 m=3（3 阶 B 树），ceil (3/2)=2，所以每个分支节点的子节点数 k 满足 2≤k≤3，对应的关键字数为 1≤n≤2；
3. 叶子节点的结构：每个叶子节点包含 k-1 个关键字，其中 ceil (m/2) ≤k ≤m（与分支节点的子节点数范围相同），且所有叶子节点都在同一层；
4. 关键字的有序性：每个节点中的关键字从小到大排列，即 K₁<K₂<...<Kₙ（n 为节点中关键字的个数）；
5. 子节点的值域划分：节点中的 k-1 个关键字恰好是 k 个孩子包含的元素的值域划分。若节点的结构为 (A₀,K₁,A₁,K₂,A₂,...,Kₙ,Aₙ)，则：
   • A₀所指子树的所有关键字都小于 K₁；
   • Aᵢ所指子树的所有关键字都大于 Kᵢ且小于 Kᵢ₊₁（1≤i≤n-1）；
   • Aₙ所指子树的所有关键字都大于 Kₙ；
6. 关键字个数限制：每个节点的关键字个数 n 满足 ceil (m/2)-1 ≤n ≤m-1。例如 m=3 时，ceil (3/2)-1=1，m-1=2，所以每个节点的关键字数 n 满足 1≤n≤2。

2.2 B - 树的核心特性解读

（1）“多叉” 是降低高度的关键

B 树通过 “多叉” 结构让每个节点承载更多的关键字和子节点指针，从而大幅降低树的高度。例如，对于 m=1024 的 1024 阶 B 树，每个节点最多可以存储 1023 个关键字和 1024 个子节点指针。此时，树的高度 h 满足：h ≤ log_{ceil (m/2)} N （N 为总关键字数）

对于 N=620 亿个关键字，ceil (1024/2)=512，log₅₁₂620 亿≈log₅₁₂(6.2×10¹⁰)≈log₂(6.2×10¹⁰)/log₂512≈35.8/9≈4，即树的高度仅为 4 层。这意味着，即使是 620 亿条数据，最多只需 4 次磁盘 IO 就能找到目标，这在磁盘存储场景中是革命性的提升。

（2）“平衡” 是保证性能稳定的基石

B 树要求所有叶子节点都在同一层，这意味着从根节点到任何叶子节点的路径长度都相同。这种严格的平衡保证了查找、插入、删除操作的时间复杂度稳定在 O (logₘN)，不会出现类似二叉搜索树的性能退化问题。

（3）节点结构是 “磁盘友好” 的设计

B 树的节点结构（多个关键字 + 多个子节点指针）非常适合磁盘存储。磁盘的读写单位是 “块”（通常为 4KB、8KB），B 树的节点大小可以设计为与磁盘块大小一致，这样每次读取一个节点就只需一次磁盘 IO，最大化利用了磁盘的块存储特性。

2.3 B - 树的节点结构详解

根据 B 树的定义，每个节点的结构可以表示为：(n, A₀, K₁, A₁, K₂, A₂, ..., Kₙ, Aₙ)

其中各部分的含义：

• n：节点中关键字的个数，满足 ceil (m/2)-1 ≤n ≤m-1；
• Kᵢ（1≤i≤n）：关键字，且 K₁<K₂<...<Kₙ；
• Aᵢ（0≤i≤n）：指向子树根节点的指针，且 Aᵢ所指子树的所有关键字都小于 Kᵢ₊₁（Aₙ所指子树的所有关键字都大于 Kₙ）；
• 特别注意：子节点指针的个数永远比关键字个数多 1（n 个关键字对应 n+1 个子节点指针），这是 B 树节点结构的核心特点。

例如，3 阶 B 树的节点（m=3）：

• 关键字个数 n 满足 1≤n≤2（ceil (3/2)-1=1，m-1=2）；
• 子节点指针个数为 n+1，即 2≤Aᵢ个数≤3。

当 n=2 时，节点结构为 (A₀, K₁, A₁, K₂, A₂)，其中：

• A₀子树的关键字 < K₁；
• K₁ < A₁子树的关键字 < K₂；
• A₂子树的关键字 > K₂。

这种结构清晰地划分了子树的关键字值域，为查找和插入操作提供了明确的方向。

三、B - 树的插入分析：从原理到实操（以 3 阶 B 树为例）

B 树的插入操作需要遵循两个核心原则：一是保证插入后关键字有序；二是保证 B 树的所有性质不被破坏（节点关键字个数不超标、所有叶子节点在同一层）。

为了让分析更直观，我们以3 阶 B 树（m=3，每个节点最多 2 个关键字、3 个子节点，最少 1 个关键字、2 个子节点）为例，详细拆解插入过程。插入的序列为：{53, 139, 75, 49, 145, 36, 101}。

3.1 插入的核心规则

1. 插入位置必在叶子节点：B 树的插入操作只能在叶子节点进行，这是为了保证所有叶子节点在同一层，避免破坏树的平衡性；
2. 插入后检测节点合法性：插入关键字后，若节点的关键字个数 n < m-1（3 阶 B 树中 m-1=2，即 n≤2），则插入成功；若 n = m-1（即节点满了），则需要对节点进行分裂；
3. 分裂后向上传递：节点分裂后，中间的关键字需要向上插入到父节点中，若父节点也满了，则继续分裂，直到根节点（根节点分裂后会生成新的根节点，树的高度加 1）。

3.2 分步拆解插入过程

第一步：插入 53（树为空）

• 树为空时，直接创建根节点，将 53 插入到根节点中；
• 此时根节点的关键字个数 n=1（满足 1≤n≤2），插入成功。
• 树的结构：

[53]

第二步：插入 139（根节点未满）

• 从根节点开始查找插入位置：139 > 53，所以插入到 53 的右侧；
• 插入后根节点的关键字为 [53, 139]，n=2（满足最大值限制），插入成功。
• 树的结构：

[53, 139]

第三步：插入 75（根节点满，需要分裂）

• 查找插入位置：75 介于 53 和 139 之间，插入到根节点中，此时根节点的关键字为 [53, 75, 139]，n=3（超过 m-1=2，需要分裂）；
• 分裂流程（核心步骤）：
  1. 找到节点的中间位置：3 阶 B 树的中间位置为 mid = (m-1)/2 = 1（索引从 0 开始），中间关键字为 75；
  2. 创建新节点，将中间位置右侧的关键字（139）和对应的子节点指针（此处无子节点）搬移到新节点中；
  3. 将中间关键字（75）向上插入到父节点中（此时父节点为空，所以 75 成为新的根节点）；
  4. 建立新根节点与原节点（[53]）、新节点（[139]）的父子关系。
• 分裂后的树结构：

        [75]
       /    \
  [53]        [139]

第四步：插入 49 和 145（叶子节点未满）

• 插入 49：
  1. 查找插入位置：从根节点 75 开始，49 <75，进入左子节点 [53]；
  2. 49 <53，插入到 53 的左侧，此时左子节点的关键字为 [49, 53]，n=2（满足限制），插入成功。
• 插入 145：
  1. 查找插入位置：从根节点 75 开始，145 > 75，进入右子节点 [139]；
  2. 145 > 139，插入到 139 的右侧，此时右子节点的关键字为 [139, 145]，n=2（满足限制），插入成功。
• 插入后的树结构：

        [75]
       /    \
[49, 53]    [139, 145]

第五步：插入 36（叶子节点满，分裂后向上插入）

• 查找插入位置：从根节点 75 开始，36 <75，进入左子节点 [49, 53]；
• 36 <49，插入到 49 的左侧，此时左子节点的关键字为 [36, 49, 53]，n=3（超过限制，需要分裂）；
• 分裂左子节点 [36, 49, 53]：
  1. 中间位置 mid=1，中间关键字为 49；
  2. 创建新节点，将中间右侧的关键字（53）搬移到新节点中，原节点剩余关键字 [36]；
  3. 将中间关键字 49 向上插入到父节点 [75] 中；
  4. 父节点插入 49 后，关键字为 [49, 75]，n=2（满足限制），插入成功。
• 插入后的树结构：

        [49, 75]
       /    |    \
  [36]    [53]    [139, 145]

第六步：插入 101（叶子节点满，分裂后父节点也满，继续分裂）

• 查找插入位置：从根节点 [49, 75] 开始，101 > 75，进入右子节点 [139, 145]；
• 101 <139，插入到 139 的左侧，此时右子节点的关键字为 [101, 139, 145]，n=3（超过限制，需要分裂）；
• 分裂右子节点 [101, 139, 145]：
  1. 中间位置 mid=1，中间关键字为 139；
  2. 创建新节点，将中间右侧的关键字（145）搬移到新节点中，原节点剩余关键字 [101]；
  3. 将中间关键字 139 向上插入到父节点 [49, 75] 中；
  4. 父节点插入 139 后，关键字为 [49, 75, 139]，n=3（超过 m-1=2，需要分裂父节点）；
• 分裂父节点（根节点）[49, 75, 139]：
  1. 中间位置 mid=1，中间关键字为 75；
  2. 创建新节点，将中间右侧的关键字（139）搬移到新节点中，原节点剩余关键字 [49]；
  3. 父节点是根节点，分裂后生成新的根节点，将中间关键字 75 插入到新根节点中；
  4. 建立新根节点与原节点（[49]）、新节点（[139]）的父子关系；
  5. 原右子节点分裂后的两个节点 [101] 和 [145]，分别作为新节点 [139] 的左、右子节点。
• 最终的树结构：

            [75]
           /    \
      [49]        [139]
     /    \      /    \
  [36]    [53]  [101]  [145]

3.3 插入过程总结

B 树的插入操作可以概括为 “查找插入位置→插入关键字→检测节点是否满→满则分裂→向上传递中间关键字” 的循环过程，直到满足 B 树的所有性质为止。核心要点是：

1. 插入位置始终在叶子节点，保证叶子节点在同一层；
2. 节点分裂是维持 B 树平衡的关键，分裂后中间关键字向上传递，确保父节点的关键字有序且个数合法；
3. 根节点分裂会导致树的高度加 1，但由于所有叶子节点都在同一层，树的平衡性依然得到保证。

四、B - 树的插入实现：C++ 代码详解

理解了 B 树的插入原理后，我们来动手实现一个通用的 B 树（模板类）。本次实现采用 C++ 语言，支持任意可比较的关键字类型，默认实现 3 阶 B 树（可通过模板参数修改阶数）。

4.1 设计思路

1. 节点结构设计：每个节点需要存储关键字数组、子节点指针数组、父节点指针和有效关键字个数；
2. 查找功能实现：提供 Find 函数，查找目标关键字的位置，若未找到则返回其应插入的叶子节点和插入索引；
3. 插入关键字辅助函数：提供_InsertKey 函数，在指定节点的指定位置插入关键字和对应的子节点指针；
4. 插入主函数：实现 “查找→插入→检测→分裂→向上传递” 的完整流程；
5. 验证函数：通过中序遍历验证 B 树的关键字是否有序（中序遍历结果有序是 B 树插入正确的必要条件）。

4.2 节点结构定义

首先我们要定义 B 树的节点结构，采用模板类实现，模板参数 K 为关键字类型，M 为 B 树的阶数（默认 M=3）。

#include <iostream>
#include <utility>
#include <cassert>
using namespace std;

// 模板参数K：关键字类型，M：B树的阶数（默认3阶）
template<class K, int M = 3>
struct BTreeNode
{
    K _keys[M];                  // 存储关键字，最多M-1个有效关键字
    BTreeNode<K, M>* _pSub[M + 1]; // 存储子节点指针，最多M个，比关键字多1个
    BTreeNode<K, M>* _pParent;   // 父节点指针，分裂时需要向上插入
    size_t _size;                // 当前节点的有效关键字个数

    // 构造函数：初始化所有指针为nullptr，有效关键字个数为0
    BTreeNode()
        : _pParent(nullptr)
        , _size(0)
    {
        for (size_t i = 0; i <= M; ++i)
        {
            _pSub[i] = nullptr;
        }
    }
};

节点结构说明：

• _keys [M]：由于 B 树的每个节点最多有 M-1 个关键字，所以数组大小定义为 M（预留一个位置方便插入时临时存储）；
• _pSub [M+1]：子节点指针数组的大小为 M+1，因为 n 个关键字对应 n+1 个子节点指针，最多 M 个关键字（实际最多 M-1 个有效）对应 M+1 个子节点指针；
• _pParent：父节点指针，用于节点分裂后向上插入中间关键字；
• _size：有效关键字个数，范围为 [ceil (M/2)-1, M-1]。

4.3 B 树类定义

B 树类包含根节点指针，以及查找、插入、中序遍历等核心成员函数。

template<class K, int M = 3>
class BTree
{
    typedef BTreeNode<K, M> Node;
public:
    // 构造函数：初始化根节点为nullptr
    BTree()
        : _pRoot(nullptr)
    {}

    // 插入关键字
    bool Insert(const K& key);

    // 中序遍历（验证B树是否有序）
    void InOrder()
    {
        _InOrder(_pRoot);
        cout << endl;
    }

private:
    // 中序遍历辅助函数（递归实现）
    void _InOrder(Node* pRoot);

    // 查找关键字：返回值为pair<所在节点, 关键字在节点中的索引>，未找到则索引为-1
    pair<Node*, int> Find(const K& key);

    // 在指定节点中插入关键字和对应的子节点指针
    void _InsertKey(Node* pCur, const K& key, Node* pSub);

private:
    Node* _pRoot; // B树的根节点指针
};

4.4 查找功能实现（Find 函数）

Find 函数的功能是查找目标关键字 key：

• 若找到，返回包含该关键字的节点和其在节点中的索引；
• 若未找到，返回该关键字应插入的叶子节点和索引 - 1。

查找过程遵循 B 树的关键字值域划分规则：从根节点开始，在当前节点的关键字数组中顺序查找（也可优化为二分查找），根据比较结果进入对应的子节点，直到找到目标或到达叶子节点。

template<class K, int M>
pair<typename BTree<K, M>::Node*, int> BTree<K, M>::Find(const K& key)
{
    Node* pCur = _pRoot;
    Node* pParent = nullptr;
    size_t i = 0;

    while (pCur)
    {
        i = 0;
        // 在当前节点的关键字中查找，找到则返回
        while (i < pCur->_size)
        {
            if (key == pCur->_keys[i])
            {
                // 找到：返回节点指针和索引i
                return make_pair(pCur, i);
            }
            else if (key < pCur->_keys[i])
            {
                // 关键字小于当前位置的关键字，进入左子节点
                break;
            }
            else
            {
                // 关键字大于当前位置的关键字，继续向右查找
                ++i;
            }
        }

        // 未在当前节点找到，记录父节点，进入第i个子节点
        pParent = pCur;
        pCur = pCur->_pSub[i];
    }

    // 到达叶子节点仍未找到，返回父节点（插入位置）和索引-1
    return make_pair(pParent, -1);
}

查找函数优化：由于节点中的关键字是有序的，当节点的关键字个数较多时（如高阶 B 树），可以将顺序查找改为二分查找，进一步提升查找效率。二分查找版本的实现如下：

// 优化版Find函数（二分查找）
template<class K, int M>
pair<typename BTree<K, M>::Node*, int> BTree<K, M>::Find(const K& key)
{
    Node* pCur = _pRoot;
    Node* pParent = nullptr;

    while (pCur)
    {
        int left = 0;
        int right = pCur->_size - 1;
        int pos = -1;

        // 二分查找当前节点的关键字
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (key == pCur->_keys[mid])
            {
                return make_pair(pCur, mid);
            }
            else if (key < pCur->_keys[mid])
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
                pos = mid; // 记录最后一个小于key的位置
            }
        }

        // 确定进入哪个子节点：pos+1（若pos=-1则进入第0个子节点）
        int i = pos + 1;
        pParent = pCur;
        pCur = pCur->_pSub[i];
    }

    return make_pair(pParent, -1);
}

4.5 插入关键字辅助函数（_InsertKey 函数）

_InsertKey 函数的功能是在指定节点 pCur 的指定位置插入关键字 key 和对应的子节点指针 pSub，插入过程需保持节点内关键字的有序性（类似插入排序）。

template<class K, int M>
void BTree<K, M>::_InsertKey(Node* pCur, const K& key, Node* pSub)
{
    // 从后往前移动元素，为新关键字腾出位置
    int end = pCur->_size - 1;
    while (end >= 0 && key < pCur->_keys[end])
    {
        // 关键字后移
        pCur->_keys[end + 1] = pCur->_keys[end];
        // 子节点指针同步后移（子节点指针比关键字多1个，所以是end+2）
        pCur->_pSub[end + 2] = pCur->_pSub[end + 1];
        --end;
    }

    // 插入新关键字和子节点指针
    pCur->_keys[end + 1] = key;
    pCur->_pSub[end + 2] = pSub;

    // 如果子节点不为空，更新子节点的父节点指针
    if (pSub)
    {
        pSub->_pParent = pCur;
    }

    // 更新节点的有效关键字个数
    ++pCur->_size;
}

函数说明：

• 插入时从节点的末尾开始向前移动元素，直到找到合适的插入位置，确保插入后关键字仍有序；
• 子节点指针需要同步后移，因为子节点指针的个数比关键字多 1 个，所以移动的索引是 end+2；
• 若插入的是分裂后的子节点（pSub 不为空），需要更新 pSub 的父节点指针，使其指向当前节点 pCur。

4.6 插入主函数（Insert 函数）

Insert 函数是 B 树插入操作的核心，需要实现 “查找→插入→检测→分裂→向上传递” 的完整流程。

template<class K, int M>
bool BTree<K, M>::Insert(const K& key)
{
    // 情况1：树为空，直接创建根节点并插入关键字
    if (_pRoot == nullptr)
    {
        _pRoot = new Node;
        _pRoot->_keys[0] = key;
        _pRoot->_size = 1;
        return true;
    }

    // 情况2：树非空，查找插入位置
    pair<Node*, int> ret = Find(key);
    // 关键字已存在，插入失败（B树默认关键字唯一）
    if (ret.second != -1)
    {
        cout << "关键字" << key << "已存在，插入失败！" << endl;
        return false;
    }

    K insertKey = key;       // 待插入的关键字（可能是分裂后的中间关键字）
    Node* insertSub = nullptr; // 待插入的子节点（分裂后的新节点）
    Node* pCur = ret.first;  // 插入位置的叶子节点

    while (true)
    {
        // 插入关键字到当前节点
        _InsertKey(pCur, insertKey, insertSub);

        // 检测当前节点的关键字个数是否合法（n < M-1）
        if (pCur->_size < M)
        {
            // 合法，插入成功
            return true;
        }

        // 节点满了，需要分裂
        // 步骤1：计算中间位置（3阶B树mid=1，5阶B树mid=2，即(m-1)/2）
        int mid = M / 2; // 因为M是阶数，M-1是最大关键字个数，mid=(M-1)/2（整数除法）

        // 步骤2：创建新节点，将中间位置右侧的关键字和子节点指针搬移到新节点
        Node* newNode = new Node;
        size_t j = 0;
        // 搬移关键字：mid+1到pCur->_size-1
        for (size_t i = mid + 1; i < pCur->_size; ++i)
        {
            newNode->_keys[j] = pCur->_keys[i];
            newNode->_pSub[j] = pCur->_pSub[i];

            // 若子节点不为空，更新子节点的父节点为新节点
            if (newNode->_pSub[j])
            {
                newNode->_pSub[j]->_pParent = newNode;
            }

            ++j;
        }
        // 搬移最后一个子节点指针（子节点指针比关键字多1个）
        newNode->_pSub[j] = pCur->_pSub[pCur->_size];
        if (newNode->_pSub[j])
        {
            newNode->_pSub[j]->_pParent = newNode;
        }
        // 更新新节点的有效关键字个数
        newNode->_size = j;

        // 步骤3：更新原节点pCur的有效关键字个数（移除中间及右侧的关键字）
        pCur->_size = mid;

        // 步骤4：将中间关键字和新节点向上插入到父节点
        insertKey = pCur->_keys[mid]; // 中间关键字
        insertSub = newNode;          // 新节点

        // 步骤5：判断当前节点是否为根节点
        if (pCur == _pRoot)
        {
            // 根节点分裂：创建新的根节点，插入中间关键字和两个子节点
            Node* newRoot = new Node;
            newRoot->_keys[0] = insertKey;
            newRoot->_pSub[0] = pCur;
            newRoot->_pSub[1] = newNode;
            newRoot->_size = 1;

            // 更新原节点和新节点的父节点为新根节点
            pCur->_pParent = newRoot;
            newNode->_pParent = newRoot;

            // 更新B树的根节点
            _pRoot = newRoot;
            return true;
        }
        else
        {
            // 非根节点分裂：继续向上插入到父节点
            pCur = pCur->_pParent;
        }
    }
}

关键步骤解析：

1. 树为空处理：直接创建根节点，插入关键字后返回；
2. 查找插入位置：调用 Find 函数找到叶子节点和插入位置，若关键字已存在则返回失败；
3. 插入关键字：调用_InsertKey 函数在叶子节点插入关键字；
4. 节点分裂判断：若插入后节点关键字个数等于 M（满了），则进行分裂；
5. 节点分裂流程：
   • 计算中间位置 mid：对于 m 阶 B 树，mid=(m-1)/2（整数除法）；
   • 创建新节点，将 mid 右侧的关键字和子节点指针搬移到新节点；
   • 更新原节点的有效关键字个数为 mid；
   • 将中间关键字和新节点向上插入到父节点；
6. 根节点分裂处理：若分裂的是根节点，创建新的根节点，插入中间关键字和两个子节点，树的高度加 1。

4.7 中序遍历验证（_InOrder 函数）

B 树的中序遍历结果是有序的（从小到大），因此可以通过中序遍历验证插入操作是否正确。中序遍历的规则是：先遍历第 0 个子节点，再访问第 0 个关键字，接着遍历第 1 个子节点，再访问第 1 个关键字，以此类推，最后遍历第 n 个子节点（n 为有效关键字个数）。

template<class K, int M>
void BTree<K, M>::_InOrder(Node* pRoot)
{
    if (pRoot == nullptr)
    {
        return;
    }

    // 中序遍历：左子树 → 关键字 → 右子树
    for (size_t i = 0; i < pRoot->_size; ++i)
    {
        _InOrder(pRoot->_pSub[i]); // 遍历第i个子节点
        cout << pRoot->_keys[i] << " "; // 访问第i个关键字
    }

    // 遍历最后一个子节点（第size个子节点）
    _InOrder(pRoot->_pSub[pRoot->_size]);
}

4.8 测试代码

为了验证 B 树的插入功能是否正确，我们编写测试代码，插入序列 {53, 139, 75, 49, 145, 36, 101}，并通过中序遍历查看结果是否有序。

int main()
{
    // 定义3阶B树
    BTree<int, 3> btree;

    // 插入测试数据
    int keys[] = {53, 139, 75, 49, 145, 36, 101};
    for (auto key : keys)
    {
        btree.Insert(key);
    }

    // 中序遍历（预期结果：36 49 53 75 101 139 145）
    cout << "B树中序遍历结果：";
    btree.InOrder();

    // 测试插入重复关键字
    btree.Insert(75);

    return 0;
}

4.9 测试结果

运行测试代码后，输出结果如下：

B树中序遍历结果：36 49 53 75 101 139 145 
关键字75已存在，插入失败！

中序遍历结果为有序序列，说明插入操作正确；重复关键字插入失败，符合 B 树的关键字唯一要求。

4.10 代码优化与扩展

（1）支持关键字不唯一

默认实现中 B 树的关键字是唯一的，若需要支持重复关键字，可以修改 Find 函数和 Insert 函数：

• Find 函数：找到关键字后不返回，继续查找直到叶子节点，插入到重复关键字的右侧；
• Insert 函数：移除 “关键字已存在则返回失败” 的判断。

（2）高阶 B 树优化

对于高阶 B 树（如 M=1024），节点的关键字个数较多，_InsertKey 函数中的顺序移动元素会影响效率。可以通过以下方式优化：

• 采用二分查找确定插入位置，减少比较次数；
• 使用数组或 vector 存储关键字和子节点指针，支持高效的插入操作（但 vector 的动态扩容可能带来开销，需权衡）。

（3）磁盘 IO 模拟

在实际应用中，B 树的节点存储在磁盘上，需要模拟磁盘 IO 操作：

• 将节点的大小设计为与磁盘块大小一致（如 4KB）；
• 实现节点的读写函数，将节点数据写入磁盘或从磁盘读取到内存；
• 在 Find 和 Insert 函数中，当访问子节点时，触发磁盘 IO 操作，读取子节点到内存。

总结

B 树作为一种专为外部存储优化的平衡多叉树，其核心优势在于低高度、高平衡、磁盘友好，完美解决了海量数据存储场景下的检索效率问题。 B树的设计充满了智慧，是数据结构与实际应用场景深度结合的典范。希望本文能帮助你彻底掌握 B 树的核心知识，在未来的开发和面试中脱颖而出！如果你有任何疑问或建议，欢迎在评论区留言交流～