索引原理：B+ 树

「加个索引就快了」——但为什么快？为什么范围查询也快？为什么有时候有索引还是慢？这些问题的答案都藏在 B+ 树的结构里。这一章不急着教你建索引（下一章的事），先把地基打牢：理解 InnoDB 到底怎么组织数据。

1. 从「为什么不用别的结构」说起

先明确目标：磁盘上的数据，如何支持快速的等值查询和范围查询？

结构	等值查询	范围查询	问题
无序数组（堆表）	O(n) 全扫	O(n)	都慢
哈希表	O(1)	不支持	`BETWEEN`、`ORDER BY`、前缀 LIKE 全废
二叉搜索树	O(log n)	支持	树太高：百万数据高约 20 层 = 20 次磁盘 IO
B+ 树	O(log n)	极好	树矮胖：千万数据只有 3~4 层

关键洞察：磁盘 IO 以页为单位（InnoDB 默认 16KB），一次 IO 的成本远高于内存里比较几百次。所以要让树尽量「矮胖」——每个节点装满一整页、塞几百上千个键，层数就压下来了。这正是 B+ 树的设计。

2. B+ 树的结构

                    ┌─────────────────────┐
        根节点       │  10   |  50   |  90  │          ← 只存键+指针
                    └──┬───────┬───────┬──┘
              ┌────────┘       │       └────────┐
        ┌─────▼─────┐   ┌─────▼─────┐   ┌──────▼────┐
 内节点  │ 10|20|35  │   │ 50|65|78  │   │ 90|95|99  │   ← 只存键+指针
        └─┬──┬──┬───┘   └───────────┘   └───────────┘
      ┌───┘  │  └───┐
 ┌────▼──┐┌──▼───┐┌─▼─────┐
 │10..19 ││20..34││35..49 │  ...                        ← 叶子节点：存数据
 │ 整行  ││ 整行  ││ 整行  │
 └───┬───┘└──┬───┘└──┬────┘
     └──────▶└──────▶ ...   叶子间双向链表，支撑范围扫描

B+ 树（对比 B 树）的三个要点：

只有叶子节点存数据，内节点只存键和子节点指针——内节点能塞更多键，树更矮；
叶子节点之间用双向链表串起来——范围查询定位到起点后顺着链表扫即可，不用回到树上；
所有叶子在同一层，任何查询的 IO 次数稳定。

算一笔账：主键 BIGINT(8 字节) + 指针(6 字节) = 14 字节，一个 16KB 内节点约存 1170 个键；叶子节点按每行 1KB 算存 16 行。三层 B+ 树容量约 1170 × 1170 × 16 ≈ 2190 万行——查任何一行最多 3 次页读取，根节点和大部分内节点还常驻 Buffer Pool，实际磁盘 IO 往往只有 1 次。

这也解释了第 6 章的伏笔：为什么 LIKE 'abc%' 能走索引而 '%abc' 不能——B+ 树按键有序排列，前缀确定就能定位子树；开头不确定则无从下手。

3. 聚簇索引：数据即索引

InnoDB 的表本身就是一棵按主键组织的 B+ 树，叶子节点存的就是完整的行数据——这叫聚簇索引（clustered index）。「表」和「主键索引」是同一个东西，数据的物理组织顺序就是主键顺序。

由此推出三个重要结论：

主键查询最快：一次 B+ 树查找直达整行；
主键要短：下一节会看到，所有二级索引的叶子都要存主键值，主键越长所有索引越臃肿。BIGINT 8 字节很合适，UUID 字符串 36 字节就很糟；
主键要趋势递增：新行总是追加到最右侧叶子页，顺序写。随机主键（如 UUID）会插到树的任意位置，导致页分裂——目标页满了就得分裂成两页、挪一半数据，写放大且页利用率下降。

自增主键：          随机主键（UUID）：
[1|2|3][4|5|6][7|8|_]   [a3|c1|f2][b7|d4|e9] ← 新值 c8 要插中间
          ↑ 顺序追加            ↑ 页满 → 分裂 → 挪数据

4. 二级索引与回表

在非主键列上建的索引叫二级索引（secondary index）。它也是一棵 B+ 树，但叶子节点不存整行，只存「索引列值 + 主键值」：

二级索引查询与回表

-- users 表：id 主键，uk_email 二级索引
SELECT * FROM users WHERE email = 'alice@example.com';
 
-- 需要 email 之外的列 → 走 uk_email 后必须回表
EXPLAIN SELECT * FROM users WHERE email = 'alice@example.com';
 
