高可用高性能存储应用

学习目标

学完本章你应该能够：

1. 讲清 B+Tree 为什么是索引的默认选择，以及它相比二叉树 / B-Tree 的本质差异。
2. 用自己的话解释回表、覆盖索引、最左匹配，并能在写 SQL 时主动避免回表。
3. 用 MVCC 三要素（隐藏字段 / Undo Log / ReadView）解释"读不阻塞写、写不阻塞读"是怎么实现的。
4. 说清 RC 与 RR 的本质区别是 ReadView 生成时机，以及 RR 如何在快照读与当前读下避免幻读。
5. 在面试中把主从复制、分库分表、一致性 Hash 讲成可对比的工程选型，而不是零散知识点。

前置知识：

• MySQL 基本使用与 SQL 基础
• 磁盘 I/O 与"页（Page）“的基本概念
• 至少听说过索引、事务、隔离级别这些词

本章你会动手做的事：

1. 用 EXPLAIN 验证一条 SELECT 是否走了覆盖索引，对比回表前后的 rows 与 Extra。
2. 开两个 MySQL 会话，实测 RC 与 RR 下"同一个事务内两次读同一行"的结果差异。
3. 用一致性 Hash 的伪代码，模拟一次节点扩容，数一数到底迁移了多少数据。

索引

索引的本质是什么

索引的本质是一种有序的数据结构，目的是加速数据的查找。

其核心思想——用额外的写入开销和存储空间，换取查询时的极速定位，把 O(n) 的全表扫描降到 O(log n) 甚至 O(1)。

1. 类比：书的目录

没有索引，数据库就像一本没有目录的字典，要查一个词只能从第一页逐页翻到最后。有了索引，你翻目录几秒定位到页码，直接翻过去。

2. 数据结构层面

索引底层是一种排序好的、支持快速二分查找的数据结构。MySQL InnoDB 用的是 B+Tree：

• 所有叶子节点按主键顺序存储，节点之间通过双向链表连接
• 既支持等值查询（二分定位到叶子节点）
• 也支持范围查询（链表遍历相邻节点）

3. 物理层面

索引本身存储在磁盘上，是独立数据页的集合（InnoDB 下存在于 .ibd 文件中）。

写维护代价：每次 INSERT / UPDATE / DELETE 操作，除了修改数据行本身，相关的索引页也要同步维护（页分裂、页合并、重排序等）。索引不是免费的——每多建一个索引，写入性能就多一份负担。

二叉树

1. 树的基本概念

数据结构中，树结构形状类似一棵倒立的大树，由一堆结点和边组成的具有层级关系的数据结构（非线性）。

2. 基础概念

3. 图示说明

graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> E((E))
    B --> F((F))
    C --> D((D))
    C --> G((G))

• A 为树根节点，也是 B、C 的父节点
• B、C 为 A 的子节点
• B 与 C 互为兄弟节点
• E、F、D、G 为叶子节点

4. 极端情况

graph TD
    A((A)) --> B((B))
    B --> C((C))
    C --> D((D))
    D --> E((E))
    E --> F((F))
    F --> G((G))

这种情况就像一个链表，每个节点只存储一个键值，导致树的高度过高。查询一条记录可能需要数十次甚至上百次磁盘随机 I/O，性能无法接受。从而出现了新的数据结构平衡二叉树

平衡二叉树

1. 图示说明

graph TD
    H((H)) -->|3| D((D))
    H -->|3| L((L))
    D -->|2| B((B))
    D -->|2| F((F))
    L -->|2| J((J))
    L -->|2| N((N))
    B -->|1| A((A))
    B -->|1| C((C))
    F -->|1| E((E))
    F -->|1| G((G))
    J -->|1| I((I))
    J -->|1| K((K))
    N -->|1| M((M))
    N -->|1| O((O))

2. 基础概念

• 相对平衡，左右两个子树的深度差绝对值不能超过1
• 左右两个子树也必须是平衡二叉树
• 可以避免二叉树的极端情况

3. 平衡二叉树的不足

InnoDB 默认页大小 16KB，但在平衡二叉树中，每个节点只存 1 条数据（1 个 key + 子节点指针）。一个 16K 的页就装了 1 条记录，严重浪费磁盘空间和 I/O，数据量大时节点暴增，树的高度飙升，查询磁盘I/O次数暴涨。

B Tree

1. 图示说明

2. 基础概念

• 每个节点最多有 m 个子节点
• 除根节点外，所有非叶子节点，子节点数量 ≥ ⌈m/2⌉（向上取整）
• 根节点最少可以有 2 个子节点（如果根不是叶子）
• 一个节点内的关键字（key）数量 = 子节点数 − 1
• 节点内部关键字从小到大有序排列
• 所有叶子节点在同一层（核心：绝对平衡）

举例：4 阶 B 树（最多 4 个子节点）
每个节点关键字数量：1～3 个
非根节点最少 2 个子节点，最少 1 个 key

3. 极端情况

• 节点又存数据又存索引
• 每个节点的空间被Data占用
• 一次磁盘I/O读取的数据不多
• 范围查询要中序遍历，效率一般

B+Tree

1. 图示说明

2. 基础概念

• 非叶子节点只保存索引，Data全在叶子节点
• 每个节点能装更多索引
• 一次磁盘I/O读取的数据更多
• 范围查询只需顺着链表扫一遍

MySQL如何使用索引

Myisam

1. 文件结构

• 表结定义信息（*.frm）
• 索引文件（*.myi）
• 数据文件（*.myd）

2. 图示说明

InnoDB

1. 文件结构

• 表定义信息（*.frm）
• 数据和索引（*.ibd）

2. 图示说明

回表

1.图示说明

2. 基础概念

1. name 普通二级索引叶子节点存储：索引列 name + 主键值，不存放完整行数据；
2. 查询时先通过 name 索引找到对应的主键；
3. 拿着主键再去主键索引（聚簇索引）查找完整行数据；
4. 这个二次查表的动作，就叫回表。

3. InnoDB 有两种索引

• InnoDB 有两种索引： 聚簇索引（主键索引） 叶子节点 = 完整一行数据，就是图左侧结构。
• 二级索引（普通索引，name 索引） 叶子节点 = 索引字段 + 主键 ID，没有全部数据（图右侧）。

