文章目标

通过对行存储结构、数据页结构的相关介绍帮助大家掌握存储结构，为索引优化提供扎实的理论基础

先看下整体的一个大概内容

Compact行格式示意图

同一个页中行与行之间的关系（通过链表完成的）

页与记录之间的关系

页与页之间的关联关系（通过双向链表来完成的）

索引查找的架构图

进一步细化

InnoDB行存储结构

InnoDB页简介（了解）

InnoDB将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，即MySQL管理存储空间的基本单位，InnoDB中页的大小一般为16kb（当然是可以设置）。也就是在一般情况下，一次最少从磁盘中读16kb的内容到内存中，一次最少把内存中的16kb内容刷新到磁盘中。页内的物理地址是连续的。

InnoDB页结构示意图

InnoDB行格式类型、行格式的语法、COMPACT行格式（了解）

InnoDB行格式类型

• Compact（重点）
• Redundant
• Dynamic
• Compresseed

记录的额外信息（重点）

变长字段长度列表

MySQL支持变长的数据类型，VARCHAR(M)、VARBINARY(M)、TEXT类型、BLOB类型等，这些变长的数据类型占用的存储空间分为两部分：

1. 真正的数据内容
2. 占用的字节数

如果不保存真实数据占用字节数，那么MySQL服务无法判断出真实数据有多长，导致无法准确取数。在Compact行格式中，把所有变长类型的长度存放在行记录的开头部位形参一个表，按照列的顺序逆序存放。

插入两条数据，用于后期讲解

示意图：

实际数据存储图：

我们可以看到aaaa、bbb、cc是存储在一块的，如果不记录占用字节数，是无法分辨的

需要注意一点的是，变长字段长度列表只存储非NULL值的占用长度，值为Null的长度是不存储的。

NULL值列表

表中的某些列可能存储NULL值，如果把这些NULL值都放到记录的真实数据中存储会很占空间，所有Compact行格式把这些值为Null的列统一管理起来，存储到Null值列表中。

1. 首先统计哪些列可以为NULL值

表中有允许存储NULL的列，则将每个允许存储NULL的列对应一个二进制位，二进制位按照列的顺序逆序排序

表record_format_demo有3个值允许为NULL的列，所以这3个列和二进制位的对应关系

2. 根据列的实际值，用1或0填充Null值列表

• 二进制位的值为1时，代表该列的值为NULL
• 二进制位的值为0时，代表该列的值不为NULL
• NULL值列表必须用整数个字节的位表示，如果使用的二进制位个数不是整数个字节，则在字节的高位补0
• NULL值只占用标志位空间，不占用真实数据空间

两条记录在填充了NULL值列表后的示意图是这样的：

3. 表中没有允许存储NULL的列，则不分配NULL值列表

记录头信息

除了变长字段长度列表、NULL值列表之外，还有一个就是用于描述行的记录头信息，他是由固定的五个字节组成。五个字节也就是40个二进制位，不同的位代表不同的意思，如图：

每个位是用来干什么的

记录的真实数据

记录的真实数据除了我们插入的那些列的数据，MySQL会为每个记录默认的添加一些列（也称之为隐藏列），具体的列如下：

需要注意的是，MySQL服务器会为每条记录都添加transaction_id和roll_pointer这两个列，但是row_id只有在表没有定义主键的时候才会为记录添加，相当于MySQL服务器帮我们来添加一个主键。

COMPACT行格式的VARCHAR(M)

• 真实数据
• 变长字段长度
• NULL值标识，如果该列有NOT NULL属性则没有这部分存储空间

如果VARCHAR类型的列没有NOT NULL属性，那最多只能存储65532个字节的数据，因为变长字段长度需要占用两个字节，NULL值标识需要占用一个字节。

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

行溢出

一个页的大小一般为16KB，也就是说16384字节，而一个VARCHAR（M）类型的列就最多可以存储65532字节，这样就可能造成一个页存储不了一条记录，则需要多页存储一条记录。

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

简图就是这样：

问题：那超过768个字节的数据就会行溢出吗？

