← 返回学习路线

SYSTEM

索引

八股1.1 索引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 中活跃事务的最小 ID
  • max_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 级别没有间隙锁。