回表定义： 当 SQL 使用二级索引查询，需要读取不在二级索引叶子节点里的字段时，利用二级索引拿到的主键，再去聚簇索引检索完整数据的过程。

4. 结合示例理解

假设有表：

user(id PRIMARY KEY, name, age)
-- name建立普通索引

场景 1：触发回表

SELECT age FROM user WHERE name='张三';

执行流程（对应你的图）：

1. 在 name 索引 B + 树搜索「张三」→ 叶子节点拿到主键 id=1
2. 回表: 拿着 id=1 去主键索引 B + 树查找，取出整行数据，获取 age 这条 SQL 发生回表

场景 2：不回表 → 覆盖索引

SELECT id FROM user WHERE name='张三';

二级索引叶子本身就保存 name + id，需要的数据索引里全都有，不需要访问主键索引，避免回表。 这就是优化手段：建立覆盖索引消除回表。

5. 回表带来的性能问题

• 需要两次 B + 树查找（二级索引一次 + 主键索引一次）；
• IO 次数翻倍，大数据量、分页场景下性能衰减明显；
• 如果一条 SQL 匹配大量数据，会产生大量随机 IO，查询变慢。

6. 如何避免回表

核心方案：覆盖索引（Covering Index） 把查询用到的所有字段全部加入二级索引，让数据库仅依靠二级索引就能拿到全部所需数据，不用访问主键索引。

-- 创建联合索引，name+age
CREATE INDEX idx_name_age ON user(name, age);
-- 此时 SELECT age FROM user WHERE name='张三'; 不再回表

索引覆盖

如何避免回表上已经写了

索引面试题

1. MySQL 为什么不用二叉搜索树（BST）或平衡二叉树（AVL/红黑树）？

• 磁盘 I/O 瓶颈：数据库数据存储在磁盘上，而磁盘访问速度远慢于内存。BST 和 AVL 树每个节点只存储一个键值，导致树的高度过高。查询一条记录可能需要数十次甚至上百次磁盘随机 I/O，性能无法接受。
• 局部性原理失效：B+Tree 的节点大小通常设置为操作系统页的大小（如 16KB），一次 I/O 可以加载多个键值到内存中利用预读机制；而二叉树节点小且分散，无法有效利用磁盘顺序读取的优势。
• 范围查询效率低：二叉树结构不适合做区间扫描，而 B+Tree 叶子节点通过链表相连，天然支持高效的范围查询和排序。

2. MySQL 为什么用 B+Tree，不用 B-Tree？

• 非叶子节点不存数据：B+Tree 的非叶子节点只存索引键，不存卫星数据（Row Data）。这意味着同样大小的页能容纳更多索引项，树更矮胖，进一步减少磁盘 I/O 次数。
• 叶子节点链表连接：B+Tree 所有叶子节点通过双向链表串联，极大提升了范围查询（Range Scan）和全表扫描的效率；而 B-Tree 需要中序遍历整棵树，I/O 开销巨大。
• 查询性能稳定：B+Tree 每次查询都必须走到叶子节点，路径长度一致，性能可预测；B-Tree 可能在中间节点就命中数据，导致不同记录的查询耗时波动较大。
• 缓存友好：由于非叶子节点不含数据，更多的索引可以被加载到 Buffer Pool 中，提高热数据的命中率。

3. MySQL 为什么不建议用 UUID 当主键？

• 页分裂与碎片化：UUID 是无序的，插入新记录时会随机定位到 B+Tree 的某个中间位置，导致频繁的页分裂（Page Split）和大量内存移动，产生严重磁盘碎片。
• 写入性能差：无序写入破坏了 B+Tree 的顺序追加特性，将顺序 I/O 退化为大量随机 I/O，显著降低插入吞吐量。
• 空间浪费：UUID 通常为 36 字节字符串（或 16 字节二进制），比自增 BIGINT（8字节）大得多，导致索引页填充率低、树更高、缓存命中率下降。
• 二级索引膨胀：InnoDB 二级索引叶子节点存储的是主键值，UUID 过长会导致所有二级索引体积急剧膨胀。

4. MySQL 中的聚集索引、稀疏索引如何理解？

• 聚集索引（Clustered Index）：InnoDB 中主键索引即聚集索引，其叶子节点直接存储完整的行数据。表数据物理上按主键顺序存储，“索引即数据”。一张表只能有一个聚集索引。
• 稀疏索引（Sparse Index）：指索引并不为每一行都建立条目，而是对"数据块"或"页"建立索引（例如 MyISAM 的主键索引或非聚簇索引）。但在 InnoDB 语境下，通常讨论的是密集索引（每行都有索引项）。若特指稀疏索引，它节省空间但无法精确定位单行，需配合顺序扫描；InnoDB 实际上使用的是密集索引，但有时在分区表或特定优化场景下会体现稀疏特性。

  注：面试中常问的其实是"聚集 vs 非聚集"，若确指稀疏索引，应强调其与密集索引在粒度上的区别。

5. LIKE ‘aaa%’ 一定会用到索引么？

不一定。 只有当满足以下条件时才会使用索引：

• 前缀匹配（% 不在开头）；
• 该列上有合适的索引（单列索引或联合索引的最左列）；
• 没有发生隐式类型转换（如字符串列传了数字）；
• 字符集/排序规则兼容；
• 优化器评估认为走索引比全表扫描更优（例如 aaa% 匹配了表中 90% 的数据，优化器可能放弃索引）。

若是 LIKE '%aaa' 或 LIKE '%aaa%'，则必然无法使用 B+Tree 索引（除非使用全文索引）。

6. 为什么不建议写 SELECT * FROM 进行查询？

• 增加 I/O 和网络开销：读取不必要的列会增加磁盘读取量、Buffer Pool 占用及网络传输带宽。
• 覆盖索引失效：无法利用覆盖索引（Covering Index），必须回表查询完整行数据，丧失仅从索引获取数据的性能优势。
• 影响执行计划：可能导致优化器选择错误的索引或放弃索引。
• 代码维护风险：表结构变更（加/删列）可能导致应用层解析错误或性能突变，缺乏显式字段声明使代码可读性和健壮性变差。

