B-树：从二叉搜索到多路平衡、磁盘友好的索引结构

在讲平衡二叉树的那一章里，我们认识了 AVL 树和红黑树——它们都在回答同一个问题：怎么让二叉搜索树别退化成一串链表。它们用旋转、用颜色纪律，把树的高度压到了对数级别，从而让增删查都稳在 O(logN)。这一章我们把这些结构统统装回抽屉，问一个更"大"的问题：如果数据量大到根本装不进内存，只能在磁盘上慢慢读，那 logN 次访问还快吗？

答案会出乎你的意料。你会发现，面对磁盘，我们关心的不再是"旋转多少次"，而是"读几次磁盘"。而读一次内存和读一次磁盘的时间差，能差出十万八千里。为了把"读磁盘的次数"降下来，人们情愿牺牲掉一点点"二叉树"的优雅，去拥抱一棵又矮又胖的树——这就是本课的主角：B-树。

先给你一个直觉：普通二叉平衡树是"又高又瘦"——每个节点只存一个关键字、最多两个孩子，所以树很高。而 B-树是"又矮又胖"——每个节点能存一堆关键字、带一堆孩子。同样是装 10 亿个元素，平衡二叉查找树可能要 30 层，而一棵合适的 B-树只要 3、4 层。层数越少，意味着从根一路摸到目标数据时，"穿过磁盘"的次数越少——这就是它存在的全部意义。下面我们一层一层把这棵树剥开。

为什么需要 B-树：内存速度与磁盘 IO 的天壤之别

先说结论：B-树是为"数据只能放在磁盘、需要按索引快速读取"这种场景量身定做的数据结构。要真正理解为什么，得先看清内存和磁盘有多"慢"。

先复习一下咱们讲过的各种搜索结构。假设数据量不是很大，能一次性放进内存，那我们有这么一连串选择：

序号	结构	对数据格式的要求	查找复杂度
1	顺序查找	无要求	O(N)
2	二分查找	数据有序	O(log₂N)
3	二叉搜索树（BST）	无要求（但可能退化成链表）	O(N) 最坏
4	二叉平衡树（AVL 树、红黑树）	无要求	O(log₂N)
5	哈希表	无要求（需哈希函数）	平均 O(1)

注意这句话的条件："数据量相对不是很大，能够一次性存放进内存"。学业里的题目、面试里的小数组，都满足这个前提。可真到现实世界，数据量往往是这个量级：一个千万级用户表、几十亿条订单、上 T 的磁盘数据。内存多大？一个常见服务器内存也就几十到几百 GB，想装下全量数据往往是不现实的——数据只能躺在磁盘上（机械硬盘、SSD，统称外存/磁盘）。

一旦数据在磁盘上，又想要快速搜索某条数据，人们最先想到的办法是：把"关键字 + 该关键字对应数据所在磁盘地址"构建成一棵内存里的搜索树。也就是说，树本身放在内存里（很快），但每个叶子或者说每个记录，得靠它的"磁盘地址"去磁盘里把真正的数据读回来。这样，访问任意一条数据，成本就取决于——沿着树走的时候，要读几次磁盘。

问题来了。前面那张表里所有"优秀"的结构，放在桌面内存里都很威风，可一旦牵扯到磁盘：

平衡二叉搜索树的缺陷：它的高度是 log₂N，这在内存里是毫秒甚至微秒级的事。可是当大树上的每一条边、每一个节点都对应一次磁盘读取时，log₂N 次磁盘访问就太昂贵了。举例：10 亿个节点，log₂N 约等于 30——你要读 30 次磁盘才能定位到叶子。而一次磁盘随机读，机械硬盘大概要 5~~10 毫秒，30 次就是 150~~300 毫秒。对人来说"一眨眼"，对数据库每秒要处理成千上万次查询的场景来说，这是灾难。

哈希表的缺陷：哈希表平均效率 O(1)，看起来很完美。但在某些极端场景下，哈希冲突在某一个桶里堆积严重，访问次数会剧增，同样难以接受。而且哈希表天然无序，做不了范围查询（大于某个值、在某个区间这种），这在追求"索引能走区间扫"的数据库里是个硬伤。

那怎么加速对磁盘上数据的访问？方向就两条：

提高 IO 的速度。SSD 相比机械盘确实快了不少，但归根结底，SSD 随机读也就微秒到毫秒级，相比内存的纳秒级，仍然慢了好几个数量级——并没有本质提升。
降低树的高度。这是真正的破局点。如果能用"多叉树"代替"二叉树"，让每个节点承载更多关键字、更多孩子，树就能在同样的数据量下矮很多。树矮了，从根读到叶子的磁盘访问次数就少了。这就是 B-树的设计哲学。

一句话记牢：在内存场景里我们优化的是"比较次数"，在磁盘场景里我们优化的是"磁盘读取次数"；后者能省就省，因为一次磁盘 IO 顶得上成千上万次内存访问。 为了让"省 IO"到位，二叉树的高度都嫌高，必须上多路。

B-树的出生与"B-树"这个名字里的大坑

学过数据结构的人，几乎都听过 B-树、B+树、B-树、B*树这几个"亲兄弟"。但光是名字就能把人绕晕。先把这个坑填平——B-树和 B+树里的"B"不是用来减号的，这不是"B 减树"。

1970 年，两位计算机科学家 Rudolf Bayer 和 Edward M. McCreight 在著名的 Boeing 公司（波音）工作期间提出了一种适合**外查找（在外存上查找）**的平衡多路搜索树，取名叫 B-tree。这个 "B" 到底是什么缩写，Bayer 本人也没给过权威定论，流传的说法有 balanced（平衡）、broad（宽阔）、bushy（茂密）等等。总之它就是"树"的名字，跟减法毫无关系。

坑在哪？很多中文教材把 B-tree 写成 "B-树"，中间的短横只是"连接号"，表示这是"一棵 B 树"，跟"减号"无关。可一旦写成 "B-树"，初学者就容易读成 "B 减树"（B minus tree），还猜测会不会有个对应的 "B 加树"（B+树，B plus tree），立刻就乱套了。其实 B-树就是 B 树，它读作"B 树"；而 B+树是 B 树的改进版，二者是两个不同的结构（后面 B+树一节专门讲）。至于 B*树，那是 B+树再改进的版本。记住这个名字的脉络，后面的路就顺了。

这里还要顺带决定一个"阶"的口径。"阶"（order）是描述 B-树规模的单位，记作 m。一棵 m 阶的 B-树，可以近似理解为"每个节点最多有 m 个孩子"。注意不同教材对"阶"的定义有细微差别——有的说"m 阶 = 每个节点最多 m 个孩子"，有的说"m 阶 = 每个节点最多 m 个关键字"。咱们用最主流、最贴合课件的一种：m 阶 B-树 = 每个节点最多有 m 个孩子、最多 m-1 个关键字。这个口径后面全篇一致，先钉死它。

B-树的定义：m 阶多路平衡搜索树

所谓 B-树，一套完整的说法是这样：一棵 m 阶（order m）B-树，是一棵平衡的 m 路平衡搜索树，或者是空树，或者满足下面这几条性质。我把每条都拆分解释，因为它比二叉树的规则啰嗦，但每一条都有它的物理意义。

根节点至少有两个孩子。（根如果是叶子则例外，那说明整棵树就一个节点；只要根是非叶，它就至少要有两个孩子。）
每个分支节点的"孩子数" k 满足 ceil(m/2) ≤ k ≤ m。 术语先登场：分支节点也叫非叶节点，就是那些"既有数据又有孩子、起着分岔作用"的中间节点。而 叶子（叶节点） 是"处于最底层的、没有孩子的节点"。ceil 是向上取整函数：ceil(3/2)=2，ceil(4/2)=2，ceil(5/2)=3。这个下界 ceil(m/2) 极其重要——它保证了 B-树不会像普通 BST 那样一路退化成长细的链儿，每个非叶节点再怎么"瘦"，孩子数也够多。
每个分支节点都包含 k-1 个关键字和 k 个孩子，其中 ceil(m/2) ≤ k ≤ m。注意这个"孩子总比关键字多一个"——因为 k 个孩子把区间切成了 k 段，而这 k 段正好由中间的 k-1 个关键字来划分。
每个叶子节点都包含 k-1 个关键字，且同样满足 ceil(m/2) ≤ k ≤ m。也就是说，连叶子也必须有足够的"填充度"，不能随便几个字就放下。
所有的叶子节点都必须在同一层。 这是 B-树的"绝对平衡"——从根到任意一个叶子，经过的层数必须完全一样。这跟 AVL/红黑树那种"近似平衡"不同，B-树要求所有叶子严格对齐到底层，这也是它名字里"平衡"二字的直接体现。
每个节点中的关键字从小到大排列，节点里 k-1 个关键字正好是 k 个孩子所辖元素的值域划分。也就是说，整棵树是一个绝对严格的多路搜索树：左子树全小、右子树全大，只不过一个节点里有多个"分界点"，把区间切成好多段。

