索引其实就是对数据按照某种格式进行存储的文件。就InnoDB来讲，索引文件里面会有很多的基本单元【页】。

为什么有页的概念？

查询数据的时候直接交互磁盘，效率显然又会很慢，所以真正处理数据的过程其实是在内存中，这样就需要把磁盘的数据加载到内存，如果是写操作，可能还要将内存的数据再次刷新到磁盘。如果内存与磁盘的数据交互过程是基于一条条记录来进行的，显然又会很慢，所以InnoDB采取的方式是将数据划分为若干个页，以页来作为内存和磁盘交互的基本单位，默认大小为16KB。

数据或者叫记录，其实是以【行】的格式存储在页里面的，可以简单的理解成页里面的一行对应一条记录。

当然索引文件里面肯定不光只有页，还会有其余的东西，页里面也不光只有行格式，也会有额外的信息，这个下面我们会详细分析，至此我们仅仅需要明确一下索引的概念和层级关系。

明确了这个层级关系之后，接下来我们来从最基础的行格式来进行分析。

一，行格式

我们平时都是以记录为单位向表中插入数据的，这些记录在磁盘上的存储形式被称为行格式或者记录格式，截至目前，一共有4种行格式。分别是 compact redundant dynamic compressed，MySQL5.7默认的行格式为dynamic。

1. 如何指定行格式

CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称
ALTER TABLE 表名 ROW_FORMAT=行格式名称

比如我们创建一张表来指定行格式：

create table record_format(
  c1 varchar(10),
  c2 varchar(10) not null,
  c3 char(10),
  c4 varchar(10)
)charset=ascii row_format=compact;
INSERT INTO record_format_demo(c1, c2, c3, c4) VALUES('aaaa', 'bbb', 'cc', 'd'), ('eeee', 'fff', NULL, NULL);

2.compact 行格式

首先我们来看Compact行格式。

一条完整的行格式可以被分为两个部分：记录额外信息的部分&记录真实数据的部分。

2.1 额外的信息

额外的信息实包含三部分：变长字段的长度列表，NULL值列表和记录头信息。

2.1.1 变长字段长度列表

MySQL支持很多的变长字段，我们就以最经典的varchar来进行举例，变长字段的数据存储多少字节其实是不固定的，所以在存储真实的数据的时候，要记录一下真实数据的字节数，这样的话，一个变长字段列实际上就占用了两部分的空间来存储：【真实数据】&【真实数据占用字节数】。

注意：对于一个列varchar(100)，我们实际上存储一个10字节的数据，当在内存中为这个列的数据分配内存空间的时候，实际上会分配100字节，但是这个列的数据在磁盘上，实际上只会分配10字节。

在Compact行格式中，会把所有的变长字段占用的真实长度全部逆序存储在记录的开头位置，形成一个变长字段长度列表。

比如我们刚才创建的那张表，我们来分析一下：

c1,c2,c4三个列都是变长字段，所以这三个列的值的长度其实都需要保存到变长字段长度列表，因为这张表的字符集的ASCII，所以每个字符实际只占用1字节来进行编码：

因为这些长度是按照逆序来存放的，所以最终变长字段长度列表的字节串用十六进制表示的效果就是【010304】。

因为我们演示的这条记录中，c1,c2,c4列中的字符串都比较短，所以真实的数据占用的字节数就比较小，真实数据的长度用一个字节就可以表示，但是如果变长列的内容占用字节数比较多，可能就需要用2个字节来表示。对此InnoDB的规定是：

【W】：某个字符集中表示一个字符最多需要使用的字节数

【M】：当前列类型最多能存储的字符数(比如varchar(100),M=100),如果换算成字节数就是W*M

【L】：真实占用的字节数

1. 如果M*W<=255,那么使用1字节来表示字符串实际用到的字节数。

InnoDB在读记录的变长字段长度列表的时候会先去查看表结构，判断用几个字节去存储的。

1. 如果M*W>=255,这个时候再次分为两种情况：
   1. 如果L<=127，那就用1个字节表示
   2. 否则就用2个字节表示

如果某个变长字段允许存储的最大字节数大于255的时候，怎么区分他正在读取的字节是一个单独的字段长度还是半个字段长度呢？

InnoDB用该字节的第一个二进制为作为标志位，0：单独的字段长度，1：半个字段长度。