7. 最左匹配原则怎么理解？

针对联合索引 (a, b, c)，B+Tree 先按 a 排序，a 相同再按 b 排序，b 相同再按 c 排序。因此：

• ✅ WHERE a=1、WHERE a=1 AND b=2、WHERE a=1 AND b=2 AND c=3 可用索引；
• ❌ WHERE b=2、WHERE c=3、WHERE b=2 AND c=3 无法使用索引（缺少最左列 a）；
• ⚠️ WHERE a=1 AND c=3 只能用 a 的索引部分，c 无法利用（b 缺失导致 c 无序）；
• ⚠️ 范围查询（>、<、BETWEEN、LIKE ‘xx%’）之后的列无法继续使用索引，因为范围条件破坏了后续列的全局有序性。

8. 为什么建议主键 ID 是递增的，和 B+Tree 有什么关系？

• 顺序追加避免页分裂：递增 ID 保证新记录总是插入 B+Tree 最右侧叶子节点末尾，无需移动已有数据，几乎零页分裂。
• 最大化页填充率：顺序写入使每个数据页都能被充分利用，减少碎片，提升缓存效率。
• 顺序 I/O 替代随机 I/O：批量插入时磁盘可进行顺序写，吞吐远高于随机写。
• 合并写入（Change Buffer）：InnoDB 的 Change Buffer 对顺序插入有专门优化，进一步提升写入性能。

9. 为什么 InnoDB 引擎要求一定要建立主键索引？

• 数据组织依赖：InnoDB 是索引组织表（Index-Organized Table），表数据必须按照某个索引物理存储。若无显式主键，InnoDB 无法确定数据的物理排列顺序。
• 唯一标识需求：MVCC、事务回滚、Binlog 复制、锁机制等都依赖于能唯一标识每一行的键。
• 自动降级策略：若用户未定义主键，InnoDB 会选择第一个非 NULL 的唯一索引作为隐含主键；若也没有，则自动生成一个 6 字节的隐藏 ROW_ID 作为聚簇索引。但这会带来额外开销且不可控，因此官方强烈建议显式定义自增整型主键以获得最佳性能和可控性。

事务

需要的知识点

• 事务（Transaction）的ACID属性
• 锁（Lock）机制（行锁、表锁、乐观锁、悲观锁）
• MVCC多版本并发控制
  • 并发访问数据库系统时，提高读写效率，因为级锁以后会影响效率
  • 当前读：总是读取最新版本的记录（insert、update、delete）需要加锁
  • 快照读：读取历史版本的记录（不加锁的select * from语句）

MVCC原理

1. MVCC概念解析

全称叫多版本并发控制（Multi-Version Concurrency Control）核心思想是： 一行数据被更新时，不是简单覆盖旧数据,而是保留多个历史版本，

这样不同事务，在不同的时间点就能看到不同版本的数据

这样最大的好处就是读不阻塞写，写不阻塞读，如下面的例子

比如A事务正在把余额从100改成200，但是还没提交，这个时候事务B来查询余额，如果读200就可能读到未提交的数据，就是脏读，如果加锁，又会降低并发， MVCC的做法是：事务B不读事务A未提交的新版本，而是读自己快照里可见的旧版本

2. InnoDB MVCC实现

InnoDB是如何实现这些的，就是靠了三个东西，（隐藏字段、Undo Log、ReadView）

隐藏字段： 负责记录版本信息，每个字段都有一个隐藏的字段，记录事务版本号

Undo Log： 负责保存历史版本，串联形成版本链

ReadView： 负责判断当前事务到底能看到哪个版本，是隔离机制的支撑

这三个东西合起来就是MVCC的底层核心

3. 隐藏字段

InnoDB每行字段，除了我们建表时定义的字段以外，内部还会维护一些隐藏字段，和MVCC最相关的有两个：一个叫trx_id,一个叫roll_pointer

trx_id： 当前这个数据版本是由哪个事务创建的，比如事务10把余额改成了200，那么这一行的trx_id就会记录成10，也就是说这个版本是事务10创建的

roll_pointer： 可以理解为就是一个指针，指向Undo Log里的上一个历史版本，比如一条记录经历了三次修改，事务5把余额设成100，事务10改成200， 事务20又改成300

4. Undo Log

很多人都认为Undo log是用来回滚事务的，其实它还有一个非常重要的作用：给MVCC提供历史版本，

比如：原来余额是100，事务A执行把余额改成了200。InnoDB会把旧值100先写入undo log，再把当前记录改成200，如果事务A进行回滚，数据库可以通过undo log把数据恢复成100，如果其它事务还需要读旧版本，也可以通过undo log找到余额100

所以undo log有两个作用就是事务回滚和MVCC历史版本读取

5. ReadView

undo log保存了多个事务版本，但问题是：一个事务查询时，到底应该看到哪个版本呢？答案是：根据ReadView判断

readview可以理解成：事务在某个时间点生成的一张可见快照，记录当时系统里哪些事务还活着，哪些事务已经提交

里面几个核心信息是：

• m_ids ：当前活跃事务ID列表（可以理解为我生成快照时还有哪些事务没有提交）
• min_trx_id ：活跃事务中最小的事务ID （这些没有提交的事务里ID最小的是谁）
• max_trx_id ：下一个即将分配的事务ID （我生成快照那一刻，系统事务ID已经分配到哪里了）
• creator_trx_id ：创建这个Read View的事务ID （当前事务自己是谁）

有了这几个数据，InnoDB就能判断某个数据版本，对当前事务到底可不可见

版本可见性规则总结就是四句话：假设某个数据版本的事务ID是trx_id 第一，如果trx_id等于creator_trx_id，那么这个版本对当前事务可见 第二，如果trx_id小于min_trx_id，那么这个版本对当前事务可见，说明已经提交了 第三，如果trx_id大于等于max_trx_id，那么这个版本对当前事务不可见，说明这个trx_id是在快照之后才创建的，对于快照来说属于未来数据，不可见 第四，如果trx_id在min_trx_id和max_trx_id之间，就要看trx_id是否在m_ids里，如果在，说明这个事务正在执行中，不可见，如果不在，说明这个事务已经提交了，可见

6. 完整示例

现在有初始的事务5，查询的事务10，修改数据的事务20

