第 23 章 索引原理与设计

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

三层 B+ 树：扇出 1170、每叶 16 行 ⟹ 约 2100 万行

                       [ 根页 root：仅键 + 子页号 ]
                        /            |            \
                       /             |             \
        [非叶页 L2-a]  ...   [非叶页 L2-b]  ...   [非叶页 L2-c]   ← 1170 个子页
               \               |                /
                \              |               /
        ┌───────────┬───────────┬───────────┬───────────┐
        │ 叶页 P1   │ 叶页 P2   │ 叶页 P3   │  ...      │         ← 1170 × 1170 个叶页
        │ 行 行 ... │ 行 行 ... │ 行 行 ... │           │
        └─────┬─────┴─────┬─────┴─────┬─────┴─────┬─────┘
              └───────────┴───────────┴───────────┘
                叶页双向链表：范围扫描 = 顺序 I/O
                每个非叶页还带前驱/后继页号 + 页目录（page directory）

树高与承载量估算（页 16 KB = 16384 B；非叶条目 = 键 8 B + 页号 6 B = 14 B）
  扇出 F = 16384 / 14 ≈ 1170    每叶行数 R = 16384 / 1024 ≈ 16
  三层 = 1170 × 1170 × 16 ≈ 2.1×10⁷ 行（二层 1.9 万行，四层 ≈ 2.5×10¹⁰ 行）
  定位任意一行的页 I/O 次数 = 树高 = 3 次（根页常驻 buffer pool 时 = 2 次）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

聚簇索引（clustered index）与二级索引（secondary index）的叶页对比

  聚簇索引 B+ 树                          二级索引 B+ 树（以 idx_name 为例）
  ┌──────────────────────┐               ┌──────────────────────┐
  │ 非叶：键 = id        │               │ 非叶：键 = name      │
  └──────────┬───────────┘               └──────────┬───────────┘
             ↓                                      ↓
  ┌──────────────────────┐               ┌──────────────────────┐
  │ 叶页 = 数据页        │               │ 叶页 = (name, id)    │
  │ (id=1, name='a',... )│               │ ('a', 1)             │
  │ (id=2, name='b',... )│               │ ('b', 2)             │
  │ ...  整行都在叶页     │               │ ...  只有键 + 主键    │
  └──────────────────────┘               └──────────────────────┘
         命中即得整行                      命中只得到 id ⇒ 回表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

CREATE TABLE t_order (
    id      BINARY(16) NOT NULL,   -- 用 BINARY(16) 而非 CHAR(36)：索引条目与所有二级索引都小一半以上
    amount  DECIMAL(10,2) NOT NULL,
    PRIMARY KEY (id)
) ENGINE=InnoDB;

-- 第二参数 1 交换时间高位与低位，让二进制按时间有序：目的不是省字节，而是把随机插入点变成近似顺序插入点
INSERT INTO t_order (id, amount) VALUES (UUID_TO_BIN(UUID(), 1), 99.00);

-- 函数作用在常量而非列上，所以不破坏索引；若写成 WHERE BIN_TO_UUID(id) = '...' 则索引失效
SELECT BIN_TO_UUID(id) AS id_text, amount FROM t_order WHERE id = UUID_TO_BIN('...', 1);

1
2
3
4
5
6
7
8
9

-- 建表：联合索引 (a, b)，叶页实际存 (a, b, id)
CREATE TABLE t (id BIGINT PRIMARY KEY AUTO_INCREMENT, a INT, b INT, c VARCHAR(64), KEY idx_ab (a, b)) ENGINE=InnoDB;

-- 覆盖：需要 a、b、id 三列，全都在 idx_ab 叶页里，Extra 显示 Using index
EXPLAIN SELECT a, b, id FROM t WHERE a = 1 AND b = 2;
-- 不覆盖：c 不在 idx_ab 里，必须回表拿 c，Extra 不出现 Using index
EXPLAIN SELECT a, b, c FROM t WHERE a = 1 AND b = 2;
-- SELECT * 必然不覆盖（除非表只有这几列）：列越多越不可能被单个索引覆盖
EXPLAIN SELECT * FROM t WHERE a = 1 AND b = 2;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

联合索引 idx_abc (a, b, c) 在 B+ 树中的实际排序

  全树先按 a 升序排列；a 相同的记录按 b 升序；a、b 都相同的按 c 升序。
  （叶页内部：只存 (a, b, c, id)，id 是隐式附加的最后一列）

  叶页示意（每格 = 一条索引记录）：
  ┌──────────────┬──────────────┬──────────────┬──────────────┐
  │ (1, 5, 9, 11)│ (1, 6, 2, 12)│ (1, 6, 3, 13)│ (2, 4, 8, 14)│ ...
  └──────────────┴──────────────┴──────────────┴──────────────┘
    a=1 段 ─────────────────────→ │ a=2 段 → ...
                    b: 5 → 6 → 6（a 相同才有 b 有序）
                              同 a 同 b 时 c: 2 → 3

  ⟹ 三个可用性判据：
  ① a 是全局有序的 ⇒ 能用 a 做等值定位（B+ 树下降）
  ② b 只在 a 固定的子段内有序 ⇒ 必须 a 等值后 b 才可用
  ③ c 只在 a、b 都固定的子段内有序 ⇒ 必须 a、b 都等值后 c 才可用

1
2
3
4
5
6
7
8