对于一些占用字节数特别多的字段，单个页都无法存储的时候，InnoDB会把一部分数据放到所谓的溢出页，在变长字段长度列表中只会记录当前页的字段长度，所以用两个字节也可以存的下。

此外，变长字段的长度列表中只存储真实数据值为非NULL的列占用的长度，真实数据为NULL的列的长度是不存储的。

也并不是所有的记录都会有变长字段长度列表，假如表中的列要是没有变长字段，或者记录中的变长字段值都是NULL，那就没有变长字段长度列表了。

2.1.2 NULL值列表

如果一条记录有多个字段的真实值为NULL，不统一管理的话就会比较占用空间，所以抽取出来了NULL值列表。

当然如果这个表的所有字段都是NOT NULL约束的，就不会有NULL值列表。

看一下处理过程：

1. 首先统计出表中允许存储NULL的字段
2. 如果表中没有NULL字段的列，那就没必要再往下了，否则将每个允许存储NULL的列对应的一个二进制位按照列的顺序逆序排列。1：NULL，0：不是NULL。
3. MySQL规定NULL值必须用整数个字节的位表示，如果使用的二进制位个数不是整数个字节，则在字节的高位补0。

以此类推，如果一个表中有9个字段允许为NULL，那么这个记录的NULL值列表部分就需要2个字节来表示。

这个时候再来看我们上面创建的表中的记录。

2.1.3 记录头信息

由五个固定的字节组成，换算成二进制就是40位，每一部分代表不同的信息。

接下来来看记录的真实数据。

2.2 真实数据

除了表中显式定义的列，MySQL会往我们的表中放一些隐藏列。

【row_id】：这个玩意，跟主键的选择有关，如果我们显式定义了表的主键，就不会有它，如果我们没显式定义主键，那么会去选择一个unique的列作为主键，如果unique的列也没有，那么就会生成一个row_id列作为隐藏的主键。

【transaction_id】&【roll_pointer】和一致性非锁读(MVCC)有关,后面遇到的时候我会在分析介绍。

在完善下我们开头创建的那张表的记录形象。

至此，其实就剩下我们显式插入数据库的真实记录了，但是还有一个特殊的类型需要说明一下。

2.2.1 CHAR 也是变长的？

在Compact行格式下只会把变长类型的列的长度逆序记录到变长字段长度列表，但是这其实和我们的字符集有关系，上面我们创建的表显式指定为ASCII字符集，这个时候一个字符只会用一个字节表示，但是假如我们指定的是其它字符集，比如utf8，这个时候一个字符用几个字节表示就不确定了，所以CHAR列的真实字节长度也会被记录到变长字段长度列表。

另外，变长字符集的CHAR(M)类型的列要求至少占用M个字节，而VARCHAR(M)就没有这个要求。

对于使用utf8字符集的CHAR(10)的列来说，该列存储的数据字节长度的范围是10～30个字节。即使我们向该列中存储一个空字符串也会占用10个字节，这是怕将来更新该列的值的字节长度大于原有值的字节长度而小于10个字节时，可以在该记录处直接更新，而不是在存储空间中重新分配一个新的记录空间，导致原有的记录空间成为所谓的碎片。

3. 行溢出

上面提到了，如果一条记录的真实字节数太大，就会导致行溢出，把超出的一部分数据存储到其他行或者页。

3.1 varchar(M)最多能存储的数据

varchar(M)的列最多可以占用65535个字节。其中M代表该类型最多存储的字符数量。

实际上，MySQL对一条记录占用的最大存储空间是有限制的，除了BLOB，TEXT类型的列之外，其他所有的列(不包含隐藏列和记录头信息)占用的字节长度加起来不能超过65535个字节。这个65535个字节除了列本身的数据之外，还包括一些其他的数据，比如说我们为了存储一个varchar列，其实还需要占用3部分空间。

1. 真实数据
2. 真实数据占用的字节长度
3. NULL值标识，如果该列有NOT_NULL属性则可以没有这部分存储空间

如果该varchar类型的列没有NOT NULL属性那最多只能存储65532个字节的数据，因为真实数据的长度可能占用2个字节，NULL值标识需要占用1个字节。

如果VARCHAR类型的列有NOT NULL属性，那最多只能存储65533个字节的数据，因为真实数据的长度可能占用2个字节，不需要NULL值标识。

