接触B树的时机通常有两种。一种是还在读书时背数据结构教材的定义，背完应付考试，考完就忘；另一种是工作之后因为索引优化、慢查询排查，被数据库底层结构逼着回来补课。我属于第二种。记得有一次线上范围查询慢得离谱，EXPLAIN 显示索引已经命中，但磁盘I/O次数就是压不下去。后来翻 MySQL InnoDB 的存储引擎文档，看到“聚簇索引采用B+树”，才意识到自己连B树和B+树的定义都没真正吃透，连“为什么数据库不用红黑树”这种问题都答不上来。所以今天不聊具体调优，就把B树的定义这件事彻底讲明白，顺便解释清楚那些“为什么要这样定义”的问题。
1. 先搞清楚：B树到底是在哪种场景下被逼出来的
1.1 二叉树很漂亮，但到了磁盘上就不太对劲
二叉搜索树在内存里足够优雅。但如果插入有序数据，二叉树会退化成链表，查找复杂度从 O(logn) 滑到 O(n)，这是老生常谈。于是有了 AVL 树和红黑树，通过旋转和染色把树高控制在 O(log n)，性能非常稳定。
但这里藏着一个前提：所有操作都发生在内存里。内存随机访问一次大约几十纳秒，快。可一旦数据量大到必须放到磁盘，顺序就完全反过来了。磁盘随机 I/O 一次大约要 10 毫秒，这是内存的几十万倍。在这个量级下，树的层数直接决定一切，因为每下沉一层，基本就意味着多一次磁盘随机读。
假设一棵红黑树里有 100 万条记录，树高大概 20 层。最坏情况下，一次查找要走 20 次磁盘 I/O，20 乘以 10 毫秒就是 200 毫秒。一个查询耗掉 200 毫秒，放在数据库场景里基本等于灾难。更麻烦的是，红黑树每个节点只存一个键，一次磁盘 I/O 读回来一个页，结果这个页里只有一个键真正被用到，剩下全部浪费。
所以说，直接把红黑树放到磁盘存储系统里，它是一棵“瘦高”的树。而磁盘存储系统想要的，恰恰是一棵“矮胖”的树。
1.2 磁盘预读逼出来的“一次读一个节点”
磁盘读取不是按字节随机读的，而是按“页”或“块”为单位的，常见的有 4KB、8KB、16KB。操作系统和存储引擎都遵循局部性原理：读一个页，就把整页内容都加载进来，不管你这次实际要用的只是其中一个键。
如果我们能让树做到“一个节点正好占一个页”，那么一次磁盘 I/O 下来，就能同时获得一堆键和一堆分支指针，性价比极高。B树的出发点就在这里：把二叉树那种“一个节点一个键”的结构，改成“一个节点存多个键、带多个孩子指针”的多路搜索树。
这个“多个”不是 10 个 8 个那种小打小闹。拿 InnoDB 举例，默认页大小是 16KB，一个索引页里能塞下接近一千个键。层数被压到三四层，百万千万级的数据量，一次查询只需要 3~4 次磁盘 I/O，和红黑树的 20 层放在一起对比，差距立刻就能看出来。
所以你看，B树定义不是拍脑袋定出来的数学游戏，它是对“磁盘页大小有限、随机I/O昂贵、预读按页进行”这三个现实约束的直接回应。
2. 定义拆解：一棵m阶B树到底长什么样子
教科书上的定义一般长这样：
一棵 m 阶 B树满足以下条件：
- 每个节点最多有 m 个子节点，也就是说最多有 m-1 个键。
- 除了根节点和叶节点之外，每个内部节点至少有 ceil(m/2) 个子节点。
- 如果根节点不是叶节点，那么它至少有两个子节点。
- 所有叶节点都在同一层。
- 如果一个内部节点有 k 个子节点，那么这个节点恰好包含 k-1 个键。
这五条里，前两条是关于“度”的上下界，第三条是对根节点的特殊豁免，第四条是“绝对平衡”，第五条是“键和孩子指针的对应关系”。
我见过不少读者第一遍看完这组定义就懵，主要是两个原因：一是分不清“子节点数”和“键数”的换算，二是理解不了“为什么非根节点要有下界”。先解决第一个。
2.1 先区分“阶”和“键数”，定义就明白了一半
“m 阶”的含义，是“最多能有多少个孩子指针”。每个内部节点的实际结构里，键和孩子指针是交错排列的：假如有 3 个键，就会分出 4 个区间，指向 4 个孩子。这就是第五条，k 个子节点的节点，恰好有 k-1 个键。
这张对应关系可以用下表记住：
| 节点类型 | 孩子数范围 | 键数范围 |
|---|---|---|
| 根节点（非叶） | 2 ~ m | 1 ~ m-1 |
| 非根内部节点 | ceil(m/2) ~ m | ceil(m/2)-1 ~ m-1 |
| 叶节点 | 无孩子 | 按定义约定，可存键也可不存 |
这里要提醒一下，“叶节点”在不同教材里的约定并不一致。有的书上把最底层包含键的节点叫叶节点，有的把查找失败时到达的空指针位置叫叶节点，CLRS 那种经典教材用的就是后者。工程上我接触到的 B树/B+树实现，通常更关注“最底层的节点也存键，并且非根节点的键数下限同样适用”。你在写答案或者看文档时，先确认对方用的是哪套约定，就能少踩很多坑。
2.2 用5阶B树感受一下合法形态
假设 m=5，一棵 5 阶 B树：
- 每个节点最多 5 个孩子，最多 4 个键。
- 非根内部节点至少有 ceil(5/2)=3 个孩子，至少 2 个键。
- 根节点如果非叶，至少有 2 个孩子，至少 1 个键。
- 所有叶子必须同层。
于是合法节点最稀疏的状态是：根节点 1 个键带 2 个孩子，往下每一层内部节点都是 2 个键带 3 个孩子。这棵树仍然满足所有条件。相比二叉树“每个节点必须满 2 个孩子”的刚硬约束，B树给你的弹性空间大很多，这也是为什么插入删除之后通过分裂和合并就能恢复合法状态，而不需要旋转。
如果把“键数下限”记作 L=ceil(m/2)-1，上限记作 U=m-1，那么一棵 B树的日常维护本质上就是：插入时，任何节点键数超过 U 就分裂；删除后，任何非根节点键数低于 L 就借或者合并。这个视角在后面验证定义时会非常有用。
提示：很多人背完定义只记住“最多 m 个孩子”，却把键数上下限和高度上限推导当成无所谓的东西。实际上，B树面试题和工程理解的难点，大多藏在下界和高度推导里。
2.3 “定义”和“实现”别混为一谈
还有一点值得单独说：B树定义描述的是逻辑结构，并不管你磁盘页怎么编排。一个节点占用一个页，页内除了键和孩子指针之外，通常还有页头信息、空闲空间、页目录等，这些是存储引擎的实现细节。定义保证的是“最坏情况下需要多少次磁盘I/O、查找复杂度是多少”；实现层要解决的是“在一个页内部怎么二分查找键、怎么维护页间指针、怎么标记删除”。
把这两层分开，很多困惑会消失。比如有人纠结“B树删除后键没了，但数据还在”，这大概率是把定义层和 InnoDB 里标记删除的实现混在一起了。
3. 键数上下界不是随便拍的：与磁盘I/O的谈判条件
3.1 上界：一个页装不下太多键
B树一个节点对应磁盘上一个页，页大小就是一次 I/O 的读取单位。如果允许节点无限制地塞键，节点大小一旦超过页大小，那么一次 I/O 就装不下。读取一个节点可能要多次 I/O，前面说的“一次 I/O 换一堆键”的优势就全没了。所以，节点最多 m 个孩子、最多 m-1 个键，这个上界本质上是页容纳能力的硬约束。
数据库里页大小可以调，B树节点的容量上限跟着变。这就是为什么不同存储引擎里 B+树的“扇出”（一个节点能带的孩子数）不同，它不是算法设计者随意选的，而是由页大小除以单条索引记录平均大小算出来的。
当然，实际中一个页不会塞到 100% 满，因为要留空间给更新、删除带来的页内碎片整理。但从定义角度，我们只讨论逻辑上限。别拿“页其实不会装那么满”去质疑B树节点上限，那是两码事。
3.2 下界：防止节点稀到失去意义
下界 ceil(m/2) 是最容易被忽略、也最重要的一条。你可以这样理解：如果没有下界，只规定“每个节点最多 m 个孩子”，那删除操作可以把节点删到只剩 1 个键 2 个孩子，甚至更空。树的形状会越来越瘦高，层数变多，查找时的磁盘 I/O 次数也跟着变多。
下界的意义在于：每个非根节点至少要“半满”。这样在给定数据量的前提下，整棵树的高度会有一个严格的上限，磁盘 I/O 量才可控。
这里可以推一下高度上限。设 m 阶 B树的最小孩子数为 t=ceil(m/2)。树高为 h 时，根至少有 2 个孩子，第 2 层至少有 2t 个节点，第 3 层至少有 2t^2 个节点，依此类推。整棵树的节点总数最少是：
1 + 2t + 2t^2 + ... + 2t^(h-1)
反过来，给定 n 个键，树的高度 h 最多大约是 log_t(n) 这个量级。t 越大，h 越小。当 m=1000（InnoDB 的量级），t=500，哪怕数据量到千万，树高也只有 3~4 层。这就是“B树矮胖”的量化解释。
3.3 根为什么可以“节外生枝”
第三个条件说根节点可以有 1 个键 2 个孩子，甚至一棵树只有一个根节点时，它可以只有 0 个键。根被单独豁免下界，是因为它代表树的起点。如果根也要半满，那些数据量很少的树就永远建不起来了，你刚创建一个 B树，总不能逼它先填满半页。
真正要防止的是根退化成一个单链。所以根节点非叶时，至少要有 2 个孩子，否则一棵 B树退化成单链，“所有叶子同层”的性质也会被破坏。
4. 用一次插入和删除操作验证定义：分裂与合并不是额外操作，就是定义本身
定义如果只是背下来，过几天就忘。我建议用一遍插入和删除的过程去“反推”定义，这样每条规则都有具体的触发场景。
4.1 m=3时的插入过程
以 3 阶 B树为例。m=3 时，每个节点最多 2 个键 3 个孩子，非根节点至少有 1 个键 2 个孩子。这种形态也叫 2-3 树。
依次插入 10、20：
root: [10, 20]再插入 30 时，根节点已经有 2 个键，达到上限。按 B树的插入策略，先把 30 放进节点，此时节点里有 3 个键，超过上限 m-1=2。需要分裂：把中间键 20 提升为新根，左右各成一个节点 [10] 和 [30]。结果：
[20] / \ [10] [30]这个例子说明，B树只有一种方式会长高：根分裂。而且每长高一次，原来根的孩子降为新根的孩子，所有叶子仍然在同一层。这不是偶然，分裂规则就是“中间键上升、左右两个节点降为它的孩子”，天然保持同层。
继续插入 40 和 50。先插入 40，检索路径走到右孩子 [30]，插入后变为 [30,40]，合法。再插入 50，右孩子变为 [30,40,50]，超限，于是中间键 40 提升到根。最终根变成 [20,40]，三个孩子分别是 [10]、[30]、[50]。你会看到，根和内部节点分别经历了一次分裂，但整棵树仍然完美满足定义的所有条件。
4.2 删除后的借键与合并
删除操作触及下界。还是 3 阶 B树，某个非根节点只剩 1 个键，删除之后变成 0 个键，低于下限 L=ceil(3/2)-1=1。此时有两种补救方式：
- 向兄弟节点借一个键：把父节点中的一个键拉下来，兄弟的一个键顶上去。这个过程不改变层数，叶子仍然同层。
- 如果兄弟也只剩 1 个键，借不了，那就从父节点拉一个键下来，和两个孩子合并。父节点键数因此减少，如果父节点键数低于下限，继续向上合并。最极端的情况是根也被拖下水，这时树的高度减一。
删除操作里非常重要的一点是：B树的层高可以被压缩。当根的两个孩子合并时，根失去存在的必要，整棵树降低一层。这正好和插入时“根分裂长高一层”形成对称。
通过这一遍操作你会发现，B树定义里的上界对应插入时的分裂阈值，下界对应删除时的借键/合并阈值，叶子同层由分裂和合并的操作方式天然保证。所以B树维护平衡不靠旋转，靠的就是“越过上界就分裂、跌穿下界就合并”这两条规则。
5. 把定义放回坐标系里：B树和红黑树、B+树的差异
很多人学 B树时有个困扰：它和红黑树、B+树看起来都像“自平衡的多路树”，区别到底是什么。我自己的记忆方法就三句话：红黑树服务内存，B树服务磁盘，B+树是B树的存储引擎改良版。
5.1 B树 vs 红黑树
从定义上说，红黑树本质是一棵结构受限的二叉搜索树，节点最多 2 个孩子，通过颜色约束保证任一节点到叶子的路径长度差不会超过两倍。B树则是绝对平衡的多叉树，所有叶子同层，树高和红黑树相比差一个数量级都不止。
红黑树在磁盘场景下不占优势，但它更多用于内存中的关联容器，比如 C++ STL 的 map/set、Java 的 TreeMap。B树设计目标是减少磁盘 I/O 次数，所以它牺牲了“二叉树结构简单”，换来了“高扇出+低层数”。两者本质上是不同存储介质的适配产物，不存在谁全面优于谁的问题。
5.2 B树 vs B+树
B+树可以看作 B树的改良：键全部冗余存储在内部节点，只有叶节点携带数据（或指向数据行的指针），叶节点之间用链表串联。这个差异看着小，影响却很大：
| 对比项 | B树 | B+树 |
|---|---|---|
| 数据位置 | 每一层节点都可能携带数据 | 只在叶子节点携带数据 |
| 内部节点存什么 | 键+数据或数据指针 | 只存键和指针 |
| 查找路径 | 可能在中途节点命中 | 必须走到叶子才算查完 |
| 范围查询 | 中序遍历麻烦 | 叶子链表顺序扫描非常快 |
| 页内扇出 | 相对低 | 更高，因为内部节点不存数据 |
| 磁盘I/O稳定性 | 平均次数可能更低，但方差大 | 无论命中与否都走完整路径，I/O次数更稳定 |
B+树能被 InnoDB 用起来，核心就两条：一是内部节点不存数据，同样一个 16KB 页能装下更多键，扇出更大，树更矮；二是叶子带链表，范围查询和 ORDER BY 可以直接从链表顺序读，不用反复回父节点做中序遍历。
注意，这不是说 B树在所有场景下都不如 B+树。在内存型数据库、需要频繁修改的中间件场景，B树因为数据可能就近在内部节点命中，有时能省去从叶子回溯的一层 I/O；B+树则无论怎么查都得下沉到叶。选哪个，取决于你是否看重范围扫描和顺序读。
5.3 看数据库文档时留个心
很多文章说“MySQL 索引用的是 B+树”，准确说法是 InnoDB 的聚簇索引和二级索引采用 B+树。而一些 NoSQL、文件系统、老式系统可能直接用 B树或 B树变体，比如 B*树、B-link tree、COW B-tree。这些变体都是在基础定义之上迎合并发、写优化或日志型存储而做的调整。
所以当你查某个产品文档时，先确认它说的是“B树”还是“B+树”，再看是不是“B树变体”。先把基础定义吃透，后面理解和区分这些变体会轻松很多。
6. 关于B树定义，最常见的那几个误区与记忆锚点
最后把我这些年见过的高频误区归拢一下。这些错误几乎都发生在“定义没吃透”的阶段。
6.1 误区一：把B树当成二叉树
很多人看到“B树”就联想到 Binary Tree，于是画出两叉结构。实际上，B树的 B 更通行的说法是 Balanced 或发明人 Rudolf Bayer 姓氏首字母，但无论哪种解释，都跟 Binary 没关系。一棵 B树每个内部节点可以带远超两个的孩子。你只要记住“m 阶最好理解成最多几个孩子”，就不会走偏。
6.2 误区二：B树和B+树混用
面试里经常有人背完 B树定义，回答索引问题时却说“B+树的优点是不存储数据”，但完全说不清 B+树在 B树基础上改了哪几个点。建议把这俩当“经典款和改良款”对比记，重点抓数据位置和叶子链表这两条。
6.3 误区三：以为所有节点必须“至少半满”
准确表述是“非根非叶节点，孩子数至少 ceil(m/2)，键数至少 ceil(m/2)-1”。根节点有豁免。还有不少人把“孩子数半满”误写成“键数半满”，多算一。可以记：先算孩子，再减一，得到键。比如 m=5，孩子至少 3，键至少 2。
6.4 误区四：以为叶节点一定存数据或者一定不存数据
这取决于定义约定。定义里的“叶子”是逻辑层面的位置概念，说的是树的最低一层。至于最低一层的节点里放不放数据，不同教材、不同引擎有不同安排，不是 B树定义本身能统一回答的。考试和面试里遇到，先问清楚对方用的哪套约定。
6.5 几个记忆锚点
如果非要把定义压缩成容易记住的东西，我自己的检查清单是：
- 阶数 m 是孩子指针上限，键数永远是孩子数减一。
- 内部节点半满下限掐在 ceil(m/2)，根特殊处理。
- 所有叶子同一层，这是 B树绝对平衡的体现。
- 插入越过上限就分裂，删除跌破下限就合并或借键。根分裂是树变高的唯一方式，根合并是树变矮的唯一方式。
- 一个节点大概对应一个磁盘页，所有上下界设置都在围绕“控制磁盘 I/O 次数”这个目标。
个人体会是，B树定义最好的学习方式不是背，而是拿一支笔在纸上画一棵 2-3 树的插入删除，画两遍所有条件就都活了。我当年被慢查询折腾的时候，也没有一开始就啃 CLRS，是先看着 InnoDB 索引页的示意图，回头对照 B树定义，才真正看懂“为什么长这样”。如果你也是从数据库或者文件系统入手学 B树的，建议下一步直接去对比 B+树，再用同样的方法画一棵 B+树的插入删除。到时候你会发现，很多曾经死记硬背的东西，突然就串起来了。