把这些性质翻译成人话，一棵 m 阶 B-树就是：每个节点能装一堆有序关键字，孩子比关键字多一个，所有孩子区间有序划分，所有叶子严格同层，而且无论根还是叶都要保持"不低于半满"。 下面用 ASCII 画一棵 3 阶 B-树（也就是常说的 2-3 树，因为 3 阶 = 每个节点最多 3 个孩子、最多 2 个关键字）帮你建立图形直觉：

                    [ 40 ]
                   /       \
            [ 20 ]          [ 60   90 ]
            /    \          /    \     \
         [10]  [30]   [45  55]  [70]  [95]
         (叶子) (叶子)   (叶子) (叶子)  (叶子)

看一下这棵 3 阶 B-树是不是满足所有性质：根节点一个关键字 40（3 阶根允许 1 到 2 个关键字）、两个孩子，OK；非叶节点 [20] 一个关键字两个孩子，[60,90] 两个关键字三个孩子——孩子数在 2 到 3 之间（ceil(3/2)=2 ≤ k ≤ 3），OK；所有叶子都在同一层，OK；每个节点内关键字有序，且孩子的值域划分正确——30 的左孩子（右子树）是 [45 55]（在 40 和 60 之间）、[70] 在 60 到 90 之间、[95] 在 90 之右，全对。这棵树麻雀虽小，五脏俱全。

节点的结构：数组实现一个"小多点"

讲实现之前，必须先说清楚 B-树的一个节点在内存里长什么样。它不像二叉树节点只有 _left/_right 两个指针，而是一个包含"一堆关键字 + 一堆孩子指针"的复合体。

用课件里的定义，一个 m 叉的节点结构是这样的：

┌────────────────────────────────────────────────────┐
│  节点 (可容纳最多 m 个孩子、最多 m-1 个关键字)        │
│                                                    │
│    pSub[0]  pSub[1]  pSub[2] ... pSub[m]  ← m+1 个指针│
│   keys[0]  keys[1]  ... keys[m-1]       ← m 个数据  │
│                                                    │
│   即：一个节点 = 一块"有序的键盒" + 一圈"孩子的抓手"  │
└────────────────────────────────────────────────────┘

有几个细节必须记牢，否则实现必错：

孩子永远比数据多一个。 因为 k-1 个关键字把区间切成 k 段，所以节点里如果有 n 个关键字，就必须配 n+1 个孩子位置。关键字的"位置"和孩子指针的"位置"是这样咬合的：keys[i] 的左孩子是 pSub[i]，右孩子是 pSub[i+1]。也就是说，从 pSub[0] 开始，孩子指针和关键字索引差着一位：pSub[0]、keys[0]、pSub[1]、keys[1]、pSub[2]、keys[2]... 一层叠一层，交互排列。这和你记忆里的"二叉树左孩子右孩子"不一样，是 B-树实现里最容易写串的地方。

配合 parent 指针方便向上回溯。 当节点被插满、触发分裂时，需要把中间关键字"顶"到父节点，父节点可能又满、又要继续顶……这种自底向上的调整，和红黑树的插入很像，都需要频繁往"爸爸、爷爷"那里爬。所以每个节点带一个 _pParent，实现会省掉一大截麻烦。

预备一个"存货"槽位。 注意，虽然 m 阶节点最多装 m-1 个关键字，可我们在实现时通常给"键数组"开 m 位、给孩子数组开 m+1 位。为什么多出来这一位？因为插入的瞬间，关键字会先塞进来，节点暂时变成"满的超载状态"（装到 m 个），我们正是靠这个瞬间的溢出信号，才得以发现"该分裂了"。多留的一个位置，就是为了稳住这个"即将分裂"的中间态，别让它越界。这个"超一存一、满即分裂"的思想，是理解 B-树插入的总钥匙。

把上面的结构落成 C++ 模板，节点定义长这样（M 就是阶）：

#include <iostream>
#include <utility>          // std::pair
using namespace std;
 
// M 阶 B-树的节点模板
template<class K, int M = 3>       // 默认按 3 阶（即 2-3 树）演示
struct BTreeNode
{
    K _keys[M];                     // 关键字数组，开 M 位（多留 1 位容纳"暂满"态）
    BTreeNode<K, M>* _pSub[M + 1];  // 孩子指针数组，比关键字多 1 位
    BTreeNode<K, M>* _pParent;      // 父亲指针，分裂后向上回溯用
    size_t _size;                   // 当前节点里真正用到的关键字个数
 
    // 构造函数：把所有孩子指针初始化为空、个数清零
    BTreeNode()
        : _pParent(nullptr)
        , _size(0)
    {
        for (size_t i = 0; i <= M; ++i)   // 孩子数组有 M+1 个，全部置空
            _pSub[i] = nullptr;
    }
};

再强调一遍这个数组布局的对应关系，因为它贯穿后面的查找、插入、分裂全部代码：_pSub[i] 是 _keys[i] 的左孩子，_pSub[i+1] 是 _keys[i] 的右孩子。 一句话：孩子数组永远比关键字数组"多一位、并且错一位咬合"。

B-树的高度：多路为什么能把树压矮

现在回答最核心的问题：为什么多路就能压矮树高？ 用一句话：因为同一个节点能"装下去"的孩子更多了，所以同层能容纳的节点数以更大的底数爆炸式增长。

推导一下。设一棵 m 阶 B-树有 N 个关键字。回忆性质：每个非叶节点的孩子数介于 ceil(m/2) 和 m 之间。开动脑筋想两个极端：

树最矮的情境：让每个节点都尽量"装满"，也就是每层都用到最多的 m 个孩子。这样层数最少。极端时，高度 h 和 N 的关系大致是 N ≤ m^{h+1} - 1（等比数列求和），反过来 h ≈ log_m N。底数越大，h 越小。
树最高的情境：让每个节点都尽量"保持最瘦"，也就是每层都用最少的 ceil(m/2) 个孩子。这样层数最多。极端时高度 h 大致达到大约 log_{m/2} N。

把这两个极端夹起来，一棵含 N 个关键字、阶为 m 的 B-树，其高度 h 满足：

log_m N   ≤   h   ≤   log_{m/2} N
（装满时最低）    （最瘦时最高）

这里的表述做一点严谨化说明：更严格的下界/上界推导会考虑"根至少两个孩子""非根节点至少有 ceil(m/2) 个孩子"这些细节，最终得到的界是：

h  ≈  log_{ceil(m/2)} (N+1)   到    log_m (N+1)  之间

好，光说数字没感觉，我们来算一个震感很强的例子。假设数据量是 N = 62 × 10^9（620 亿个关键字，这量级在超大数据库中完全存在），如果树是 4 阶二叉树之类，log₂N 高达约 36；而如果我们选用 m = 1024 的 B-树，那么：

h ≤ log_{m/2} N = log_{512} (62 × 10^9)

因为 512³ = 1.34 亿，512⁴ = 687 亿，所以 log_{512}(62 × 10^9) 略小于 4，也就是 h ≤ 4。

结论震撼之处就在这：620 亿个元素，用 1024 阶的 B-树，只要读不超过 4 次磁盘就能定位到目标叶子。 而如果换成二叉平衡树，那要读 36 次磁盘。4 次 vs 36 次，就是"低效索引"和"高效索引"的天壤之别。定位到叶子之后，叶子内部的关键字也就几十到几百个，在内存里二分查找一下，瞬间就找到目标。这就是 B-树在数据库索引领域几乎一统天下的根本原因。