如果VARCHAR(M)类型的列使用的不是ascii字符集，那会怎么样呢？

如果VARCHAR(M)类型的列使用的不是ascii字符集，那M的最大取值取决于该字符集表示一个字符最多需要的字节数。在列的值允许为NULL的情况下，gbk字符集表示一个字符最多需要2个字节，那在该字符集下，M的最大取值就是32766（也就是：65532/2），也就是说最多能存储32766个字符；utf8字符集表示一个字符最多需要3个字节，那在该字符集下，M的最大取值就是21844，就是说最多能存储21844（也就是：65532/3）个字符。

上述所言在列的值允许为NULL的情况下，gbk字符集下M的最大取值就是32766，utf8字符集下M的最大取值就是21844，这都是在表中只有一个字段的情况下说的，一定要记住一个行中的所有列（不包括隐藏列和记录头信息）占用的字节长度加起来不能超过65535个字节！

3.2 记录中的数据太多产生溢出

MySQL中磁盘和内存交互的基本单位是页，也就是说MySQL是以页为基本单位来管理存储空间的，我们的记录都会被分配到某个页中存储。而一个页的大小一般是16KB，也就是16384字节，而一个VARCHAR(M)类型的列就最多可以存储65532个字节，这样就可能造成一个页存放不了一条记录的尴尬情况。

在Compact和Redundant行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据，把剩余的数据分散存储在几个其他的页中，然后记录的真实数据处用20个字节存储指向这些页的地址（当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数），从而可以找到剩余数据所在的页。

从图中可以看出来，对于Compact和Redundant行格式来说，如果某一列中的数据非常多的话，在本记录的真实数据处只会存储该列的前768个字节的数据和一个指向其他页的地址，然后把剩下的数据存放到其他页中，这个过程也叫做行溢出，存储超出768字节的那些页面也被称为溢出页。画一个简图就是这样：

不只是 VARCHAR(M)类型的列，其他的 TEXT、BLOB 类型的列在存储数据非常多的时候也会发生行溢出。

3.3 行溢出的临界点

发生行溢出的临界点是什么呢？也就是说在列存储多少字节的数据时就会发生行溢出？

MySQL中规定一个页中至少存放两行记录，至于为什么这么规定我们之后再说，现在看一下这个规定造成的影响。我们往表中插入亮条记录，每条记录最少插入多少字节的数据才会行溢出呢？

分析一下页空间是如何利用的

1. 每个页除了存放我们的记录以外，也需要存储一些额外的信息，乱七八糟的额外信息加起来需要132个字节的空间（现在只要知道这个数字就好了），其他的空间都可以被用来存储记录。
2. 每个记录需要的额外信息是27字节。这27个字节包括下边这些部分： | 内容 | 大小(字节) | | —- | —- | | 真实数据的长度 | 2 | | 列是否是NULL值 | 1 | | 头信息 | 5 | | row_id | 6 | | transaction_id | 6 | | roll_pointer | 7 |

因为表中具体有多少列不确定，所以没法确定具体的临界点，只需要知道插入的字段数据长度很大就会导致行溢出的现象。

4.Dynamic & Compressed 行格式

这俩行格式和Compact行格式挺像，只不过在处理行溢出数据时有点儿分歧，它们不会在记录的真实数据处存储字段真实数据的前768个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址，就像这样：

Compressed行格式和Dynamic不同的一点是，Compressed行格式会采用压缩算法对页面进行压缩，以节省空间。

至此，行格式就分析的差不多了，接下来我们来看页的存储结构。

二，页的存储结构

InnoDB为了不同的目的设计了许多种页，比如存放表空间头部信息的页，存放 Insert Buffer信息的页，存放Innode信息的页，存放undo日志信息的页等等。

本节分析存放表中记录的页，官方成为索引页，为了分析方便，我们暂且叫做数据页。

系统变量innodb_page_size表明了InnoDB存储引擎中的页大小，默认值是16384字节，也就是16kb。 该变量只能在第一次初始化MySQL数据目录时指定，之后就再也不能更改了。

数据页代表的这块16kb的存储空间被划分为多个部分，不同部分有不同的功能。

从图中可以看出，一个InnoDB数据页的存储空间大致被划分为了7个部分，有的部分占用的字节数是确定的，有的占用的字节数不是确定的。

