SYSTEM
索引
src/content/notes/system/索引.md 一、MySQL
1.1 索引
B+Tree 为什么适合做索引
B+Tree 是 B-Tree 的变体,核心设计取舍在于”磁盘 I/O 次数”和”范围查询效率”。
为什么不用 B-Tree:
B-Tree 的每个节点既存索引也存数据,导致单个节点能容纳的索引键数量减少。同样数据量下,B-Tree 的树更高,磁盘 I/O 次数更多。而且 B-Tree 的叶子节点之间没有指针连接,范围查询需要回到根节点重新遍历。
为什么不用 Hash 索引: Hash 索引虽然等值查询 O(1),但不支持范围查询(>、<、BETWEEN)、不支持排序(ORDER BY)、不支持最左前缀匹配。数据库场景中范围查询和排序极其频繁,Hash 索引适用面太窄。
B+Tree 的关键优势:
- 非叶子节点只存储索引键 + 指针,不存数据,一个节点能容纳更多键,树更矮。InnoDB 页大小默认 16KB,三阶 B+Tree 可支撑约 2000 万行数据。
- 数据全部存放在叶子节点,且叶子节点通过双向链表连接,范围查询只需定位起点后顺序扫描链表即可。
-- 查看索引树高度(通过 information_schema 间接估算)
SELECT
b.table_name,
b.index_name,
b.stat_value AS leaf_pages,
ROUND(b.stat_value * 16384 / 1024 / 1024, 2) AS leaf_size_mb
FROM information_schema.innodb_buffer_page b
WHERE b.index_name = 'PRIMARY';
聚簇索引 vs 非聚簇索引(回表、覆盖索引)
聚簇索引:索引和数据行存储在同一棵 B+Tree 中,叶子节点就是数据页本身。InnoDB 的主键索引就是聚簇索引,一张表只能有一个聚簇索引。
非聚簇索引(二级索引):叶子节点存储的是索引键值 + 主键值,而非完整数据行。通过二级索引查到主键后,还需要回聚簇索引中查找完整数据,这个过程叫回表。
-- 假设有表:user(id PK, name, age, city),在 city 上建了二级索引 idx_city
-- 下面这条查询需要回表:
SELECT * FROM user WHERE city = '北京';
-- 1. 先走 idx_city 找到主键 id
-- 2. 再回聚簇索引查完整行数据
-- 覆盖索引:查询字段全在索引中,无需回表
SELECT id, city FROM user WHERE city = '北京';
-- Extra 列显示 Using index,表示走了覆盖索引
为什么 InnoDB 选择聚簇索引存储:聚簇索引将索引和数据合并在一棵 B+Tree,主键查询只需一次 I/O 即可拿到完整行数据。非聚簇索引虽然多一次回表,但因为主键值在索引中已排序,回表操作是主键查找,效率很高。
联合索引最左前缀原则
联合索引 (a, b, c) 在 B+Tree 中按 a→b→c 的顺序排列。最左前缀原则要求查询条件必须从联合索引的最左列开始使用,否则无法走索引。
-- 联合索引 idx_abc(a, b, c)
-- 能走索引的情况:
SELECT * FROM t WHERE a = 1; -- 使用 a
SELECT * FROM t WHERE a = 1 AND b = 2; -- 使用 a, b
SELECT * FROM t WHERE a = 1 AND b = 2 AND c = 3; -- 使用 a, b, c
SELECT * FROM t WHERE a = 1 AND c = 3; -- 只能用到 a(索引下推前只走 a)
-- 不能走索引的情况:
SELECT * FROM t WHERE b = 2; -- 缺少最左列 a
SELECT * FROM t WHERE b = 2 AND c = 3; -- 缺少最左列 a
为什么这样设计:B+Tree 的排序规则是先按 a 排序,a 相同再按 b 排序,b 相同再按 c 排序。如果跳过 a 直接查 b,B+Tree 中的数据在 b 列上并不全局有序,无法利用二分查找。
索引下推 ICP(Index Condition Pushdown)
MySQL 5.6 引入的优化。在没有 ICP 时,存储引擎根据联合索引取出满足最左前缀的记录后,全部回表交给 Server 层过滤其余条件。ICP 将部分 WHERE 条件”下推”到引擎层,在回表前先过滤,减少回表次数。
-- 联合索引 idx_name_age(name, age)
SELECT * FROM user WHERE name LIKE '张%' AND age > 18;
-- 无 ICP:引擎层按 name 前缀匹配取出所有"张X"记录,全部回表,Server层再过滤 age>18
-- 有 ICP:引擎层取出"张X"后,先用 age>18 过滤,只对满足条件的记录回表
-- Explain 的 Extra 列显示 "Using index condition"
面试题
Q:为什么 MySQL 用 B+Tree 而不是 B-Tree?
A:B+Tree 非叶子节点只存索引不存数据,单页能容纳更多键,树更矮,磁盘 I/O 更少;叶子节点通过双向链表连接,范围查询和排序效率远高于 B-Tree 需要中序遍历。B-Tree 每个节点都存数据,导致树更高,且叶子节点无链表连接,范围查询需要多次回到根节点。
Q:什么是覆盖索引?什么是回表?
A:覆盖索引指查询所需的所有字段都包含在索引中,引擎层直接从索引返回数据,无需回聚簇索引查完整行,Extra 显示 Using index。回表是指通过二级索引拿到主键值后,还要去聚簇索引中查找完整数据行的过程。覆盖索引避免了回表,减少磁盘 I/O,应尽量让查询只返回索引覆盖的列。
Q:联合索引 (a,b,c),哪些查询能走索引?
A:能走索引:a=1、a=1 AND b=2、a=1 AND b=2 AND c=3、a=1 AND c=3(仅 a 部分走索引,ICP 下推后 b 仍可参与过滤但不算走索引范围扫描)。不能走索引:b=2、b=2 AND c=3(缺少最左列 a)、a>1 AND b=2(a 走范围扫描后 b 无法有序,无法利用索引)。
1.2 事务隔离级别
四种隔离级别 + 对应问题
| 隔离级别 | 脏读 | 不可重复读 | 幻读 | 说明 |
|---|---|---|---|---|
| READ UNCOMMITTED (RU) | 可能 | 可能 | 可能 | 能读到未提交的数据 |
| READ COMMITTED (RC) | 避免 | 可能 | 可能 | 只能读到已提交的数据 |
| REPEATABLE READ (RR) | 避免 | 避免 | 可能 | 同一事务内多次读同一行结果一致 |
| SERIALIZABLE | 避免 | 避免 | 避免 | 串行化执行,完全隔离 |
- 脏读:事务 A 读到了事务 B 未提交的数据,B 回滚后 A 读到的是无效数据。
- 不可重复读:事务 A 两次读同一行,中间事务 B 修改了该行并提交,A 两次读到不同值。
- 幻读:事务 A 两次执行同一范围查询,中间事务 B 新增/删除了行,A 第二次多/少了行。
MySQL 默认 RR,为什么不是 RC
MySQL InnoDB 默认隔离级别是 RR(可重复读),而 Oracle、PostgreSQL 等数据库默认 RC。MySQL 选择 RR 的原因与主从复制有关:
早期 MySQL 的主从复制基于 binlog_format=statement,主库按语句顺序写入 binlog,从库按顺序回放语句。在 RC 隔离级别下,事务的执行顺序可能影响结果——例如先 UPDATE 后 SELECT,与先 SELECT 后 UPDATE 的结果不同,导致主从数据不一致。RR 级别下 InnoDB 通过 Next-Key Lock 锁住范围,保证同一事务内相同查询结果一致,使 statement 格式 binlog 的复制是安全的。
不过现代 MySQL 也支持 binlog_format=row,基于行的复制不依赖语句顺序,因此很多互联网公司(如阿里)将隔离级别改为 RC 以提升并发性能。
面试题
Q:MySQL 的四种事务隔离级别?
A:READ UNCOMMITTED 可能脏读;READ COMMITTED 避免脏读但可能不可重复读;REPEATABLE READ 避免脏读和不可重复读,InnoDB 在 RR 级别通过 Next-Key Lock 也能避免大部分幻读;SERIALIZABLE 完全串行化避免所有问题但性能最差。MySQL 默认 RR,原因是配合 statement 格式 binlog 保证主从复制一致性。实际生产中很多公司改为 RC 提升并发度,配合 row 格式 binlog。
1.3 MVCC
undo log 版本链
MVCC(多版本并发控制)的核心思路:读操作不阻塞写操作,写操作也不阻塞读操作。每行数据维护多个历史版本,读操作根据自己的可见性规则选择合适的版本。
InnoDB 每行数据隐藏了两个字段:trx_id(最近修改该行的事务ID)和 roll_pointer(指向 undo log 中该行的上一个版本)。每次更新一行,旧值被写入 undo log,roll_pointer 指向旧版本,多个版本通过 roll_pointer 串联成一条版本链。
当前行数据 (trx_id=300)
└─ roll_pointer → undo log v2 (trx_id=200)
└─ roll_pointer → undo log v1 (trx_id=100)
ReadView 生成时机(RC vs RR 的区别)
ReadView 是事务在读取数据时生成的”快照”,包含当前活跃(未提交)事务的 ID 列表。通过 ReadView 判断某个版本对当前事务是否可见:
min_trx_id:ReadView 中活跃事务的最小 IDmax_trx_id:下一个将被分配的事务 ID- 可见性判断规则:
trx_id < min_trx_id:事务已提交,可见trx_id >= max_trx_id:事务在 ReadView 生成后才启动,不可见min_trx_id <= trx_id < max_trx_id:若 trx_id 在活跃列表中则不可见,否则可见
RC 和 RR 的关键区别:
| ReadView 生成时机 | 效果 | |
|---|---|---|
| RC | 每条 SELECT 都生成新的 ReadView | 每次读都能看到最新已提交的数据 → 不可重复读 |
| RR | 事务内第一条 SELECT 时生成,后续复用 | 事务内多次读看到的数据一致 → 可重复读 |
面试题
Q:MVCC 是怎么实现的?
A:MVCC 通过 undo log 版本链 + ReadView 实现。每行数据有隐藏的 trx_id 和 roll_pointer,更新时旧值写入 undo log,通过 roll_pointer 串联成版本链。读操作生成 ReadView,包含当前活跃事务列表,按照 trx_id 与活跃列表的比较规则判断哪个版本可见。RC 隔离级别每次 SELECT 生成新 ReadView,所以能看到其他事务最新提交的修改(不可重复读);RR 隔离级别只在第一次 SELECT 时生成 ReadView,后续复用,所以整个事务内读到的数据一致。MVCC 只在快照读(普通 SELECT)生效,当前读(SELECT FOR UPDATE、UPDATE、DELETE)不走 MVCC 而是加锁。
1.4 锁
行锁、间隙锁、临键锁
InnoDB 行锁是加在索引上的,不是加在数据行上的。如果查询没有走索引,会导致锁升级为表锁。
| 锁类型 | 作用范围 | 说明 |
|---|---|---|
| Record Lock(记录锁) | 单行 | 锁住索引上的一条记录 |
| Gap Lock(间隙锁) | 开区间 (a, b) | 锁住两个记录之间的间隙,防止插入,解决幻读 |
| Next-Key Lock(临键锁) | 前闭后开 (a, b] | Record Lock + Gap Lock,锁住记录及其左侧间隙 |
-- 表 t 有数据:id=10, id=20, id=30(id 是主键)
-- 事务 A 在 RR 级别下执行:
SELECT * FROM t WHERE id BETWEEN 15 AND 25 FOR UPDATE;
-- 会加 Next-Key Lock:(10, 20] 和 (20, 30)
-- 事务 B 执行 INSERT INTO t VALUES (16); 会被阻塞,因为 16 在 (10,20] 间隙内
唯一索引等值查询优化:当等值查询命中唯一索引时,Next-Key Lock 会退化为 Record Lock,不会锁住间隙,因为唯一索引已保证不会有重复值插入。
意向锁、MDL(元数据锁)
**意向锁(IS / IX)**是表级锁,作用是让”表锁”和”行锁”之间快速判断是否冲突。事务在加行级共享锁前先加表级 IS 锁,加行级排他锁前先加表级 IX 锁。这样当另一个事务要加表锁时,只需检查意向锁,不用逐行扫描。
MDL(Metadata Lock)元数据锁:MySQL 5.5 引入,保护表结构不被并发修改。事务访问表时自动加 MDL 读锁,执行 DDL(ALTER TABLE 等)时加 MDL 写锁。DDL 要等所有持有 MDL 读锁的事务释放,所以线上大表加字段容易导致阻塞甚至锁等待雪崩。
面试题
Q:MySQL 有哪些锁?间隙锁解决什么问题?
A:按粒度分:表锁(意向锁 IS/IX、MDL 元数据锁、AUTO-INC 锁)和行锁(Record Lock 记录锁、Gap Lock 间隙锁、Next-Key Lock 临键锁)。按模式分:共享锁(S,读锁)和排他锁(X,写锁)。间隙锁锁住索引记录之间的间隙,防止其他事务在间隙中插入新行,从而解决 RR 隔离级别下的幻读问题。Next-Key Lock 是 InnoDB 在 RR 级别下默认的行锁类型,等于 Record Lock + Gap Lock,锁住记录及其左侧间隙。需要注意的是间隙锁只在 RR 级别存在,RC 级别没有间隙锁。