事务5: 初始化余额为100

事务20: 把余额修改成了200，当前的版本链就是 100 -> trx_id=5 ====> 200 -> trx_id=20

事务10: 查询余额，事务10会生成一个自己的Read View，事务10会拿到最新版本就是余额200，但是它会拿自己的Read View判断事务20这个版本我能不能看，如果事务20在我生成快照时还是活跃事务，那就不可见，于是事务10沿着roll_pointer去undo log里面找旧版本，找到了余额100，trx_id=5的，在判断事务5早都提交了，所以可见，读取到100

事务隔离级别

ACID属性详解

事务的四大特性，简称 ACID，是数据库事务正确执行的四个基本要素：

四大特性的关系

graph LR
    A[事务ACID] --> A1[A 原子性]
    A --> A2[C 一致性]
    A --> A3[I 隔离性]
    A --> A4[D 持久性]

    A1 -->|实现| A1S[Undo Log 回滚日志]
    A3 -->|实现| A3S[锁 + MVCC]
    A4 -->|实现| A4S[Redo Log 重做日志]

    A1S --> A2
    A3S --> A2
    A4S --> A2
    A2 -->|最终目标| A2S[数据合法一致]

一致性是最终目标，原子性、隔离性、持久性是实现一致性的手段。

四种隔离级别

SQL 标准定义了四种隔离级别，从低到高：

MySQL InnoDB 默认隔离级别是 可重复读（RR），且通过 MVCC + 间隙锁在快照读场景下避免了幻读。

三种并发问题

graph TD
    subgraph 脏读
        A1[事务A 更新数据] -->|未提交| A2[事务B 读到未提交数据]
        A1 -->|回滚| A3[事务B 读到的是脏数据]
    end

    subgraph 不可重复读
        B1[事务B 第一次读取] --> B2[事务A 更新并提交]
        B2 --> B3[事务B 第二次读取]
        B3 --> B4[同一行数据两次结果不同]
    end

    subgraph 幻读
        C1[事务B 范围查询] --> C2[事务A 插入新行并提交]
        C2 --> C3[事务B 再次范围查询]
        C3 --> C4[结果集多了一些行 — 幻影行]
    end

1. 脏读（Dirty Read）

事务 A 修改了数据但尚未提交，事务 B 就读到了这个未提交的数据。如果事务 A 回滚，事务 B 读到的就是"脏"数据——从未真正存在过的数据。

-- 事务A                          -- 事务B
BEGIN;
UPDATE account SET balance = 200
WHERE id = 1;
-- 未提交
                                  BEGIN;
                                  SELECT balance FROM account WHERE id = 1;
                                  -- 读到 200（脏读！真实值仍是100）
ROLLBACK;
                                  -- 事务B基于200做的所有决策都是错误的

2. 不可重复读（Non-Repeatable Read）

事务 B 内两次读取同一行数据，结果不同，因为期间事务 A 修改并提交了这行数据。

-- 事务B                         -- 事务A
BEGIN;
SELECT balance FROM account
WHERE id = 1;
-- 读到 100
                                 BEGIN;
                                 UPDATE account SET balance = 200
                                 WHERE id = 1;
                                 COMMIT;
SELECT balance FROM account
WHERE id = 1;
-- 读到 200（不可重复读！）
COMMIT;

3. 幻读（Phantom Read）

事务 B 内两次执行同一范围查询，结果集行数不同，因为期间事务 A 插入或删除了符合条件的行。

-- 事务B                         -- 事务A
BEGIN;
SELECT * FROM account
WHERE balance > 100;
-- 假设查到3行
                                 BEGIN;
                                 INSERT INTO account VALUES(99, 300);
                                 COMMIT;
SELECT * FROM account
WHERE balance > 100;
-- 查到4行，多了一行（幻读！）
COMMIT;

RC 和 RR 的本质区别 — ReadView 生成时机

InnoDB 中 RC 和 RR 都依赖 MVCC，核心区别在于 ReadView 生成的时机：

graph TD
    subgraph RC 读已提交
        RC1[事务开始] --> RC2[SELECT 1 生成ReadView]
        RC2 --> RC3[SELECT 2 重新生成ReadView]
        RC3 --> RC4[SELECT 3 再次重新生成ReadView]
        RC4 --> RC5[每次SELECT 看到的数据可能不同]
    end

    subgraph RR 可重复读
        RR1[事务开始] --> RR2[第一次SELECT 生成ReadView]
        RR2 --> RR3[整个事务期间复用同一个ReadView]
        RR3 --> RR4[多次SELECT 结果一致]
    end

锁机制

1. 锁的分类总览

graph TD
    LOCK[InnoDB 锁] --> G[按粒度]
    LOCK --> T[按类型]
    LOCK --> A[按思想]

    G --> G1[表锁 Table Lock]
    G --> G2[行锁 Row Lock]
    G --> G3[全局锁 Global Lock]

    T --> T1[共享锁 S锁 读锁]
    T --> T2[排他锁 X锁 写锁]
    T --> T3[意向锁 IS / IX]

    A --> A1[悲观锁]
    A --> A2[乐观锁]

2. 共享锁与排他锁

兼容矩阵：
         S(共享)   X(排他)
S(共享)    ✅        ❌
X(排他)    ❌        ❌

3. 意向锁（Intention Lock）

意向锁是表级锁，目的是协调行锁和表锁之间的关系，提升加锁效率。

• IS（意向共享锁）：事务打算对表中某些行加 S 锁前，先在表上加 IS
• IX（意向排他锁）：事务打算对表中某些行加 X 锁前，先在表上加 IX

意向锁之间互相兼容，它只用于快速判断"表上是否有行锁”，避免逐行扫描。

4. 行锁的三种类型

InnoDB 的行锁是基于索引实现的，没有索引则退化为表锁。

记录锁（Record Lock）

锁定索引上的一条记录，是最精确的行锁。

-- 假设id是主键，id=1的记录上加记录锁
SELECT * FROM user WHERE id = 1 FOR UPDATE;
-- 锁住的仅仅是 id=1 这一条索引记录

间隙锁（Gap Lock）

锁定索引记录之间的间隙，但不锁记录本身，防止其他事务向间隙中插入数据。

