索引

底层结构

hash表索引缺点：

1. 利用hash存储需要将所有的文件添加到内存，比较耗费内存空间

2. 如果所有的查询都是等值查询，那么hash确实很快，但是在实际场景中查找的数据更多，而且不都是等值查询，因此hash表就不太合适

3. 不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

二叉树索引格式缺点：

1. 不论是二叉树还是红黑树，都会因为树的深度而造成io次数变多，影响数据读取的效率。

2. 平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高

B树索引格式：

1. 若非叶子结点中的数据过大，比如每次1.9k，磁盘大小为4k。此时会退化成二叉树，会出现树的深度加深而造成io次数变多，影响读取效率。

2. B树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。

3. 如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

4. 联合索引一定满足最左原则，若跳过最左的第一个索引，直接从第二个索引开始搜索的话，第二个索引不一定是排好序的，会需要进行全栈搜索。

InnoDB和MyIsam

mysql一页 有16kb大

MyIsam

1. MyISAM的数据文件和索引文件是分开存储的。MyISAM使用B+树构建索引树时，叶子节点中存储的键值为索引列的值，数据为索引所在行的磁盘地址。

InnoDB中Data存储的为行数据，而MyIsam中存储的是磁盘地址。

2. 在 MyISAM 中,辅助索引和主键索引的结构是一样的，没有任何区别，叶子节点的数据存储的都是行记录的磁盘地址。只是主键索引的键值是唯一的，而辅助索引的键值可以重复。

3. 查询数据时，由于辅助索引的键值不唯一，可能存在多个拥有相同的记录，所以即使是等值查询，也需要按照范围查询的方式在辅助索引树中检索数据。

InnoDB

innoDB将所有的信息一起存放，包括数据和索引

主键索引（聚簇索引）

每个InnoDB表都有一个聚簇索引 ，聚簇索引使用B+树构建，叶子节点存储的数据是整行记录。一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下：

1. 在表上定义主键PRIMARY KEY，InnoDB将主键索引用作聚簇索引。

2. 如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。

3. 如果以上两个都没有，InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索引。该ROWID字段会在插入新行时自动递增。

在中InnoDB，辅助索引中的叶子节点存储的数据是该行的主键值,在检索时，InnoDB使用此主键值在聚簇索引中搜索行记录。

锁

根据加锁的范围，MySQL里面的锁大致可以分成全局锁、表级锁和行锁三类

全局锁

全局锁就是对整个数据库实例加锁。

在此状态下，其他线程进行下列操作会被阻塞：

1. 数据的更新

2. 表的定义（表的建立，和结构的修改）

3. 更新类事务的提交

使用场景：

做全库逻辑备份，即将整库每个select出来成文本。

缺点：

• 如果在主库上面进行备份，那么会造成在整个备份过程中，更新过程不可执行，全部业务都得搁置。

• 如果在从表上面进行备份，那么在备份期间从库不能执行主库同步过来的binlog，会导致主从延迟。

表锁

MySQL里面表级别的锁有两种：一种是表锁，一种是元数据锁（meta data lock，MDL）

表锁需要显示的加上，针对于访问线程。如果在某个线程A中执行lock tables t1 read,t2 wirte;这个语句，则其他线程写t1、读写t2的语句都会被阻塞。同时，线程A在执行unlock tables之前，也只能执行读t1、读写t2的操作。连写t1都不允许

MDL不需要显式使用，在访问一个表的时候会被自动加上。MDL的作用是，保证读写的正确性。在对表进行增删改查时，对表进行mdl读锁；对表进行结构变更，对表加上mdl写锁。

行锁

MySQL的行锁是在引擎层由各个引擎自己实现的。但不是所有的引擎都支持行锁，比如MyISAM引擎就不支持行锁

两段锁协议

将事务分成两个部分，加锁和解锁。

死锁和死锁检测

解决死锁的两种策略：

• 一种策略是，直接进入等待，直到超时。这个超时时间可以通过参数innodb_lock_wait_timeout来设置，innoDB默认超时未50s

• 另一种策略是，发起死锁检测，发现死锁后，主动回滚死锁链条中的某一个事务，让其他事务得以继续执行。将参数innodb_deadlock_detect设置为on，表示开启这个逻辑

如果所有事务都要更新同一行的场景，每个新来的被堵住的线程都要判断会不会由于自己的加入导致死锁，这是一个时间复杂度是O(n)的操作

怎么解决由这种热点行更新导致的性能问题？

1. 如果确保这个业务一定不会出现死锁，可以临时把死锁检测关掉