答：查看下面的行溢出临界点

• MySQL中规定一个页中至少存放两行记录
• 每个页除了存放记录以外，需要存储一些元数据信息（136个字节的空间）
• 每个记录需要的元数据是27字节

计算行溢出临界点

InnoDB的页存储

我们先来看下InnoDB页结构示意图

看一下页结构字段描述

记录在页中的存储

前面我们聊到了记录头不同位代表着不同的信息，没有映像的可以查看上面的记录头信息，

delete_mask:这个属性标记着当前记录是否被删除，占用一个二进制位，值为0的时候代表记录并没有删除，为1的时候代表记录被删除掉了。

min_rec_mask:这个属性标记改记录是否为B+树的非叶子节点中的最小记录，值为0，代表着不是B+树非叶子节点中的最小记录。

heap_no:这个属性表示当前记录在本页中的位置，从图中可以看出来，我们插入的4条记录在本页的位置分别为2、3、4、5。InnoDB会自动在每个页里边加两条记录，这两条记录也称为伪记录或者虚拟记录，一个代表最小记录，一个代表最大记录。

next_record:表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。下一条记录指的并不是我们插入的顺序，而是按照主键值的顺序。而且规定最小记录的下一条记录就是本页中主键值最小的记录，本页中主键值最大的记录的下一条记录就是最大记录值，让我们看下图就很一目了然了：

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

页中的数据被删除掉短时间是不会被回收的，长时间的话那肯定是会被回收的，不然太浪费存储空间了，如果删除后，立即又添加回，那么页中记录指向又会恢复原来的。

页目录

• 将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录），划分为几个组
• 每个组的最后一条记录的头信息中的n_owned属性表示该组内共有几条记录
• 将每个组的最后一条记录的地址偏移量按顺序存储起来，每个地址偏移量也被称为一个槽（英文名：Slot）。这些地址偏移量都会被存储到靠近页的尾部的地方，页中存储地址偏移量的部分也被称为Page Directory。

• 现在Page Directory部分中有两个槽，也就意味着我们的记录被分成了两个组，槽0中记录着最小记录的地址偏移量；槽1中记录着最大记录的地址偏移量。
• 注意最小和最大记录的头信息中的n_owned属性

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

• 为什么最小记录的n_owned值为1，而最大记录的n_owned值为5？

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

1. 初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组
2. 之后每插入一条记录都把这条记录放到最大记录所在的组，直到最大记录所在的组中的记录数等于8个
3. 在最大记录所在组中的记录数等于8个的时候在插入一条记录时，将最大记录所在组平均分裂成2个组，然后最大记录所在的组就剩下4条记录了，然后就可以把插入的那条记录放到相应的组中。

在往表中插入6条数据

现在如何从这个页目录中查找记录？因为各个槽代表的记录的主键都是从小到大排序的，所以可以使用二分法来快速查找。

小结：各个数据页可以组成一个双向链表，而每个数据页中的记录又可以组成一个单向链表，每个数据页都会为存储在它里边的记录生成一个页目录，在通过主键查找某条记录时，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

页与记录之间的关系

MySQL索引

在一个页中查找

以主键为搜索条件

在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到记录

以其他列作为搜索条件

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

在多页中查找

大部分情况下表中存放的记录是非常多的，需要很多的数据页来存储这些记录。在多页中查找记录的话可以分为两个步骤：

1. 定位到记录所在的页
2. 从所在的页内中查找相应的记录

无论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页中根据相应的查找方式去查找指定的记录。因为要遍历所有的数据页，所有这种方式显然是超级耗时的

在多页中查找时，为什么要遍历所有的数据页？

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

• 下一个数据页中的主键值必须大于上一页中的主键值
• 给所有的页建立目录项

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

我们时常会对记录进行增删，假设我们把一页中的记录都删除掉，该页也就没有存在的必要了，那意味着对应的目录项也就没有存在的必要了，这就需要把该目录项后的目录项都向前移动一下

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

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

目录项记录和用户记录的不同点：

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

数据查找