1. 记录在页中的存储

我们先来创建一张表

mysql> create table page_demo(
    -> c1 int ,
    -> c2 int ,
    -> c3 varchar(10000),
    -> primary key(c1)
    -> ) charset=ascii row_format=Compact;
Query OK, 0 rows affected (0.03 sec)

因为我们指定了主键，所以存储实际数据的列里面不会有隐藏的row_id,我们来看一下他的行格式。

再次回顾下记录头中5个字节表示的数据。

针对当前这个表的行格式简化图：

接下来我们往表中插入几条数据：

INSERT INTO page_demo VALUES(1, 100, 'aaaa'), (2, 200, 'bbbb'), (3, 300, 'cccc'), (4, 400, 'dddd');

为了分析这些记录在页的User Records 部分中是怎么表示的，把记录头信息和实际的列数据都用十进制表示出来了（其实是一堆二进制位），所以这些记录的示意图就是：

分析一下头信息中的每个属性是什么意思。

1.1 delete_mask

标记当前记录是否被删除，占用1个二进制位，0：未删除，1：删除。

被删除的记录不会立即从磁盘上删除，因为删除他们之后吧其他的记录在磁盘上重新排列需要性能消耗，所以只是打一个删除标记，所有被删掉的数据会组成一个垃圾链表，在这个链表中的记录占用的空间成为可重用空间，之后如果有新的记录插入到表中，可能会把这些删除的记录覆盖掉。

将delete_mask 设置为1 和 将被删除的记录加入到垃圾链表中其实是两个阶段。

1.2 min_rec_mask

B+树的每层非叶子节点中的最小记录都会添加该标记，如果这个字段的值是0，意味着不是B+树的非叶子节点中的最小记录。

1.3 n_owned

1.4 heap_no

这个属性表示当前记录在本页中的位置，我们插入的四条记录在本页中的位置分别是 2，3，4 ，5 。为什么不见 0 和 1 的记录呢？

这是因为InnoDB自动给每个页里边加了两个记录，由于这两个记录并不是我们自己插入的，所以有时候也称为虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录。

记录是如何比较大小的？对于一条完整的记录来说，比较记录大小就是比较主键的大小。比方说我们插入的4行记录的主键值分别为1，2，3，4，这也就意味着这四条记录的大小从大到小递增。

但是不管我们往页中插入了多少自己的记录，InnoDB都规定他们定义的两条伪记录分别为最小记录和最大记录。这两条记录的构造十分简单，都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的。

由于这两条记录不是我们自己定义的记录，所以他们并不存放在页的User Records部分，他们被单独放在一个称为Infimum+Supremum的部分。

从图中我们可以看出来，最小记录和最大记录的heap_no值分别是0 和 1 ， 也就是说他们的位置最靠前。

1.5 record_type

这个属性表示当前记录的类型。0：普通记录，1：B+树非叶子节点记录，2：最小记录，3：最大记录。

我们自己插入的记录是普通记录 0 ， 而最大记录和最小记录record_type 分别为 2 和 3。

1.6 next_record

表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。这其实是一条链表，可以通过一条记录找到他的下一条记录，但是下一条记录指的并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定 infimum记录 的下一条记录就是本页主键值最小的用户记录，而本页中主键最大的用户记录的下一条记录就是supremum记录。

如果从中删除一条记录，这个链表也是会跟着变化的，假如现在删除第二条记录

delete from page_demo where c1 =2 ;

删除第二条记录以后：

发生的变化：

• 第二条记录并没有从存储空间中移除，而是把该记录的delete_mask设置为1
• 第二条记录的next_records值变成了0，意味着该记录没有下一条记录了
• 第一条记录的next record指向了第三条记录
• 最大记录的 n_owned 值从5 变成了4

所以，不论我们怎么对页中的记录做增删改查操作，InnoDB始终会维护一条记录的单链表，链表中各个节点是按照主键值由小到大的顺序连接起来的。

next_records 为啥要指向记录头信息和真实数据之间的位置呢？为啥不干脆指向整条记录的开头位置，也就是记录的额外信息开头的位置呢？

因为这个位置刚刚好，向左读取就是记录头信息，向右读取就是真实数据。我们前边还说过变长字段长度列表，null值列表中的信息都是逆序存放的，这样可以使记录中位置靠前的字段和他们对应的字段长度信息在内存中的距离更近，可能会提高高速缓存的命中率。

