B 树与 B+ 树：面试完全指南

一、一句话总结B 树每个节点都存数据B 树内部节点只存索引叶子节点存所有数据 链表二、核心对比表面试必背对比项B 树B 树数据存储位置内部节点 叶子节点只在叶子节点内部节点存 key 数据只存 key叶子节点结构只存数据数据 指向下一叶子的指针叶子节点链表❌ 无✅ 有范围查询快树的高度较高内部节点占空间更矮内部节点能装更多 key典型应用嵌入式数据库、早期文件系统MySQL InnoDB、大型数据库三、为什么数据库用 B 树优势解释I/O 更少内部节点只存 key树更矮范围查询快叶子节点链表顺序访问数据集中所有数据在叶子缓存更高效四、什么时候用 B 树数据量较小可放内存嵌入式系统SQLite不需要频繁范围查询实现简单五、B 树叶子节点存什么索引类型叶子节点内容聚簇索引主键完整数据行二级索引索引列 主键回表换个说法存的是索引映射指向数据记录的指针六、什么是页分裂 / 页合并页分裂节点插入满时拆成两个节点父节点增加一个 key页合并删除后节点太“空”和兄弟合并父节点减少一个 key七、时间复杂度B / B 树O(log_m N)m 很大如 1000树高通常3~4红黑树内存O(log₂ N)八、面试必问模拟题Q为什么不用红黑树做数据库索引红黑树树高 ≈ log₂ N千万级数据约 24 次 I/OB 树树高 ≈ log_m Nm≈1000 时约 3 次 I/O磁盘 I/O 是瓶颈B 树少几十倍。九、一张图帮你记忆你可以自己画B 树 [20, 40] / | \ [10] [30] [50, 60] B 树 [20, 40] / | \ [10] [30] [50, 60] ← 内部节点无数据 ↓ ↓ ↓ 数据 数据 数据 ← 叶子节点存数据 链表十、总结一句话B 树全能但中庸B 树为磁盘和范围查询而生