一张 100 万行的 users 表，SELECT * FROM users WHERE phone = '13800138000'，有索引时 0.5ms，删掉索引后 800ms——差距一千多倍。这个差距不来自 MySQL 的任何"优化魔法"，只来自一个选择：索引该用什么数据结构。这篇把候选结构逐个放到索引这个位置上称重，看 B+ 树凭什么留下；最后打开 InnoDB 的存储页算一笔账，解释"一棵 3 层的 B+ 树能扛 2000 万行"这个常被引用的数字。
先定需求：索引必须会什么
评价一个索引结构，先列出一台数据库对它的全部期待：
- 等值查询：
WHERE id = 12345，要快。 - 范围查询：
WHERE id BETWEEN 100 AND 200、WHERE create_time > '2026-01-01'，要快。业务报表、分页、时间线全靠它。 - 排序：
ORDER BY id，最好不用再排一遍。 - 写入不能太慢：表是持续增删改的，结构不能一写就崩。
四个条件同时满足，才够格当 MySQL 的索引。下面逐个淘汰。
逐个称重：四条路都走到头
哈希表：等值快，范围废
哈希表等值查询 O(1)，看起来最快。但哈希把键打散了——键 100 和键 101 在表里的位置毫无关系。范围查询只能整表扫一遍，ORDER BY 也指望不上。
Memory 引擎默认就是哈希索引，所以它只适合临时表、缓存这类"只按键取"的场景。InnoDB 有个自适应哈希（Adaptive Hash Index），但那是对热点页的补充加速，主结构不是它。
有序数组：查询满分，写入不及格
数组按序存放，二分查找 O(logN)，范围查询也顺。问题在插入：往中间插一个元素，后面全部后移一位，O(N)。一张每天几十万次写入的表，数组结构撑不住。
它只适合一次写入、长期只读的数据，比如按月归档的历史表。在线业务表不用它。
二叉搜索树：树太高，磁盘受不了
平衡二叉树（红黑树）查询 O(logN)，插入 O(logN)，看似全能。致命点在磁盘：二叉树每个节点只有 2 个分叉，100 万行需要约 20 层。
磁盘读取有个物理特性——读 1 字节和读 16KB 的成本几乎一样（寻道时间是主体，读取本身极快）。所以数据库以"页"为单位读写。二叉树每层存一个节点、读一次页，20 层就是 20 次页读。索引查询慢就慢在这：树越高，IO 次数越多。
结论：要降低 IO，就得把树压矮——每个节点多装几个分叉。
B 树：矮下来了，但还能更矮
B 树一个节点存多个键和多个分叉，树高从 20 层压到 3~4 层，磁盘 IO 骤减。它已经很接近答案，差两点：
- 非叶子节点也存整行数据，数据把节点撑满，分叉数（扇出）上不去——同样的 16KB，装的数据越多，能留给孩子指针的位置越少。
- 范围查询要中序回溯：扫 100~200 这个区间，得在树上反复爬上爬下，没法"顺着一条链往前走"。
B+ 树对这两点各动一刀，成为最终答案。
B+ 树的两刀
第一刀：数据和索引分家。 非叶子节点只存键和指针，不存数据。同样的 16KB，能塞进更多的键，扇出更大，树更矮。数据全部下沉到叶子节点。
第二刀：叶子节点串成双向链表。 叶子层从左到右按键有序，相邻叶子之间有指针相连。范围查询变成：树上定位到起点，然后沿链表向右平推，一次 IO 读一整页，连续区间一气呵成。ORDER BY id 同理——叶子天然有序，不需要额外排序。
一句话记住这棵树：非叶子是指路牌，叶子才是数据；叶子手拉手，范围查询一路向右。
打开 16KB 的页，算一笔账
InnoDB 的一切磁盘操作以页为单位，默认 16KB。B+ 树的每个节点就是一个页。页内部的结构可以简化成三块：
- File Header：页号、前后页指针、校验和等元信息；
- User Records：一条条记录，按主键有序紧密排列，删除的记录空间复用；
- Page Directory：页尾的"目录槽"，把记录分组，页内查找先用二分定位槽，再在组内遍历——所以页内查找也不是全页扫描。
现在算扇出。非叶子节点的一条"键 + 指针"记录，主键用 bigint 占 8 字节，页内指针占 6 字节，共 14 字节：
16384 B / 14 B ≈ 1170 个分叉
叶子节点存整行，假设一行数据 1KB，每页装 16 行。一棵 3 层的树：
根 1 页 → 1170 个中间节点
中间层 → 1170 × 1170 ≈ 137 万个叶子页
叶子层 → 137 万 × 16 行 ≈ 2190 万行
这就是"3 层 B+ 树扛 2000 万行"的出处。行更瘦（比如 200B）这个数还能翻几倍；行更宽（大字段多）则撑不到 2000 万。数字随行宽浮动，但量级由页大小和键宽决定，不受表大小影响。
对查询意味着什么：定位任意一行，最多走 3 个页。而根节点几乎永远命中 Buffer Pool（内存），第二层热点页也大概率在内存，真实磁盘 IO 往往只有 0~1 次。这就是开头那条 0.5ms 查询的完整账单。
追问两个"为什么不用"
为什么不用跳表？ 跳表是 Redis zset 的选择。它是链表结构，节点分散在堆内存各处，靠指针跳跃。内存里随机访问纳秒级，跳表很好用；放磁盘上，每跳一次可能就是一次页读，局部性太差。B+ 树一个节点 16KB 整页读出，一次 IO 换回上千个键的有序信息，磁盘利用率碾压。
为什么不用 LSM 树？ LSM（RocksDB、TiKV 底层）把随机写转成顺序追加写，写性能极好，代价是读要合并多层结构、后台要 compaction。MySQL 面对的 OLTP 场景读写混合、单行查询占大头，B+ 树读路径短的优势更值钱。选型没有绝对对错，是读写比例的取舍。
小结
哈希管不了范围，数组管不了写入，二叉树太高，B 树不够矮。B+ 树用"非叶子只存键 + 叶子串链表"两刀，换来低树高和大扇出，再用 16KB 页这个物理单位把每次 IO 的收益拉满。下一篇进入 InnoDB 内部：主键索引和二级索引各自长什么样、回表是怎么回事、联合索引的列顺序在树里到底怎么排。