Mysql 索引以及锁初探

前段时间在面试字节的时候，面试官拿着 Sql 问我这个锁和索引之间的联系是什么的时候？人懵住了，这玩意还有联系？之后意识到是自己学习东西太过于肤浅，没有建立体系，导致这么简单的问题没答出来，悔不当初 QAQ。

Mysql 存储数据的方式

Mysql 底层存储数据是通过一个一个数据页所组成的，一页中存储的数据属于同一张表，但同一张表的数据不一定分布在同一页，从粗到细粒度大致是：

表空间 (Tablespace)
 └── 段 (Segment)
      └── 区 (Extent)
           └── 页 (Page, 16KB)
                └── 行记录 (Row)

我们这里主要分析页和行的结构

数据页（Data Page）

上图展示的就是一页的数据内容，Mysql 的行数据被单向链表的形式组织起来，为了提高页内检索效率，所以有了槽和分组的概念。他们的对应关系是，一个数据页中有多个槽，每个槽中有一个或多个数据行，数据行以单向链表的形式组织起来，然后链表头部和尾部分别是记录中的最小记录和最大记录标识。通过这样的形式组织起来的数据有什么好处呢？答曰提高检索效率。如果只单纯使用单向链表，那就意味着每次查找只能单向搜索。而使用槽，槽指针指向了一个分组内的最大记录，那就意味着在一页内可以用二分查找来提高检索的时间复杂度。

行记录（Data Row）

上面讲述了一页是如何组织的，下面来看看一行是如何组织的。这就是一行数据，从左到右分别记载了：

变长字段列表：记录行数据中变长字段占用的字节数
Null 值列表：记录行数据中，可以为 Null 的列是否为 Null，也就是说一列对应一个 Bit 位，如果为 Null，在对应的 bit 位为 0
记录头：这里主要包含了一些辅助信息，比如记录的类型（是否是 B+树的叶子）、下一条记录的位置以及是否被删除标记。
RowId：当表设置了主键或者唯一性约束，则这一列隐藏，如果没设置，则 Mysql 会默认生成 RowId 字段。
TrxId：这条记录是由哪行所生成的。
Rollptr：UndoLog 的列表挂载，用于回滚和 MVCC。上面就是一行记录，也就是说，当你创建一个表，Mysql 底层就是这么组织的。

索引

Mysql 索引分类

按照数据结构：Hash 索引、FullText 索引、B+ 树索引
按照底层存储：聚簇索引、非聚簇索引
按照建立索引的字段类型：主键索引、唯一索引、前缀索引、普通索引
按照字段数量：单列索引、组合索引我们主要来关注聚簇索引和非聚簇索引，我们知道聚簇索引就是主键索引，其存储了主键和整行的数据，而非聚簇索引的一行第一列是索引值，第二行是主键值。为什么？Why？为什么第存全量数据？这是因为 Mysql 的底层数据组织结构造成的，B+ 树存储索引是要存储全量的数据页的，如果说非聚簇索引也存储全量数据，就等于在建立索引的时候，需要将所有数据页进行一次全量拷贝 + 组织，就意味着底层会出现大量重复的数据，所以 InnoDB 选择第二列存储主键值，这样当检索到索引后，只需要再去聚簇索引中，找到对应的数据即可。

Mysql 索引的数据组织结构

我们知道 InnoDB 的索引底层是基于 B+ 树的，而索引和页的关系是什么呢？答案是索引由数据页组成。 Mysql 的数据是这样存的，当你创建一个表并存入数据时，Mysql 会默认生成一个基于主键的聚簇索引，就是无论你主动创建索引与否，Mysql 都会生成聚簇索引，这不只是为了提高检索速度，而是 InnoDB 的行锁机制是基于索引的。所以这里也就 CallBack 到了开头的，索引和锁的关系。

锁

Mysql 以 InnoDB 作为底层存储后，有以下锁：

全局锁
表级锁
行级锁

全局锁

全局锁的粒度非常粗，作用于整个数据库，一般是在实现备份迁移等操作的时候执行，上了全局锁，整个数据库会陷入只读。

flush tables with read lock

全局锁本次不是我们主要探讨的范围，所以按住不表。

表级锁

表级锁可以分为下面几类：

表锁
元数据锁
意向锁
Auto-Inc 锁

表锁

表锁顾名思义，就是将表锁住，分为读锁或写锁

lock table xxx read;
lock table xxx write;

read 锁是表级共享锁，在上锁之后，允许上锁事务和其他事务读取该表，但其和其他事务都不能写这个表，而上锁事务也不能读写其他锁。 write 锁是表级独占锁，上锁后，只允许本事务操作表，阻塞其他所有操作该表的事务。不难看出，其实虽然是表锁，但是实际上粒度还是很粗，往下看。