因为主键值为2的记录已经被我们删除了，但是存储空间并没有回收，如果再次把这条记录插入到表中，会发生什么？

INSERT INTO page_demo VALUES(2, 200, 'bbbb');

从图中可以看到，InnoDB并没有因为新记录的插入而为他申请新的存储空间，而是直接复用了原来删除的记录的存储空间。

2. Page Directory（页目录）

如果我们想根据主键值查找页中某条记录该咋办？

select * from page_demo where c1 = 3;

1. 将所有正常的记录(包括两条隐藏记录但是不包括已经标记为删除的记录)划分为几组
2. 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该组拥有多少条记录
3. 将每个组的最后一条记录的地址偏移量单独提取出来按照顺序存储到靠近页的尾部的地方，这个地方就是所谓的【Page Directory】,也就是页目录。页目录中的这些地址偏移量被称为槽，所以页目录就是由槽组成的

比方说刚才创建的表中正常的记录由6条，InnoDB会把他们分成两组，第一组中只有一条最小记录，第二组中是剩余的5条记录。

现在页目录部分中有两个槽，也就意味着我们的记录被分成了两个组，槽1中的值为112，代表最大记录的地址偏移量；槽0的值为99，代表最小记录的地址偏移量。

注意最大和最小记录的头信息的n_owned属性：

1. 最小记录中的n_owned值为1，这就代表着以最小记录结尾的这个分组中只有1条记录，也就是最小记录本身
2. 最大记录中的n_owned值为5，这就代表着以最大记录结尾的这个分组中只有5条记录，包括最大记录本身还有我们自己插入的4条记录

【99】&【112】这样的地址偏移量很不直观，我们用箭头指向的方式替代数字。

InnoDB对每个分组中的记录条数是有规定的：对于最小记录所在的分组只能有 1 条记录，最大记录所在的分组拥有的记录条数只能在 1~8 条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间。所以分组是按照下边的步骤进行的：

• 初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组。
• 之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8个。
• 在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。

由于现在page_demo表中的记录太少，无法演示添加了页目录之后加快查找速度的过程，所以再往page_demo表中添加一些记录：

INSERT INTO page_demo VALUES(5, 500, 'eeee'), (6, 600, 'ffff'), (7, 700, 'gggg'), (8, 800, 'hhhh'), (9, 900, 'iiii'), (10, 1000, 'jjjj'), (11, 1100, 'kkkk'), (12, 1200, 'llll'), (13, 1300, 'mmmm'), (14, 1400, 'nnnn'), (15, 1500, 'oooo'), (16, 1600, 'pppp');

现在看怎么从这个页目录中查找记录。因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用所谓的二分法来进行快速查找。5个槽的编号分别是：0、1、2、3、4，所以初始情况下最低的槽就是low=0，最高的槽就是high=4。比方说我们想找主键值为6的记录，过程是这样的：

1. 计算中间槽的位置：(0+4)/2=2，所以查看槽2对应记录的主键值为8，又因为8 > 6，所以设置high=2，low保持不变。
2. 重新计算中间槽的位置：(0+2)/2=1，所以查看槽1对应的主键值为4，又因为4 < 6，所以设置low=1，high保持不变。
3. 因为high - low的值为1，所以确定主键值为6的记录在槽2对应的组中。此刻我们需要找到槽2中主键值最小的那条记录，然后沿着单向链表遍历槽2中的记录。但是我们前边又说过，每个槽对应的记录都是该组中主键值最大的记录，这里槽2对应的记录是主键值为8的记录，怎么定位一个组中最小的记录呢？别忘了各个槽都是挨着的，我们可以很轻易的拿到槽1对应的记录（主键值为4），该条记录的下一条记录就是槽2中主键值最小的记录，该记录的主键值为5。所以我们可以从这条主键值为5的记录出发，遍历槽2中的各条记录，直到找到主键值为6的那条记录即可。由于一个组中包含的记录条数只能是1~8条，所以遍历一个组中的记录的代价是很小的。

所以在一个数据页中查找指定主键值的记录的过程分为两步：

1. 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。
2. 通过记录的next_record属性遍历该槽所在的组中的各个记录。

3.Page Header（页面头部）