顺带把"为何选多路"这个疑问焊死：多路不是追求什么花哨，而是用"单节点内存里的线性/二分比较"来换取"更少的磁盘 IO"。 节点内比较是内存操作、飞快；磁盘 IO 是外存操作、极慢。两者成本不在一个数量级，所以拼命让每个节点塞更多东西、让树更矮，永远划算。

B-树的查找：沿"值域区间"往下钻

查找是 B-树最基本的操作，理解它，插入也就通了一大半。它本质上和二叉搜索树的查找是一回事，只是"一层"现在是"一个节点"，节点内部有 n 个关键字把孩子分成了 n+1 个值域区间。

这里先把"关键字"一词说透：在 B-树语境里，关键字（key）就是用来排序、索引用作查询依据的那个值，比如用户 id、订单号。实际存储里往往是"关键字 + 对应的记录"（这组叫键值对，key-value pair），B-树的节点里主要是按关键字组织的，真正那条数据要么挂在叶子、要么通过地址引用指向磁盘——这是后话。总之我们要找的就是某个关键字。

查找从根节点出发，对每个节点做这几件事：

在当前节点的关键字数组里，从前往后找到第一个"大于等于目标值"的位置 i。若 _keys[i] == key，恭喜，找到了，直接返回。
若 _keys[i] > key（或已走到头 i == size，说明比这节点所有关键字都大），那么目标一定落在这个节点第 i 个孩子的子树里——因为 keys[i] 的左孩子恰是 pSub[i]（记住这条咬合关系）。
于是向下走到 pSub[i]，重复上述步骤，直到到达空指针（没找到）或命中。

用代码实现查找，它返回两个信息：找到的那个节点 + 关键字在节点里的下标；如果没找到，它返回"目标应该插入的那个节点（必然是叶子）+ 下标 -1"。这么设计是为了插入复用——插入恰恰要找"该往哪个叶子插"。

// 查找 key。
// 返回 pair<所在节点, 关键字下标>，若找到则 second >= 0；
// 若找不到则返回"应插入的叶子节点"且 second == -1（插入逻辑会复用这个位置）
template<class K, int M>
pair<BTreeNode<K, M>*, int> BTree<K, M>::Find(const K& key)
{
    BTreeNode<K, M>* pCur = _pRoot;   // 从根开始找
    BTreeNode<K, M>* pParent = nullptr; // 记录父亲（找不到时用来返回"该插哪"）
    size_t i = 0;
 
    while (pCur)                        // 只要还有节点可走
    {
        i = 0;
        // 在 pCur 这个节点内部线性（或二分）扫描关键字
        while (i < pCur->_size)
        {
            if (key == pCur->_keys[i])          // 命中了第 i 个关键字
                return make_pair(pCur, (int)i); // 返回节点和下标
            else if (key < pCur->_keys[i])      // 该关键字比目标大
                break;                          // 应落在它左侧的孩子里，跳出内层循环
            else
                ++i;                            // 继续往右扫下一个关键字
        }
        // 走到这说明节点里没命中，落点应是第 i 个孩子（keys[i] 的左孩子 = pSub[i]）
        pParent = pCur;                 // 记录当前节点为父亲
        pCur = pCur->_pSub[i];          // 下钻到第 i 个孩子的子树
    }
    // 找到空指针了，说明 key 不存在
    return make_pair(pParent, -1);      // 返回父亲节点和 -1，表示"应插入到 parent"
}

查找的复杂度：沿着高度 h 一路下钻，每层在一个节点内部做一次查找。节点内部关键字个数最多 m-1，可在内存里用二分得到 O(log m)；再乘上高度 h，总比较次数大约 O(log m · h)。再用上一节的高度界代入，总次数被夹在 log_m N ~ log_{m/2} N 量级之间——注意这里"次数"其实是"访问的节点数"，而每一次访问一个节点，在磁盘场景下就是一次磁盘 IO。而真正的亮点是：这一步 IO 已经是"定位到节点"的全部成本，节点内部再怎么比都是内存级，几乎免费。

B-树的插入：定位叶片、就地插入、满了就分裂

插入的思路，用一句话概括：新关键字必然落在某个叶子节点上，插进去后如果这个叶子被撑爆了，就把"中间关键字"上提并分裂。 这个"撑爆就分裂、分裂可能一路顶到根"的连锁过程，是 B-树插入的核心难点。

先申明一个关键事实：B-树的数据总是插到叶子上的。 为什么要翻越重重节点专选叶子？因为只有叶子"没挂孩子"（叶子是最后一层），往里塞一个值不需要替身去接管大片的区间；而如果你硬要往某个非叶节点里塞，那个节点的整个孩子顺序和值域划分都会被搅乱，得不偿失。所以标准做法永远是：顺着值域往下，"跌"到目标区间的那个叶子，然后落进去。这也是上面 Find 返回"应插入的叶子节点"的原因。

完整的插入过程，教案式的七步总结：

空树特判：如果树为空，直接 new 一个根节点，把 key 放进去，完事。
找位置：调用 Find(key)；若 key 已存在（返回的 second != -1），按"键唯一"的原则直接返回 false，不插入。
落到叶子：Find 返回的节点 pCur 必为叶子，这就是待插节点。
按插入排序插进去：在 pCur 的关键字数组里，用"从后往前挪、找到第一个比 key 小的位置"的插入排序法，把 key 塞进去。这一步同时可能要在对应位置"挂上"一个额外的孩子指针（通常来自上一层分裂产生的，先按下不表）。
检测是否还满足性质：插完检查 pCur 的有效关键字个数（_size）。如果还小于 m，说明没超载，一切安好，插入成功结束。
如果超载，就要分裂：_size 达到 m（超了，正常最多 m-1），必须分裂。分裂的做法：找出节点里中间位置的关键字（下标 = m/2，这里整除即可），把它"提"上去作父节点的关键字；把中间位置右侧的所有关键字和所有孩子，整体搬进一个新申请的新节点；原节点只保留中间位置左侧的部分；然后，把中间关键字和那个新节点，作为一对"新的 (key, 孩子)"插入到父节点中去——这就回到了第 4 步，继续对父节点做同样的检测（父节点若也因此超载，就继续往上裂）。
一路裂到根：如果分裂"顶"到了根，那就 new 一个新的根节点，让旧根和新分裂出的节点当它的两个孩子、把中间关键字放进新根，插入结束，树长高一层。

这七步里面，第 6 步的"分裂"是全部精妙所在，务必看清。我用一个具体的 3 阶（2-3 树）构建，手把手带你跑一遍经典序列 {53, 139, 75, 49, 145, 36, 101}，把"插满 → 超载 → 分裂 → 上提 → 顶到根"的过程钉进脑子里。

用 {53, 139, 75, 49, 145, 36, 101} 亲手构建一棵 3 阶 B-树

3 阶 B-树：每个节点最多 3 个孩子、最多 2 个关键字；超过 2 个就必须分裂。下面一步一步画。

第 1 步，插 53。 树空，直接作根。

[ 53 ]

第 2 步，插 139。 53 比 139 小，139 落 53 右边；节点里现在 2 个关键字，没满。

[ 53  139 ]

第 3 步，插 75。 75 落在 53 和 139 之间；节点立刻有了 3 个关键字——超载了（超了正常上限 2）。此时触发第一次分裂。3 个关键字是 [53, 75, 139]，中间关键字是 75，把它上提；53 留左侧，139 去右侧共享一个兄弟。整棵树只有这一个节点，它又是根，于是 new 一个新根装 75。图示：

插75超载：     拆开：           新根：
[53 75 139]  →   75(提起来)  →      [ 75 ]
                /        \          /     \
             [53]       [139]     [53]   [139]

注意一个现象：分裂永远是把一个超载节点"噼"成一左一右两个节点，中间关键字交给爸爸。这颗树从 1 层长成了 2 层。

第 4 步，插 49。 49 < 75，走左子树，落进左叶 [53]，于是左叶变成 [49, 53]。最大允许 2 个关键字，没超。

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

