MySQL

数据库三大范式

1. 第一范式：确保每列保持原子性
2. 第二范式：确保表中的每列都和主键相关
3. 第三范式：确保每列都和主键直接相关，而不是间接相关，消除传递依赖

InnoDB使用B+树作为索引

B树和B+树的介绍：https://www.cnblogs.com/makai/p/10861296.html
B树和B+树的区别：B树所有节点都存放数据，B+树只在叶子节点存放数据。
B+更适合作为索引的原因：

1. B+树的磁盘读写代价更低：B+树的非叶子节点没有关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对磁盘IO次数就降低了。
2. B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点在关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3. B+树的区间查询效率更高：由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫描一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适用于区间查询。

不使用AVL索引的原因：大规模的数据会使树的深度过大而造成磁盘IO过于频繁进而导致效率低下。
不使用哈希索引的原因：虽然单值查询效率高，但是撑不住范围查询。
不使用数组索引的原因：虽然查询效率高，但是增删效率不够。

InnoDB、MyISAM、Memory

参考：https://segmentfault.com/a/1190000008227211

三种对比：

使用场景：

• InnoDB：支持事务处理和外键，支持崩溃修复和并发控制。对于频繁更新和删除的表，也可以选择InooDB。
• MyISAM：插入数据库快，空间和内存使用比较低。对于完整性和并发性要求比较低的表，可以选择MyISAM。
• Memory：所有的数据都在内存中，数据的处理速度快，但是安全性不高，适用于临时查询且数据量不大的表。

InnoDB选择自增id主键

如果使用自增ID作为主键：
自增的主键的值是顺序的，所以InnoDB把每一条记录都存储在一条记录的后面。当达到页面的最大填充因子时候（innodb默认的最大填充因子是页大小的15/16，会流出1/16的空间留作以后的修改）：

1. 下一条记录就会写入新的页中，一旦数据按照这种顺序的方式加载，主键页就会近乎于顺序的记录填满，提升了页面的最大填充率，不会有页的浪费。
2. 新插入的行一定会在原有的最大数据行下一行，MySQL定位和寻址很快，不会为计算新行的位置而做出额外的消耗。
3. 减少了页分裂和碎片的产生。

如果使用UUID作为主键：
因为UUID相对顺序的自增id来说是毫无规律可言的，新行的值不一定要比之前的主键的值要大，所以innodb无法做到总是把新行插入到索引的最后，而是需要为新行寻找新的合适的位置从而来分配新的空间。
这个过程需要做很多额外的操作，数据的毫无顺序会导致数据分布散乱，将会导致以下的问题：

1. 写入的目标页很可能已经刷新到磁盘上并且从缓存上移除，或者还没有被加载到缓存中，innodb在插入之前不得不先找到并从磁盘读取目标页到内存中，这将导致大量的随机IO。
2. 因为写入是乱序的，innodb不得不频繁的做页分裂操作，以便为新的行分配空间，页分裂导致移动大量的数据，一次插入最少需要修改三个页以上。
3. 由于频繁的页分裂，页会变得稀疏并被不规则的填充，最终会导致数据会有碎片。

把随机值载入到聚簇索引以后，有时候会需要做一次OPTIMEIZE TABLE来重建表并优化页的填充，这将又需要一定的时间消耗。

总结：使用innodb应该尽可能的按主键的自增顺序插入，并且尽可能使用单调的增加的聚簇键的值来插入新行。

MySQL主从复制流程

涉及文件：

1. Master的binlog：逻辑日志
2. Slave的master.info：主库信息
3. Slave的relay log：中继日志
4. Slave的relay-log.info：relay log应用的信息

涉及线程：

1. 主库：Binlog_Dump Thread
2. 从库：Slave_IO Thread
3. 从库：Slave_SQL Thread

流程如下：

1. Slave的IO线程会读取master.info文件中配置好的主库信息，比如说存放的有：Mater数据库的用户名密码、端口和binlog索引位置，获取到信息之后去连接Master的主库IO线程，并请求从指定日志文件的指定位置之后的日志内容；
2. Master接收到Slave的IO请求后，通过负责复制的Binlog_Dump线程根据请求信息读取指定日志指定位置之后的日志信息，返回给Slave。返回信息中除了日志更新信息，还包括binlog名称和binlog位置；
3. Slave的IO线程将接收到的日志内容更新到本机的relay log（中继日志）文件的最末端，并将读取到的binlog名称和binlog位置保存到master.info文件中；
4. Slave的SQL线程检测到relay log中新增内容后，会将relay log的内容解析成SQL语句，然后在本数据库中按照解析出来的顺序执行，并在relay-log.info中记录当前relay log名称和relay log位置。

Limit&Offset大数据优化

参考：https://www.jb51.net/article/214861.htm

1. 使用覆盖索引 + 子查询优化 (先在索引树中找到起始位置id的值：where id > select id from table order by id limit m, n)；
2. 起始位置重定义，记住上次查询结果的主键位置，避免使用偏移量offset；
3. 降级策略，配置limit的偏移量offset和获取数的最大值，超过则返回空数据。

读已提交和可重复读

参考：https://www.cnblogs.com/luozhiyun/p/11216287.html