为了能得到一个数据页中存储的记录的状态信息，比如本页中已经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等等，特意在页中定义了一个叫Page Header的部分，它是页结构的第二部分，这个部分占用固定的56个字节，专门存储各种状态信息。

4.File Header（文件头部）

File Header针对各种类型的页都通用，也就是说不同类型的页都会以File Header作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页是谁，这个部分占用固定的38个字节。

InnoDB为了不同的目的而把页分为不同的类型，我们上边介绍的其实都是存储记录的数据页，其实还有很多别的类型的页，具体如下表：

我们存放记录的数据页的类型其实是FIL_PAGE_INDEX，也就是所谓的索引页。

有时候我们存放某种类型的数据占用的空间非常大（比方说一张表中可以有成千上万条记录），InnoDB可能不可以一次性为这么多数据分配一个非常大的存储空间，如果分散到多个不连续的页中存储的话需要把这些页关联起来，FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了，而无需这些页在物理上真正连着。需要注意的是，并不是所有类型的页都有上一个和下一个页的属性，不过我们现在分析的数据页（也就是类型为FIL_PAGE_INDEX的页）是有这两个属性的，所以所有的数据页其实是一个双链表。

5.File Trailer(文件尾部)

如果页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一半的时候中断电了咋办？

为了检测一个页是否完整，在每个页的尾部都加了一个File Trailer部分，这个部分由8个字节组成，可以分成2个小部分：

1. 前四个字节代表校验和
2. 后四个字节代表页面被最后修改时对应的日志序列位置

这个File Trailer & File Header 类似，都是所有类型的页通用的。

至此，整个数据页的结构我们也基本上分析完了，现在在回头看一下开头我们那张恐怖的图，是不是感觉清晰很多了呢？接下来，我们来分析索引的结构。

三，索引

1.假如没有索引

我们先来看看没有索引的情况下，我们进行数据的查找(毕竟没有对比就没有伤害)。

1.1 在一个页中查找

假设表中的记录很少，所有的记录仅仅用一个页就存放下了，这个时候按照不同的搜索条件其实可以分为两种情况讨论：

【以主键为搜索的条件】：可以再页目录中根据二分查找快速定位到槽，在根据槽定位到该组的最小索引记录，然后进行遍历匹配查找。

【以其他列作为搜索条件】：在数据页中并没有为非主键列建立所谓的页目录，所以无法通过二分法快速定位相应的槽。在这种情况下，只能从最小记录开始依次往后遍历单链表中的每条记录，然后对比每条记录是否符合搜索条件，显然，效率很低。

1.2 在很多页中查找

很多时候，表的记录一个页都是存储不下的，这个时候的查找其实分为两个步骤：

【定位到记录所在的页】

【从所在的页内查找相应的记录】

因为我们不能快速的定位到所在的页，所以只能从第一页开始沿着双链表往后遍历定位页，定位到页以后在根据在一个页中的查找方式进行匹配查找，显而易见，这个时候效率低的可怕。

有了痛点，就会有大牛去思考整个生命周期，完善逻辑和资源倾斜，形成一套自己的方法论，想办法为快速查找赋能。

2. 索引

我们先创建一张表：

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)

2.1 一个简单的索引方案

我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？

因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以 不得不 依次遍历所有的数据页。

如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办？

对比根据主键值快速定位一条记录从而在页中的位置建立页目录，我们也可以想办法为快速定位记录所在的数据页而建立一个别的目录。

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

假设我们现在每一页只能放三条记录，现在已经放了主键为1,3,5的三条记录。这个时候我们再添加一条主键为4的记录，我们不得不为他分配一个新的页。

注意：新分配的数据页编号可能和原来并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。他们只是通过维护着上一页和下一页的编号而建立了链表关系。

原来页中主键最大的值为5，现在我们新插入一条记录，如果直接放在新页里面，那就会有问题，这不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值得要求，所以在插入主键值为4 的记录的时候需要伴随一次记录的移动，也就是把主键值为5 的记录移动到新分配的页中，然后把主键值为4 的记录插入到原来的页中。

这个过程表明了在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。

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

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

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

1. 页的用户记录中最小的主键值，我们用key来表示。
2. 页号，我们用page_no表示。

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

1. 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 209），它对应的页是页9。
2. 再根据前边说的在页中查找记录的方式去页9中定位具体的记录。