第 5 步，插 145。 145 > 75，走右子树，落进右叶 [139]，右叶变 [139, 145]。没超。

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

第 6 步，插 36。 36 < 75，走左子树；左叶是 [49, 53]，36 应落在 49 左边 → [36, 49, 53]，又超载。三个关键字 [36, 49, 53]，中间 49 上提。但这次叶子不是根，所以 49 要被"顶"到它的爸爸（当前根 [75]）里，同时左边 [36] 和新产生的 [53] 挂在 49 之下：

插36超载：        中间49上提：       当前根变：       根不超（2个键），结束
 [36 49 53]      [36] [49] [53]      [ 49  75 ]
                                        /     \
                                     [36]    [53] [139 145]

等等，这里要严谨：49 顶到根后，根的左区间变 -∞~49 挂 [36]、49~75 挂分裂出的 [53]、75~∞ 挂 [139 145]。于是根从 [75] 变成两个孩子 [75] 和新兄弟？不对，得对照值域。根原先是 [75]——一个关键字两个孩子，左边孩子管 -∞~75、右边孩子管 75~∞。49 要顶进根，而 49 属于根的左区间，所以 49 插到根的关键字数组里 75 的左边，根变成 [49, 75]，三个值域区间分别是 -∞~49、49~75、75~∞。原本"左叶子"分裂成了 [36]（管 -∞~~49）和 [53]（管 49~~75），右叶子 [139 145] 管 75~∞。可得中间状态：

第6步之前：
        [ 75 ]
       /      \
   [49 53]   [139 145]

第6步：往左叶插36 → [36 49 53] 超载 → 中间49上提到根 [75]，变 [49 75]，
       左叶裂成 [36] 和 [53]。结果：
          [ 49  75 ]
         /    \      \
     [36]    [53]   [139 145]

根有两个关键字 [49, 75]，没超（上限是 2），OK。

第 7 步，插 101。 101 落在 75 和 139 之间？看根 [49, 75]，101 > 75，进入根的第三个区间（75~∞），到右子树的节点 [139 145]，101 落在 139 左边 → [101, 139, 145]，超载。三键 [101, 139, 145]，中间 139 上提，裂成 [101] 和 [145]。139 要顶回爸爸根 [49, 75]，落 75 右边 → 根变 [49, 75, 139]，又超载，再裂一次：中间 75 上提，裂成 [49] 和 [139]。惨了，这次超载的是根，于是新建一层根挂 75 和两棵子树：

插101后：根 [49 75] 、右叶 [101 139 145]
→ 右叶裂出139上提到根 → 根 [49 75 139] 超载
→ 中间75上提作为新根，裂成左[49] 右[139]
最终：
           [ 75 ]
          /      \
      [ 49 ]    [ 139 ]
      /    \    /    \   \
    [36]  [53][101] [145]      （缺一支，实际是 [36]/[53] 分别在 49 左右）

这里把最终形态的区间关系补齐：新根 [75]，左子树管 -∞~~75（根是 [49]，左孩子 [36] 管 -∞~~49、右孩子 [53] 管 49~~75）；右子树管 75~~∞（根 [139]，左孩子 [101] 管 75~~139、右孩子 [145] 管 139~~∞）。完整图示：

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

你可以核对一遍中序（左-中-右，DFS）：36, 49, 53, 75, 101, 139, 145——严格有序。这说明整棵树是合法且完美的多路平衡搜索树。到此，七个元素全部插入完成，树的每一层都保持了"非根非叶至少 ceil(3/2)=2 个孩子"的性质，所有叶子都在同一层。

这一路下来，你应该已经牢牢抓住 B-树插入的两个"动嘴点"：

只往叶子插，从不往非叶节点塞；
插满（超载）就二分裂，中间关键字上提，裂出来的右兄弟挂上去，然后向父看齐、一路顶到根（根超载就长高一层）。

顺手埋一个"坑"提醒你：在第 6、第 7 步，裂出来的孩子要保持"值域严格在分界点之间"，一旦挂反了，整棵树就成了一条散开的链，中序就不有序了——这是日后你自己写分裂时最容易翻车的地方。

B-树的插入实现（C++ 完整版）

理论讲透了，把它落成能编译运行的 C++。核心是两个函数：_insertKey（把一个值 + 一个孩子塞进某个节点）和 Insert（找叶子、打循环、遇超载就分裂）。我按"可独立运行"的标准把整棵 B-树类写全，最后用上面那个序列 {53, 139, 75, 49, 145, 36, 101} 验证中序有序。

#include <iostream>
#include <utility>          // std::make_pair
using namespace std;
 
// ---------- 节点定义 ----------
template<class K, int M = 3>          // M=阶，默认 3（2-3 树）
struct BTreeNode
{
    K _keys[M];                     // 关键字数组（多留1位容纳"暂满"中间态）
    BTreeNode<K, M>* _pSub[M + 1];  // 孩子指针数组，比关键字多1位、错位咬合
    BTreeNode<K, M>* _pParent;      // 父亲指针，分裂后向上回溯
    size_t _size;                   // 当前有效关键字个数
 
    BTreeNode()
        : _pParent(nullptr), _size(0)
    {
        for (size_t i = 0; i <= M; ++i)   // 初始化全部孩子为空
            _pSub[i] = nullptr;
    }
};
 
// ---------- B-树类 ----------
template<class K, int M = 3>
class BTree
{
    typedef BTreeNode<K, M> Node;
 
public:
    BTree() : _pRoot(nullptr) {}
 
    ~BTree()                       // 析构回收所有结点，防止内存泄漏
    {
        destroy(_pRoot);
    }
 
