看过InnoDB存储引擎原理的同学都知道，MySQL的索引底层用的是B+树，但很多资料只给结论不给原因。事实上，从二叉查找树到B+树的演进，每一步都是为了解决真实场景下的性能瓶颈，尤其是磁盘IO的代价问题。把这条演进线索理清楚，你不仅知道B+树好在哪，还能明白建索引时那些规则背后的逻辑。
从二叉查找树到多路平衡树：为什么树的分叉越多越好
先从最简单的数据结构说起。二叉查找树的查询复杂度是O(log n)，看起来已经很快了，但把它放到数据库场景下就会暴露致命问题：数据量一大，树会变得非常高。假设表里有一千万行数据，二叉树的高度大约是23层，意味着一次查询最坏要经历23次节点访问。
而每一次节点访问，本质上都可能是一次磁盘IO。数据库的数据文件是按页（InnoDB默认16KB）为单位读写的，从磁盘读取一个页面的耗时是内存访问的成千上万倍。所以衡量索引结构好坏的核心指标不是CPU比较次数，而是查询过程中的磁盘IO次数，它直接由树的高度决定。
二叉树每个节点只有两个分叉，树必然很高；如果把节点改成能容纳上百个分叉的多路结构，树就能被大幅压扁。B树就是这样的多路平衡查找树，一个16KB的页可以存放大量键值和指针。粗略估算一下：假设主键为bigint占8字节，指针6字节，一个非叶子节点大约能存下1170个索引项，那么三层B+树就能支撑大约两千万行数据的索引，一次查询最多三次页读取，其中根节点通常还常驻内存，实际IO次数更少。这就是多路查找树相对于二叉树、红黑树的绝对优势。
B树与B+树的核心区别：数据到底存在哪个节点
B树有一个特点：键和数据分布在所有节点上，无论根节点、内部节点还是叶子节点，每个键都可能挂着一整行数据。这带来一个隐性问题，单个节点能存放的键变少了。一行用户记录可能是几百字节甚至更大，16KB的页原本能塞一千多个键，挂上数据后可能只能放几十条，树的整体高度被抬高，磁盘IO次数随之增加。
B+树做了两个关键改造。第一，非叶子节点只存索引键和指向下层的指针，不存完整数据，这样每个节点能容纳的键达到最大值，树被压到最矮。第二，所有数据行都存放在叶子节点，且叶子节点之间用双向链表串联起来。这两个改动看似简单，收益却非常大。
B树结构（数据分散在所有节点）：
[35|数据] -- 内部节点也存数据
/ | \
[17|数据][35|数据][62|数据] -- 数据占用空间，键数量少
B+树结构（数据只在叶子节点）：
[35|60] -- 内部节点只存键和指针
/ | \
[17|35]→[35|60]→[60|88] -- 叶子节点存全部数据，且有序链表相连
对比一下查询行为。在B树中查找某个键，可能在任意一层就命中并返回，运气好第一层就找到，运气差要走到最后一层，查询耗时是不稳定的。而B+树无论查什么值，都必须从根一路走到叶子节点，每次查询的IO次数完全相同。这个特性叫查询稳定性，对于需要精确评估响应时间的线上系统来说非常重要。
范围查询为什么是B+树的主场
数据库的日常查询里，范围条件占了相当大比重，比如按时间区间拉取订单、按ID区间分页导出数据。这类查询正是B+树碾压B树的地方。
用B树做范围查询时，只能依赖中序遍历：找到起点后需要回到上层节点再下探，整个过程伴随着大量的回溯和随机访问，IO次数难以控制。而B+树的叶子节点本身就是一条有序链表，范围查询只需要两步：先从根下探定位到范围起点，然后沿着链表向右顺序扫描到终点即可。顺序扫描意味着可以充分利用磁盘预读，相邻的叶子页在物理上也往往靠近，缓存命中率非常高。
-- 这条SQL在B+树上的执行过程： -- 1. 沿根到叶子定位到 create_time = '2024-01-01' 的第一条记录 -- 2. 沿叶子链表向右扫描，直到超过 '2024-02-01' 停止 SELECT * FROM orders WHERE create_time >= '2024-01-01' AND create_time < '2024-02-01';
这也解释了为什么最左前缀原则存在：联合索引(a, b, c)本质上就是先按a排序、a相同时按b排序的多列B+树，查询条件必须从最左列开始才能利用这条有序链表，跳过a直接用b条件，树上的顺序就断了，只能全索引扫描甚至全表扫描。
哈希表查询是O(1)，为什么不用它做默认索引
单点等值查询时，哈希表确实比B+树快，一次哈希计算加一次桶定位就能拿到数据。Memory引擎就支持显式哈希索引，InnoDB内部也有自适应哈希机制对热点页做优化。但哈希作为通用索引结构，缺陷是致命的。
首先，哈希函数把键打散到各个桶里，彻底破坏了数据的有序性。范围查询、排序、分组操作全部失效，只能全表扫描。其次，哈希无法支持模糊匹配，LIKE 'abc%'这种前缀匹配本质是利用有序性定位，哈希结构做不到。再次，哈希冲突需要链表或再散列处理，最坏情况下退化成O(n)，而且冲突链的存储位置分散，对磁盘IO极不友好。B+树虽然单点查询要经过三四次页访问，但换来的是对等值、范围、排序、前缀匹配的全面支持，综合下来才是最优解。
理解结构之后如何指导实践
明白了B+树的原理，很多索引优化的规则就不再是死记硬背的条文。主键为什么推荐用自增ID？因为自增主键保证新数据永远追加到B+树最右侧的叶子节点，避免页分裂；如果用随机值比如UUID做主键，插入位置随机分散，会频繁触发页分裂和数据搬移，既浪费空间又拖慢写入。
索引列为什么不宜太长？因为索引键越短，一个16KB的页能放的键越多，树越矮，IO越少。这就是前缀索引index(col(20))存在的意义：用截断后的前缀换取更紧凑的树结构。同理，SELECT *为什么不好？因为二级索引的叶子节点只存主键值，查完还得回表，而覆盖索引能把需要的列全部放进索引，让查询在叶子层直接完成，省掉回表的随机IO。
总结一下这条主线：磁盘IO是索引设计的核心约束，多路结构压缩树高，非叶子节点不存数据进一步压缩树高，叶子链表支撑范围扫描，有序性支撑排序与前缀匹配。B+树不是在单项竞赛中夺冠的选手，而是在等值、范围、排序、写入、空间这五项综合评分里最均衡的选择，这也正是InnoDB选择它的原因。