381 万变 42，索引凭什么
老王看完上一篇的数字还是不甘心：加个索引快 200 倍，它又不是魔法，凭什么呢？这就要把 InnoDB 存数据的底牌翻开——B+ 树。理解了它的结构，后面所有索引规则（最左前缀、为什么主键要自增、为什么UUID 慢）全都顺理成章。
一切从页开始
InnoDB 管理数据的最小单位不是行，是页（Page），每页固定 16KB。磁盘 I/O 是按页读的——就算你只要一行数据，也得把整页读进内存。所以衡量索引优劣的唯一标准是：找到目标数据，需要读几次页。
主键索引（聚簇索引）的叶子页里放着完整的行数据，页内的行按主键有序排列，页与页之间用双向链表串起来。有序，是后面一切范围查询能力的来源。
三层 B+ 树能装两千万行
算一笔经典账。非叶子节点不存数据，只存「主键 + 指向子页的指针」：bigint 主键 8 字节 + 指针 6 字节 = 14 字节，一页 16KB 能放约 1170 个这样的条目——1170 就是扇出（fan-out）。叶子节点放行数据，假设一行 1KB，一页放 16 行。三层树容量：
- 第二层：1170 个节点，每个再扇出 1170 → 1170 × 1170 ≈ 137 万个叶子页
- 叶子层：137 万页 × 16 行 ≈ 2190 万行
也就是说两千万行的表，按主键查一条数据最多 3 次页 I/O（树高 3 层）。根页常驻内存、第二层大概率也在，实际磁盘 I/O 往往只有 1 次。这就是「索引让查询从全表扫变成点查」的物理真相——B+ 树矮胖，每往下一层就缩小上千倍的范围。
为什么不是别的树
| 候选结构 | 出局原因 |
|---|---|
| 二叉搜索树 / 红黑树 | 二叉，扇出只有 2，千万数据树高 23 层以上，磁盘 I/O 次数爆炸；且每个节点一次 I/O，太奢侈 |
| 哈希表 | 等值查询确实 O(1)，但不支持范围查询和排序——WHERE create_time > x、ORDER BY 全废 |
| B 树 | 最接近的对手。但 B 树非叶子节点也存数据，一页装不下几个条目，扇出骤降、树变高；范围查询还要中序回溯跨层遍历 |
B+ 树的两个关键取舍：非叶子节点只存索引不存数据（换来上千的扇出、3 层树高），叶子节点用链表串联（范围查询顺着链表扫就行，不用回到上层）。数据库查询大按范围、大排序，B+ 树就是为这个场景长的。
聚簇索引与二级索引
InnoDB 每张表只有一棵聚簇索引（数据本身就按主键组织成一棵 B+ 树），其余索引都叫二级索引。二级索引的叶子节点存的不是整行，是主键值——查到主键后，还得回聚簇索引再查一次完整行，这个动作叫回表。
两个直接推论：一是二级索引越小越好（只存主键，轻），所以给 varchar 列建索引常指定前缀长度；二是回表有代价，一次回表一次树查找，扫 1 万行回 1 万次表就很难受——怎么用覆盖索引消灭回表，下一篇细讲。
还有一个工程铁律现在能讲透了：主键要用自增或趋势递增的 ID。自增主键永远往最右边的页追加写入，页写满就开新页，顺序又快又满；UUID 这类随机主键每次都要往树的中间插，页分裂、页碎片、缓存命中率下降，全是随机写的代价。这也是第 20 篇分库分表选分布式 ID 时要重提的话题。
树的结构讲完了。但「联合索引怎么排顺序、什么情况算覆盖」这些设计题，光懂结构还不够——下一篇用最左前缀原则把它们串起来。
咖啡凉了，记得趁热喝。
评论 (0)