本文最后更新于 2024-04-27，文章内容可能已经过时。

二次记录，以做面试复习之用。

思维导图

1.索引为什么用b+树：

1、B+Tree vs B Tree

B+Tree 只在叶子节点存储数据，而 B 树的非叶子节点也要存储数据，所以 B+Tree 的单个节点的数据量更小，在相同的磁盘 I/O 次数下，就能查询更多的节点。

另外，B+Tree 叶子节点采用的是双链表连接，适合 MySQL 中常见的基于范围的顺序查找，而 B 树无法做到这一点。

2、B+Tree vs 二叉树

对于有 N 个叶子节点的 B+Tree，其搜索复杂度为O(logdN)，其中 d 表示节点允许的最大子节点个数为 d 个。

在实际的应用当中， d 值是大于100的，这样就保证了，即使数据达到千万级别时，B+Tree 的高度依然维持在 3~4 层左右，也就是说一次数据查询操作只需要做 3~4 次的磁盘 I/O 操作就能查询到目标数据。

而二叉树的每个父节点的儿子节点个数只能是 2 个，意味着其搜索复杂度为 O(logN)，这已经比 B+Tree 高出不少，因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。

3、B+Tree vs Hash

Hash 在做等值查询的时候效率贼快，搜索复杂度为 O(1)。

但是 Hash 表不适合做范围查询，它更适合做等值的查询，这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。

1.1 基础知识：

二叉树就是度不超过2的树(每个结点最多有两个子结点)。

最基础的二叉树是无序的，查询效率极低。排序之后的二叉树为二叉查找树，也是二叉排序树。

在二叉查找树中，任一节点对应的两棵子树的最大高度差为1，这样的二叉查找树称为平衡二叉树。

1.2 红黑树：

红黑树也是一种特殊的二分查找树，但是红黑树是可以不让树频繁的去旋转平衡，归根结底就一句话： 最长子树只要不超过最短子树的两倍就OK，添加了变色的行为来保证树的平衡。

1.3 b树：

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个)，

问题：

InnoDB 这种存储引擎默认情况下读的是 16kb，一共读取了三个磁盘块，意味着一共读取了 48k 的数据，假如说上面的这些 p 指针和 16 这些 key 值都不需要占用额外的存储空间，一条数据占用 1kb 的空间，那意味着当前节点里面最多存 16 条数据，下一个磁盘块也是 16 条，第三个磁盘块也是 16 条，计算一下的话是 16×16×16，也就是 4096 条数据。这个支撑的数据量也太少了。在生产环境中随便的一个 mysql 表都要上百万条，不可能是只有几万或者几千，这不太可能，这时候就要思考 b 树有什么问题了。

1.4 b+树：

数据存储再叶子节点中，这样就不会造成存储空间有限的问题了。

2.索引失效：

模糊匹配或者计算。

select * 覆盖索引

3.事务的隔离级别：

并发控制理论Concurrency Control）决定了隔离程度与并发能力是相互抵触的，隔离程度越高，并发访问时的吞吐量就越低。

3.1 可串行化：

读锁，写锁，范围锁。

3.2 可重复读：幻读：范围查询

常规实现：读锁，写锁，不加范围锁。

mysql特有的实现：read write 数据快照，在事务开始时生成

会出现幻读问题，只能解决这类问题中的纯读（一部分）。

3.3 读已提交：不可重复读：前后两次

常规实现：事务查询完成后，读锁就被释放。如果事务前后两次读取，可能会不同，而可重复读因为有读锁，数据肯定是相同的。

mysql实现：在每个语句执行前都会重新生成一个 Read View，「读提交」隔离级别是在每个 select 都会生成一个新的 Read View，也意味着，事务期间的多次读取同一条数据，前后两次读的数据可能会出现不一致，因为可能这期间另外一个事务修改了该记录，并提交了事务。

3.4 读未提交：脏读：未提交数据

读未提交。读未提交对事务涉及的数据只加写锁，会一直持续到事务结束，但完全不加读锁。脏读：读未提交在数据上完全不加读锁，这反而令它能读到其他事务加了写锁的数据，

读已提交的查询过程中是有读锁的，所以能避免脏读。

4.mvcc机制：

“多版本并发控制”（Multi-Version Concurrency Control，MVCC）

针对数据库隔离级别的无锁优化，相当于另一种全新的实现。

为每一行记录新增俩字段。

MVCC 的基本思路是对数据库的任何修改都不会直接覆盖之前的数据，而是产生一个新版副本与老版本共存，以此达到读取时可以完全不加锁的目的。

