前言

索引和锁在数据库中可以说是非常重要的知识点了，在日常的功能开发中也会频繁的接触到。

本文从github、博客、《高性能MySQL》上整理总结了一些常用的知识点，希望大家看完都能有所收获，开发过程中更能得心应手。

一、为什么索引能提高查询速度

众所周知，索引可以提高数据库的查询速度。同时， 索引也会降低插入、删除、修改等维护任务的速度。那索引到底是个啥，能这么神奇？回答这个问题前，我们先来扯一扯关于MySQL中数据的基本存储结构。

MySQL中页的基本存储结构

首先介绍下Mysql的基本存储结构——页(记录都存在页里边)：

页的本质就是一块16KB大小的存储空间，InnoDB为了不同的目的而把页分为不同的类型，其中用于存放记录的页也称为数据页，我们先看看这个用于存放记录的页长什么样。数据页代表的这块16KB大小的存储空间可以被划分为多个部分，不同部分有不同的功能，各个部分如图所示：

数据库的基本存储结构1.png

大致说明一下各部分的作用：

其中，存储的记录会按照我们指定的行格式存储到User Records部分。但是在一开始生成页的时候，其实并没有User Records这个部分，每当我们插入一行记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了，这个过程的图示如下：

数据库的基本存储结构2.png

数据库的基本存储结构3.png

• 数据页之间可以组成一个双向链表

• 而每个数据页中的记录又可以组成一个单向链表

  每个数据页都会为存储在它里面的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录

  以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。

所以说，如果我们写select * from user where username = 'shuaididi'这样没有进行任何优化的sql语句，默认会这样做：

• 需要依次遍历双向链表，定位到记录所在的页 。

• 从所在的页内中查找相应的记录 。由于不是根据主键查询，只能遍历所在页的单链表了

很明显，在数据量很大的情况下这样查找会超级耗时的 ！ 时间复杂度为O（n） 。

MySQL中行的基本存储结构

为了故事的顺利发展，我们新建一张表，然后说明数据是如何在计算机中被存储的。

 mysql> CREATE TABLE index_demo(
   ->   c1 INT,
   ->   c2 INT,
   ->   c3 CHAR(1),
   ->   PRIMARY KEY(c1)
   -> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec) 

这个新建的index_demo表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键，这个表使用Compact行格式来实际存储记录的。为了我们理解上的方便，我们简化了一下index_demo表的行格式示意图：

数据库表的行格式1.png

我们只在示意图里展示记录的这几个部分：

• record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、2表示最小记录、3表示最大记录、1我们还没用过，等会再说～

• next_type：记录头信息的一项属性，表示下一条地址的偏移量，为了方便大家理解，我们都会用箭头来表明下一条记录是谁。

• 各个列的值：就是各个数据列的值，其中我们用橘黄色的格子代表c1列，深蓝色的格子代表c2列，红色格子代表c3列。

• 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

为了节省篇幅，我们之后的示意图中会把记录的其他信息这个部分省略掉，因为它占地方并且不会有什么观赏效果。另外，为了方便理解，我们觉得把记录竖着放看起来感觉更好，所以将记录格式示意图的其他信息去掉并把它竖起来的效果就是这样：

数据库表的行格式2.png

把一些记录放到页里边的示意图就是：

数据库表的行格式3.png

一个简单的索引方案

回到正题，我们为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以 不得不 依次遍历。所以如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办？就像为数据页中的记录建立一个目录一样，我们也可以为所有的数据页建立一个目录，建这个目录必须完成下边这些事儿：

• 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

  为了故事的顺利发展，我们这里需要做一个假设：假设我们的每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设之后我们向index_demo表插入3条记录：

 mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
 Query OK, 3 rows affected (0.01 sec)
 Records: 3  Duplicates: 0  Warnings: 0
 mysql>

那么这些记录已经按照主键值的大小串联成一个单向链表了，如图所示：

一个简单的索引方案1.png

从图中可以看出来，index_demo表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入一条记录：

mysql> INSERT INTO index_demo VALUES(4, 4, 'a');Query OK, 1 row affected (0.00 sec)mysql>

因为页10最多只能放3条记录，所以我们不得不再分配一个新页：

一个简单的索引方案2.png

这里需要注意的一点是，新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。它们只是通过引用建立了链表关系。另外，页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页的主键值必须大于上一个页中的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下：

一个简单的索引方案3.png

为了避免插入不连续数据导致的页分裂和数据移动，通常把主键设置为自增。同时，要避免使用UUID等随机字符串作为主键。

• 给所有的页建立一个目录项。

  由于数据页的编号可能并不是连续的，所以在向index_demo表中插入许多条记录后，可能是这样的效果：

  一个简单的索引方案4.png

  因为这些16KB的页在物理存储上并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：

• • 页的用户记录中最小的主键值，我们用key来表示。

  • 页号，我们用page_no表示。

• 所以我们为上边几个页做好的目录就像这样子：

一个简单的索引方案5.png

• 以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5。我们只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为20的记录，具体查找过程分两步：

• 1. 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 209），它对应的页是页9。

  2. 再根据前边说的在页中查找记录的方式去页9中定位具体的记录。

至此，针对数据页做的简易目录就搞定了。不过忘了说了，这个目录有一个别名，称为索引。