-- 假设表中id有 1, 5, 10 三条记录
SELECT * FROM user WHERE id > 1 AND id < 5 FOR UPDATE;
-- 间隙锁锁住 (1, 5) 这个开区间
-- 其他事务无法 INSERT id=2, id=3 等

临键锁（Next-Key Lock）

临键锁 = 记录锁 + 间隙锁，锁住一个左开右闭区间 (前一个记录, 当前记录]。

这是 RR 隔离级别下 InnoDB 行锁的默认加锁方式，用于解决幻读问题。

-- 假设表中id有 5, 10, 15 三条记录
SELECT * FROM user WHERE id > 5 AND id <= 10 FOR UPDATE;
-- 临键锁锁住 (5, 10] 和 (10, 15) 前面部分
-- 即其他事务无法 INSERT id=6,7,8,9,10

graph LR
    subgraph "临键锁 = 记录锁 + 间隙锁"
        A["(5, 10]"] --> B[间隙锁 5~10]
        A --> C[记录锁 10]
    end

5. 乐观锁与悲观锁

悲观锁示例

-- 事务A：先锁定再修改
BEGIN;
-- 加排他锁，其他事务必须等待
SELECT * FROM account WHERE id = 1 FOR UPDATE;
-- 拿到余额 balance = 100
UPDATE account SET balance = balance - 50 WHERE id = 1;
COMMIT;

-- 事务B：如果同时执行同样的FOR UPDATE，会阻塞直到事务A提交

乐观锁示例

-- 表结构增加 version 字段
-- CREATE TABLE account(id INT PRIMARY KEY, balance INT, version INT DEFAULT 0);

-- 事务A：先读，再更新时检查版本
BEGIN;
-- 第一步：读出当前余额和版本号
SELECT balance, version FROM account WHERE id = 1;
-- 假设读到 balance=100, version=1

-- 第二步：更新时带上版本号条件（CAS思想）
UPDATE account
SET balance = balance - 50, version = version + 1
WHERE id = 1 AND version = 1;
-- 如果 affected_rows = 1，说明没有冲突，更新成功
-- 如果 affected_rows = 0，说明版本已被其他事务修改，需要重试
COMMIT;

6. 死锁

死锁产生条件

两个或多个事务互相持有对方需要的锁，形成循环等待。

graph LR
    A[死锁四条件] --> A1[互斥: 锁不能共享]
    A --> A2[持有等待: 拿着锁还等锁]
    A --> A3[不剥夺: 不能强行抢锁]
    A --> A4[循环等待: 形成环路]

死锁示例

-- 事务A                          -- 事务B
BEGIN;                            BEGIN;
UPDATE account SET balance=200    UPDATE account SET balance=300
WHERE id = 1;                     WHERE id = 2;
-- A持有id=1的X锁                  -- B持有id=2的X锁

UPDATE account SET balance=200    UPDATE account SET balance=300
WHERE id = 2;                     WHERE id = 1;
-- A等B释放id=2的锁                -- B等A释放id=1的锁
-- 循环等待 → 死锁！

InnoDB 死锁处理

InnoDB 使用 等待图（Wait-For Graph） 算法自动检测死锁：

1. 为每个事务建立等待关系（事务A等待事务B → 画一条 A→B 的边）
2. 如果图中出现环 → 检测到死锁
3. 选择回滚代价最小的事务（Undo 量最少的）作为牺牲者
4. 返回 ERROR 1213 (40001): Deadlock found

也可以通过 innodb_deadlock_detect 参数关闭死锁检测（高并发场景下检测本身有性能开销），改用 innodb_lock_wait_timeout 超时回滚。

事务面试题

1. 谈谈你对 ACID 的理解

• 原子性由 Undo Log 实现，事务执行过程中记录"反向操作"日志，回滚时根据 Undo Log 恢复。
• 持久性由 Redo Log 实现，事务提交时先写 Redo Log（WAL 机制），即使 Buffer Pool 数据还没刷盘，崩溃后也能用 Redo Log 恢复。
• 隔离性由锁 + MVCC 共同实现。写写之间用锁保证串行化，读写之间用 MVCC 实现非阻塞读。
• 一致性是前三者的最终目标，数据库层面通过约束（主键、外键、唯一索引）和事务保证数据从一个合法状态转到另一个合法状态。

2. MySQL 的 RR 级别真的能避免幻读吗？

• 快照读（普通 SELECT）：通过 MVCC，整个事务复用同一个 ReadView，不会看到新插入的行，可以避免幻读。
• 当前读（SELECT … FOR UPDATE / INSERT / UPDATE / DELETE）：通过临键锁锁定间隙，阻止其他事务在范围内插入数据，也可以避免幻读。
• 混合场景的边界 case：如果事务先快照读、再当前读，可能"看到"之前快照读时不可见的行。严格来说这是快照读和当前读混用造成的现象，而非 RR 本身的缺陷。

3. 乐观锁和悲观锁怎么选择？

• 写多读少、竞争激烈 → 选悲观锁，冲突概率高，乐观锁大量重试反而更慢。
• 读多写少、竞争温和 → 选乐观锁，无锁开销，吞吐量更高。
• 极端高并发场景下，乐观锁的 CAS 重试（自旋）会导致 CPU 飙升，此时应考虑分布式锁或队列串行化。

4. InnoDB 行锁是锁记录还是锁索引？

锁的是索引，不是数据行本身。InnoDB 是索引组织表，数据行挂在聚簇索引的叶子节点上。如果 WHERE 条件走的是主键索引，就在主键索引上加锁；如果走的是二级索引，先锁二级索引，再回表锁主键索引。如果查询条件没有命中任何索引，InnoDB 只能逐行加锁，效果等同于表锁。

5. 什么是 MVCC 的版本链？

每行记录的隐藏字段 roll_pointer 指向 Undo Log 中的上一个版本，Undo Log 中的每个旧版本也通过 roll_pointer 指向更早的版本，形成一条链表。ReadView 沿着版本链依次判断每个版本是否可见，直到找到第一个可见版本。当没有事务再依赖某个旧版本时，Purge 线程会清理对应的 Undo Log。

主从复制和读写分离

主从复制原理