CREATE_VERSION（插入数据）和 DELETE_VERSION（删除数据）中插入全局严格自增的事务id。

如果删除视为上面这俩玩意儿的组合。

如果要查：根据隔离级别展示：

隔离级别是可重复读：总是读取 CREATE_VERSION 小于或等于当前事务 ID 的记录，在这个前提下，如果数据仍有多个版本，则取最新（事务 ID 最大）的。
隔离级别是读已提交：总是取最新的版本即可，即最近被 Commit 的那个版本的数据记录。

MVCC 是只针对“读+写”场景的优化，如果是两个事务同时修改数据，即“写+写”的情况，那就没有多少优化的空间了，此时加锁几乎是唯一可行的解决方案。

没有必要迷信什么乐观锁要比悲观锁更快的说法，这纯粹看竞争的剧烈程度，如果竞争剧烈的话，乐观锁反而更慢。

5.幻读：

很大程度上避免幻读现象（并不是完全解决了）

针对快照读（普通 select 语句），是通过 MVCC 方式解决了幻读，因为可重复读隔离级别下，事务执行过程中看到的数据，一直跟这个事务启动时看到的数据是一致的，即使中途有其他事务插入了一条数据，是查询不出来这条数据的，所以就很好了避免幻读问题。
针对当前读（select ... for update 等语句），是通过 next-key lock（记录锁+间隙锁）方式解决了幻读，因为当执行 select ... for update 语句的时候，会加上 next-key lock，如果有其他事务在 next-key lock 锁范围内插入了一条记录，那么这个插入语句就会被阻塞，无法成功插入，所以就很好了避免幻读问题。

6.各种锁：

6.1 数据库锁：

6.2 针对表的锁：

6.2.1 表锁：

对整个表进行加锁。

6.2.2 元数据锁：

同样针对整个表，但是只针对表的结构，索引等关键信息。

6.2.3 意向锁：

意向锁的目的是为了快速判断表里是否有记录被加锁。

意向共享锁和意向独占锁是表级锁，不会和行级的共享锁和独占锁发生冲突，而且意向锁之间也不会发生冲突，只会和共享表锁（*lock tables ... read*）和独占表锁（*lock tables ... write*）发生冲突。

6.2.4 AUTO-INC 锁:

主键自增锁.

6.3 行级锁：

记录锁：s x 读写锁

gap lock：范围锁

Next-Key Lock:组合上面两种锁

插入意向锁：一个事务在插入一条记录的时候，需要判断插入位置是否已被其他事务加了间隙锁（next-key lock 也包含间隙锁）。

6.3 死锁：

死锁的四个必要条件：互斥、占有且等待、不可强占用、循环等待。

为每个锁设置超时时间。

7.日志：

7.1 为什么需要日志：

无论在单机系统中，还是在分布式系统中，都会出现数据执行到一半崩溃或者问题。此时要想保证可靠性（也就是acid中的原子性和持久性），必须在状态复制和日志复制中选择一个，而状态复制，也就是状态的记录成本太高，所以大多数的单机系统和分布式系统都会使用日志的形式，仅以数据追加的形式保证。

这就要求，在磁盘中写入数据就不能像程序修改内存中变量值那样，直接改变某表某行某列的某个值，而是必须将修改数据这个操作所需的全部信息，包括修改什么数据、数据物理上位于哪个内存页和磁盘块中、从什么值改成什么值，等等，以日志的形式——即仅进行顺序追加的文件写入的形式（这是最高效的写入方式）先记录到磁盘中。只有在日志记录全部都安全落盘，数据库在日志中看到代表事务成功提交的“提交记录”（Commit Record）后，才会根据日志上的信息对真正的数据进行修改，修改完成后，再在日志中加入一条“结束记录”（End Record）表示事务已完成持久化，这种事务实现方法被称为“Commit Logging”（提交日志）。

7.2 undo log：

主要用于实现事务的原子性（Atomicity）和一致性（Consistency）。当事务需要回滚或者其他事务需要读取旧的数据版本时，就需要使用undo log。undo log记录了事务执行过程中对数据的修改，如果事务失败需要回滚，或者其他事务需要读取数据修改前的版本，就会使用undo log中的信息来还原数据。

在事务没提交之前，MySQL 会先记录更新前的数据到 undo log 日志文件里面，当事务回滚时，可以利用 undo log 来进行回滚。

