索引底层原理-锁机制

• 2022 年 3 月 7 日
• 筆記
• 数据库, 锁

索引

注意：本小节会涉及数据结构与算法相关知识。

索引就好像我们书的目录，每本书都有一个目录用于我们快速定位我们想要的内容在哪一页，索引也是，通过建立索引，我们就可以根据索引来快速找到想要的一条记录，大大提高查询效率。

本版块我们会详细介绍索引的几种类型，以及索引的底层存储原理。

单列索引

单列索引只针对于某一列数据创建索引，单列索引有以下几种类型：

• NORMAL：普通的索引类型，完完全全相当于一本书的目录。
• UNIQUE：唯一索引，我们之前已经用过了，一旦建立唯一索引，那么整个列中将不允许出现重复数据。每个表的主键列，都有一个特殊的唯一索引，叫做Primary Key，它不仅仅要求不允许出现重复，还要求不能为NULL，它还可以自动递增。每张表可以有多个唯一索引，但是只能有一个Primary索引。
• SPATIAL：空间索引，空间索引是对空间数据类型的字段建立的索引，MYSQL中的空间数据类型有4种，分别是GEOMETRY、POINT、LINESTRING、POLYGON，不是很常用，这里不做介绍。
• FULLTEXT：全文索引（MySQL 5.6 之后InnoDB才支持），它是模糊匹配的一种更好的解决方案，它的效率要比使用like %更高，并且它还支持多种匹配方式，灵活性也更加强大。只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引。

我们来看看如何使用全文索引，首先创建一张用于测试全文索引的表：

CREATE TABLE articles (
  id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
  title VARCHAR(200),
  body TEXT,
  FULLTEXT (body));