-- 只要 email 和主键 id，二级索引叶子上就有 → Extra 出现 Using index，不回表
EXPLAIN SELECT id FROM users WHERE email = 'alice@example.com';

执行过程分两步：

第 1 步：走 uk_email 的 B+ 树
   email='alice@ex.com'  ──▶  叶子节点：(alice@ex.com, id=1)
                                              │ 拿到主键
第 2 步：回表──用 id=1 再走一次聚簇索引        ▼
   id=1  ──▶  聚簇索引叶子：完整的行 (1, alice, alice@ex.com, ...)

第 2 步就叫回表（书里也叫 Bookmark Lookup）。一次二级索引查询 = 两次 B+ 树查找。

回表的代价在范围查询返回大量行时急剧放大：二级索引上拿到 10 万个主键，就要回聚簇索引查 10 万次，而这些主键在聚簇索引里是随机分布的——10 万次随机 IO 可能比全表顺序扫描还慢。这就是优化器有时「有索引却不走」的根本原因：它算过账了。

如果查询的列全部包含在二级索引里，就不用回表——这叫覆盖索引，是下一章的重点优化手段。

5. 数据页与行格式

5.1 页的内部结构

页（16KB）是 InnoDB 管理存储的最小单位，行在页内的组织：

┌────────────────────────────┐
│ 页头（38B）：页号/前后页指针  │  ← 前后页指针构成叶子链表
├────────────────────────────┤
│ 行记录1 → 行记录2 → 行记录3  │  ← 行之间单链表相连，按主键升序
│ ...（堆式存放，逻辑有序）     │
├────────────────────────────┤
│ 空闲空间                    │
├────────────────────────────┤
│ 页目录：稀疏的槽指针数组      │  ← 页内二分查找用
├────────────────────────────┤
│ 页尾（8B）：校验和           │
└────────────────────────────┘

页内查找先在页目录里二分定位到槽，再沿链表顺序找几步——所以「定位一行」= 树上找到页 + 页内二分，都很快。

5.2 行格式（ROW_FORMAT）

8.0 默认 DYNAMIC 行格式，要点：

每行除了列数据，还有隐藏列：row_id（无主键时）、trx_id（最近修改事务，6 字节）、roll_pointer（指向 undo log，7 字节）——后两个是 MVCC 的基石，第 17 章重逢；
变长列（VARCHAR/TEXT）太长时，页内只留 20 字节指针，数据放溢出页。这就是「大字段拖慢全表」的原因之一；
一个页至少放 2 行，单行上限约 8000 字节（不含溢出部分）。

查看索引与行格式

-- 每个索引由哪些列按什么顺序组成
SELECT index_name, seq_in_index, column_name, non_unique
FROM information_schema.statistics
WHERE table_schema = 'shop' AND table_name = 'orders'
ORDER BY index_name, seq_in_index;
 
-- 表的引擎、行格式与行数估算
SELECT table_name, engine, row_format, table_rows
FROM information_schema.tables
WHERE table_schema = 'shop';

在 mysql 客户端里也可以用 SHOW TABLE STATUS LIKE 'orders'\G 竖排查看同样的信息。

⚠️频繁 UPDATE 变长列会造成页碎片

把 VARCHAR 从短改长，原位置放不下就要迁移行、留下碎片；大量删除同样留洞。表经历大规模增删改后，OPTIMIZE TABLE 重建可回收空间、恢复页的紧凑度。

ℹ️为什么范围查询也快

WHERE id BETWEEN 100 AND 200：树上定位 id=100 所在叶子页（3 次页访问），然后沿叶子链表顺序扫到 200 为止。定位一次 + 顺序读——B+ 树对范围查询的友好是哈希索引永远给不了的。

小结

B+ 树矮胖：内节点只存键、叶子存数据且链表相连，千万行 3 层搞定
InnoDB 表 = 聚簇索引：叶子就是整行，主键查询一步到位
主键要「短 + 趋势递增」：短让二级索引瘦，递增避免页分裂
二级索引叶子存「索引列 + 主键」，查其他列要回表；回表多了不如全扫，优化器会算账
行里的 trx_id 和 roll_pointer 是 MVCC 伏笔；大字段会溢出页外

🎯练习

估算：主键 BIGINT、行均 200 字节的表，三层 B+ 树大约能存多少行？（内节点键+指针按 14 字节算）
对 users 表分别执行按 id 查询和按 email 查询，口述两者的 B+ 树访问路径差异（几棵树、几步、有无回表）。
解释：为什么 SELECT id FROM users WHERE email = 'x' 比 SELECT * FROM users WHERE email = 'x' 理论上更快？（提示：覆盖索引，下一章展开）