至此，针对数据页做的简易目录就搞定了。这个目录其实就是【索引】。

2.2 InnoDB中的索引方案

上面的方案存在什么样的问题？

• InnoDB是使用页来作为管理存储空间的基本单位，也就是最多能保证16KB的连续存储空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。
• 我们时常会对记录进行增删，假设我们把页28中的记录都删除了，页28也就没有存在的必要了，那意味着目录项2也就没有存在的必要了，这就需要把目录项2后的目录项都向前移动一下。

InnoDB复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。

那InnoDB怎么区分一条记录是普通的用户记录还是目录项记录呢？通过记录头信息里的record_type属性，它的各个取值代表的意思如下：

• 0：普通的用户记录
• **1**：目录项记录
• 2：最小记录
• 3：最大记录

把前边使用到的目录项放到数据页中的样子就是这样：

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

• 目录项记录的record_type值是1，而普通用户记录的record_type值是0。
• 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列。
• 头信息里面有一个叫min_rec_mask的属性，只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0。

除此之外，两者就没有区别了，页的组成结构也是一样一样的（就是我们前边介绍过的7个部分），都会为主键值生成Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。

现在以查找主键为20的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

1. 先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，因为12 < 20 < 209，所以定位到对应的记录所在的页就是页9。
2. 再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录。

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

当然是再多整一个存储**目录项记录**的页。

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

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

现在因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要3个步骤，以查找主键值为20的记录为例：

1. 确定目录项记录页

我们现在的存储目录项记录的页有两个，即页30和页32，又因为页30表示的目录项的主键值的范围是[1, 320)，页32表示的目录项的主键值不小于320，所以主键值为20的记录对应的目录项记录在页30中。

1. 通过目录项记录页确定用户记录真实所在的页。
2. 在真实存储用户记录的页中定位到具体的记录。

那么问题来了，在这个查询步骤的第1步中我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？

为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下边这个图来描述它：

其实这是一种组织数据的形式，或者说是一种数据结构，它的名称是B+树。

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

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

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放100条记录。
• 如果B+树有2层，最多能存放1000×100=100000条记录。
• 如果B+树有3层，最多能存放1000×1000×100=100000000条记录。
• 如果B+树有4层，最多能存放1000×1000×1000×100=100000000000条记录。

一般情况下，我们用到的B+树都不会超过4层，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的Page Directory（页目录），所以在页面内也可以通过二分法实现快速定位记录。

2.3 聚簇索引

上边介绍的B+树本身就是一个目录，或者说本身就是一个索引。它有两个特点：

1. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
   • 页内的记录是按照主键的大小顺序排成一个单向链表。
   • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
   • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
2. B+树的叶子节点存储的是完整的用户记录。
   所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

我们把具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建，InnoDB存储引擎会自动的为我们创建聚簇索引。另外，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

2.4 二级索引

聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件怎么办？

我们可以多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则，再建一棵B+树，效果如下图所示：

这个B+树与上边介绍的聚簇索引有几处不同：

1. 使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
   1. 页内的记录是按照c2列的大小顺序排成一个单向链表。
   2. 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
   3. 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。
2. B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
3. 目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

所以如果我们现在想通过c2列的值查找某些记录的话就可以使用我们刚刚建好的这个B+树了。以查找c2列的值为4的记录为例，查找过程如下：

1. 确定目录项记录页

根据根页面，也就是页44，可以快速定位到目录项记录所在的页为页42（因为2 < 4 < 9）。

1. 通过目录项记录页确定用户记录真实所在的页。

在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。

1. 在真实存储用户记录的页中定位到具体的记录.

到页34和页35中定位到具体的记录。

1. 但是这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。

我们根据这个以**c2**列大小排序的**B+**树只能确定我们要查找记录的主键值，所以如果我们想根据**c2**列的值查找到完整的用户记录的话，仍然需要到**聚簇索引**中再查一遍，这个过程也被称为**回表**。也就是根据c2列的值查询一条完整的用户记录需要使用到2棵B+树！！！

为什么我们还需要一次回表操作呢？直接把完整的用户记录放到叶子节点不就好了么？

如果把完整的用户记录放到叶子节点是可以不用回表，相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引（英文名secondary index），或者辅助索引。由于我们使用的是c2列的大小作为B+树的排序规则，所以我们也称这个B+树为为c2列建立的索引。