存储目录项记录的页不止一个，如果想根据主键值查找一条用户记录大致需要3个步骤：

1. 确定目录项记录页。现在的存储目录项记录的页有两个，即页30和页32，又因为页30表示的目录项的主键值的范围是【1,320】，页32表示的目录项的主键值不小于320，所以主键值为20的记录对应的目录项记录在页30中。
2. 通过目录项记录页确定用户记录真实所在的页
3. 在真实存储用户记录的页中定位到具体的记录

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

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

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

聚簇索引

• 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义

1. 页内的记录是按照主键的大小顺序排成一个单链表
2. 各个存放用户记录的页也是根据页中记录的主键大小顺序排成一个双向链表
3. 各个存放目录项的页也是根据页中记录的主键大小顺序排成一个双向链表

• B+树的叶子节点存储的是完整的用户记录

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

二级索引

上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。如果我们想以别的列作为搜索条件时，该如何遍历？

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

二级索引与聚簇索引的几个不同点：

• 使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：

1. 页内的记录是按照c2列值的大小顺序排成一个单向链表。
2. 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表
3. 各个存放目录项的页也是根据页中记录的c2列大小顺序排成一个双向链表

• B+树的叶子节点存储的并不是完整的用户记录，而是c2列+主键
• 目录项记录中不再是主键+页号的，而变成了c2列+页号

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

1. 确定目录项记录页
2. 通过目录项记录页确定用户记录真实所在的页
3. 在真实存储用户记录的页中定位到具体的记录
4. 该B+树的叶子节点中的记录只存储了c2和主键（c1）两个列，所以我们必须再根据主键（c1）值去聚簇索引中再查找一遍完整的用户记录

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

联合/组合索引

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

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

注意一点，以c2和c3列的大小为排序规则建立的B+树称为联合索引，它的意思与分别为c2和c3列建立索引的表述是不同的。

• 建立联合索引只会建立如上图一样的一颗B+树。
• 为c2和c3列分别建立索引会分别以c2列和c3列的大小为排序规则建立2棵B+树。

MyISAM中的索引

简单介绍一下MyISAM中的索引，InnoDB中主键索引即数据，聚簇索引的那颗B+树的叶子节点中已经把所有完整的用户记录都包含了，而MyISAM的索引方案虽然也使用了B+树，
但是却将索引和数据分开存储：

• 将表中的记录按照插入时间顺序的存储在存储空间上，可以通过地址快速访问到一条记录。
• MyISAM会单独为表的主键创建一个B+树索引，只不过在B+树的叶子节点中存储的不是完整的用户记录，而是主键值+地址的组合。

聚簇索引的优缺点

优势：根据主键查询条目时，不用回表，数据记录就在主键节点下

劣势：如果碰到不规则主键数据插入时（例如主键值为 1,3,2,8,7,6,4插入），造成频繁的页分裂（行迁移），消耗性能。

聚簇索引的主键值，应尽量是连续增长的值，而不是要是随机值（不要使用随机字符串和UUID），否则会造成大量的页分裂和页移动。

最左匹配原则

例如：联合索引（c2,c3）

• 先把各个记录和页按照c2列进行排序（即最左优先）
• 在记录的c2列相同的情况下，再对c3列进行排序

此时，B+树中存在两个顺序：c2和c2,c3

此时，一颗B+树中含有两颗索引树：（c2）、（c2,c3）

例如：联合索引（c2,c3,C4）

• 先把各个记录和页按照c2列进行排序（即最左优先）
• 在记录的c2列相同的情况下，再对c3列进行排序
• 在记录的c3列相同的情况下，再对c4列进行排序

此时，B+树中存在三个顺序：c2 和 c2,c3 和 c2,c3,c4

此时，一颗B+树中含有三颗索引树：（c2）、（c2,c3）、（c2,c3,c4）

对（c2,c3,c4）这样的数据检索时，B+树是按照从左到右的顺序来搜索的，比如当（5,2,8）这样的数据来检索时，b+树会优先比较c2来确定
下一步的所搜方向，如果c2相同再依次比较c3和c4，最后得到检索的数据

