MySQL 索引为什么是 B+ 树？二叉树、哈希、B 树是怎么被淘汰的

面试被问到“MySQL 索引为什么用 B+ 树”，多数人的回答停留在“叶子节点存数据、非叶子节点不存、叶子节点用双向链表支持范围查询”。

这话没错，但没讲清“为什么非得是 B+ 树”。

二叉树不行吗？哈希表不行吗？B 树又差在哪？

把这条选择逻辑讲透，比背几个特征有用得多。

索引要解决的就一件事：少做 IO

先认一个前提：

MySQL 的数据，不管是行记录还是索引，都躺在磁盘上。

查数据必然要走 IO，而 IO 是这几个环节里最慢的一环。

所谓“查询快”，本质是把 IO 压下去了。

压 IO 只有两个方向：

减少 IO 的次数，减少每次 IO 搬运的量。

后面所有设计都围着这两件事转。

数据装不进内存，只能分块读

公司的业务表，数据量上百万是常态，千万也不稀奇。

千万行整张表动辄几个 G，不可能一次性塞进内存。

内存宝贵，全量加载既不现实也没必要。

那就分块读，用到哪块读哪块。

这个“分”的思路就是分而治之，不新鲜。

页是 IO 的最小单位：InnoDB 默认 16KB

分块读，块多大合适？

InnoDB 会把数据和索引组织成一个个 Page。

默认情况下，一个 InnoDB Page 是 16KB，索引的 B+ 树节点也以 Page 为基本组织单位。

后面讨论“一次能从磁盘加载多少索引数据”，就先以 16KB 这个默认 Page 大小为基准。

一个 Page 能塞下多少键和指针，直接决定树的扇出和高度。

一条查询，本质是 K-V 查找

拿 SELECT * FROM user WHERE id = 10 来说，按 id 找整行，其实就是用 id 当 key、整行当 value 的一个 K-V 查找。

那索引文件里应该记什么，才能帮你从磁盘上把这个 value 捞出来？

至少得有"在哪个文件、从哪开始、读多长"。

索引存的，就是怎么定位数据行的线索。

索引和数据放一起，少绕一步

如果索引和数据分开存储，查到索引记录后，还需要根据索引记录提供的位置去访问数据页。

MyISAM 就是这种组织方式：

索引放 .MYI，数据放 .MYD，两个文件分开。

它的索引叶子节点保存的是数据文件中的行位置，找到位置后再去数据文件读取对应记录。

InnoDB 换了思路：

聚簇索引把整行直接塞进叶子节点，索引和数据在同一个 .ibd 文件里。

顺着主键索引走到底，行就到手了，不用再跳一次。

对按主键查询整行数据来说，InnoDB 的聚簇索引可以直接在叶子节点拿到整行记录，避免额外根据地址跳转到独立数据文件。

这也是 InnoDB 在主键查询路径上的一个重要优势。

候选结构挨个看

数据结构那么多，为什么最终是 B+ 树？

我们一个一个排除。

哈希表查单值快，范围查询却失效

哈希表靠散列定位，等值查询很快。

问题是哈希之后的数据不再保持原始 key 的大小顺序。

比如查询 id BETWEEN 10 AND 100，无法像 B+ 树一样先定位到 10，再顺着索引一路扫描到 100。

因此哈希结构天然不擅长范围查询和排序。

索引逃不开范围查询和排序，哈希表这一条就出局。

二叉树家族分支太少，树被拔高

BST、AVL、红黑树，本质都是二叉，每个节点最多两个孩子。

存同样多的数据，树只能往上长。

千万行数据，平衡二叉树的高度接近 log₂(1000万) ≈ 24。

树越高，查找路径需要访问的节点越多；

对于磁盘索引来说，这意味着潜在的页面访问次数更多。

虽然数据库会缓存部分上层节点，但相比高扇出的多路平衡树，二叉树的树高依然明显偏高。

B 树虽然降低了树高，但非叶子节点还要存数据

B 树放宽了分支数，一个节点能挂多个孩子，树一下就矮了。

B 树允许数据记录或记录指针出现在非叶子节点中。

相比 B+ 树只在叶子节点保存数据，非叶子节点需要承担更多存储内容，因此在相同页面大小下通常能容纳的索引键和子节点指针更少，扇出也可能更低。

B+ 树把数据挪到叶子节点，非叶子节点只管指路

B+ 树做了一刀切的分工：

非叶子节点只存索引键和子节点指针，不碰数据；

所有真正的内容都落在叶子节点。

以 InnoDB 为例，聚簇索引的叶子节点存完整行记录，二级索引的叶子节点存索引键和对应的主键值。

非叶子节点不存数据，同样 16KB 就能塞下更多键，扇出更大，树更矮。

在典型的数据规模和索引设计下，B+ 树通常能保持较低的树高，即使面对千万级数据，也只需要访问有限层级的索引页。

叶子节点的双向链表让范围查询和排序顺着链走就行，不用跳回上层节点。

B+ 树到底赢在哪

矮，是它的命根子。

树高通常只有三到四层，一次查询只需要沿着有限层级完成查找。

由于上层索引页通常会被缓存，实际磁盘 IO 次数往往更少。

非叶子节点只存键，扇出最大化，这是它能这么矮的原因。

叶子节点的双向链表，把“范围查询”从哈希表的软肋变成了强项。

相同树高下比 B 树存得多，是因为它没把宝贵的节点空间浪费在数据上。

还有一条面试常加分的细节：

选索引列时，字段占的空间越小越好。

键越短，一个 16KB 节点能塞的键越多，扇出越大，树越矮，IO 越少。

这也是为什么很多表倾向使用自增整数或其他趋势递增的主键，而不是直接使用随机 UUID。

以 UUIDv4 这类随机值为例，插入位置分散，容易导致聚簇索引页频繁分裂，增加写入和维护成本。