元数据锁

元数据就是表结构数据，当修改表结构数据的时候，需要加表级的元数据写锁（DML 写锁）。而当我们对表进行 CRUD 操作的时候，是对表加的元数据读锁（DML 读锁）。当我们执行 CRUD 操作的时候买如果有其他事务要修改表结构，此时 DML 写锁会被 DML 读锁阻塞。同理，当有事务在修改表结构的时候，CRUD 操作的 DML 读锁会被 DML 写锁阻塞。

意向锁

意向锁是当我们修改或增加一行数据的时候，为了能当其他线程快速知道他想修改的数据有没有被上锁，而增加的机制。

在使用 InnoDB 引擎的表里对某些记录加上「共享锁」之前，需要先在表级别加上一个「意向共享锁」；
在使用 InnoDB 引擎的表里对某些纪录加上「独占锁」之前，需要先在表级别加上一个「意向独占锁」；我们看下面这个例子：

	TrxA	TrxB
T1	begin	begin
T2	select * from a where id = ’123‘ for update // 因为执行了当前读，所以 123 这行数据加上了 X 锁
T3		select * from a lock in share mode // B 此时想给表 A 加一个 S 锁，但是不知道表内有没有数据上锁，所以需要全表扫描一遍，才能知道

我们发现，事务 B 想要定位事务 A 上的锁，需要将数据全查一遍，耗时耗力，意向锁应运而生。当事务 A 在给某行数据加锁的时候，会先加一个表级的意向锁，告知其他事务当前表中那些数据处于锁态。当事务 B 要加锁之前，直接看表上有没有意向锁，就能很清楚知道了。（注意，表级意向锁只表达意向，不表达阻塞，这点很关键）

	TrxA	TrxB
T1	begin	begin
T2	select * from a where id = ’123‘ for update // 因为执行了当前读，所以 123 这行数据加上了 X 锁，并且给表加了一个 IX 锁
T3		select * from a lock in share mode // B 此时想给表 A 加一个 S 锁，但是不知道表内有没有数据上锁，发现表上有个 IX 锁，所以知道有行处于锁态，事务 B 阻塞

表级意向锁分为 IS 锁和 IX 锁，就是意向共享锁和意向独占锁。

	IS	IX	S	X
IS	兼容	兼容	兼容	不兼容
IX	兼容	兼容	不兼容	不兼容
X	不兼容	不兼容	不兼容	不兼容
S	兼容	不兼容	兼容	不兼容

如何理解这个呢？很简单，首先，表级的 X 锁是要保证表内不能有任何数据在操作的，所以与 IX 锁排他，而 S 锁允许其他事务读该表，所以与 IS 锁是兼容的，但不能和 IX 锁兼容，因为 IX 锁有可能修改数据。至于 IS 和 IX 锁是相互都兼容的，因为 IS 和 IX 只是为了表示表内有没有数据行被锁定而已，不具备额外的语意。

Auto-Inc 锁

Mysql 插入数据时，可以不指定自增主键的字段，其底层会通过 Auto-Inc 加锁然后自增实现。在 Mysql 5.1 之前，都是用这种方式的，当事务中的插入语句执行的时候，给对应表加一个表级的 Auto-Inc 锁，执行完一句，就解开。但是，Auto-Inc 是独占的，也就是说，大量插入操作执行插入操作的时候，性能很差，所以在 5.1 之后，就换了实现方式。在 5.1 后，Mysql 插入数据时，对于自增列，会有两种策略。默认情况下，是这两种策略：当能确定插入行数的时候，使用 Mutex 机制实现，而非表锁；而对于不确定行数的插入，使用 Auto-Inc 表级锁。对于确定插入行数的插入操作，执行插入 → 获取互斥量 → 从自增计数器取号 → 释放互斥量。这样一来，使得锁的粒度细了许多。要知道，他们一个从上到下，从外到内的关系，粒度是：Lock（锁） > Latch（闩） > Mutex（互斥量）。

行级锁

InnoDB 强就强在他锁的粒度有到行级，对比 MyISAM，MyISAM 是没有行级锁的。InnoDB 有下面这些行级锁：

Record Lock
Gap Lock
Next-Key Lock
插入意向锁 InnoDB 的行级锁都依赖于索引，换句话说，Mysql 的行级锁实际上是索引项锁

记录锁（Record Lock）

记录锁是针对表中的某条数据加锁，其粒度是一条数据。当你的查询或者修改能保证定位到一行且唯一的时候，会加记录锁，否则为了保障不发生幻读等问题，会考虑加下面的锁。