InnoDB会为每个事务创建一致性视图ReadView，用于解决RC(Read Commited)和RR(Read Repeatable)隔离级别的事务。
ReadView中主要包含4个比较重要的内容：

• m_ids：表示在生成ReadView时当前系统中活跃的读写事务的事务id列表。
• min_trx_id：表示再生成ReadView时当前系统中活跃的读写事务中最小的事务id，也就是m_ids中的最小值。
• max_trx_id：表示生成ReadView时系统中应该分配给下一个事务的id值。
• creator_trx_id：表示生成该ReadView的事务的事务id。

对于使用InnoDB引擎的表来说，它的聚簇索引记录都包含必要的隐藏列：

• trx_id：每个事务对某条聚簇索引记录进行改动时，都会把该事务的transaction id赋值给trx_id隐藏列。
• roll_pointer：对记录进行该送，会把旧版本记录写入到undo log日志，roll_pointer指向修改前的版本。

在访问某条记录时，只需要按照下边的步骤判断记录的某个版本是否可见：

1. 如果被访问版本的trx_id属性值与ReadView中的creator_trx_id值相同，说明当前事务在访问它自己修改过的记录，所以该版本可以被当前事务访问；
2. 如果被访问版本的trx_id属性值小于ReadView中的min_trx_id值，说明生成该版本的事务在当前事务生成ReadView前已经提交，所以该版本可以被当前事务访问；
3. 如果被访问版本的trx_id属性值大于ReadView的max_trx_id之间，说明生成该版本的事务在当前事务生成ReadView后才开启，所以该版本不可以被当前事务访问；
4. 如果被访问版本的trx_id属性值在ReadView的min_trx_id和max_trx_id之间，那就需要判断一下trx_id属性值是不是在m_ids列表中，如果在，说明创建ReadView时生成该版本的事务还是活跃的，该版本不可以被访问；如果不在，说明创建ReadView时生成该版本的事务已经被提交，该版本可以被访问。

在MySQL中，RC和RR隔离级别的主要区别就在于生成ReadView的时机不同：

• 读已提交：每次读取数据前都生成一个ReadView
• 可重复读：第一次读取数据时生成一个ReadView

InnoDB如何解决幻读

参考1：https://blog.csdn.net/weixin_43705457/article/details/104849943 参考2：https://www.cnblogs.com/crazylqy/p/7821481.html

为了防止幻读，InnoDB采用next-key锁定算法，该算法将记录锁与间隙锁相结合，记录锁防止更新，间隙所防止插入。
InnoDB以这样的方式执行锁定：当它搜索或扫描索引时，它会在遇到的索引记录上设置共享锁或者独占锁。

对于不同的where查询条件，间隙锁的加锁范围不同：

1. id = n：向左扫描获取一个最靠近n的值l（不存在则 l = -∞），向右扫描获取一个最靠近n的值r（不存在则 r = +∞），在[l, r)这个范围内加间隙锁。
2. id > n：向左扫描获取一个最靠近n的值l（不存在则 l = -∞），在[l, +∞)这个范围内加间隙锁。
3. id < n：向右扫描获取一个最靠近n的值r（不存在则 r = +∞），在(-∞, r)这个范围内加间隙锁。
4. id between n1 and n2：向左扫描获取一个最靠近n1的值l（不存在则 l = -∞），向右扫描获取一个最靠近n2的值r（不存在则 r = +∞），在[l, r)这个范围内加间隙锁。

例如：
现在有一张数据库表gap_lock，内容如下：

-- 案例1
start transaction;
select * from gap_lock where number = 4 for update;
检索条件number=4，向左取得最靠近的值2作为左区间，向右取得最靠近的值5作为右区间。
所以这时候number间隙锁的范围是(2, 4)、(4, 5)，即这时候不能插入number=3的数据。
-- 案例2
start transaction;
select * from gap_lock where number = 7 for update;
检索条件number=7，数据库中没有number=7的相关记录，向左取得最靠近的值4作为左区间，向右取得最靠近的值11作为右区间。
所以这时候number间隙锁的范围是[5, 11)，即这时不能插入number大于等于5且小于11的数据。
-- 案例3
start transaction;
select * from gap_lock where number = 13 for update;
检索条件number=13，向左取得最靠近的值11作为左区间，向右由于没有记录因此取得无穷大作为右区间。
所以这时候number间隙锁的范围是[11, +⚮)，即这时不能插入number大于等于11的数据。
-- 案例4
start transaction;
select * from gap_lock where number > 5 for update;
检索条件number>5，向左取得最靠近的值5作为左区间，
所以这时候number间隙锁的范围是[5, ++⚮)，即这时不能插入number大于等于5的数据。
-- 案例5
start transaction;
select * from gap_lock where number < 13 for update;
检索条件number<13，向右由于没有记录因此取得无穷大作为右区间。
所以这时候number间隙锁的范围是(-∞, +∞)，即这时无法插入数据。
-- 案例5
start transaction;
select * from gap_lock where number between 6 and 10 for update;
检索条件number<13，向左取得最靠近的值5作为左区间，向右取得最靠近的值1作为右区间。
所以这时候number间隙锁的范围是[5, 11)，即这时不能插入大于等于5且小于11的数据。