Appearance
索引与 B+ 树
概念
上一章把 SQL 讲通了，但有个问题一直没回答：数据库凭什么能把 WHERE sno = 'S3' 做得那么快？
如果没有额外结构，它只能一行一行看过去——这叫全表扫描。一亿行的表，就得看一亿行。SQL 是声明式的，可声明式的语言也没法凭空知道数据在哪。
索引（index）就是为解决这件事而额外维护的数据结构：把"要找的那一列"按某种顺序另存一份，并记住每一份对应原表的哪一行。以后再来找，先查索引定位，再去原表取行。
类比很好用：索引就是书后面的索引页。有了它，你不必从第一页翻到最后一页找"B+ 树"这个词在哪——直接翻到索引页，看到页码，跳过去就行。代价也一样：书厚了几页，而且每次改内容，索引页也得跟着改。
一句话概括索引的本质：拿空间和写速度，换读速度。
原理
一、先算一笔账：一次查找到底要读几页
数据不在内存里，在磁盘上。磁盘的读写单位是页（InnoDB 默认 16 KB）。所以衡量查找快不快，看的不是"比较了多少次"，而是"读了多少页"。
- 全表扫描 100 万行，每页装 16 行 → 62500 页。
- 走 B+ 树索引，树高 3 层 → 3 页。
两者相差 两万多倍。这就是索引存在的全部理由，也是本章第一个要算清的数。
二、为什么是 B+ 树
这一节是上一章与数据结构的交汇点。B 树与 B+ 树的完整定义、插入分裂、删除合并，都在 B 树与 B+ 树 里讲过，这里只说数据库为什么选 B+ 树。
| 比较项 | B 树 | B+ 树 | 对数据库意味着什么 |
|---|---|---|---|
| 非叶结点存什么 | 关键字 + 记录指针 | 只存索引项，不存记录 | 同样一页能塞更多索引项，树更矮 |
| 关键字出现次数 | 全树一次 | 非叶的是叶子里的复本 | 内部结点纯粹是"路标" |
| 查找终止位置 | 命中非叶结点即可返回 | 必须走到叶子 | 每次查找路径长度一样，耗时稳定 |
| 叶子之间 | 无联系 | 有序链表连起来 | 范围查询变成顺序读 |
最后两行才是关键。数据库的查询很少只找一个值：
WHERE id BETWEEN 100 AND 200— 范围查询ORDER BY create_time— 排序WHERE a = 1 AND b > 5— 前缀 + 范围
这些在 B+ 树上都能靠沿着叶子链表往下扫完成，而 B 树必须回头做中序遍历。"叶子连成链表"这一条，就是 B+ 树取代 B 树成为索引标配的根本原因。
三、两种组织方式：聚簇索引与二级索引
同一个 B+ 树结构，按"叶子里存什么"分成两类：
| 类型 | 叶子存什么 | 一张表能有几个 |
|---|---|---|
| 聚簇索引（clustered） | 整行数据 | 只有一个（InnoDB 里就是主键索引） |
| 二级索引（secondary，也叫辅助索引、非聚簇索引） | 索引列 + 主键值 | 可以有多个 |
聚簇索引决定了"数据在磁盘上按什么顺序摆"——表本身就是一棵按主键排序的 B+ 树。所以在 InnoDB 里：
- 按主键查：一遍 B+ 树就拿到整行。
- 按别的列查：先在二级索引里找到主键，再拿主键回聚簇索引取整行——这一步叫回表。
回表读的页数是翻倍的：二级索引 3 页 + 聚簇索引 3 页 = 6 页。
四、覆盖索引：不回表
如果查询要的列全都在索引里，就不用回表了——这就叫覆盖索引（covering index）。
sql
-- 如果建了索引 idx(city, sname)
SELECT sname FROM S WHERE city = '北京'; -- 两列都在索引里 -> 不回表
SELECT * FROM S WHERE city = '北京'; -- 要所有列 -> 必须回表代价对比很清楚：6 页 vs 3 页，省 50%。
这也是为什么 SELECT * 常常被劝退：它天然放弃了覆盖索引的可能。
五、复合索引与最左前缀
复合索引就是把几列拼在一起建一棵树，排序规则是"先按第一列排，第一列相同再按第二列排，以此类推"。这件事带来一条硬规矩：
最左前缀原则——只有从索引最左边那一列开始、连续的条件，才能用来定位。
对索引 (a, b, c)：
| 条件 | 用得上的列 | 说明 |
|---|---|---|
a | 1 列 | 全部用上 |
a AND b | 2 列 | 全部用上 |
a AND b AND c | 3 列 | 全部用上 |
b / c / b AND c | 0 列 | 完全用不上索引 |
a AND c | 1 列 | a 能定位，c 只能退化成过滤 |
记住一句话：索引是字典的目录，你得从第一个字开始查。中间断了，右边的就用不上。
（有个细节别记死：a AND c 里 c 并非"白写"，如果 a 的选择性很差，优化器可能干脆扫索引 (a,b,c) 全表覆盖，比回表便宜。规矩是"能不能当查找条件"，不是"有没有用"。）
六、索引失效的常见情形
建了索引不等于用得上。下面几种写法会让索引当场作废：
| 写法 | 为什么失效 |
|---|---|
WHERE YEAR(create_time) = 2026 | 对索引列做了函数运算，树是按原值排的，算完就废了 |
WHERE age = '20'（age 是数字） | 隐式类型转换，等于给列加了个转换函数 |
WHERE name LIKE '%张' | 前置通配符，第一个字符都不确定，没法定位起点 |
WHERE a = 1 OR b = 2（只有 a 建了索引） | OR 两边都要能走索引，否则只能全表扫 |
WHERE a + 1 = 3 | 运算写在列这一侧 |
共同的病根只有一个：索引树是按列的"原值"排序的。只要你在列上套了任何函数或转换，排序顺序就对不上了。
LIKE 的三种写法值得单独记：
| 写法 | 结果 |
|---|---|
LIKE 'abc%' | 能定位前缀 abc（3 个字符） |
LIKE 'a%c' | 只能用上前缀 a（1 个字符） |
LIKE '%abc' | 用不上 |
LIKE 'ab_' | 能定位前缀 ab（_ 是单字符通配符） |
规律：能确定多少连续前缀，就能定位多少。
七、哈希索引与 B+ 树索引
| 哈希索引 | B+ 树索引 | |
|---|---|---|
| 单值查找 | O(1)，一次定位 | O(log n)，3 次 I/O |
| 范围查找 | 做不到 | 沿叶子链表扫 |
| 排序 | 无序，用不上 | 天然有序 |
| 最左前缀 | 不适用（要全键） | 支持 |
| 典型用户 | Memory 引擎、Redis | InnoDB 的默认索引 |
哈希索引单点查找更快，却做不了范围查询和排序。数据库的主要查询里范围与排序占比很高，所以 B+ 树成了默认选择——不是因为它在某一点上最快，而是因为它在所有场景下都不差。
示例
例 1：把三层 B+ 树的账算出来（C）
#include <stdio.h>
int main(void) {
long long page = 16384; /* InnoDB 默认页大小 16 KB */
long long key = 8; /* 主键 BIGINT 占 8 B */
long long ptr = 6; /* 页号在 InnoDB 里占 6 B */
long long row = 1024; /* 假定每行 1 KB */
long long fanout = page / (key + ptr); /* 非叶结点能放几个索引项 */
long long leaf = page / row; /* 叶子结点能放几行 */
printf("页 %lld B，索引项 %lld + %lld = %lld B\n", page, key, ptr, key + ptr);
printf("扇出 = %lld / %lld = %lld\n", page, key + ptr, fanout);
printf("叶子 = %lld / %lld = %lld 行/页\n", page, row, leaf);
printf("2 层 = %lld * %lld = %lld 行\n",
fanout, leaf, fanout * leaf);
printf("3 层 = %lld * %lld * %lld = %lld 行\n",
fanout, fanout, leaf, fanout * fanout * leaf);
long long n = 1000000;
long long scan = (n + leaf - 1) / leaf; /* 向上取整：一共要读多少页 */
printf("全表扫描：%lld 行 / %lld 行每页 = %lld 页 I/O\n", n, leaf, scan);
printf("B+ 树查找：3 层 = 3 页 I/O\n");
printf("相差 %.2f 倍\n", (double)scan / 3.0);
printf("回表 3+3=6 页，覆盖索引 3 页，省 50.0%%\n");
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
页 16384 B，索引项 8 + 6 = 14 B
扇出 = 16384 / 14 = 1170
叶子 = 16384 / 1024 = 16 行/页
2 层 = 1170 * 16 = 18720 行
3 层 = 1170 * 1170 * 16 = 21902400 行
全表扫描：1000000 行 / 16 行每页 = 62500 页 I/O
B+ 树查找：3 层 = 3 页 I/O
相差 20833.33 倍
回表 3+3=6 页，覆盖索引 3 页，省 50.0%三个数字值得盯着看：
- 扇出 1170：一个非叶结点能指出 1170 条路。"宽"是 B+ 树矮的原因。
- 3 层装 2190 万行：而 4 层就是 256 亿行。层数每加一层，容量乘 1170，但 I/O 只多一次。
- 62500 页 vs 3 页：两万多倍的差距，全部来自"有没有一棵能快速定位的树"。
例 2：容量、最左前缀、LIKE 一次算清（Python）
import math
def dw(s):
"""显示宽度：中文算 2 列"""
return sum(2 if ord(c) > 0x2000 else 1 for c in str(s))
def pad(s, w):
return str(s) + " " * max(0, w - dw(str(s)))
def table(head, rows, gap=2):
data = [[str(c) for c in r] for r in rows]
w = [max([dw(head[i])] + [dw(r[i]) for r in data]) + gap for i in range(len(head))]
print(" " + "".join(pad(head[i], w[i]) for i in range(len(head))))
for r in data:
print(" " + "".join(pad(r[i], w[i]) for i in range(len(head))))
PAGE = 16384 # InnoDB 默认页大小 16 KB
KEY, PTR = 8, 6 # 主键 BIGINT 8 B + 页号 6 B
FANOUT = PAGE // (KEY + PTR)
ROW = 1024 # 假定每行 1 KB
LEAF = PAGE // ROW
print("=== 1. 一个非叶结点能放多少个索引项（扇出） ===")
print(" 页 %d B，索引项 = 主键 %d B + 页号 %d B = %d B" % (PAGE, KEY, PTR, KEY + PTR))
print(" 扇出 = %d / %d = %d（向下取整，剩 %d B 放页头等开销）"
% (PAGE, KEY + PTR, FANOUT, PAGE - FANOUT * (KEY + PTR)))
print()
print("=== 2. 一个叶子结点能放多少行（行大小 1 KB） ===")
print(" %d / %d = %d 行/页" % (PAGE, ROW, LEAF))
print()
print("=== 3. 各层数能存多少行 ===")
table(["层数", "算式", "可存行数"],
[[1, "%d" % LEAF, LEAF],
[2, "%d × %d" % (FANOUT, LEAF), FANOUT * LEAF],
[3, "%d × %d × %d" % (FANOUT, FANOUT, LEAF), FANOUT * FANOUT * LEAF],
[4, "再多乘一层", FANOUT ** 3 * LEAF]])
print(" 三层就过了 2000 万 —— 这就是'三层 B+ 树撑起一张大表'这句话的来历。")
print()
N = 1000000
print("=== 4. 100 万行：全表扫描 vs 索引查找（I/O 次数） ===")
scan = math.ceil(N / LEAF)
print(" 全表扫描：%d 行 / %d 行每页 = %d 页 I/O" % (N, LEAF, scan))
print(" B+ 树查找：3 层 = 3 页 I/O")
print(" 相差 %.2f 倍" % (scan / 3))
print()
print("=== 5. 回表与覆盖索引 ===")
print(" 二级索引找到主键：3 页；拿着主键回聚簇索引取整行：又 3 页 -> 共 6 页")
print(" 覆盖索引（需要的列都在索引里，不用回表）：3 页")
print(" 省 (6 − 3) / 6 = %.1f%%" % ((6 - 3) / 6 * 100))
print()
print("=== 6. 复合索引 (a, b, c) 的最左前缀 ===")
def usable(prefix, cols):
"""返回条件里能作为查找前缀用上的列数"""
n = 0
for i, c in enumerate(prefix):
if i < len(cols) and c == cols[i]:
n += 1
else:
break
return n
cols = ("a", "b", "c")
table(["WHERE 条件", "能当查找用的列", "说明"],
[[" AND ".join(p), str(usable(p, cols)),
"全部用上" if usable(p, cols) == len(p) else
("用不上索引" if usable(p, cols) == 0
else "只用上前 %d 列，后面的退化成过滤" % usable(p, cols))]
for p in [("a",), ("a", "b"), ("a", "b", "c"),
("b",), ("c",), ("b", "c"), ("a", "c")]])
print()
print("=== 7. LIKE 能不能用索引 ===")
rows = []
for pat in ["'abc%'", "'%abc'", "'a%c'", "'ab_'", "'a_c'"]:
body = pat.strip("'")
if body.startswith("%"):
rows.append([pat, "不能", "开头就是通配符，前缀不确定"])
else:
head = ""
for ch in body:
if ch in "%_":
break
head += ch
rows.append([pat, "能", "能定位前缀 '%s'（%d 个字符）" % (head, len(head))])
table(["LIKE 模式", "用得上索引", "说明"], rows)
print()
print("=== 8. 行变大，层数不变，能装的行数变小 ===")
def cap(rowsize, h):
return FANOUT ** (h - 1) * (PAGE // rowsize)
table(["行大小", "叶子行数/页", "2 层可存", "3 层可存"],
[["%d B" % r, PAGE // r, cap(r, 2), cap(r, 3)] for r in [200, 512, 1024, 4096]])
print(" 行越大，叶子装得越少，树就得越高 —— 所以'大字段外置'不只是省磁盘，也省 I/O。")
print()
print("=== 9. 索引不是白拿的：写的时候要还 ===")
table(["二级索引个数", "插入一行要维护的索引数", "读加速", "写代价"],
[[k, 1 + k, "3 层 -> 3 页" if k else "无索引可走", "%d 处" % (1 + k)]
for k in [0, 1, 3, 6]])
print(" 每多一个索引，读多一条路，写就多维护一处 —— 索引是拿写换读，不是白拿。")
print(" 这也解释了一条经验：索引不是越多越好，没有查询用得上的索引就是纯负担。")
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
=== 1. 一个非叶结点能放多少个索引项（扇出） ===
页 16384 B，索引项 = 主键 8 B + 页号 6 B = 14 B
扇出 = 16384 / 14 = 1170（向下取整，剩 4 B 放页头等开销）
=== 2. 一个叶子结点能放多少行（行大小 1 KB） ===
16384 / 1024 = 16 行/页
=== 3. 各层数能存多少行 ===
层数 算式 可存行数
1 16 16
2 1170 × 16 18720
3 1170 × 1170 × 16 21902400
4 再多乘一层 25625808000
三层就过了 2000 万 —— 这就是'三层 B+ 树撑起一张大表'这句话的来历。
=== 4. 100 万行：全表扫描 vs 索引查找（I/O 次数） ===
全表扫描：1000000 行 / 16 行每页 = 62500 页 I/O
B+ 树查找：3 层 = 3 页 I/O
相差 20833.33 倍
=== 5. 回表与覆盖索引 ===
二级索引找到主键：3 页；拿着主键回聚簇索引取整行：又 3 页 -> 共 6 页
覆盖索引（需要的列都在索引里，不用回表）：3 页
省 (6 − 3) / 6 = 50.0%
=== 6. 复合索引 (a, b, c) 的最左前缀 ===
WHERE 条件 能当查找用的列 说明
a 1 全部用上
a AND b 2 全部用上
a AND b AND c 3 全部用上
b 0 用不上索引
c 0 用不上索引
b AND c 0 用不上索引
a AND c 1 只用上前 1 列，后面的退化成过滤
=== 7. LIKE 能不能用索引 ===
LIKE 模式 用得上索引 说明
'abc%' 能 能定位前缀 'abc'（3 个字符）
'%abc' 不能 开头就是通配符，前缀不确定
'a%c' 能 能定位前缀 'a'（1 个字符）
'ab_' 能 能定位前缀 'ab'（2 个字符）
'a_c' 能 能定位前缀 'a'（1 个字符）
=== 8. 行变大，层数不变，能装的行数变小 ===
行大小 叶子行数/页 2 层可存 3 层可存
200 B 81 94770 110880900
512 B 32 37440 43804800
1024 B 16 18720 21902400
4096 B 4 4680 5475600
行越大，叶子装得越少，树就得越高 —— 所以'大字段外置'不只是省磁盘，也省 I/O。
=== 9. 索引不是白拿的：写的时候要还 ===
二级索引个数 插入一行要维护的索引数 读加速 写代价
0 1 无索引可走 1 处
1 2 3 层 -> 3 页 2 处
3 4 3 层 -> 3 页 4 处
6 7 3 层 -> 3 页 7 处
每多一个索引，读多一条路，写就多维护一处 —— 索引是拿写换读，不是白拿。
这也解释了一条经验：索引不是越多越好，没有查询用得上的索引就是纯负担。四条结论：
- C 段与 Python 段的前四个数完全一致：扇出 1170、叶子 16、3 层 21902400、全表 62500 页。同一套算术，两种实现。
- 行越大，树的容量越小：行 200 B 时 3 层能装 1.1 亿，行 4 KB 时只剩 547 万——差 20 倍。"把大字段拆出去"不是洁癖，是让索引保持苗条。
- 最左前缀的边界很清楚：
(a, b, c)上，b、c、b AND c三条一列都用不上；a AND c只用得上a一列。 - 索引是双向的：读加速的代价写在第九节——多一个索引，插入一行就多维护一处。所以"给每列都建索引"是典型的负优化。
考点
考点
1. 三类查找的 I/O 次数
| 场景 | 页 I/O |
|---|---|
| 走 3 层 B+ 树索引取到行 | 3 |
| 走二级索引再回表 | 6（3 + 3） |
| 走覆盖索引（不回表） | 3 |
| 全表扫描 100 万行（16 行/页） | 62500 |
2. B+ 树的容量公式
- 扇出 = 页大小 ÷ (索引键长度 + 页号长度)。InnoDB 页 16 KB、主键 8 B、页号 6 B → 1170。
- 叶子行数 = 页大小 ÷ 行大小。
- h 层可存行数 = 扇出^(h−1) × 叶子行数。3 层 1 KB 行 → 21902400。
3. B+ 树胜过 B 树的两条理由（必须能说出）
- 非叶结点不存记录指针 → 同样的页能放更多索引项 → 树更矮。
- 叶子链表相连 → 范围查询与
ORDER BY变成顺序读，查找路径长度还恒定。
4. 聚簇 vs 二级索引
- 聚簇索引叶子存整行，一张表只能有一个（InnoDB 就是主键索引）；表本身按主键排序。
- 二级索引叶子存"索引列 + 主键"，可以有多个；查非索引列要回表。
- 因此：二级索引上的
SELECT *一定回表，按需选列才可能覆盖。
5. 最左前缀原则
索引 (a, b, c) 只在条件从 a 开始且连续时生效。判法就一句：在索引定义里从左往右逐列对，对到不相等就停。
6. 索引失效的五种写法
① 列上套函数（YEAR(col) = 2026）；② 隐式类型转换（字符串比数字列）；③ 前置通配符 LIKE '%x'；④ OR 的一侧没索引；⑤ 把运算写在列这一侧（a + 1 = 3）。
共同病根：索引按列的"原值"排序，一旦套函数，顺序就对不上。
7. 易错点清单
- 以为"建了索引就一定走索引"：优化器会算代价，选择性差的列（如性别）它宁可不走。
- 以为
a AND c在索引(a, b, c)上完全用不上：a能用上，c只是退化成过滤。 - 把"用上索引"等同于"效率高"：回表 6 页不一定比全表扫描便宜，行数少时才划算。
- 认为哈希索引更先进：它做不了范围查询和排序，所以数据库默认仍是 B+ 树。
- 记混"页"与"行"：磁盘 I/O 的单位是页，不是行——这是全章所有算法的基础。
- 忽略写代价：每个索引都要在插入/更新时同步维护，索引不是白拿的。
小结
- 索引是拿空间与写速度换读速度的辅助结构；衡量的尺子是读了多少页，不是比较了多少次。
- 数据库选 B+ 树，靠的是两条：非叶结点不存记录（树矮） 与 叶子连成链表（范围查询顺）。
- 聚簇索引叶子存整行、只有一个；二级索引叶子存"索引列 + 主键"，要回表；把需要的列放进索引就成覆盖索引，I/O 直接减半。
- 复合索引守最左前缀；列上套函数、隐式转换、前置通配符是索引失效的三大常见写法。
回到主线：SQL 说得再准、索引建得再好，只要多个用户同时改同一份数据，就会出问题——两个人同时读到旧值、同时写回，一个人的改动凭空消失。这一章只讲了"怎么找得快"，下一章要讲"怎么在并发下不出错"：事务与并发控制。
下一篇：事务与并发控制
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。