MySQL 笔记：B+ 树索引原理，为什么不用哈希和红黑树

前言#

日常写索引就是一句 KEY idx_status (status)，但"为什么是 B+ 树"这件事很少有人细想。结论先放这里：InnoDB 的索引结构是 B+ 树，不是哈希表，也不是二叉搜索树或红黑树，这是存储引擎在磁盘这个介质上做出来的取舍。

二叉树为什么不合适#

一棵普通的二叉搜索树，每层只有两个孩子。100 万行数据，树高大约 20 层；即使做成 AVL 或者红黑树保证平衡，树高依然是 log2(n) 的量级，只是避免了退化成链表。

关键在于：索引不是放在内存里比关键字，而是放在磁盘上。每下探一层就是一次随机 IO，而磁盘读写是按页来的，InnoDB 默认页大小 16 KB：

mysql -e "SHOW VARIABLES LIKE 'innodb_page_size';"

既然一页能装很多内容，就没必要每层只放两个孩子。把非叶子节点改成只存"键值加子页指针"，一个 16 KB 页可以装上千个键，分支系数一下就上去了：

第 1 层（根）  ：约 1000 多个键
第 2 层        ：约 1000 × 1000 个键
第 3 层（叶子）：存放真正的数据

三层就能覆盖百万级行数，一次主键查询最多三次 IO。B+ 树的长处不在于比较得更快，而在于用更大的分支系数换更少的磁盘访问次数。

B+ 树的三个特点#

• 非叶子节点不存行数据，只存键和页指针，因此每页能容纳更多键，分支系数更大
• 叶子节点之间用双向链表串联，ORDER BY、BETWEEN、LIMIT 这类顺序访问沿链表走就行，不必每行都从根重新下树
• InnoDB 的主键索引（聚簇索引）叶子节点存整行；二级索引的叶子存的是主键值，命中之后还要按主键再走一次树才能取到其他列，这就是"回表"

为什么不用哈希索引#

哈希索引做等值查询是 O(1)，看着很香，但有三个绕不过去的硬伤：

1. 只支持等值和 IN，范围条件、BETWEEN、前缀模糊 LIKE 'abc%' 全都用不上
2. 哈希表本身不保序，ORDER BY 还得额外排序
3. 冲突严重时同一个桶退化成链表，而且哈希结构要常驻内存，没法经济地落在磁盘上

所以 InnoDB 不提供手动创建哈希索引，只有引擎自己维护的"自适应哈希索引"：它统计索引上的等值访问频率，觉得划算时才在内存里临时建一层哈希。MEMORY 引擎则可以直接声明 HASH 索引，因为它本来就在内存里。

小结#

• 索引的瓶颈是磁盘 IO 次数，B+ 树靠大分支系数把树高压到三层左右
• 叶子层的双向链表让范围和排序扫描很便宜，这是经典 B 树不具备的
• 二级索引命中后仍要回表，能用覆盖索引就别回表
• 哈希索引快在等值，代价是丢掉范围、排序和磁盘组织能力