高可用高性能存储应用

InnoDB存储引擎架构

索引

索引的本质是什么

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

其核心思想——用额外的写入开销和存储空间，换取查询时的极速定位，把 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