MySQL

MySQL 的索引为什么使用 B+ 树，而不是二叉树或哈希表？

面试题考点

是否理解数据库存储引擎和磁盘 IO 之间的关系。

面试官想听的

1、B+ 树能减少磁盘 IO

2、B+ 树能支持范围查询，但是哈希不能

3、InnoDB 是页结构，B+ 树能天然适配页存储

面试示例回答

B+ 树是专门为磁盘存储设计的数据结构。

在 MySQL 中，一个节点通常是 16KB，当我们查询时，每次 IO 会把整个节点读入内存。

详情请参考：http://xhslink.com/o/e1Fu4WUJnR

由浅入深分析

1、为什么不是二叉树：太高、IO 次数多、查找慢。

2、为什么不是 B 树：B 树每层都存数据，遍历效率低。

3、为什么不是哈希表：无法排序和范围查询。

4、为什么是 B+ 树：高度低（减少 IO）；叶子节点链表适合顺序遍历；与磁盘页结构天然契合。

面试加分点

1、能讲出 B+ 树与页的关系：InnoDB 一页 16KB，一个节点可存多个索引键，IO 更高效。

2、能举出真实的项目例子进行辅助说明：比如，我在 XX 公司实习时曾做过慢 SQL 优化，定位下来发现因为字段未建索引导致全表扫描，用 B+ 树索引后性能从 3 秒降到 0.1 秒。

3、能提及聚簇索引：主键索引是聚簇的，叶子节点直接存整行数据，这也是 B+ 树的优势之一。