2. 控制并发度

3. 将一行改成逻辑上的多行来减少锁冲突。以影院账户为例，可以考虑放在多条记录上，比如10个记录，影院的账户总额等于这10个记录的值的总和。这样每次要给影院账户加金额的时候，随机选其中一条记录来加。这样每次冲突概率变成员原来的1/10，可以减少锁等待个数，也就减少了死锁检测的CPU消耗

mysql 内存和日志

内存模型

mysql内存模型

Buffer Pool模型

Buffer Pool模型

buffer pool里面有三个链表：

free链表 ：其作用是管理空闲页，实际上存储的是一个个小控制块 ，控制块中存放的是对应结点的地址指针

flush链表：其作用是管理脏页，结构和free链表相同 ，但表达意义不同

lru链表：其作用是进行淘汰页、将最近最久未使用的页替换出来。通常将lru链表分成热数据部分和冷数据部分，比例默认为5 ： 3。

• 设置为2部分的原因为： 若为设置冷热区分 ， 依次全表扫描就会将原理的大多数热点页全部替换掉，但后续替换进去的页实际访问量很少，得不偿失。

• 冷数据区域数据进入热数据区域的时机：访问同一页的时间间隔 >1s 。为何间隔时间大于而非小于1秒 ， 是因为如果全表扫描的话，数据是一行一行的遍历，相同的一页会很快的被访问，时间间隔远远小于一秒。

日志

日志分布图

redo log（物理日志）

1. 若脏页没有来得及刷新到磁盘中，mysql挂掉了。可使用redo log进行恢复 -------> 读取磁盘中原来的数据 + redolog 中的操作 == 在原数据上将以前的操作再做一遍，以达到恢复的效果。

2. 重做时 ，只需要顺序的读取redolog ，是顺序io，速度快。

redolog更新

     磁盘中的redolog file默认是2个 ， 当两个都写满了的时候，会触发检查点，将其中某个logfile文件中的操作结合buffer pool中的脏页刷新到磁盘中。 例如： 0号文件满了 ， 将继续写入当1号文件。若1号文件也满了，后续动作是触发checkpoint ， 将0号文件中的对应的脏页 刷新到磁盘中，后将redo log记录覆盖到0号文件中。

redolog持久化

即： 将log Buffer中的缓存写入到磁盘中（redo log）。

更新时机（innoDB_flush_log_at_trx_commit参数控制）

配置值	描述
0	表示提交事务时，不立刻对redo log进行持久化，这个任务交给后台线程去做（相当于定时刷新）
1	表示事务提交时，立刻把redo log进行持久化 （默认使用）
2	表示事务提交时，立即将redo log写入操作系统缓冲区，并不会直接将redo log进行持久化，这种情况下，如果数据库挂了，但是操作系统没挂，那么事务的持久性还是可以保证的。

bin log（逻辑日志）

• 二进制文件

• binlog再mysql的server层实现

• binlog为逻辑日志，记录的是一条语句的原始逻辑

• binlog不限大小，追加写入，不会覆盖以前的日志

bin log 和redo log区别

bin log中记录的是一条一条的sql语句，redolog 记录的是某页上的某个位置。当恢复时，binlog需要重新进行sql的写入更改（需要查询等） ， redolog可以直接进行修改。

undo log

相当于与原来的sql 进行相反的操作

数据更新写入流程图

数据更新写入流程图

二阶段提交

mysql一页有16kb ， 而操作系统一页为4kb ， 故将数据库页数据写到磁盘中需要4次。若写的某一次中系统掉电了，则会使得数据不一致。

使用双写缓冲区保证一致性

1、写入双写缓冲区，写入成功，则进行后续；没写成功，也没有影响，数据库仍然处在一致性状态

2、写入表空间，写入完成则进行数据持久化完成。若还未写入完成时，掉电，也没有影响，double write buffer 的数据时持久化好的，可以直接使用。

update操作

1. 更新buffer pool里面的页里面的数据

2. 生成一个redo log

3. commit，持久化 这个redo log对象

操作流程：

1. server服务层的执行器，调用存储引擎层的API接口，去查询数据。

2. innodb存储引擎层查询buffer pool缓存中的数据。

3. 如果查询缓存中包含待查询的数据，则直接返回给server服务层的执行器。

4. 如果缓存中没有结果则从磁盘中去读取数据，读取数据后，再返回给server服务层，同时把查询到的数据更新到buffer pool中的数据内容。

5. server层的执行器收到查询后的数据后，执行更新操作。