间隙锁（Gap Lock）

间隙锁顾名思意，是锁住一个范围内的数据，比如说 A、B、C、E，当你需要在 CE 中插入 D 时，Mysql 就会在 CE 中间加一个间隙锁(C，E)，当其他线程操作 CE 中间的数据的时候，需要先检查 CE 间有没有间隙锁，如果有则需要阻塞。间隙锁是依赖于操作数据范围的右边界的，也就是说，如果你要对(C，E)上间隙锁，锁的信息是在 E 上的，也就是说后续的锁如果要找间隙锁，需要读他想操作的数据的右边第一条数据包含了锁信息。 Why we Need Gap Lock？Mysql 的间隙锁只在 RR 的级别下生效，主要作用实际上是为了防止幻读，先按下不表，后续展开。

临键锁（Next-Key Lock）

临键锁可以理解为 RecordLock + GapLock，即 GapLock 为(C，E)，而临键锁为(C，E]。

插入意向锁

有了意向锁的前车之鉴，也很好理解插入意向锁的作用。插入意向锁也是非互斥的，但是每个事务在加插入意向锁之前，就要判断要插入的区间中有没有间隙锁或者临键锁，如果有，那么这个插入操作会被阻塞。其实际上就是搭配间隙锁使用的。

上锁机制

这里所有的上锁机制都是描述行锁的上锁机制，而且因为本身 InnoDB 分为聚簇索引和非聚簇索引，其也对应了不同的上锁机制。

读操作

按照聚簇索引和非聚簇索引，我们可以把读操作可以分为下面四种情况：

读主键索引或唯一索引命中（聚簇）
读主键索引或唯一索引未命中（聚簇）
读普通索引单点查询（非聚簇）
读普通索引范围查询（非聚簇）
未命中索引

读主键索引或唯一索引命中

当读主键索引或唯一索引命中的时候，比如说下面的语句

select * from students where id = '11'

当 id 作为一个主键的时候，我们读操作单点命中该索引，而主键具备唯一性，所以我们只需要一个 RecordLock 锁住这条数据即可。

读主键索引或唯一索引未命中

当读主键索引或唯一索引为命中的时候，会对读的索引所处的位置加 GapLock，防止幻读。这样一来，当有其他事务想在事务 A 期间在相同位置插入一条数据前，会检查到区间内有一把间隙锁，导致插入操作被阻塞，事务 A 也从而避免了幻读。

读普通索引单点查询

注意，读普通索引单点查询的时候，是否还能通过加一个记录锁保证其可靠性呢？答案是不能的。普通索引最大的特征就是索引列可能存在重复的值，所以如果不能将索引列以及可能发生问题的间隙全部锁住，是不能保证可靠性的。也就是说，假如单点查询命中，此时会在 Mysql 中所有命中列索引都插入一个 RecordLock，并且在这些记录前后都插入间隙锁，防止新数据插入。这个也不难理解，如果不锁住周围，那再插入一个 id = 3 的数据在 id = 4 之前，那又可能会发生幻读。

读普通索引范围查询

范围查询的思路也类似，就是会将范围内所有的行都加锁，这时候就会涉及到 Next-Key Lock。

很好理解，除了对应数据行外，要对每个间隙都严格加锁，以保证不会有其他事务插入数据导致幻读。

未命中索引查询

Mysql 的行锁是依附于索引项锁的，如果未命中索引，那就无法上锁，此时会出现锁升级，也就是升级为一个表级的锁。这样会导致性能严重抖动，所以要尽量避免这种情况的发生。

插入操作

对于下面这样一个 Sql 语句

insert into students ('id', 'name', 'age') values ('12', 'xiaobai', '10')

其底层会先走聚簇索引进行插入，然后维护非聚簇索引。更新聚簇索引的步骤如下：

首先尝试在插入的位置获取插入意向锁（主要检查当前位置有没有被 GapLock 和 Next-Key Lock）。如果获取失败，则阻塞，获取成功，则往下执行。
接着校验是否存在唯一键冲突，如果未出现唯一键冲突，则插入数据并上 X 锁，如果出现唯一键冲突，需要对冲突的键加 S 锁和间隙锁
如果冲突，校验冲突的键是否是已删除的记录或者草稿记录，如果是，则插入记录并加 X 锁
如果冲突的键是正常的记录，那么返回唯一键错误。这里有一个关键点就是，当唯一键冲突的时候，会对冲突的键加 S 锁和间隙锁，这是为什么呢？这里加 S 锁和对这条记录左右加上间隙锁主要是为了校验这个记录是不是一条已经删除的记录或者草稿记录，如果不在左右加上间隙锁，如果此时有其他事务插入了数据，那就乱套了。