graph LR
    subgraph Master 主库
        M1[客户端写入] --> M2[执行SQL 修改数据]
        M2 --> M3[写入Binlog 二进制日志]
    end

    M3 -->|网络传输| S1

    subgraph Slave 从库
        S1[IO线程 拉取Binlog] --> S2[写入Relay Log 中继日志]
        S2 --> S3[SQL线程 回放Relay Log]
        S3 --> S4[数据同步完成]
    end

三个核心组件

复制流程详解

sequenceDiagram
    participant Client as 客户端
    participant Master as Master主库
    participant IOThread as Slave IO线程
    participant SQLThread as Slave SQL线程
    participant Slave as Slave数据

    Client->>Master: INSERT/UPDATE/DELETE
    Master->>Master: 执行SQL，修改数据
    Master->>Master: 写入Binlog
    IOThread->>Master: 请求拉取Binlog（基于位点/GTID）
    Master-->>IOThread: 返回Binlog事件
    IOThread->>IOThread: 写入本地Relay Log
    SQLThread->>IOThread: 读取Relay Log
    SQLThread->>Slave: 回放SQL，同步数据

复制的三种方式

1. 异步复制（Asynchronous Replication）

MySQL 默认方式。Master 写完 Binlog 就直接返回客户端，不等待 Slave 确认。

graph LR
    C[客户端] -->|写入| M[Master]
    M -->|1.写Binlog| M
    M -->|2.立即返回OK| C
    M -.->|3.异步推送| S[Slave]
    style M fill:#4CAF50,color:#fff
    style C fill:#2196F3,color:#fff

• 优点：性能最好，Master 不受 Slave 影响
• 缺点：Master 崩溃时可能丢失未同步的数据
• 适用：对数据一致性要求不高的场景

2. 半同步复制（Semi-Synchronous Replication）

Master 写完 Binlog 后，至少等待一个 Slave 确认收到日志后才返回客户端。

sequenceDiagram
    participant C as 客户端
    participant M as Master
    participant S as Slave

    C->>M: 写入请求
    M->>M: 执行SQL + 写Binlog
    M->>S: 推送Binlog
    S->>S: 写入Relay Log
    S-->>M: ACK确认收到
    M-->>C: 返回OK（确保至少一个Slave已收到）

• 优点：数据安全性更高，至少一个 Slave 有日志副本
• 缺点：增加一个网络 RTT 的延迟
• 适用：对数据一致性要求较高的场景

3. 全同步复制（Fully Synchronous）

Master 等待所有 Slave 都确认收到并执行完毕才返回客户端。

• 优点：数据完全一致
• 缺点：性能极差，实际很少使用

读写分离

graph TD
    APP[应用层] --> PROXY[数据库中间件/代理]
    PROXY -->|写请求| M[Master主库]
    PROXY -->|读请求1| S1[Slave1从库]
    PROXY -->|读请求2| S2[Slave2从库]
    PROXY -->|读请求3| S3[Slave3从库]

    M -->|Binlog同步| S1
    M -->|Binlog同步| S2
    M -->|Binlog同步| S3

读写分离的核心思想

• 写操作（INSERT / UPDATE / DELETE）→ 走主库
• 读操作（SELECT）→ 走从库
• 通过增加从库数量，水平扩展读能力

实现方式

主从延迟问题

产生原因

graph TD
    M[Master主库] -->|Binlog 并发写入| M1[多个线程并发执行]
    S[Slave从库] -->|SQL线程单线程回放| S1[回放速度跟不上写入速度]
    S1 --> S2[从库数据滞后于主库]
    S2 --> S3[用户读到旧数据]

核心原因是 Slave 的 SQL 线程是单线程，而 Master 是多线程并发写入，回放速度跟不上写入速度。

解决方案

分库分表

为什么需要分库分表

当单库单表面临以下瓶颈时，就需要考虑分库分表：

graph TD
    A[单库单表瓶颈] --> A1[数据量过大: 单表超过千万行查询变慢]
    A --> A2[磁盘IO瓶颈: 单机磁盘扛不住]
    A --> A3[连接数瓶颈: 单库连接数有上限]
    A --> A4[单点故障: 主库宕机全部不可用]

1. 垂直拆分

垂直分库

按业务模块拆分到不同的数据库中。

graph LR
    subgraph 拆分前 单库
        DB1[all_db: 用户表 订单表 商品表 评价表]
    end

    subgraph 拆分后 多库
        DB2[user_db: 用户表]
        DB3[order_db: 订单表]
        DB4[product_db: 商品表]
        DB5[review_db: 评价表]
    end

    DB1 --> DB2
    DB1 --> DB3
    DB1 --> DB4
    DB1 --> DB5

垂直分表

将一张宽表按字段拆分为多张表，将热数据和冷数据分离。

-- 拆分前：一张宽表，查询时加载不必要的大字段
CREATE TABLE user (
    id BIGINT PRIMARY KEY,
    name VARCHAR(50),
    age INT,
    bio TEXT,           -- 大字段，很少查询
    avatar LONGBLOB     -- 大字段，很少查询
);

-- 拆分后：主表存热数据
CREATE TABLE user (
    id BIGINT PRIMARY KEY,
    name VARCHAR(50),
    age INT
);

-- 扩展表存冷数据
CREATE TABLE user_ext (
    user_id BIGINT PRIMARY KEY,
    bio TEXT,
    avatar LONGBLOB
);

2. 水平拆分

水平分库

将同一个表的数据按某种规则分散到不同的数据库中。

graph TD
    subgraph 拆分前
        T1[订单表 1000万行 在单库]
    end

    subgraph 拆分后 按用户ID取模
        D1[db_0: 订单表 用户ID%3=0的数据]
        D2[db_1: 订单表 用户ID%3=1的数据]
        D3[db_2: 订单表 用户ID%3=2的数据]
    end

    T1 --> D1
    T1 --> D2
    T1 --> D3

水平分表

在同一个数据库内，将大表拆分为多个结构相同的小表。

-- 拆分前
CREATE TABLE order_2024 (...);  -- 全年数据一张表

-- 拆分后 按月份
CREATE TABLE order_202401 (...);  -- 1月数据
CREATE TABLE order_202402 (...);  -- 2月数据
CREATE TABLE order_202403 (...);  -- 3月数据
-- ...