    // 查找：命中返回(节点,下标)且下标>=0；未命中返回(目标叶子, -1)
    pair<Node*, int> 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])
                    return make_pair(pCur, (int)i);  // 命中
                else if (key < pCur->_keys[i])
                    break;                            // 应落到 i 号孩子的子树
                else
                    ++i;
            }
            pParent = pCur;               // 记录父母
            pCur = pCur->_pSub[i];        // 下钻：keys[i] 的左孩子是 pSub[i]
        }
        return make_pair(pParent, -1);    // 叶子 + -1，留给插入复用
    }
 
    // 把一个新的 (关键字, 右孩子指针) 按插入排序塞进 pCur 节点
    void _insertKey(Node* pCur, const K& key, Node* pSub)
    {
        int end = (int)pCur->_size - 1;      // 从最后一个关键字往前找插入点
        while (end >= 0 && key < pCur->_keys[end])
        {
            // 把更大的关键字及它的右孩子整体右移一位，腾出空位
            pCur->_keys[end + 1] = pCur->_keys[end];
            pCur->_pSub[end + 2] = pCur->_pSub[end + 1];
            --end;
        }
        // 落位：关键字插到 end+1，右孩子插到 end+2（咬合关系）
        pCur->_keys[end + 1] = key;
        pCur->_pSub[end + 2] = pSub;
        if (pSub)                          // 若带了分裂出的孩子，维护它的父亲指针
            pSub->_pParent = pCur;
        ++pCur->_size;                     // 有效关键字数 +1
    }
 
    // 插入一个关键字（约定 key 唯一）。成功返回 true，已存在返回 false
    bool Insert(const K& key)
    {
        // 空树：直接造一个根
        if (_pRoot == nullptr)
        {
            _pRoot = new Node;
            _pRoot->_keys[0] = key;
            _pRoot->_size = 1;
            return true;
        }
 
        // 定位插入位置 / 查重
        pair<Node*, int> ret = Find(key);
        if (ret.second != -1)              // 已存在则拒绝重复插入
            return false;
 
        K    k    = key;       // k 为待插入的关键字（分裂时会被替换成向上顶的中间键）
        Node* pSub = nullptr;  // pSub 为伴随该关键字一起插入的孩子（分裂产物）
        Node* pCur = ret.first;// 目标叶子节点
 
        // 自叶子向上打循环：插一次、检查一次，超载就裂，裂完向上继续
        while (true)
        {
            _insertKey(pCur, k, pSub);     // 1) 把 (k, pSub) 塞进当前节点
 
            if (pCur->_size < M)           // 2) 没超载：性质满足，直接成功
                return true;
 
            // 3) 超载（size == M），必须分裂
            Node* temp = new Node;         // 申请右兄弟
            int mid = (M >> 1);            // 中间位置下标（整除）
 
            // 4) 把中间位置右侧的关键字连同孩子搬进 temp
            for (size_t i = mid + 1; i < pCur->_size; ++i)
            {
                // 一次搬一对：关键字 keys[i] 及它的左孩子 pSub[i]（咬合关系）
                temp->_keys[temp->_size] = pCur->_keys[i];
                temp->_pSub[temp->_size] = pCur->_pSub[i];
                if (pCur->_pSub[i])                       // 维护孩子被搬走后的父亲
                    pCur->_pSub[i]->_pParent = temp;
                ++temp->_size;
            }
            // 5) 孩子比关键字多搬移一个：把最右孩子（原节点最后一个孩子的右孩子）也搬给 temp
            temp->_pSub[temp->_size] = pCur->_pSub[pCur->_size];
            if (pCur->_pSub[pCur->_size])
                pCur->_pSub[pCur->_size]->_pParent = temp;
 
            // 6) 先取出要上提的中间关键字
            //    注意顺序：此下标 mid 在下面收缩节点 size 之后就会"逻辑越界"，
            //    所以必须现在就读走，不能等到 size 变小后再读
            K kk = pCur->_keys[mid];
 
            // 7) 再让原节点收缩：只保留中间键左侧的 size 个关键字
            //    （右侧已搬走 temp，中间键被取走上提，所以再减一个）
            pCur->_size -= (temp->_size + 1);
 
            // 8) 若裂的是根：新建一层根，装中间键 + 旧根 + 新兄弟
            if (pCur == _pRoot)
            {
                _pRoot = new Node;
                _pRoot->_keys[0] = kk;
                _pRoot->_pSub[0] = pCur;   // 旧（左）根作新根左孩子
                _pRoot->_pSub[1] = temp;   // 新兄弟作新根右孩子
                _pRoot->_size = 1;
                pCur->_pParent = _pRoot;
                temp->_pParent = _pRoot;
                return true;               // 到根为止，结束
            }
            else
            {
                // 9) 裂的不是根：把中间键 + 新兄弟继续塞给父节点，循环回到第1步
                k    = kk;      // 上提的中间键
                pSub = temp;    // 新分裂出来的右兄弟
                pCur = pCur->_pParent;     // 上移到父节点
            }
        }
    }
 
    // 中序遍历：如果得到有序序列，说明插入正确、树是合法的 B-树
    void InOrder()
    {
        inOrder(_pRoot);
        cout << endl;
    }
 
    void destroy(Node* r)        // 递归释放整棵树
    {
        if (!r) return;
        for (size_t i = 0; i <= r->_size; ++i)   // 每个孩子都递归删
            destroy(r->_pSub[i]);
        delete r;
    }
 
    void inOrder(Node* r)        // 中序：孩子、关键字、孩子、关键字……交替访问
    {
        if (!r) return;
        for (size_t i = 0; i < r->_size; ++i)
        {
            inOrder(r->_pSub[i]);        // 先把第 i 个孩子的区间打完
            cout << r->_keys[i] << ' ';  // 再打第 i 个关键字
        }
        inOrder(r->_pSub[r->_size]);     // 最后还有个最右孩子
    }
 
private:
    Node* _pRoot;
};
 
// ---------- 验证 ----------
int main()
{
    BTree<int, 3> t;                 // 3 阶 B-树（2-3 树）
    int a[] = {53, 139, 75, 49, 145, 36, 101};
 
    for (int e : a)
    {
        t.Insert(e);
        cout << "插入 " << e << endl;
    }
 
    cout << "\n中序遍历结果: ";
    t.InOrder();                     // 期望严格有序：36 49 53 75 101 139 145
    cout << "\n若序列严格递增，说明分裂与上提均正确，树合法。\n";
 
    // 查重：已存在的 key 再插应返回 false 且不破坏结构
    cout << "再次插入 75 应失败(false): "
         << (t.Insert(75) ? "true" : "false") << endl;
    cout << "再次插入 7（不存在）应成功(true): "
         << (t.Insert(7) ? "true" : "false") << endl;
    cout << "插入 7 后中序: ";
    t.InOrder();                     // 期待：7 36 49 53 75 101 139 145
    return 0;
}

把这段存成 btree.cpp，用 g++ -std=c++11 btree.cpp -o btree && ./btree 编译运行，你会看到中序严格有序的输出 36 49 53 75 101 139 145——样例序列一次性跑通。这套实现里几个"最容易写错"的角落，我拎出来给你敲黑板：

角落一：孩子数组和关键字数组的错位咬合。 分裂搬移时，temp->_pSub[temp->_size] = pCur->_pSub[i] 搬的是 keys[i] 的左孩子；循环结束后，temp->_pSub[temp->_size] = pCur->_pSub[pCur->_size] 搬的才是最右那个孩子。务必记得"孩子比关键字多搬一个"，漏了最后这一句，右兄弟就少一条子树，中序立刻断掉。

角落二：pCur->_size -= (temp->_size + 1) 里的那个 +1。 因为中间那个关键字被"提走"给父节点了，所以原节点不仅少了 temp 的那些右半，还要多减一个（送出去的中间键）。少这个 +1，原节点就会多算一个关键字，整棵树的分裂计数就全乱了。

角落三：必须先"取中间键"，再"收缩节点 size"。 顺序不能颠倒。原因是：中间键要读的是 pCur->_keys[mid]，而一旦执行 pCur->_size -= (temp->_size + 1) 把 size 缩到 mid，下标 mid 就超过了新的 size-1，变成逻辑越界（数组里虽然还残留着那个值，但已不属于"有效范围"）。所以正确姿势是把 K kk = pCur->_keys[mid]; 放在收缩 size 之前，先把它读走，再去动 size——代码里就是这么排的，别为了省一行把顺序写反，那是典型的越界隐患。

角落四：根节点要不要长高。 只有当"被分裂的节点恰好是根"时，才需要 new 一个新根来装中间键、并把旧根和新兄弟挂到它身下。非根节点分裂，绝不动根，只是把中间键向上抛，让 while 循环在父节点继续"插一查一裂一"。判断 pCur == _pRoot 的时机要准确，否则会出现"多个根"或"根长期不更新"的怪病。

B-树的删除：借位与合并（思路版）

插入讲透了，足以理解 B-树的精髓。但一个数据结构只说插入不说删除，总觉得欠点什么。删除偶尔会考，尤其是"借位"和"合并"这对概念，这里给足思路（完整伪代码可参考《算法导论》的红黑树 & B-树章节，或《数据结构（C++语言版）》内部）。要提醒的是：B-树的删除比插入更麻烦，因为"删掉一个关键字"可能让一个节点跌破"至少 ceil(m/2)-1 个关键字"的下限，必须想办法补救。

删除分两类情况：

其一，删的是叶子里的关键字。 直接删掉它。删完该叶子关键字个数还 ≥ ceil(m/2)-1（不低于半满），那万事大吉；如果跌破了半满，就要处理"下溢"。

其二，删的是非叶（分支）节点里的关键字。 不能直接删——那个节点还有孩子区间需要这个分界点来划分。标准做法是用它的"前驱"或"后继"来顶上：前驱 = 左子树里最大的关键字，后继 = 右子树里最小的关键字。它俩由于位于"树的最左边/最右边"，必然存在于某个叶子里。于是"删非叶关键字"被巧妙地**转化成了"删一个叶子关键字"**再套情况一。

真正棘手的，是删完叶子跌破半满时的两种补救：

借位（borrow）：看它的左兄弟或右兄弟有没有"富余"（兄弟的关键字个数 > ceil(m/2)-1）。若有，就从父节点"拨下来"一个关键字补给自己，再从富余兄弟"顶上去"一个关键字还给父节点。留意这里有个细节：父子之间借还关键字时，兄弟那边还要顺带"让"一个孩子指针过来（因为关键字在父子和兄弟间流转时，值域区间变了，孩子区间也要跟着迁位）。
合并（merge）：如果左、右兄弟也全都不足半满（每个都刚到下限），谁也借不出，那就把它和兄弟合并成一个节点，中间那个父节点里的分隔关键字也被"拉下来"一起并入。合并后，父节点的关键字个数通常减 1，若父节点因此又跌破半满，就继续向上递归借位或合并——最坏一路合并到根。若根只剩一个关键字且两个子合并成一个，根就"下沉"一层，树变矮。