对（c3，c4）没有c2数据检索时,B+树就不知道第一步该查哪个节点，因为建立B+树的时候c2就是第一个比较因子，必须要先根据c2来搜索才能
知道下一步去哪查询

对（c2,c4）这样的数据来检索时，b+树可以用c2来指定搜索方向，但下一个字段c3的缺失，所以只能把等于c2的数据都找到，然后再匹配c4的数据 ( ICP特性 )

最左前缀的使用，有两条说明：

• MySQL从左向右匹配直到遇到范围查询（>,<,between,like）就停止匹配

示例:where a = 1 and b = 2 and c >3 and d = 4

如果建立（a b c d）顺序的索引，d是用不到索引的

如果建立（a b d c）顺序的索引则都可以用到

• where条件中的=和in是可以乱序的，mysql的查询优化器会帮你优化成索引可以识别的形式

示例：建立（a,b,c）索引

where a=1 and b=2 and c=3

where b=2 and c=3 and a=1

案例解析：

索引长度用了16个字节，全部用到了

用到了8个字节，extra：Using index condition是在索引中过滤的，也就是ICP特性

用到了4个字节，不用二次排序，因为c1,c2,c3整体是有序的，c1=x时c2,c3自然是有序的

用到了4个字节，要二次排序

用了4个字节，不用二次排序，要进行回表查找c5

不用二次排序了，因为c2的值定了，实际上是c1,c2,c3

索引覆盖

• 如果一个索引包含（或覆盖）所有需要查询的字段的值，称为‘覆盖索引’。即只需扫描索引而无须回表。

优点：

• 不用回表，减少二次查询或减少随机查询IO
• 减少了遍历数据页的数量。因索引条目小于数据行的大小，所以索引叶子节点占用的数据页数量远远小于原表记录所占用的数据页的数量。

Extra：Using index就是索引覆盖

索引选择性

既然索引可以加快查询速度，那么是不是只要查询语句就建上索引呢？

答案：不，因为虽然索引加快了查询速度，但是索引也是有代价的：索引本身要占用存储空间，同时索引会加重插入、删除和修改记录时的负担，因此索引并不是越多越好。一般两种情况下不建议使用索引。

• 第一种情况是表记录比较少，例如一两千条甚至几百条记录的表，没必要建立索引。
• 另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality），与表记录数（#T）的比值：Index Selectivity = Cardinality / #T

总结：
前缀索引兼顾索引大小和选择性，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于索引覆盖，因为索引值是不全的。

大数据分页查询和延迟关联

limit offset，N的时候，随着offset增加，语句耗时也在增加。因为mysql是取offset+n行，然后放弃前offset行，返回N行，当offset特别大时，效率就非常低下。

延迟关联：通过使用索引覆盖查询返回需要的主键，再根据主键关联原表获得需要的数据。

使用延迟关联解决大数据页查询瓶颈

1. 首先通过索引覆盖获取需要的主键

---聚簇索引，索引节点就是原纪录

select emp_no from employees limit 100000,10；

通过二级索引 走覆盖索引 效果会更好

alter table employees add index idx_emp_no(emp_no); --索引值+主键值
复制代码

2. 主表关联

select * from employees m inner join (select emp_no from employees limit 100000,10) as s on m.emp_no = s.emp_no
复制代码

索引与排序

排序的两种方式

• Order by沿着某个索引的顺序，查询的结果本身就有序
• 先取出数据，形成临时表做filesort（文件可能在磁盘上，也可能在内存中），不建议使用，性能差

order by满足两种情况会使用index方式：

• order by语句使用了索引最左前缀
• where条件与order by条件的组合满足索引最左前缀

创建联合索引的原则

• 联合索引总体选择性越高越好
• 分组及排序时，让排序沿着某个索引排序，放置二次排序
• 在不考虑分组及排序时，尽量选择区分度高的列作为联合索引的前导列。B+树是按照前导列进行排序的，将选择性高的列放到前面能够最快地过滤出需要的记录
• 联合索引不宜过长，可利用前缀索引降低索引条目长度