3. 分片策略

4. 分库分表带来的问题

跨库 JOIN 无法使用

-- 拆分前可以 JOIN
SELECT * FROM order o JOIN user u ON o.user_id = u.id;

-- 拆分后 order 在db_0，user 在db_1，无法直接JOIN
-- 解决方案：
-- 1. 应用层组装：分别查询后在内存中拼接
-- 2. 冗余字段：在订单表中冗余存储用户名等常用字段
-- 3. 广播表/全局表：将小表（如省市区）在每个库都存一份

分布式事务

graph TD
    A[分布式事务问题] --> A1[订单在db_0]
    A --> A2[库存在db_1]
    A --> A3[需要跨库保证原子性]
    A3 --> A4[解决方案: 2PC / TCC / Saga / 本地消息表]

全局唯一 ID

单库时可以用自增 ID，分库分表后各库的自增 ID 会冲突。

跨库分页排序

-- 单库分页很简单
SELECT * FROM order ORDER BY create_time DESC LIMIT 10 OFFSET 100;

-- 分库后：需要每个库各查前110条，在内存中合并排序再取10条
-- 分页越深，性能越差
-- 解决：禁止深度分页 / 游标分页 / ES辅助搜索

一致性Hash算法

1. 传统 Hash 取模的问题

-- 传统方案：hash(key) % N
-- 例如：user_id % 4 决定数据存到哪个库

graph LR
    subgraph 4个节点时
        A1[数据1: hash%4=1 → node1]
        A2[数据2: hash%4=2 → node2]
        A3[数据3: hash%4=3 → node3]
        A4[数据4: hash%4=0 → node0]
    end

    subgraph 扩容到5个节点
        B1[数据1: hash%5=1 → node1]
        B2[数据2: hash%5=2 → node2]
        B3[数据3: hash%5=3 → node3]
        B4[数据4: hash%5=4 → node4 ← 位置变了!]
    end

当节点数从 4 变为 5 时，hash(key) % N 中 N 变了，几乎所有数据的映射结果都变了，导致大量数据需要重新迁移。

2. 一致性Hash原理

一致性 Hash 将整个 Hash 值空间组织成一个虚拟的圆环（Hash 环），范围是 0 ~ 2^32 - 1。

graph TD
    A[一致性Hash核心步骤] --> A1["1. 计算节点的Hash值，映射到环上"]
    A1 --> A2["2. 计算数据的Hash值，映射到环上"]
    A2 --> A3["3. 数据顺时针方向找到最近的节点，由该节点负责"]

graph TD
    subgraph Hash环
        N0[Node A hash=100]
        N1[Node B hash=3000]
        N2[Node C hash=8000]
        N3[Node D hash=15000]

        D1[Data1 hash=500 → 归Node B]
        D2[Data2 hash=6000 → 归Node C]
        D3[Data3 hash=20000 → 归Node A 环绕]
    end

数据顺时针方向找到的第一个节点就是它的归属节点。Data1 的 Hash 是 500，在 Node A(100) 之后、Node B(3000) 之前，所以归 Node B。

节点扩容时的影响

新增一个 Node E（Hash=4000），只需要迁移 Node C(8000) 到 Node E(4000) 之间逆时针方向的数据，其他数据完全不受影响。

graph TD
    subgraph 扩容前
        E1["Node A=100"]
        E2["Node B=3000"]
        E3["Node C=8000 → 负责 3000~8000 的数据"]
    end

    subgraph "新增Node E=4000后"
        F1["Node A=100"]
        F2["Node B=3000"]
        F3["Node E=4000 → 负责 3000~4000 的数据 从C迁移过来"]
        F4["Node C=8000 → 负责 4000~8000 的数据"]
    end

只影响了相邻节点之间的数据，不涉及全局迁移——这就是一致性 Hash 的核心优势。

3. 数据倾斜与虚拟节点

当节点数量少时，数据在环上分布不均匀，可能出现某个节点承担大部分数据的情况。