更新普通索引的步骤如下：

用普通索引升序 + 主键值升序的原则，找到数据插入位置
在插入位置加上插入意向锁，如果加锁失败，则阻塞，如果成功，则继续
在插入位置插入数据并加上 X 锁

插入死锁例子

原始数据如下

id	key	index	data
1	c	C	3
2	g	G	7
3	j	J	10
4	k	K	11

执行下面两个事务

	Trx_A	Trx_B
T1	bgein	begin
T2	insert into ’table’ (‘key’, ‘index’, ‘data’) values (’n’, ‘N’, 14); // 在(k, +∞) 加插入意向锁，插入数据成功，并且对记录增加 X 锁
T3		insert into ’table’ (‘key’, ‘index’, ‘data’) values (’n’, ‘N’, 14); // 插入意向锁插入成功，唯一值校验失败，对 n 左右加上间隙锁，然后在申请 n 的 S 锁的时候，发生阻塞
T4	insert into ’table’ (‘key’, ‘index’, ‘data’) values (’m’, ‘M’, 99); // 申请(j, n) 的插入意向锁，发现事务 B 加了间隙锁，所以阻塞
T5	事务 A 阻塞死锁	事务 B 阻塞死锁

按照上面两个事务执行，可能会发生死锁。Mysql 有自己的死锁检测算法，当其检测到死锁的时候，会主动回滚其中一个事务。

更新操作

对于下面这样一条 Sql

update students set age=10 where name='xiaobai'

对于聚簇索引和非聚簇索引，他们采取的加锁方案是不一致的：

加锁步骤

对于非聚簇索引：

先定位到所有 name 相等的记录，然后对这些记录加 Next-key Lock。如果加锁失败，则阻塞。

对于聚簇索引：

根据非聚簇索引的主键值，在聚簇索引中找到所有符合条件的记录
对聚簇索引的匹配到的记录增加 X 锁

修改步骤

如果只修改非索引列，则直接复用 X 锁进行修改
修改二级索引列，此时需要删除原索引行，然后重新插入，相当于旧记录用 X 锁删除，新记录用插入意向锁插入数据后对新数据加 X 锁（相当于 Delete 操作 + Insert 操作）
修改主键值，原行 X 锁，然后定位到新的页的位置，然后加插入意向锁，最后插入

删除操作

删除操作分为以下几种情况，还是对比聚簇索引和非聚簇索引：

命中聚簇索引
未命中聚簇索引
命中普通索引
未命中普通索引
未命中索引

当命中聚簇索引（唯一键）

当命中唯一键的时候，直接对那一行数据加 X 锁即可

未命中聚簇索引

当唯一键不存在的时候，会对所处范围加 GapLock 这里加 X 锁的意图很明显是要修改数据，防止数据被并发修改出错，而这里加间隙锁的意图是什么呢？间隙锁在这里也是为了幻读的发生。

命中普通索引（非唯一键）

当命中非聚簇索引的时候，因为非唯一键，所以需要将每条匹配的数据都加上 X 锁，然后将每条数据左右之间都加上间隙锁，X 锁保证并发修改，间隙锁防止再插入相同键的数据。

未命中非普通索引

到了这一步，其实和上面的查询也很相似，为了防止幻读，Mysql 会给对应的位置插入间隙锁，防止其他事务插入数据进而导致幻读。

未命中索引或者没有使用索引

因为 InnoDB 的行锁是基于索引的，所以此时如果要用非索引列删除数据，则会直接加一个表级的 X 锁。

参考文献及博客

万字解析 mysql innodb 锁机制实现原理
 小林 Coding 图解 Mysql

Mysql 存储数据的方式#

数据页（Data Page）#

行记录（Data Row）#

索引#

Mysql 索引分类#

Mysql 索引的数据组织结构#

锁#

全局锁#

表级锁#

表锁#

元数据锁#

意向锁#

Auto-Inc 锁#

行级锁#

记录锁（Record Lock）#

间隙锁（Gap Lock）#

临键锁（Next-Key Lock）#

插入意向锁#

上锁机制#

读操作#

读主键索引或唯一索引命中#

读主键索引或唯一索引未命中#

读普通索引单点查询#

读普通索引范围查询#

未命中索引查询#

插入操作#

插入死锁例子#

更新操作#

加锁步骤#

修改步骤#

删除操作#

当命中聚簇索引（唯一键）#

未命中聚簇索引#

命中普通索引（非唯一键）#

未命中非普通索引#

未命中索引或者没有使用索引#

参考文献及博客#