什么是 B 树？为什么叫「多路平衡查找树」？它和二叉搜索树有什么区别？
简化版
B 树是一种多路平衡查找树：和二叉搜索树「每个节点最多 2 个孩子、1 个关键字」不同，B 树一个节点可以有很多个关键字、很多个孩子（几百上千路），所以同样多的数据，B 树矮得多。它专为磁盘存储设计——树越矮，查找一个数据需要的磁盘 IO 次数越少。所有叶子都在同一层，是完美平衡的。
详细版
「多路平衡查找树」三个词拆开看：
- 多路：每个节点有多个孩子（不止 2 个），一个节点存多个有序关键字，把「区间」分成多段。
- 平衡：所有叶子节点都在同一层，任何查找路径长度都相同，树高被严格控制。
- 查找树：和 BST 一样有序——节点内关键字从小到大排列，孩子子树的值落在相邻关键字之间。
对比二叉搜索树：
| 维度 | 二叉搜索树 / 红黑树 | B 树 |
|---|---|---|
| 每节点关键字数 | 1 个 | 多个（m-1 个） |
| 每节点孩子数 | ≤ 2 | ≤ m（几百上千） |
| 树高（n 个数据） | O(log₂n)，较高 | O(logₘn)，很矮 |
| 设计目标 | 内存中的查找 | 磁盘 / 外存查找 |
完整版教学
一、B 树为什么存在：为磁盘而生
二叉搜索树、红黑树都是面向内存的：内存随机访问很快，树高 O(log₂n) 完全够用。但磁盘不一样——从磁盘读一次数据（一次 IO）比内存慢几万倍，且磁盘是按「块/页」读取的（一次读一整页，比如 16KB）。
如果把红黑树放到磁盘上，它每个节点只存 1 个关键字，树高 O(log₂n)。查 10 亿数据要约 30 次比较，每次比较可能就是一次磁盘 IO——太慢了。B 树的思路是：既然一次 IO 就要读一整页，那就让一个节点装满一整页、存几百个关键字，这样「一次 IO 能排除掉几百路」，树高从 O(log₂n) 骤降到 O(logₘn)。查同样的数据，B 树可能只要 3~4 次 IO。
二、「多路」如何降低树高
关键在扇出（fan-out）——每个节点的孩子数。
- 二叉树扇出 = 2，树高 ≈ log₂n。
- B 树扇出 = m（比如 1000），树高 ≈ logₘn = log₁₀₀₀n。
举例：10 亿（10⁹）个数据，二叉树高约 30 层；而扇出 1000 的 B 树，1000³ = 10⁹，只要 3 层！扇出越大树越矮，磁盘 IO 越少。这就是「多路」的威力。
三、节点内部结构
一个 B 树节点像一个「有序的分段索引」：
[ 10 | 20 | 30 ] ← 3 个关键字，把数轴分成 4 段
/ | | \
<10 10~20 20~30 >30 ← 4 个孩子，各管一段区间节点内关键字有序排列，n 个关键字就有 n+1 个孩子指针，每个孩子子树的值落在相邻两个关键字划定的区间里。查找时在节点内部（用二分）定位到某个区间，再顺着对应孩子指针下降。
四、「平衡」：所有叶子同层
B 树是完美平衡的——所有叶子节点都在同一层，不存在某条路径特别长的情况。这靠插入时的「分裂」和删除时的「合并/借位」来维持（见插入删除专题）。因为所有叶子同层，任何一次查找走的路径长度都一样，性能非常稳定，不会像普通 BST 那样退化。
五、复杂度
设 B 树有 n 个关键字、阶为 m：
- 树高 O(logₘn)：因为扇出是 m。
- 查找 / 插入 / 删除：都是 O(logₘn) 次磁盘 IO（每层一次 IO，节点内部的比较在内存里做，忽略不计）。
关键指标是「磁盘 IO 次数 = 树高」，所以 B 树一切设计都围绕「把树压矮」。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| 多路 | 一个节点可有多个孩子 |
| 平衡 | 所有叶子在同一层 |
| 磁盘友好 | 节点大小贴合页，减少 IO |
m-order B-tree:
children <= m
keys <= m - 1
all leaves at same depthB 树是为了外存查找设计的，多路分叉用来减少访问层数。
- 误区：B 树是二叉树的一种。 B 树是多路平衡查找树，一个节点可以有多个 key 和多个孩子。
- 误区：节点内 key 无序也可以。 节点内 key 必须有序，才能在节点内定位区间并选择对应孩子。
- 误区：平衡指每个节点孩子数完全相同。 B 树平衡指所有叶子同层，同时节点关键字数量满足上下界。
- 追问：为什么 B 树适合磁盘？ 一次读入一个页大小的节点，节点内多 key 换取高扇出，降低树高和 IO 次数。
- 追问：和 BST 的根本区别是什么？ BST 每层最多二分成两路，B 树每层分成多路，树高大幅降低。
- 追问：查找复杂度如何表达？ 逻辑上 O(log_m n) 层，节点内可线性或二分查找；磁盘场景重点看层数 IO。
七、加强记忆
B 树是多路平衡查找树：一个节点存多个有序关键字、有多个孩子（大扇出），所以比二叉树矮得多（树高 O(logₘn)）。它专为磁盘设计——一次 IO 读一整页/一个节点，扇出越大树越矮、IO 次数越少（扇出 1000 时三层存 10 亿）。所有叶子在同一层、完美平衡。和 BST 的根本区别就是「一个节点几百路 vs 两路」。