为什么千万行的表，主键查询还是毫秒级？—— InnoDB 存储引擎与 B+ 树
先从一个每天都在发生的场景说起。你有一张用户表，几千万行，执行 SELECT * FROM users WHERE id = 5000000，居然几毫秒就回来了。几千万行数据，逐行扫一遍不可能这么快——那 MySQL 到底是怎么在这么多数据里瞬间定位到这一行的？
要回答这个问题，得从计算机最慢的那一环讲起：磁盘。
磁盘 IO 是真正的瓶颈
CPU 和内存都是纳秒级的，而磁盘一次随机读是毫秒级的——差了百万倍。数据库的数据存在磁盘上，如果每次查询都要把磁盘翻一遍，几千万行意味着几千万次磁盘 IO，那要等上几分钟。所以数据库的性能，本质上是在回答一个问题：怎么用最少的磁盘 IO 找到目标数据？
答案就是索引。而 MySQL 的 InnoDB 引擎选择的索引结构，是 B+ 树。
为什么偏偏是 B+ 树？
先想，索引能不能用哈希表？哈希表查一个 key 是 O(1)，听起来更快。但哈希表有个致命问题：它只擅长"精确等于"，不擅长"范围"。WHERE id > 100 AND id < 200 这种查询，哈希表得把每个 key 都算一遍哈希，没法顺序遍历。而现实业务里，范围查询、排序是家常便饭。所以哈希出局。
那红黑树、二叉搜索树呢？它们支持范围，但问题是树太高。100 万数据，平衡二叉树高度约 20 层，而每往下一层就是一次磁盘 IO，一次查询最坏要 20 次磁盘 IO——还是慢。要降低 IO 次数，就必须让树"矮"下来，也就是让每个节点能分更多叉，一次 IO 能排除更多数据。
于是方向就清楚了：多叉、矮胖的平衡树。这就是 B 树。但 InnoDB 用的是 B 树的改进版——B+ 树，区别在哪？
B 树的非叶子节点也存数据，而 B+ 树只有叶子节点存数据，非叶子节点只存 key 和指针。这一改带来了三个好处：非叶子节点更"瘦"，一个 16KB 的页能塞下更多 key，树就更矮、IO 更少；叶子节点之间用双向链表串起来，范围查询直接顺着链表扫就行；而且任何查询都要走到叶子，IO 次数是恒定的。
3 层 B+ 树能存多少数据？
这个数字面试经常被问到，值得自己算一遍。InnoDB 一页 16KB，假设主键是 8 字节的 bigint，指针 6 字节：
- 非叶子节点里，每个 key+指针 14 字节，一页约存
16384 / 14 ≈ 1170个 - 叶子节点里，假设一行 1KB，一页约存 16 行
三层 B+ 树就是 1170 × 1170 × 16 ≈ 2200 万 行。也就是说，2200 万行的表，主键查询只需要 3 次磁盘 IO。这就是 B+ 树"矮胖"的威力——面试时能当场把这个数字算出来，比背结论有说服力得多。
顺着"页"这个概念，还会引出一个工程实践：为什么推荐自增主键而不是 UUID？ 因为数据是按主键顺序插入页的，页满了会"页分裂"（把一半数据挪到新页）。自增主键是顺序追加，很少分裂；而 UUID 是随机的，会频繁触发分裂，既降低页利用率又产生写放大。
光有索引还不够：Buffer Pool
到这里，查询"只用 3 次 IO"听起来很美，但每次都真去磁盘读，还是不够快。能不能让热点数据常驻内存？这就是 Buffer Pool——InnoDB 的一块内存区域，把数据页缓存在里面，绝大多数读写直接命中内存。
Buffer Pool 的核心设计是改进版 LRU 链表，它被分成两段：young 区（前 5/8）放热点数据，old 区（后 3/8）放新读入的页。为什么分两段？为了防污染。一次 SELECT * FROM 大表 会读进来海量页，如果这些页直接进 LRU 头部，会把真正的热点数据全挤出去。分段的规则是：新页先落 old 区，只有它被再次访问了，才晋升到 young 区。全表扫描的页读一次就再也不会被访问，很快被淘汰，影响不到热点。
内存里的页被修改后就成了"脏页"，不能一直不落盘，否则断电就丢了。脏页会在几个时机刷回磁盘：redo log 写满、脏页比例过高、空闲页不足等。这也能解释一个线上现象——写入周期性卡顿，往往就是脏页集中刷盘或 redo log 写满导致的。
修改数据时，怎么保证崩溃不丢？
现在考虑写操作。如果每次 UPDATE 都直接去磁盘改数据页，那是随机写，慢。InnoDB 用了经典的 WAL（Write-Ahead Logging，先写日志再写数据）：修改时先把"做了什么改动"顺序追加到 redo log，返回客户端成功，之后再慢慢把脏页刷回磁盘。
顺序写日志比随机写数据页快得多，而且崩溃后可以靠 redo log 重放，把"已提交但没来得及落盘"的修改补回来——这就是 crash-safe。redo log 是循环写的文件，靠 checkpoint 推进释放空间。
三大日志，各管一件事
到这里，InnoDB 涉及三份日志，容易混，理清它们的职责就不会乱了：
| 日志 | 管什么 | 一句话 |
|---|---|---|
| redo log | 崩溃恢复 | 记"改了什么"，崩溃后重放，保证已提交事务不丢 |
| undo log | 回滚 + 多版本 | 记"改之前是什么"，用于回滚和 MVCC 读历史版本 |
| binlog | 主从复制 + 恢复 | 记"逻辑 SQL"，给从库回放、给数据恢复用 |
redo 和 binlog 是两份独立的日志，如果只写了一份就崩溃，会导致主从数据不一致。所以提交时用两阶段提交：先写 redo 置 prepare → 写 binlog → 再把 redo 置 commit。崩溃恢复时看 binlog 有没有写：写了就提交、没写就回滚，保证两份日志要么都成功要么都失败。
把这条线串起来
回到开头那个问题：SELECT * FROM users WHERE id = 5000000 为什么毫秒级？因为主键索引是一棵 3 层的 B+ 树，最多 3 次 IO 就能定位；而这 3 次 IO 里，热点页大概率已经在 Buffer Pool 里，实际可能一次磁盘 IO 都不发生。写操作则靠 redo log 的顺序写保证速度和崩溃安全，undo 和 binlog 分别负责回滚多版本和主从复制。
下一篇文章，我们进入事务与 MVCC：当一个事务读到一半，另一个事务把数据改了，InnoDB 是怎么让你读到一份稳定一致的快照的？