小结一下删除的骨架：删叶子/借前驱后继 → 若下溢 → 先看兄弟能否借、能借就借；借不到就与兄弟合并（顺带吃掉父亲的隔断键）→ 若父亲因此下溢，再递归上探。 这套"借黑还黑、下沉上探"的思想，和你学过的红黑树删除那套"借黑 + 上抛"其实是镜像关系，一通百通。

边界与坑：满时分裂、偶数阶、2-3 树特例、为何多路

把容易踩的坑集中排一遍雷，这节的价值在于"防患于未然"。

坑一：节点满时一定要"先插后验再裂"。 插入前节点已经满（有 m-1 个关键字），只要再插一个就超载到 m 个。很多人图省事，先在代码里现造一个"先检查满了就直接走分裂"的分支，结果要么漏了中间态、要么把分裂写成了"先裂后插"，顺序一倒，值域和指针全乱。正确姿势就是课件与上面实现那样：无论满不满，一律先插入、再检查 _size 是否达到 m，达到才裂。用"插入瞬间超载"作为分裂的触发信号，是最稳的做法。

坑二：偶数阶的中位取整。 中间位置用 mid = M >> 1（整除）。当 M 是奇数（如 3、5），m/2 正好落在中央，左右基本对称；当 M 是偶数（如 4），m/2 偏左一点点，分裂后左多右少，但只要仍然满足"每个分支节点关键字在 ceil(m/2)-1 到 m-1 之间"，就是合法 B-树。别追求"绝对对称"，B-树的定义本来就不要求左右等分，它只要求（接近）半满。

坑三：2-3 树就是 3 阶 B-树，是"最瘦的特例"。 当阶 m=3，孩子数合法区间是 ceil(3/2)=2 到 3，所以每个非根节点要么 2 个孩子要么 3 个孩子——于是它得名 2-3 树。它是最小的 B-树特例，也是几乎所有教科书用来演示分裂的首选（因为分裂只有一种形态：2 满再插就裂成 1+1，中间键上提）。理解了 2-3 树的分裂，遇到大阶 B-树只是"每个节点能装的变多"，逻辑完全一致。同理 m=4 就叫 2-3-4 树，m 阶 B-树可以叫 2-3-4-…-m 树。

坑四：合并与借位的范围判断要小心"边界情形"。 借位时左、右兄弟都可能不存在（自己是父的最左/最右孩子），要先判空；合并时要把父节点那个分隔键拿下来一起合并，父节点关键字数 -1，别忘了向上递归。这些边角（第一个孩子、最后一个孩子）是最容易写出段错误的。

坑五："为何多路足够、不用无限多路"。 你可能想，那我把阶调得越来越大，孩子越来越多，不就更矮？别急，有个反噬：节点越大，一个节点占的磁盘空间越大，而磁盘 IO 是按"块/页"整块读的。若一个节点大过一块磁盘块，读它就要跨多块，反而慢；若一味加阶，节点内二分查找虽快，但"把一个节点从磁盘搬进内存"的字节数变多，也无谓。所以实际系统里的阶，是按"让一个节点正好占满一个磁盘页"来定的，不是越大越好。像 MySQL 的 InnoDB 默认一页 16KB，一个 B+树节点就约等于一页。这个话题后面讲应用时还会碰到。

B+树：把"数据层"和"索引层"分家的升级

B-树性能已经很能打，可数据库/文件系统的索引却几乎清一色用 B+树。为什么？因为它把 B-树的几个短板给修了。先看 B+树在 B-树基础上改的四点：

有 n 棵子树的中间节点只保存 n 个关键字——也就是说，分支节点的关键字个数和孩子个数现在相等（不再是"孩子比关键字多一个"）。这是结构上的第一大变化。
分支节点的孩子指针 p[i] 指向的关键字值落在区间 [k[i], k[i+1]) 之间（左闭右开），划分方式比 B-树更规整。
所有叶子节点增加一个链接指针，串成一个有序链表。
所有关键字及其映射的真实数据，统统只出现在叶子节点上。

这四条一改，B+树就有了三个 B-树没有的先天优势：

优势一：分支节点纯当"路标"，真正的数据全在叶子。 所有查询（无论命中与否）都必须走到叶子那一层，而且单词查找是不可能在分支节点就停下的——因为分支节点根本没存数据。这样设计带来的直接好处是：分支（内部）节点可以做得更"轻"，每个节点能塞更多路标，树更矮、IO 更少。

优势二：叶子用链表串起来，范围查询直接"顺着扫"。 这在数据库里太重要了。你要查"id 在 100 到 500 之间的所有记录"，B+树先定位到第一条，然后沿着叶子之间的链表一路右扫即可，不需要回跳父节点重新 DFS。而普通 B-树做范围扫要多次在父子节点间跳转、重复访问祖先，IO 浪费明显。

优势三：分支节点容量利用率更高。 因为分支节点只存关键字不出数据，同样的磁盘页能容纳更多关键字，树的扇出更高、更矮。

把 B-树的架构和 B+树的架构放一起看，差别一目了然：

B-树（分支节点也带数据, 数据可能"提前命中"）：
        [ K1  K2 ]            ← 分支也能带数据，查找可能在此提前命中
       /    |    \
    子1   子2   子3（每棵子树里都有数据，数据分散在所有层）

B+树（数据只活在最后一条"叶子链表"上, 分支纯路标）：
     [K1 K2]  [K3 K4]  ...  ← 内层只有有序的关键字做值域路标
        \      |      /
      [d1 d2][d3 d4][d5 d6]  ← 叶子层才存数据，且用指针串成有序链表
          ◄───── 链表 ─────►

一句话给 B+树定位：分支层是"索引"，叶子层才是"数据层"。所有关键字都出现在叶子链表里，链表节点有序——这是 B+树"全部查询都必须落到叶子"这句话的本质。

还有个常被问的细节：B+树分裂时只影响原节点和父节点，不影响兄弟节点，所以它不需要像 B*树那样维护指向兄弟的指针；而且分裂时从满节点里复制一半数据到新节点（注意是"复制"，原节点里那一半关键字会保留一份作索引，因为分支节点的关键字在叶子里也要完整出现一次）。

B*树：空间利用率更高的 B+树

B*树是 B+树的又一次升级，改动的点很集中：在 B+树的非根、非叶子分支节点上，再额外增加一个指向"兄弟节点"的指针。别小看这一根指针，它带来了本质不同的分裂策略。

B+树分裂：一个节点满时，直接 new 一个全新节点，把原节点一半数据复制过去，最后在父节点追加一个新指针。由于它不影响兄弟节点，所以它不需要指向兄弟的指针。
B*树分裂：当节点满时，先看它的下一个兄弟是否也满了——如果兄弟没满，就把一部分数据移到兄弟里去（注意是"移"，不是"复制"），再在原节点插入新关键字，并顺带更新父节点里那个兄弟的关键字（因为兄弟的值域范围变了）；如果兄弟也满了，就在原节点和兄弟之间再 new 一个新节点，并把 1/3 的数据各复制一份放到新节点，最后在父节点追加新节点指针。

可以看到，B树通过"把飞溅的数据分给邻座兄弟、而不是每次都生拆一个翻倍新节点"的办法，大大降低了"新建节点"的频率，于是——**B树分配新节点的概率比 B+树低，空间利用率更高**（每个节点填充更满，不像 B+树动不动就一半数据被"腾出去"）。代价是实现更复杂、维护兄弟指针的开销更大。

最后把这三兄弟用一句话各定个位，方便记忆：

B-树（B 树）：有序数组 + 平衡多叉树——一个节点一块有序小数组，多路平衡地串起来。
B+树：有序数组链表 + 平衡多叉树——分支存有序数组做索引，叶子串成有序链表放全部数据。
B*树：一棵"更丰满"的、空间利用率更高的 B+树——多了兄弟指针，靠"借邻居分摊"降低新建节点频率。

B-树在数据库索引与文件系统中的应用