graph TD
    subgraph 无虚拟节点 倾斜
        A1[Node A 负责 0~3000 大范围]
        A2[Node B 负责 3000~2^32 极大范围]
        A3[数据严重倾斜]
    end

    subgraph 引入虚拟节点 均匀
        B1[Node A → A#1 A#2 A#3 ... A#150]
        B2[Node B → B#1 B#2 B#3 ... B#150]
        B3[每个物理节点映射多个虚拟节点到环上]
        B4[数据分布趋于均匀]
    end

虚拟节点原理

• 每个物理节点映射出 多个虚拟节点（通常 150~200 个）分散在 Hash 环上
• 数据先找到虚拟节点，再映射回物理节点
• 虚拟节点越多，分布越均匀，但元数据管理开销也越大

// 一致性Hash的Java实现思路（伪代码）

// 虚拟节点数量
int VIRTUAL_NODES = 150;

// 使用TreeMap模拟Hash环（有序映射）
TreeMap<Integer, String> ring = new TreeMap<>();

// 添加节点：为每个物理节点创建虚拟节点
void addNode(String node) {
    for (int i = 0; i < VIRTUAL_NODES; i++) {
        // 虚拟节点的Hash = hash(node + "#" + i)
        int hash = hash(node + "#" + i);
        ring.put(hash, node);
    }
}

// 查找数据归属节点
String getNode(String key) {
    int hash = hash(key);
    // 顺时针找第一个 >= hash 的虚拟节点
    Map.Entry<Integer, String> entry = ring.ceilingEntry(hash);
    // 如果超过最大值，环绕到环的第一个节点
    if (entry == null) {
        entry = ring.firstEntry();
    }
    return entry.getValue();
}

// 移除节点：删除该节点的所有虚拟节点
void removeNode(String node) {
    for (int i = 0; i < VIRTUAL_NODES; i++) {
        int hash = hash(node + "#" + i);
        ring.remove(hash);
    }
}

中间件

主流分库分表中间件对比

1. ShardingSphere

Apache 顶级项目，提供三种部署模式：

graph TD
    SS[ShardingSphere] --> J[JDBC模式 客户端分片]
    SS --> P[Proxy模式 代理分片]
    SS --> S[Sidecar模式 Kubernetes]

    J --> J1[应用直接连接数据库]
    J --> J2[无需额外进程]
    J --> J3[性能最好 但仅支持Java]

    P --> P1[应用连接Proxy]
    P --> P2[Proxy转发到后端数据库]
    P --> P3[多语言支持 多一跳网络]

    S --> S1[每个Pod一个Sidecar]
    S --> S1[云原生部署]

ShardingSphere-JDBC 使用示例

# 数据源配置
dataSources:
  ds_0:
    dataSourceClassName: com.zaxxer.hikari.HikariDataSource
    jdbcUrl: jdbc:mysql://localhost:3306/db_0
    username: root
    password: root
  ds_1:
    dataSourceClassName: com.zaxxer.hikari.HikariDataSource
    jdbcUrl: jdbc:mysql://localhost:3306/db_1
    username: root
    password: root

# 分片规则
rules:
  - !SHARDING
    tables:
      t_order:
        actualDataNodes: ds_${0..1}.t_order_${0..1}
        databaseStrategy:
          standard:
            shardingColumn: user_id
            shardingAlgorithmName: db_mod
        tableStrategy:
          standard:
            shardingColumn: order_id
            shardingAlgorithmName: table_mod
    shardingAlgorithms:
      db_mod:
        type: MOD
        props:
          sharding-count: 2
      table_mod:
        type: MOD
        props:
          sharding-count: 2

2. MyCat

graph TD
    APP[应用] -->|SQL| MC[MyCat Server]
    MC -->|路由解析| MC1[SQL解析: 解析SQL语句]
    MC1 --> MC2[路由计算: 根据分片规则决定目标库表]
    MC2 --> MC3[SQL改写: 优化跨库SQL]
    MC3 --> MC4[并发执行: 多后端并发执行]
    MC4 --> MC5[结果归并: 合并多库结果集]
    MC5 -->|返回| APP

MyCat 核心概念

3. Vitess

YouTube 开源的 MySQL 数据库集群管理工具，2019 年加入 CNCF，现为毕业项目。

graph TD
    APP[应用] -->|MySQL协议| VT[vtgate 代理网关]
    VT -->|路由| VT1[vttablet 1 → MySQL 1]
    VT -->|路由| VT2[vttablet 2 → MySQL 2]
    VT -->|路由| VT3[vttablet 3 → MySQL 3]

    VT1 --> VT1A[查询重写]
    VT1 --> VT1B[连接池管理]
    VT1 --> VT1C[在线DDL]

    subgraph 管理面
        TS[topo etcd 配置中心]
        VR[vtctld 集群管理]
    end

Vitess 核心特性

• 水平分片：自动管理分片路由，支持动态resharding
• 连接池：vttablet 管理连接池，减少 MySQL 连接数
• 在线 Schema 变更：支持 VReplication 进行在线 DDL
• 多租户：支持在同一集群上隔离多个租户
• 云原生：原生支持 Kubernetes 部署

高可用架构总结

MySQL 高可用方案演进

graph TD
    A[单机MySQL] -->|主备| B[主从复制]
    B -->|加半同步| C[半同步复制 + 读写分离]
    C -->|加故障切换| D[MHA / Orchestrator 自动故障转移]
    D -->|加分片| E[ShardingSphere / Vitess 分库分表]
    E -->|云原生| F[MySQL Group Replication / MySQL InnoDB Cluster]

高可用方案对比

面试高频考点速记

自测题与动手练习

自测题（合上书能答出来，才算懂）：

1. 为什么 MySQL 不用二叉搜索树或平衡二叉树做索引？B+Tree 相比 B-Tree 又赢在哪三点？

   答：二叉树每个节点只存一个 key，树太高、磁盘 I/O 次数爆炸；B+Tree 非叶子节点不存数据 → 更矮胖，叶子链表相连 → 范围查询快，查询路径等长 → 性能稳定。

2. 什么是回表？怎么用一条 SQL 消除它？

   答：二级索引查到主键后，再回聚簇索引取完整行叫回表；建立覆盖索引（把查询字段都纳入联合索引）即可避免。

3. MVCC 里"读不阻塞写"靠哪三样东西实现？版本可见性四条规则的核心判断是什么？

   答：隐藏字段（trx_id / roll_pointer）+ Undo Log 版本链 + ReadView；核心是拿数据版本的 trx_id 与 ReadView 的 m_ids / min / max 比，判断"对我可见吗"。

4. RC 和 RR 的本质区别是什么？RR 真的能避免幻读吗？

   答：区别在于 ReadView 生成时机——RC 每次 SELECT 重建，RR 事务内第一次 SELECT 建一次复用。RR 下快照读靠 MVCC、当前读靠临键锁，都能避免幻读。

5. 一致性 Hash 相比传统 hash % N 的核心优势是什么？虚拟节点解决什么问题？

   答：节点增减只迁移相邻区间的数据，不是全局重算；虚拟节点解决节点少时的数据倾斜。

动手练习（建议真做一遍）：

1. 建表 user(id PK, name, age)，对 name 建索引后执行 SELECT age FROM user WHERE name='张三'，用 EXPLAIN 观察 Extra 是否为 Using index；再改成联合索引 (name, age) 对比。
2. 开两个会话，会话 A 设为 RR 并先 SELECT，会话 B 修改同一行并提交，验证 A 第二次读仍一致；再把 A 改为 RC 重复，观察结果变化。
3. 用文中 Java 伪代码（TreeMap 模拟 Hash 环），在 4 个节点基础上扩到 5 个，打印每个 key 归属变化，数清迁移量。

本章小结

• 索引的本质是"用写入与空间换查询速度"，B+Tree 是兼顾高度、范围查询与缓存友好的最优解。
• 回表是二级索引的代价，覆盖索引是首选优化；最左匹配决定了联合索引怎么建才不浪费。
• MVCC = 隐藏字段 + Undo Log + ReadView，让读写互不阻塞；RC / RR 的差异全在 ReadView 时机。
• 主从复制靠 Binlog → Relay Log → SQL 回放；延迟根因是 Slave 单线程回放，解法在并行复制。
• 分库分表与一致性 Hash 是解决单库单表瓶颈的两条主线，代价是跨库 JOIN、分布式事务、全局 ID。