未提交事务，写入后崩溃：程序还没修改完三个数据，但数据库已经将其中一个或两个数据的变动写入磁盘，此时出现崩溃，一旦重启之后，数据库必须要有办法得知崩溃前发生过一次不完整的购物操作，将已经修改过的数据从磁盘中恢复成没有改过的样子，以保证原子性。
已提交事务，写入前崩溃：程序已经修改完三个数据，但数据库还未将全部三个数据的变动都写入到磁盘，此时出现崩溃，一旦重启之后，数据库必须要有办法得知崩溃前发生过一次完整的购物操作，将还没来得及写入磁盘的那部分数据重新写入，以保证持久性。

undo log 还有一个作用，通过 ReadView + undo log 实现 MVCC（多版本并发控制）。

对于「读提交」和「可重复读」隔离级别的事务来说，它们的快照读（普通 select 语句）是通过 Read View + undo log 来实现的，它们的区别在于创建 Read View 的时机不同：

「读提交」隔离级别是在每个 select 都会生成一个新的 Read View，也意味着，事务期间的多次读取同一条数据，前后两次读的数据可能会出现不一致，因为可能这期间另外一个事务修改了该记录，并提交了事务。
「可重复读」隔离级别是启动事务时生成一个 Read View，然后整个事务期间都在用这个 Read View，这样就保证了在事务期间读到的数据都是事务启动前的记录。

7.3 数据库缓冲区设计：

Innodb 存储引擎设计了一个缓冲池（Buffer Pool），来提高数据库的读写性能。

有了 Buffer Poo 后：

当读取数据时，如果数据存在于 Buffer Pool 中，客户端就会直接读取 Buffer Pool 中的数据，否则再去磁盘中读取。
当修改数据时，如果数据存在于 Buffer Pool 中，那直接修改 Buffer Pool 中数据所在的页，然后将其页设置为脏页（该页的内存数据和磁盘上的数据已经不一致），为了减少磁盘I/O，不会立即将脏页写入磁盘，后续由后台线程选择一个合适的时机将脏页写入到磁盘。

写入缓存，设置为脏页：内存数据与磁盘已经不一致，然后定时刷磁盘。

7.4 redo log：

为了配合缓冲区设置出现的产物.

redo log 是物理日志，记录了某个数据页做了什么修改，比如对 XXX 表空间中的 YYY 数据页 ZZZ 偏移量的地方做了AAA 更新，每当执行一个事务就会产生这样的一条或者多条物理日志。

保存未被刷入磁盘的脏页日志。

7.5 bin log:

MySQL 在完成一条更新操作后，Server 层还会生成一条 binlog，等之后事务提交的时候，会将该事物执行过程中产生的所有 binlog 统一写入 binlog 文件。

binlog 文件是记录了所有数据库表结构变更和表数据修改的日志，不会记录查询类的操作，比如 SELECT 和 SHOW 操作。

写入 Binlog：主库写 binlog 日志，提交事务，并更新本地存储数据。
同步 Binlog：把 binlog 复制到所有从库上，每个从库把 binlog 写到暂存日志中。
回放 Binlog：回放 binlog，并更新存储引擎中的数据。

从磁盘读取到id=1的记录，放到内存。
记录undo log 日志。
记录redo log (预提交状态)
修改内存中的记录。
记录binlog
提交事务，写入redo log (commit状态)

1、在第一步、第二步、第三步执行时据库崩溃：因为这个时候数据还没有发生任何变化，所以没有任何影响，不需要做任何操作。

2、在第四步修改内存中的记录时数据库崩溃：因为此时事务没有commit，所以不管有没有将修改的数据写回磁盘，这里都要进行数据回滚，所以这里会通过undo log进行数据回滚。

3、第五步写入binlog时数据库崩溃：这里和第四步一样的逻辑，此时事务没有commit，所以这里要进行数据回滚，会通过undo log进行数据回滚。

4、执行第六步事务提交时数据库崩溃：如果数据库在这个阶段崩溃，那其实事务还是没有提交成功，但是这里并不能像之前一样对数据进行回滚，因为在提交事务前,binlog可能成功写入磁盘了，所以这里要根据两种情况来做决定。

如果binlog中记录了事务提交的相关信息：那么就"认为"事务已经提交了，这里可以根据redo log对数据进行重做。其实你应该有疑问，其实这个阶段发生崩溃了，最终的事务是没提交成功的,这里应该对数据进行回滚。这里主要的一个考虑是因为binlog已经成功写入了，而binlog写入后，那么依赖于binlog的其它扩展业务（比如：从库已经同步了日志进行数据的变更）数据就已经产生了，如果这里进行数据回滚，那么势必就会造成主从数据的不一致。

另外一种情况就是binlog不存在事务记录，那么这种情况事务还未提交成功，所以会对数据进行回滚。