B树与B+树#

MySQL 用 B+树原因： 矮胖(IO少) + 范围查询高效 + 查询时间稳定 + 3层可存亿级数据

B树和B+树都是多路平衡搜索树，核心区别在数据存储位置。B树所有节点都存数据，B+树只有叶子节点存数据，内部节点只存索引键值。B+树叶子节点之间用双向链表串联，这使得范围查询只需要找到起始叶子然后沿链表顺序扫描，效率远高于B树需要中序遍历。MySQL的InnoDB索引选用B+树有三个关键原因：第一是矮胖，内部节点不存数据所以每个节点能放更多键值，假设每页16KB、主键bigint占8字节加指针6字节，一个非叶节点能放约1170个指针，三层B+树就能存储约两千万条记录，查询只需三次磁盘IO。第二是查询时间稳定，所有查询都走到叶子节点，不像B树可能在中间层就命中导致查询时间不均匀。第三是范围查询高效，ORDER BY和BETWEEN操作直接走叶子链表。跟红黑树比，红黑树是二叉树太高导致IO次数多，不适合磁盘存储场景。

追问方向：

• “B+树相比 B 树为什么更适合数据库索引？”→ B+树数据全在叶子节点且叶子用链表串联，范围查询只需遍历链表；非叶节点不存数据，单节点能容纳更多 key，树更矮磁盘 IO 更少
• “B+树的阶数怎么确定？”→ 由磁盘页大小决定，InnoDB 默认 16KB 页，每个非叶节点尽量塞满 key+指针使树高度最低（通常 3-4 层可存千万级数据）
• “为什么 MongoDB 用 B 树而 MySQL 用 B+树？”→ MongoDB 以文档为单位读写、较少范围扫描，B 树非叶节点就能命中数据更快；MySQL 关系型查询大量范围扫描，B+树叶子链表顺序访问更高效

易错点：

• ❌ 只知道概念不知道原理——面试官会追问底层实现
• ❌ 缺乏实际使用经验——结合项目场景回答更有说服力