mysql索引B+树、MVCC、锁一文搞懂

1.innodb索引

innodb是页存储，一页是16K。

一个表的行数据都放到页里，单页都是单链表递增排序。
每个页之间都是双向链表保存。该页标记成数据页。

根据id查询时，也不知道在哪个数据页上。

因此会对数据页建立一个索引，每一个索引值的内容是数据页id，以及每一个数据页最小的id。通过二分就很容易定位到数据页。

当然，这个索引页也是16K，当数据足够多，也会进行索引页分类。

所以当索引页变多后，上面也会在建立一层索引页。

一页16*1024=16284字节

假设一个表的字段 8(bigint)+3(int)*3+8*2(timestamp)+3(utf8汉字)*20(长度)=93字节 已经很多大了。

平均一页有150条数据。

但是索引页的数据页号+索引最小值也就16字节。一页大概有1000条数据

那三层结构的树，就能支撑 150*1000*1000=1.5亿条数据。

所以一般三层的B+树就够了。也就进行三次磁盘IO，读取三次数据页。

//redo log的作用
mysql是先写日志在写数据。由于mysql使用内存buffer，并且一条sql修改的数据，会修改很多数据页，尤其是索引多的情况。并且这些数据页都是随机读取，数据很慢，因此mysql不会为很小的一次改动，就把这么多的数据页写到磁盘上。但是只写内存，服务器宕机会导致数据丢失，因此会记录redo log。这个log是磁盘顺序写，速度比较快。这就是redo日志的作用。

为什么使用B+树而不是B树

我们注意到，innodb的数据的索引模式，很像一颗树。一层层构建索引。
同时这种数据结构，数据也必须放到叶子节点上。这也是最契合需求的数据结构。

如果像B树一样，把数据放到节点上，那每一个页的能放的数据就很少，这样树的层数必然更深。从上面的分析中就可发现，150*1000*1000 随着表字段或者内容的增多，叶子页的能容纳的数据会越来越少，不过索引页里放的都是页号和索引值的最小值，这样必然索引的B+树不会超过4层就可满足数据要求。

同时B+的叶子节点之间是个链表，这样范围查找时，只需要对叶子节点进行遍历即可。

B树会把索引值和数据都在节点上，这样做范围查找时，必然要进行回溯或者多次查找。

索引

主键索引上有数据信息，因此称为聚簇索引。
其余页的索引，就是把内节点的主键最小值替换成索引列对应最小值即可。同时叶子节点存放的是索引列和主键ID的信息，因此需要再次回表查询。这种列索引称为二级索引或者辅助索引。

联合索引，就是一个内节点或者叶子节点上，有两个值。
这也解释了为啥遵循最左原则，毕竟联合索引的排序，是先比较第一个值，在比较第二个值。

2.mvcc

首先提下mysql的四种隔离级别

读未提交
读已提交
可重复读
串行

读未提交直接读取数据最新的数据就行（包括未提交的事务）。串行使用锁就行可。
所有mvcc也仅对读已提交和可重复读这两个隔离级别下的

事务中的update操作，会在聚簇索引和undo日志的 poll_pointer属性，构成一个记录的版本链。

ReadView

在上面两种隔离级别下，发生读操作时，会在不同时机生成ReadView。
其中的4个重要的内容

m_ids 生成ReadView时，活跃的（未提交的）事务id
min_trx_id 生成ReadView时，活跃的事务中，最小的事务id
max_trx_id 生成ReadView时，系统应该分配给下一个事务的id（事务id是连续递增的，注意，这里不是活跃id的最大值！！！）
creator_trx_id 生成该ReadView的事务id

有了ReadView后，在访问某条记录时，会遍历它的版本链，发现可以读到的数据。

1.如果被访问的trx_id跟ReadView的creator_trx_id一致的话，意味着当前事务访问它自己修改的记录，所以该版本可以被当前事务访问。

2.如果被访问版本的trx_id小于ReadView的min_trx_id，表示这个版本在生成ReadView之前已经提交，可以被访问。

3.如果被访问版本的trx_id大于max_trx_id，表示生成该版本的事务在当前事务ReadView生成之后开启，所以该版本也不被访问。

4.如果在min和max之间，并且在m_ids中，则不能被访问，反之说明该版本对应的事务已经结束，是可以访问的。

看完上面ReadView可见的规则后，一般都会有些迷茫的。尤其是4的规则。结合下面两种不同隔离级别下ReadView生成的时机，你就理解上面ReadView的设计了

读已提交级别

该级别规定只能读取已提交的，所以ReadView中m_ids表示正在活跃事务，也就是没有提交的事务，所以不能读取。哈哈，看到这，是不是对4理解了。活跃的事务不可读。

所以一次事务中多次读，每次都生成ReadView，检查对应的数据版本即可。

可重复读

该隔离级别要求 一次事务多同一条数据的读取，每次都得一样。因此每次都使用第一次读创建的ReadView即可。这样每次读的内容都一样了。

所以这里对ReadView是一种复用，这两种隔离级别的区别是ReadView的生成时机不一样。

二级索引与MVCC

前面说的都是聚簇索引的MVCC。
二级索引页的Page Header中有一个PAGE_MAX_TRX_ID的属性，当页面进行写操作时，发现页面的该值小于当前事务ID，直接将事务ID设置为页面的PAGE_MAX_TRX_ID。

如果读事务的ReadView的min_trx_id大于页面的最大事务id，那么该页数据都可被查看。如果小于，只需要进行回表之后，在进行可见性判断。

根据二级索引的主键id后，得到对应的聚簇索引记录后，在按照之前的逻辑进行查看。（还记得之前提到undo log里，如果没有修改的字段，log里没有，这里还需要对链表进行查询，找到该字段的最新值）

3.锁

锁模式
S锁 X锁,意向S锁，意向X锁

锁类型

LOCK_GAP
也就是间隙锁，它锁住的是某条记录之前的位置。
例如有两条主键为3和8的两条记录，3-8之间没有记录，当在8上加了间隙锁，那么其他事物，是不允许往3-8之间写数据了。

LOCK_REC_NOT_GAP单独加到一条记录上

LOCK_ORDINARY GAP和记录锁的合体，也是next-key锁

select for update是加X锁

表级锁 每个行级锁，都有对应IS，IX意向锁加到表上。

mysql加锁的方式太多，遇到死锁，可以根据死锁日志去看加锁的状态。

这里有几篇加锁case比较好的文章:https://mp.weixin.qq.com/s/Lavoo9sgulOzxQ22GRAamw 有兴趣的话，可以读一读