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

思维导图

image-20240427152900819

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,并更新存储引擎中的数据。

image-20240427152009197

  1. 从磁盘读取到id=1的记录,放到内存。

  2. 记录undo log 日志。

  3. 记录redo log (预提交状态)

  4. 修改内存中的记录。

  5. 记录binlog

  6. 提交事务,写入redo log (commit状态)

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

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

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

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

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

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