索引 (a, b, c) 下 ORDER BY 的可用性

ORDER BY a, b, c        → 叶页天然有序，直接读，无排序
ORDER BY a DESC, b DESC → 整体反向扫描，无排序
ORDER BY a ASC, b DESC  → 混合方向，8.0 前必须 filesort（8.0 可建降序索引 idx(a ASC, b DESC) 消除）
ORDER BY b, c / a, c    → 跳过 a 或跳列 ⇒ filesort
WHERE a = 1 ORDER BY b  → a 已固定，该子段内 b 有序 ⇒ 无排序
WHERE a > 1 ORDER BY b  → a 是范围，b 跨段无序 ⇒ filesort

1
2
3
4
5

-- 索引 idx_abc (a, b, c)；b 是范围，c 不能用于定位，但可以下推过滤
EXPLAIN SELECT * FROM t WHERE a = 1 AND b > 2 AND c = 3;
-- Extra: Using index condition
--   含义：c = 3 在引擎层用索引中的 c 列过滤，过滤失败的记录不回表
--   注意：这不叫覆盖索引。SELECT * 仍需回表，只是回表次数被减少了

1
2
3
4
5
6
7
8

-- 隐式转换的两个方向必须分清：转换发生在列上才失效（phone VARCHAR(11)，idx_phone）
EXPLAIN SELECT * FROM t WHERE phone = 13800000000;   -- 列被转数字 ⇒ key = NULL
EXPLAIN SELECT * FROM t WHERE phone = '13800000000'; -- 常量是字符串 ⇒ key = idx_phone

EXPLAIN SELECT * FROM t WHERE uid = '100';           -- 数字列对字符串常量：key = idx_uid

-- 用 FORCE INDEX 验证"到底是不想用还是不能用"：强制后仍回退全表，说明统计信息判断成本更高
EXPLAIN SELECT * FROM t FORCE INDEX (idx_phone) WHERE phone = 13800000000;

1
2
3
4
5
6
7
8

-- 选择性口径 = 唯一值个数 / 总行数，越接近 1 越能筛掉人（0.001 基本等于没筛）
SELECT COUNT(DISTINCT user_id) / COUNT(*) AS sel_user,
       COUNT(DISTINCT status)  / COUNT(*) AS sel_status FROM t_order;

-- 前缀长度要"从短到长试"，找选择性逼近全列的最小 N：先定 8 个字符再验证是错的做法
SELECT COUNT(DISTINCT LEFT(email, 6))  / COUNT(*) AS p6,
       COUNT(DISTINCT LEFT(email, 10)) / COUNT(*) AS p10,
       COUNT(DISTINCT email)           / COUNT(*) AS full_sel FROM t_user;

1
2
3
4
5
6
7
8

列顺序决策树

  ① 收集高频查询，把每个候选列分类：等值列（= / IN）／范围列（> < BETWEEN LIKE 'x%'）／排序列
  ② 默认顺序：等值列在前 → 排序列居中 → 范围列在后
       （范围列后面的列无法定位，见 23.6；排序列只要前面全等值就仍可免排序）
  ③ 例外一：选择性极低的等值列（如 status 只有 3 个值）放后面，放最左反而让大片行挤在一起
  ④ 例外二：ORDER BY + LIMIT 且范围列在排序列之前时，优先保排序列免 filesort，范围列放最后
  ⑤ 例外三：为了让某条高频查询被覆盖，覆盖需求可以压过选择性优劣

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

-- 该删的索引要有量化证据：从未被使用过，或是更长索引的前缀冗余
SELECT * FROM sys.schema_unused_indexes;      -- 自 performance_schema 启动以来使用计数为 0
SELECT * FROM sys.schema_redundant_indexes;   -- redundant_index 是 covering_index 的前缀

-- 等价手写检查：逐位列名与序号都相同，才说明一个是另一个的前缀
SELECT t1.INDEX_NAME, t2.INDEX_NAME, GROUP_CONCAT(t1.COLUMN_NAME ORDER BY t1.SEQ_IN_INDEX) AS cols
FROM information_schema.STATISTICS t1
JOIN information_schema.STATISTICS t2
  ON t1.TABLE_SCHEMA = t2.TABLE_SCHEMA AND t1.TABLE_NAME = t2.TABLE_NAME
 AND t1.SEQ_IN_INDEX = t2.SEQ_IN_INDEX AND t2.INDEX_NAME <> t1.INDEX_NAME
WHERE t1.TABLE_SCHEMA = 'demo' AND t1.SEQ_IN_INDEX <= 3
GROUP BY t1.INDEX_NAME, t2.INDEX_NAME;

1
2
3
4
5
6
7
8
9

索引设计/评审的实际顺序

  ① 列出全部查询与读写比 → 每条查询标出等值列／范围列／排序列／返回列
  ② 定主键：自增 BIGINT（单库）或有序 16 B（分布式）
  ③ 为"最高频且最贵"的查询建第一条联合索引：等值列 → 排序列 → 范围列
  ④ 看能否覆盖（返回列并入索引，回表次数从 k 降到 k/页行数）
  ⑤ 其余查询先试复用已有索引的最左前缀，不能复用再新建
  ⑥ 长字符串列用前缀索引，长度由选择性测量决定
  ⑦ 上线后用 sys 库视图 + 慢查询复核；新增索引必须回答"它让哪些写入变慢了"