营口市网站建设_网站建设公司_小程序网站_seo优化-安康市网站建设公司

前言

在数据结构的世界里，“搜索” 是永恒的核心命题。当我们面对几十条、几百条数据时，顺序查找的 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 - 树的诞生

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

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

为了解决这些问题，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 树，可以是空树或者满足以下所有性质的树：

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

插入位置必在叶子节点：B 树的插入操作只能在叶子节点进行，这是为了保证所有叶子节点在同一层，避免破坏树的平衡性；
插入后检测节点合法性：插入关键字后，若节点的关键字个数 n < m-1（3 阶 B 树中 m-1=2，即 n≤2），则插入成功；若 n = m-1（即节点满了），则需要对节点进行分裂；
分裂后向上传递：节点分裂后，中间的关键字需要向上插入到父节点中，若父节点也满了，则继续分裂，直到根节点（根节点分裂后会生成新的根节点，树的高度加 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，需要分裂）；
分裂流程（核心步骤）：
找到节点的中间位置：3 阶 B 树的中间位置为 mid = (m-1)/2 = 1（索引从 0 开始），中间关键字为 75；
创建新节点，将中间位置右侧的关键字（139）和对应的子节点指针（此处无子节点）搬移到新节点中；
将中间关键字（75）向上插入到父节点中（此时父节点为空，所以 75 成为新的根节点）；
建立新根节点与原节点（[53]）、新节点（[139]）的父子关系。
分裂后的树结构：

[75] / \ [53] [139]

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

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

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

3.3 插入过程总结

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

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

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

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

4.1 设计思路

节点结构设计：每个节点需要存储关键字数组、子节点指针数组、父节点指针和有效关键字个数；
查找功能实现：提供Find函数，查找目标关键字的位置，若未找到则返回其应插入的叶子节点和插入索引；
插入关键字辅助函数：提供_InsertKey函数，在指定节点的指定位置插入关键字和对应的子节点指针；
插入主函数：实现 “查找→插入→检测→分裂→向上传递” 的完整流程；
验证函数：通过中序遍历验证 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; } } }

关键步骤解析：

树为空处理：直接创建根节点，插入关键字后返回；
查找插入位置：调用 Find 函数找到叶子节点和插入位置，若关键字已存在则返回失败；
插入关键字：调用_InsertKey 函数在叶子节点插入关键字；
节点分裂判断：若插入后节点关键字个数等于 M（满了），则进行分裂；
节点分裂流程：
计算中间位置 mid：对于 m 阶 B 树，mid=(m-1)/2（整数除法）；
创建新节点，将 mid 右侧的关键字和子节点指针搬移到新节点；
更新原节点的有效关键字个数为 mid；
将中间关键字和新节点向上插入到父节点；
根节点分裂处理：若分裂的是根节点，创建新的根节点，插入中间关键字和两个子节点，树的高度加 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 树的核心知识，在未来的开发和面试中脱颖而出！如果你有任何疑问或建议，欢迎在评论区留言交流～

营口市网站建设_网站建设公司_小程序网站_seo优化

目录

前言