InnoDB中的索引方案

上边之所以称为一个简易的索引方案，是因为我们假设所有目录项都可以在物理存储器上连续存储，但是这样做有几个问题：

• InnoDB是使用页来作为管理存储空间的基本单位，也就是最多能保证16KB的连续存储空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。

• 我们时常会对记录进行增删，假设我们把页28中的记录都删除了，页28也就没有存在的必要了，那意味着目录项2也就没有存在的必要了，这就需要把目录项2后的目录项都向前移动一下，这种牵一发而动全身的设计不是什么好主意～

所以，设计InnoDB的大叔们需要一种可以灵活管理所有目录项的方式。他们灵光乍现，忽然发现这些目录项其实长得跟我们的用户记录差不多，只不过目录项中的两个列是主键和页号而已，所以他们复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。那InnoDB怎么区分一条记录是普通的用户记录还是目录项记录呢？别忘了记录头信息里的record_type属性，它的各个取值代表的意思如下：

• 0：普通的用户记录

• 1：目录项记录

• 2：最小记录

• 3：最大记录

哈哈，原来这个值为1的record_type是这个意思呀，我们把前边使用到的目录项放到数据页中的样子就是这样：

InnoDB中的索引方案1.png

从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。这里再次强调一遍目录项记录和普通的用户记录的不同点：

• 目录项记录的record_type值是1，而普通用户记录的record_type值是0。

• 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列。

• 记录头信息里面还有一个叫min_rec_mask的属性，只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0。

除了上述几点外，这两者就没啥差别了，它们用的是一样的数据页（页面类型都是0x45BF，这个属性在Page Header中），页的组成结构也是一样一样的，都会为主键值生成Page Directory（页目录）以加快在页内的查询速度。所以现在根据某个主键值去查找记录的步骤可以大致拆分成下边两步，以查找主键为20的记录为例（因为都是从一个页中通过主键查某条记录，所以都可以使用Page Directory通过二分法而实现快速查找）：

1. 先到存储目录项记录的页中通过二分法快速定位到对应目录项，因为12 < 20 < 209，所以定位到对应的记录所在的页就是页9.

2. 从页9中根据二分法快速定位到主键值为20的用户记录。

虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有16KB大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，该咋办呢？

当然是再多整一个存储目录项记录的页喽～ 为了大家更好的理解如何新分配一个目录项记录页的过程，我们假设一个存储目录项记录的页最多只能存放4条目录项记录（请注意是假设哦，真实情况下可以存放好多条的），所以如果此时我们再向上图中插入一条主键值为320的用户记录的话，那就需要一个分配一个新的存储目录项记录的页喽：

InnoDB中的索引方案2.png

从图中可以看出，我们插入了一条主键值为320的用户记录之后新生成了2个数据页

• 为存储该用户记录而新生成了页31。

• 因为原先存储目录项记录的页30的容量已满（我们前边假设只能存储4条目录项记录），所以不得不新生成了一个页32来存放页31对应的目录项。

那么问题来了，在查询过程中我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？其实也简单，为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

InnoDB中的索引方案5.png

假设我们要查询id为8的记录，查找过程如下：

InnoDB中的索引方案6.png

如图，我们生成了一个存储更高级目录项的页33，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在[1, 320)之间，则到页30中查找更详细的目录项记录，如果主键值不小于320的话，就到页32中查找更详细的目录项记录。不过这张图好漂亮喔，随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下边这个图来描述它：

InnoDB中的索引方案4.png

这玩意儿像不像一个倒过来的树呀！其实这是一种组织数据的形式，或者说是一种数据结构，它的名称是B+树。

因为我们把数据页都存放到B+树这个数据结构中了，所以我们也把我们的数据页称为节点。从图中可以看出来，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余的节点都是用来存放目录项的，这些节点统统被称为内节点或者说非叶节点。其中最上边的那个节点也称为根节点。

从图中可以看出来，一个B+树的节点其实可以分成好多层，设计InnoDB的大叔们为了讨论方便，规定最下边的那层，也就是存放我们用户记录的那层为第0层，之后依次往上加。上边我们做了一个非常极端的假设，存放用户记录的页最多存放3条记录，存放目录项记录的页最多存放4条记录，其实真实环境中一个页存放的记录数量是非常大的，假设，假设，假设所有的数据页，包括存储真实用户记录和目录项记录的页，都可以存放1000条记录，那么：

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放1000条记录。

• 如果B+树有2层，最多能存放1000×1000=1000000条记录。

• 如果B+树有3层，最多能存放1000×1000×1000=1000000000条记录。

• 如果B+树有4层，最多能存放1000×1000×1000×1000=1000000000000条记录。哇咔咔～这么多的记录！！！

  事实上非叶子节点每页存储的数据要比叶子节点多得多。

  这是因为非叶子节点不存储用户真实的数据，只存储下一层的主键和页号，占用空间较小。而叶子节点要存储真实数据，所以占用空间较大。

你的表里能存放1000000000000条记录么？所以一般情况下，我们用到的B+树都不会超过4层，那我们通过主键去查找某条记录最多只需要做4个页面内的查找，又因为在每个页面内有所谓的Page Directory（页目录），所以在页面内也可以通过二分法实现快速定位记录，这不是很diao么，哈哈！