MySQL索引为什么使用b+树？
MySQL 索引使用 B+ 树，因为它在磁盘存储环境下能高效支持 范围查询、顺序访问 和 高扇出（Fan-Out），减少 I/O 操作，提升查询性能。相比其他数据结构（如 B 树、红黑树），B+ 树更适合数据库的索引需求，尤其在 InnoDB 引擎中。
关键事实
- B+ 树特点：
- 非叶子节点只存键值，不存数据，节省空间。
- 叶子节点存所有数据，并通过链表连接，支持顺序遍历。
- 高度低，扇出高（每节点可存更多键）。
- 为何适合 MySQL：
- 磁盘 I/O 优化：B+ 树高度低，一次磁盘读取加载更多键。
- 范围查询高效：叶子节点链表顺序访问，快于跳跃式查找。
- 查询稳定性：所有查询走叶子节点，路径长度一致。
- InnoDB 使用场景：
- 主键索引（聚簇索引）：键是主键，数据是整行。
- 二级索引：键是索引列，数据是主键值。
具体原因详解
1. 磁盘 I/O 效率
- 背景：数据库索引存储在磁盘，I/O 是性能瓶颈。
- B+ 树优势：
- 非叶子节点只存键，占用空间小，一个节点可存数百到上千个键（扇出高）。
- 树高度低（如 3 层可存百万记录），减少磁盘读取次数。
- 对比 B 树：B 树节点存键和数据，扇出较低，层数更高，I/O 更多。
2. 范围查询支持
- 需求：SQL 常涉及 WHERE id BETWEEN 10 AND 20。
- B+ 树优势：
- 叶子节点按键顺序排列，双向链表连接。
- 找到范围起点后，顺序扫描即可，无需回溯。
- 对比 B 树：数据分散在所有节点，范围查询需遍历多层。
3. 顺序访问性能
- 背景：磁盘顺序读远快于随机读。
- B+ 树优势：
- 叶子节点链表支持顺序扫描，充分利用预读（Locality）。
- 对比红黑树：二叉结构，节点分散，随机访问多。
4. 查询稳定性
- B+ 树优势：
- 所有数据在叶子节点，查询路径长度固定。
- 对比 B 树：数据分布在各层，查询深度不一。
5. 空间利用率
- B+ 树优势：
- 非叶子节点不存数据，更多空间存键，减少树高。
- 示例：页大小 16KB，键 8 字节，可存约 2000 个键/节点。
示例
- 表：id 主键，100 万行数据。
- B+ 树：
- 高度 3 层，每节点 1000 个键。
- 查询 id=500000：3 次 I/O（根 → 中间 → 叶子）。
- 红黑树：
- 高度约 20 层，20 次 I/O。
延伸与面试角度
- 为什么不用红黑树？：
- 二叉树高度高（O(log N)，N 为 2），磁盘 I/O 多。
- 无顺序链表，范围查询低效。
- 为什么不用 B 树？：
- 数据分散，扇出低，范围查询需多层遍历。
- 为什么不用哈希索引？：
- 哈希支持等值查询（O(1)），但不支持范围查询。
- 实际应用：
- InnoDB 主键索引：B+ 树叶子存整行数据。
- 二级索引：叶子存主键，需回表。
- 性能数据：
- B+ 树查询百万数据，3-4 次 I/O；红黑树可能 20 次。
- 面试点：
- 问“范围查询为何快”时，提叶子链表。
- 问“与 B 树区别”时，提扇出和数据分布。
总结
MySQL 用 B+ 树因其高扇出减少 I/O、叶子链表支持范围查询和顺序访问，完美适配数据库的磁盘存储和查询需求。相比 B 树、红黑树，B+ 树在性能和功能上更优。面试时，可结合树高计算或范围查询示例，展示深入理解。