讲到这里，你大概已经猜到了——B-树家族最大的舞台就是索引。所谓索引（index），通俗讲就像一本书的目录，或者一个导站的网址导航页，目的只有一个：让你在浩如烟海的数据里，不用一条一条翻，而是直接"翻到"目标那一片。MySQL 官方给索引下过一个很本质的定义：索引（index）就是帮助 MySQL 高效获取数据的数据结构。简单说，索引就是数据结构。 这句话把"索引"的底牌一亮——索引不是什么玄学，它就是一棵（或多棵）精心组织的搜索树。

为什么数据一多就要上数据库、数据库就离不开索引？这里有个连锁逻辑：数据量大了，为了管理方便、查询高效，我们会把数据存进数据库；数据库要高效查询，就必须维护某种支持快速查找的数据结构；这个数据结构以某种方式"引用到"真实数据（要么保存记录的磁盘地址，要么直接保存记录本身），让高级查找算法得以施行——这个被维护的查找结构，就叫索引。 B-树/B+树就是支撑索引最常用的那棵树。

而且要注意一个概念：索引是基于表的，不是基于数据库的。 同一个数据库里不同表可以爱用哪种引擎用哪种，因为索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是截然不同的。我们以 MySQL 的两大明星引擎为例，看 B+树索引在两个引擎里"长"得怎么不一样。

MyISAM：非聚集索引。 MyISAM 在 MySQL 5.5.8 之前是默认引擎，不支持事务，支持全文检索，也用 B+Tree 做索引，但它的一个标志性特征是：索引文件和数据文件是分离的，索引叶节点的 data 域只保存"数据记录的地址"，不保存数据本身。用主键 Col1 建的索引，叶子存的是那条记录的磁盘地址；用别的列（比如 Col2）建辅助索引，结构一模一样，也是一棵 B+Tree，叶子同样只放地址。区别只是主索引要求 key 唯一、辅助索引允许重复。所以 MyISAM 的查询套路是：先用 B+树索引把 key 定位到"地址"，再拿这个地址去磁盘里把真正的记录读出来。因为索引与实际数据分家，它被称为**"非聚集索引"**。

InnoDB：聚集索引。 InnoDB 从 MySQL 5.5.8 开始成为默认引擎，支持事务、面向在线事务处理，它的 B+树索引实现和 MyISAM 截然不同。最震撼的区别是：InnoDB 的"数据文件"本身就是索引文件——表数据是被一棵 B+Tree 直接组织的，叶节点里完整保存着整行数据记录。也就是说不存在"数据和索引分家"这回事，表按主键组织的这棵 B+树，它的叶子就是数据。这种索引叫**"聚集索引"**。

第二个区别随之而来：InnoDB 的主索引 key 是主键。所以 InnoDB 的表必须有主键（MyISAM 可以没有）。如果没有显式指定主键，MySQL 会偷偷挑一个能唯一标识行的列当主键；要是连这样的列都没有，就自动生成一个 6 字节长整型的隐藏主键。而 InnoDB 的辅助索引（非主键列建的索引），它的 data 域存的是对应记录的"主键值"而不是地址——所以辅助索引查数要走两遍：先查辅助索引拿到主键，再拿主键回主索引定位记录（这就是常说的"回表"）。聚集索引带来一个好处是主键搜索极其高效（数据就近集中在主键区间），代价是辅助索引要多检索一遍。

顺带把刚才说的"页/磁盘块"概念落到应用层，收个尾：磁盘 IO 按块读，数据库按页读（InnoDB 默认 16KB）。之所以 B+树索引"一个节点 = 一个页/块"能高效，是因为每次 IO 整块搬进来，恰好填入一个节点，一分不浪费；而节点的"阶"就是在"一个页能塞下多少关键字"这个约束下工程权衡出来的。磁盘块（block）是操作系统/磁盘的最小读写单位，页（page）是数据库的最小存储单位——这两个词一个对外存、一个对引擎，本质都是为了"一次 IO 尽量搬更多有效数据"而设的粒度。这也是为什么"让阶匹配页大小"比"阶越大越好"更科学的根本原因。

思考题与详解答案

为了帮你把这一大篇嚼透、化掉，这里安排几道思考题。每一道我都给出带过程的详解。建议先合上答案自己推一遍，再对照——这样的记忆才牢。

思考题 1：为什么 B-树强调"多路"而不是继续用二叉树？给出一个具体的数量级对比。

详解：二叉树每一层最多容纳"二倍"的数量（满二叉树第 h 层至多 2^h 个节点），所以高度要想低得靠 log₂。而 m 阶 B-树每层人家是"m 倍"甚至更多（每节点最多 m 个孩子）。看待数据量 N = 620 亿（6.2×10^11）：二叉树高度约 log₂(N) ≈ 36 层；而 1024 阶 B-树高度 ≤ log₅₁₂(6.2×10^11) ≈ 3~4 层。每次"下一层"在磁盘场景里就是一次磁盘 IO，36 次 vs 4 次，差了近一个数量级。归根结底：二叉树把 IO 次数压在 log₂，多路 B-树把 IO 次数压在 log_m（m 可以成百上千）——这就是"多路"的账。 而你付出的代价只是节点内部一点内存中的比较（极快），在磁盘 IO 面前可以忽略。

思考题 2：一棵 m 阶 B-树，它的根、非根非叶节点、叶子节点，各自的关键字个数范围分别是什么？

详解：由 B-树性质逐一拆：

根：如果根是叶子（整棵树就一层），可以只有 1 个关键字；如果根不是叶子，它至少要有 2 个孩子 → 至少 1 个关键字，至多 m-1 个。所以统一记"1 ≤ rootKeys ≤ m-1"（根是叶子时下限就是 1）。
非根非叶节点：孩子数在 ceil(m/2) 到 m 之间，关键字 = 孩子数 - 1，故关键字在 ceil(m/2)-1 到 m-1。
叶子节点（也含根为叶子的情况）：同样持 ceil(m/2)-1 到 m-1 个关键字（非根叶子）。几个特例值得背：3 阶树除根外每个节点 1~~2 个关键字；4 阶树除根外每个节点 1~~3 个关键字。

思考题 3：为什么 B-树里"孩子指针总比关键字个数多一个"？这跟普通二叉搜索树的"两个指针"有什么区别？

