3.1.6 B Tree
在前面的二叉查找树与平衡二叉树基础上，我们正式进入B 树（B-Tree）。B 树是数据库和文件系统中最重要的数据结构之一，也是 MySQL 最终采用的B+ 树的前身。虽然 MySQL InnoDB 引擎实际使用的是 B+ 树，但掌握 B 树的结构和原理，才能真正理解数据库索引的演化逻辑。
🌲 一、B 树的定义与核心性质
B 树是一种多路平衡搜索树，它允许一个节点存储多个键，拥有多于两个子节点。这种“矮胖”结构专为磁盘 I/O 优化而设计。
一棵m 阶 B 树满足以下性质：
- 节点键数：每个非根节点包含k 个键，且满足⌈m/2⌉ - 1 ≤ k ≤ m - 1（根节点可以只有 1 个键）。
- 子树数量：每个节点如果包含 k 个键，则拥有k+1 个子节点（除非是叶子节点）。
- 叶子深度相同：所有叶子节点都在同一层，保证绝对平衡。
- 有序性：节点内键值按升序排列，且任一键左子树的所有键小于该键，右子树的所有键大于该键。
示例：4 阶 B 树（每个节点最多 3 个键，4 个子节点）
[20, 40, 60] / | | \ [5,10] [25,30,35] [50,55] [70,80,85]这棵 B 树高度仅为 2，却能存储大量数据。