INSERT INTO articles VALUES
	(NULL,'MySQL Tutorial', 'DBMS stands for DataBase ...'),
	(NULL,'How To Use MySQL Efficiently', 'After you went through a ...'),
	(NULL,'Optimising MySQL','In this tutorial we will show ...'),
	(NULL,'1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
	(NULL,'MySQL vs. YourSQL', 'In the following database comparison ...'),
	(NULL,'MySQL Security', 'When configured properly, MySQL ...');

最后我们使用全文索引进行模糊匹配：

SELECT * FROM articles WHERE MATCH (body) AGAINST ('database');

注意全文索引如何定义字段的，match中就必须是哪些字段，against中定义需要模糊匹配的字符串，我们用作查找的字符串实际上是被分词之后的结果，如果进行模糊匹配的不是一个词语，那么会查找失败，但是它的效率远高于以下这种写法：

SELECT * FROM articles WHERE body like '%database%';

组合索引

组合索引实际上就是将多行捆绑在一起，作为一个索引，它同样支持以上几种索引类型。

注意组合索引在进行匹配时，遵循最左原则。

我们可以使用explain语句（它可以用于分析select语句的执行计划，也就是MySQL到底是如何在执行某条select语句的）来分析查询语句到底有没有通过索引进行匹配。

explain select * from student where name = '小王';

得到的结果如下：

• select_type：查询类型，上面的就是简单查询（SIMPLE）
• table：查询的表
• type：MySQL决定如何查找对应的记录，效率从高到低：system > const > eq_ref > ref > range > index > all
• possible_keys：执行查询时可能会用到的索引
• key：实际使用的索引
• key_len：Mysql在索引里使用的字节数，字段的最大可能长度
• rows：扫描的行数
• extra：附加说明

索引底层原理

既然我们要通过索引来快速查找内容，那么如何设计索引就是我们的重点内容，因为索引是存储在硬盘上的，跟我们之前使用的HashMap之类的不同，它们都是在内存中的，但是硬盘的读取速度远小于内存的速度，每一次IO操作都会耗费大量的时间。

我们也不可能把整个磁盘上的索引全部导入内存，因此我们需要考虑尽可能多的减少IO次数，索引的实现可以依靠两种数据结构，一种是我们在JavaSE阶段已经学习过的Hash表，还有一种就是B-Tree。

我们首先来看看哈希表，实际上就是计算Hash值来快速定位：

通过对Key进行散列值计算，我们可以直接得到对应数据的存放位置，它的查询效率能够达到O(1)，但是它也存在一定的缺陷：

• Hash索引仅仅能满足“=”，“in”查询条件，不能使用范围查询。
• Hash碰撞问题。
• 不能用部分索引键来搜索，因为组合索引在计算哈希值的时候是一起计算的。

那么，既然要解决这些问题，我们还有一种方案就是使用类似于二叉树那样的数据结构来存储索引，但是这样相比使用Hash索引，会牺牲一定的读取速度。

但是这里并没有使用二叉树，而是使用了BTree，它是专门为磁盘数据读取设计的一种度为n的查找树：

• 树中每个结点最多含有m个孩子（m >= 2）

• 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子。

• 若根结点不是叶子结点，则至少有2个孩子。

• 所有叶子结点都出现在同一层。

• 每个非终端结点中包含有n个键值信息： (P1，K1，P2，K2，P3，……，Kn，Pn+1)。其中：

  1. Ki (i=1…n)为键值，且键值按顺序升序排序K(i-1)< Ki。
  2. Pi为指向子树根的结点，且指针P(i)指向的子树中所有结点的键值均小于Ki，但都大于K(i-1)。
  3. 键值的个数n必须满足： [ceil(m / 2)-1] <= n <= m-1。

比如现在我们要对键值为10的记录进行查找，过程如下：

1. 读取根节点数据（目前进行了一次IO操作）
2. 根据根节点数据进行判断得到10<17，因为P1指向的子树中所有值都是小于17的，所以这时我们将P1指向的节点读取（目前进行了两次IO操作）
3. 再次进行判断，得到8<10<12，因为P2指向的子树中所有的值都是小于12大于8的，所以这时读取P2指向的节点（目前进行了三次IO操作）
4. 成功找到。

我们接着来看，虽然BTree能够很好地利用二叉查找树的思想大幅度减少查找次数，但是它的查找效率还是很低，因此它的优化版本B+Tree诞生了，它拥有更稳定的查询效率和更低的IO读取次数：

我们可以发现，它和BTree有一定的区别：

• 有n棵子树的结点中含有n个键值，BTree只有n-1个。
• 所有的键值信息只在叶子节点中包含，非叶子节点仅仅保存子节点的最小（或最大）值，和指向叶子节点的指针，这样相比BTree每一个节点在硬盘中存放了更少的内容（没有键值信息了）
• 所有叶子节点都有一个根据大小顺序指向下一个叶子节点的指针Q，本质上数据就是一个链表。

这样，读取IO的时间相比BTree就减少了很多，并且查询任何键值信息都需要完整地走到叶子节点，保证了查询的IO读取次数一致。因此MySQL默认选择B+Tree作为索引的存储数据结构。

这是MyISAM存储引擎下的B+Tree实现：

这是InnoDB存储引擎下的B+Tree实现：

InnoDB与MyISAM实现的不同之处：

• 数据本身就是索引的一部分（所以这里建议主键使用自增）
• 非主键索引的数据实际上存储的是对应记录的主键值（因此InnoDB必须有主键，若没有也会自动查找替代）

锁机制

在JavaSE的学习中，我们在多线程板块首次用到了锁机制，当我们对某个方法或是某个代码块加锁后，除非锁的持有者释放当前的锁，否则其他线程无法进入此方法或是代码块，我们可以利用锁机制来保证多线程之间的安全性。

在MySQL中，就很容易出现多线程同时操作表中数据的情况，如果要避免潜在的并发问题，那么我们可以使用之前讲解的事务隔离级别来处理，而事务隔离中利用了锁机制。

• 读未提交(Read Uncommitted)：能够读取到其他事务中未提交的内容，存在脏读问题。
• 读已提交(Read Committed RC)：只能读取其他事务已经提交的内容，存在不可重复读问题。
• 可重复读(Repeated Read RR)：在读取某行后不允许其他事务操作此行，直到事务结束，但是依然存在幻读问题。
• 串行读(Serializable)：一个事务的开始必须等待另一个事务的完成。

我们可以切换隔离级别分别演示一下：

set session transaction isolation level read uncommitted;

在RR级别下，MySQL在一定程度上解决了幻读问题：

• 在快照读（不加锁）读情况下，mysql通过mvcc来避免幻读。
• 在当前读（加锁）读情况下，mysql通过next-key来避免幻读。

MVCC，全称 Multi-Version Concurrency Control ，即多版本并发控制。MVCC 是一种并发控制的方法，一般在数据库管理系统中，实现对数据库的并发访问，在编程语言中实现事务内存。

读锁和写锁

从对数据的操作类型上来说，锁分为读锁和写锁：

• 读锁：也叫共享锁，当一个事务添加了读锁后，其他的事务也可以添加读锁或是读取数据，但是不能进行写操作，只能等到所有的读锁全部释放。
• 写锁：也叫排他锁，当一个事务添加了写锁后，其他事务不能读不能写也不能添加任何锁，只能等待当前事务释放锁。

全局锁、表锁和行锁

从锁的作用范围上划分，分为全局锁、表锁和行锁：

• 全局锁：锁作用于全局，整个数据库的所有操作全部受到锁限制。
• 表锁：锁作用于整个表，所有对表的操作都会收到锁限制。
• 行锁：锁作用于表中的某一行，只会通过锁限制对某一行的操作（仅InnoDB支持）

全局锁

我们首先来看全局锁，它作用于整个数据库，我们可以使用以下命令来开启读全局锁：

flush tables with read lock;

开启后，整个数据库被上读锁，我们只能去读取数据，但是不允许进行写操作（包括更新、插入、删除等）一旦执行写操作，会被阻塞，直到锁被释放，我们可以使用以下命令来解锁：

unlock tables;

除了手动释放锁之外，当我们的会话结束后，锁也会被自动释放。

表锁

表锁作用于某一张表，也是MyISAM和InnoDB存储引擎支持的方式，我们可以使用以下命令来为表添加锁：

lock table 表名称 read/write;

在我们为表添加写锁后，我们发现其他地方是无法访问此表的，一律都被阻塞。

行锁

表锁的作用范围太广了，如果我们仅仅只是对某一行进行操作，那么大可不必对整个表进行加锁，因此InnoDB支持了行锁，我们可以使用以下命令来对某一行进行加锁：

-- 添加读锁（共享锁）
select * from ... lock in share mode;
-- 添加写锁（排他锁）
select * from ... for update;

使用InnoDB的情况下，在执行更新、删除、插入操作时，数据库也会自动为所涉及的行添加写锁（排他锁），直到事务提交时，才会释放锁。

执行普通的查询操作时，不会添加任何锁。

使用MyISAM的情况下，在执行更新、删除、插入操作时，数据库会对涉及的表添加写锁，在执行查询操作时，数据库会对涉及的表添加读锁。

提问：当我们不使用id进行选择，行锁会发生什么变化？（行锁会升级）

记录锁、间隙锁和临键锁

我们知道InnoDB支持使用行锁，但是行锁比较复杂，它可以继续分为多个类型。

记录锁

（Record Locks）记录锁, 仅仅锁住索引记录的一行，在单条索引记录上加锁。Record lock锁住的永远是索引，而非记录本身，即使该表上没有任何索引，那么innodb会在后台创建一个隐藏的聚集主键索引，那么锁住的就是这个隐藏的聚集主键索引。所以说当一条sql没有走任何索引时，那么将会在每一条聚合索引后面加写锁，这个类似于表锁，但原理上和表锁应该是完全不同的。

间隙锁

（Gap Locks）仅仅锁住一个索引区间（开区间，不包括双端端点）。在索引记录之间的间隙中加锁，或者是在某一条索引记录之前或者之后加锁，并不包括该索引记录本身。比如在 1、2中，间隙锁的可能值有 (-∞, 1)，(1, 2)，(2, +∞)，间隙锁可用于防止幻读，保证索引间的不会被插入数据。

临键锁

（Next-Key Locks）Record lock + Gap lock，左开右闭区间。默认情况下，InnoDB正是使用Next-key Locks来锁定记录（如select … for update语句）它还会根据场景进行灵活变换：

//zhuanlan.zhihu.com/p/48269420