详解：因为 k 个关键字会把值域切成 k+1 个互不相交的开区间（-∞~~K1]、[K1~~K2]、…、[Kk~∞），每一段区间对应一个子树，所以需要 k+1 个孩子指针来分别"掌管"这些区间。这就是"孩子 = 关键字 + 1"的来历。而二叉搜索树特殊在"每层只有一个关键字"，k=1，于是孩子 = 2，恰好就是左、右两个孩子。可以说：BST 只是 B-树在每个节点关键字个数的特例（m≥3 时每个节点可以存很多个）。 这也是为什么 BST 需要"两个指针"、而 B-树需要"一把指针"——不是结构不同，而是量不同。

思考题 4：对一个已满的 m 阶节点插入一个新关键字，会发生什么？请描述完整的分裂三步。

详解：当节点已满（有 m-1 个关键字），再插一个就临时变成 m 个关键字（用"多留的那个槽位"稳住），触发分裂。三步：

找到中间位置 mid = m ÷ 2（整除），确定上提关键字。
把中间关键字右侧的所有关键字和所有孩子指针，整体搬到新申请的右兄弟节点中（孩子比关键字多搬一个，即最右孩子也要搬走）。
把中间关键字和这个右兄弟，一起"塞"进父节点；若父节点也因此变满，就继续向上递归分裂，直到某一层不满为止；若裂的是根，就 new 一个新根装中间键并让旧根、新兄弟作其子女，树长高一层。一句话记：先插满、再找中、右半搬走、中键上提、父亲接力。

思考题 5：为什么插入的 key 一定落在叶子节点上？

详解：因为 B-树的搜索严格按值域区间传导：从根出发，和节点内每个关键字比较，落入某一个孩子区间，一路往下，直到抵达没有孩子的叶子。这个"顺着区间自然降落到可放置点"的过程，落到的一定是最底层叶子。从维护性讲：往叶子塞一个值不需要改动任何孩子指针的实现、也不会搅乱上层区间的划分——叶子本来就没有孩子，塞得干净。而若往非叶节点的关键字间硬插，那个位置两侧的孩子、值域划分全要重排，代价大且破坏平衡。所以**"数据只进叶子，分裂从叶子冒泡向上"**，是 B-树插入的铁律。

思考题 6：2-3 树是几阶 B-树？它最多时节点里有几个关键字？为什么要拿它当教学样例？

详解：2-3 树就是 m=3 阶的 B-树。因为 3 阶规定每个非根节点的孩子数在 ceil(3/2)=2 到 3 之间，所以每个节点要么 2 个孩子（1 个关键字）要么 3 个孩子（2 个关键字）——由此得名"2-3"。它最多 2 个关键字。它是 B-树最小的特例：分裂形态单一（节点最多 3 个关键字，一满就裂成"1+1、中间提一个"），所有机制（找叶、塞满、取中、上提、顶根、长高）都能在纸上推演清楚，又没有任何"大阶"带来的视觉噪音，所以几乎每本教科书都用它当分裂演示的样板。理解了 2-3 树，把"最多几个孩子/几个键"的数字换成更大的 m，逻辑不变。

思考题 7：删除一个非叶关键字时，为什么先要找"前驱或后继"，再套"删叶子"的口诀？

详解：因为非叶节点还"管着"一片孩子区间，这个关键字是区间划分的"界碑"，直接删掉它，界碑没了、左右区间就断了。而前驱/后继这类关键字，由于定义在"最左下的最大"或"最右下的最小"，必然位于某个叶子里。于是把"删界碑"偷换成"删叶子里的那个替身"——界碑由叶子里的前驱/后继顶上来，而叶子那边删了一个关键字，正好变成"删叶子"的简单情形。所以**"删非叶"通过替换法化归为"删叶子"**，是整套删除最简单也最关键的一步。

思考题 8：节点删除后"下溢"了，为什么优先"借"而不是优先"合并"？这两种补救的本质区别是什么？

详解：下溢指节点关键字数跌破 ceil(m/2)-1。补救优先看兄弟：

若兄弟富余（关键字数>下限），就"借位"（borrow）：父节点下拨一个关键字给自己，兄弟回顶一个关键字给父亲，同时兄弟让孩子区间跟着关键字一起迁移。借位的好处是：整棵树结构、高度都不变，只是关键字在父子兄弟间"搬运"，开销小。
只有当兄弟也到下限、谁也借不出时，才"合并"（merge）：把自己和兄弟合并成一个新节点，并把父节点里的那个隔断关键字一起拉下来并入其中。合并有个代价：父节点的关键字会少 1 个，若父亲因此下溢，就得继续向上递归借位/合并；最坏一路合并到根、根下沉、树矮一层。一句话："借"是局部调整不动树形，尽可能先借；借不动了才"合并"，而合并会向高层传导、可能让树变矮。

思考题 9：B+树相比 B-树，为什么更适合做数据库索引的范围查询？

详解：B+树的四大改动（分支只存关键字、关键字与孩子等数、叶子串成有序链表、全部数据只在叶子）合起来给了它两个杀手级能力：

所有命中都要走到叶子，而且是"沿着叶子链表走"——范围查询定位到起点后，顺着链表一路右扫即可取到一整段有序数据，复杂度近乎线性、且不来回跳祖先，IO 友好。
分支节点只存关键字、更"轻"，同样的磁盘页放得下更多路标，扇出更大、树更矮，整体 IO 次数更少。而普通 B-树做范围查询要在父子/兄弟节点间反复 DFS 跳转、多次访问祖先，既浪费 IO 也不利于顺序扫描（磁盘连续读很快，乱跳很慢）。所以追求"扫一整段"的数据库索引普遍倒向 B+树。

思考题 10：MyISAM 和 InnoDB 都用 B+树索引实现，为什么一个是"非聚集"、一个是"聚集"？它们谁查辅助索引更慢？

详解：区别就在叶节点里放的是什么。

MyISAM：索引文件与数据文件分离，B+树叶子只存"数据记录的磁盘地址"，查询要"索引定位地址 → 再去磁盘取记录"两步。因为索引和数据不在一起，叫非聚集索引。
InnoDB：数据文件本身就是一棵按主键组织的 B+树，叶子直接存整行记录，主索引即数据，叫聚集索引；辅助索引叶子存"主键值"，查辅助索引必须"回表"（先得主键、再按主键回主索引取记录）两遍。谁的辅助索引更慢？一般说 InnoDB 的辅助索引查询更慢（要回表的第二遍检索）；但 InnoDB 按主键查更快（一次到位、且记录按主键物理聚集、顺序 IO 友好）。这正是"聚集 vs 非聚集"的经典取舍——主键查询赢在 InnoDB，辅助查询赢在 MyISAM。这也解释了一句话："想要 InnoDB 快，别乱造无意义的超大主键，因为所有辅助索引都引用它。"

思考题 11（动手）：请手推序列 {10, 20, 30, 40, 50} 依次插入一棵 3 阶 B-树的全过程。

详解（一步步推）：

插 10：空树，作根 → [10]。
插 20：比 10 大，[10 20]（2 键，未满）。
插 30：比 20 还大，节点变 [10 20 30]——3 键超载。中间键 20 上提，裂成左 [10] 右 [30]，20 当新根：20 / \ [10] [30]。
插 40：从根 20 右走，落右叶 [30]，变 [30 40]，未满。树为 20 / \ [10] [30 40]。
插 50：落右叶 [30 40]，变 [30 40 50]——超载。中间键 40 上提到根 20，裂成左 [30] 右 [50]；根变 [20 40]（2 键，未满）。最终：

       [ 20  40 ]
      /    |     \
   [10]  [30]   [50]

所有叶子同层，每节点关键字数 1~2 合法，中序 10 20 30 40 50 有序。及格了。

思考题 12（自测）：下面的几个说法，指出对错并纠正。（a）B-树就是"B 减树"。（b）把 B-树的阶设得无限大，索引就能无限快。（c）B+树里数据可以"提前命中"在分支节点。详解：全文播一遍—— （a）错。B-树读作 B 树，短横是连接号不是减号，和"B 加树"也没有配套的加减关系。（b）错。节点做太大，一个节点装超过一个磁盘块/页，读它就要跨多块 IO，反而拖慢；工程上是按"让节点正好等于一页"来定阶的，不是越大越好。（c）错。B+树的分支节点只有关键字、没数据，任何命中都必须落到叶子；"分支里提前命中"是 B-树的特征，不是 B+树的。

收个尾

这一章我们把"叉树"从"二叉"一路升到了"多路"。回顾来路：先从"磁盘比内存慢得多"这个残酷现实出发，发现二叉树 log₂N 的 IO 次数在磁盘上是灾难，于是推出——要用"更矮的多路树"来压磁盘读取次数。然后我们精确定义了 m 阶 B-树的那几条性质（孩子比关键字多一个、所有叶子同层、节点不低于半满），画出了节点结构，推导了"高度被夹在 log_mN 与 log_{m/2}N 之间"的高度界，手写实现了查找、插入和分裂，用 2-3 树把"插满→取中→分裂→上提→顶根"的套路走了个遍，又补讲了删除的借位与合并、排了一圈满分裂/偶数阶/边界省的古坑。最后拓展到 B+树、B*树两位表亲，并落地到 MySQL 的 MyISAM/InnoDB 索引与磁盘页的工程实践。

现在你再回头看 MySQL 那句"索引就是数据结构"，是不是有了完全不一样的体感？当你在数据库里执行一条 WHERE 语句飞快地返回结果时，背后就是一棵 B+树在替你穿针引线；当你懂得了"页大小定阶""叶子串链表做范围扫""聚集索引存整行"这些原理，那些曾经玄妙的索引调优，也就都变成了能用数据结构语言解释的确定工程。这也正是学数据结构的乐趣——所有"看起来很快"的系统，背后都站着某个"你想懂了就会心一笑"的结构。B-树是其中特别有分量的一棵，愿你在 B+树、跳表、LSM 树这些后续邻居那里，继续保有这股"拆开电梯看钢缆"的好奇心。