6. server层调用innodb存储引擎层的API接口更新数据。

7. innodb 存储引擎层更新数据到change buffer缓存池中。

8. innddb存储引擎层记录redolog，并把其状态设置为prepare状态。

9. innodb存储引擎层通知server的执行器，change buffer已经更新，redolog已经进入prepare待提交的就绪状态，可以记录binlog日志的。

10. server层的执行器记录binlog到binlog的缓冲池中。（这里缓冲池中的日志何时刷盘就是通过参数sync_binlog来控制的）

11. server层的执行器在记录完binlog之后，通知innodb存储引擎层，binlog已经记录完成。

12. innodb存储引擎层收到server记录完binlog的通知后，更新redolog buffer中的redolog为commit状态。（此时redolog buffer中的日志何时刷盘就是通过参数innodb_flush_log_at_trx_commit来控制的。）

事务和隔离级别

ACID特性实现原理

• 原子性 undo log

• 持久性 redo log

• 隔离性 MVCC

隔离级别

1. 读未提交 （read-uncommitted） 可能出现脏读 会话a会获得其他会话的未提交到数据库中的数据

2. 读已提交 (read - committed) 可能出现不可重复读

   会话b开启事务、修改数据、但未提交，此时b可以看到当前的数据 会话a看到的还是修改前的数据。即，只 有一个事务的提交完成后，另外一个会话才能看到修改后的值

   问题：不可重复读，在同一个事务中查询两次表，出现的结果不一样

   • 1. 会话a开启事务，会话b也开启事务。两个事务同时进行查询，出现结果一致，假设结果为22.
   • 2. 会话b，对值进行修改为99，提交事务。此时会话b再次读取值为修改后的值99.
   • 3. 会话a再次读取值，值也为99. 此时会话a的事务还未结束，本应该出现的值为修改前的22，此时值为99.出现了 不可重复读现象，即读取一张表的同一数据，结果不一致。

3. 可重复读 （repeatable - read） 可能出现幻影读

   自己的事务没有提交或者回滚，是不能看到事务的操作的。

   问题：

   幻影读：第二次查询比第一次查询多了记录。

   1. 会话a和会话b都开启事务。

   2. 会话b对表新增一条数据，提交。此时会话a对表进行了第一次查询，因为还未提交或者回滚事务，会话b的事务影响不到会话a的事务，即：会话看到的还是以前的数据。

   3. 会话a此时提交或者回滚事务。进行第二次查询，此时查询数据多出来一条数据。出现幻影读

4. 串行化 （serializable）

   进行查询或者修改的时候会对表进行加锁操作，保证是串行进行

   脏读、不可重复读、幻读

MVCC 解决脏读 和 不可重复读

• RC 读已提交 生成readview的时机为 ， 在同一个事务中每次select时生成一个对应的readview，一一对应

• RR 可重复读 以事务为单位生成readview

幻影读解决

使用间隙锁解决幻影读

innoDB的锁机制原理

InnoDB行锁：给索引上的索引项加锁

1. 共享锁

2. 排他锁

3. 意向共享锁

4. 意向排他锁

5. 自增锁

6. 临键锁

> < between 
    锁定区间左开右闭

7. 间隙锁

临键锁没有匹配到记录，就会退化成间隙锁

8. 记录锁

顾名思义，记录锁就是为某行记录加锁，它封锁该行的索引记录.该索引必须是主键锁或者唯一索引列。

脏页刷新

部分刷新 fuzzy checkpoint

1. 无论如何，定时刷新

   当LRU中列表中空闲页不足时，强制LRU删除一些末尾的页，如果存在脏页，那么需要checkpoint刷新

2. master thread中的定时刷新机制

   1)InndoDB1.0.x版本之前的master thread。

   每秒，会进行一次 dirty too much checkpoint。

   每10秒

   判断过去10秒的IO操作是否小于200次，如果是，刷100个脏页；

   判断系统当前脏页比例，如果超过70%，刷新100个；如果小于70%，刷新脏页的10%

   2)InndoDB1.2.x版本之前的master thread。

   在1.0.x存在硬编码，每秒最多只会刷新100个脏页到磁盘中，这种规定其实限制了性能更高的SSD磁盘。

   在1.0.x版本，可以使用innodb_io_capacity来表示磁盘io的吞吐量。刷新脏页的数量由innodb_io_capacity来控制，默认是200。

   总结

全部刷新

sharp checkpoint：在数据库关闭时，刷新所有的脏页到磁盘，这里有参数控制，默认是开启的