假设我们的查询结果是十条，那就是要进行10次回表，那这样的话，效率不是又慢了？

在MySQL5.6对这种情况进行了优化，如果发现查询结果会导致多次回表，那么就会进行IO合并，拿到所有的主键再去进行回表。

2.5 联合索引

我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：

• 先把各个记录和页按照c2列进行排序。
• 在记录的c2列相同的情况下，采用c3列进行排序

为c2和c3列建立的索引的示意图如下：

3. InnoDB的B+树索引的注意事项

3.1 跟页面永远固定不动

前边介绍B+树索引的时候，为了理解上的方便，先把存储用户记录的叶子节点都画出来，然后接着画存储目录项记录的内节点，实际上B+树的形成过程是这样的：

• 每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个根节点页面。最开始表中没有数据的时候，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录。
• 随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
• 当根节点中的可用空间用完时继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中，然后对这个新页进行页分裂的操作，得到另一个新页，比如页b。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到页a或者页b中，而根节点便升级为存储目录项记录的页。

这个过程需要特别注意的是：一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。

3.2 内节点中目录项记录的唯一性

我们知道B+树索引的内节点中目录项记录的内容是索引列 + 页号的搭配，但是这个搭配对于二级索引来说有点儿不严谨。假设表中的数据是这样的：

如果二级索引中目录项记录的内容只是索引列 + 页号的搭配的话，那么为c2列建立索引后的B+树应该长这样：

如果我们想新插入一行记录，其中c1、c2、c3的值分别是：9、1、'c'，那么在修改这个为c2列建立的二级索引对应的B+树时便碰到了个大问题：由于页3中存储的目录项记录是由c2列 + 页号的值构成的，页3中的两条目录项记录对应的c2列的值都是1，而我们新插入的这条记录的c2列的值也是1，那我们这条新插入的记录到底应该放到页4中，还是应该放到页5中?

为了让新插入记录能找到自己在那个页里，我们需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：

• 索引列的值
• 主键值
• 页号

也就是我们把主键值也添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的。

这样我们再插入记录(9, 1, 'c')时，由于页3中存储的目录项记录是由c2列 + 主键 + 页号的值构成的，可以先把新记录的c2列的值和页3中各目录项记录的c2列的值作比较，如果c2列的值相同的话，可以接着比较主键值，因为B+树同一层中不同目录项记录的c2列 + 主键的值肯定是不一样的，所以最后肯定能定位唯一的一条目录项记录，在本例中最后确定新记录应该被插入到页5中。

3.3 一个页面最少存储2条记录

B+树只需要很少的层级就可以轻松存储数亿条记录，这是因为B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。那如果一个大的目录中只存放一个子目录会怎么样？那就是目录层级非常多，而且最后的那个存放真实数据的目录中只能存放一条记录，会导致效率很低。

其实让B+数的叶子结点值存储一条记录，让内节点存储多条记录，也还是可以发挥B+数的作用的。但是InnoDB为了避免数的层级过高，要求所有的数据页都至少可以容纳两条记录。

4. MyISAM中的索引方案简单介绍

MyISAM的索引方案虽然也使用树形结构，但是却将索引和数据分开存储：

• 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。我们可以通过行号而快速访问到一条记录。
• 使用MyISAM存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录！
  这一点和InnoDB是完全不相同的，在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引！
• 如果有需要的话，我们也可以对其它的列分别建立索引或者建立联合索引，原理和InnoDB中的索引差不多，不过在叶子节点处存储的是相应的列 + 行号。这些索引也全部都是二级索引。

由于在插入数据的时候并没有刻意按照主键大小排序，所以我们并不能在MyIsaM数据上使用二分法进行查找。

5. 创建和删除索引的语句

InnoDB和MyISAM会自动为主键或者声明为UNIQUE的列去自动建立B+树索引，但是如果我们想为其他的列建立索引就需要我们显式的去指明。

我们可以在创建表的时候指定需要建立索引的单个列或者建立联合索引的多个列：

CREATE TALBE 表名 (
    各种列的信息 ··· , 
    [KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
)

我们也可以在修改表结构的时候添加索引：

ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的单个列或多个列);

也可以在修改表结构的时候删除索引：

ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

至此，整个索引相关的结构我们就都分析完了。