MySQL 是当下一款主流的关系型数据库，它所有的数据均以磁盘文件的方式存储。在日常开发中我们都会听到许多为了加快 SQL 查询的效率而添加索引，同时许多文档也都会告诉我们要添加太多的索引， 索引不要太长， 使用数字或者空字符串来代替 NULL 等等的许多建议。那么为什么会有这些建议？这些建议又是否正确？这些答案都能从MySQL数据的物理存储方式中找到。

一行记录的存储格式

我们执行 SQl 的时候，查询的结果是一行行的格式返回的.因此在讲解索引、数据页前我们先来看一下 MySQL 中一行记录是怎么存储的：

在上图中我们可以看到,一条完整的记录分为「记录头」与「真实数据」两部份，下面展开看看记录头的部份：

1. 记录头信息
我们知道 MySQL 支持一些变长的数据类型与NULL值，比如 TEXT、VARCHAR 等等。这些类型的字段存储多少字节的数据是不固定的，所以我们在存储数据的时候把对应信息存储下来方便后续读取。因为该部份对本文影响不大，因此没有展开。

2. next_record 字段
在记录头中这个显眼的「next_record」字段相信已经引起了你的注意，正如其字面意思，该字段表示的是当前记录与一下条记录的偏移量。换一个说法就是，该字段是一个指向下一条记录的指针。

所以我们可以看到，在 InnoDB 中所有的数据就是通过该字段串起来成了一个单链表。而 MySQL 优化手段也是基于此进行改造的。

上图是我经过简化后的示意图，我把一些与本篇无关的内容隐藏掉了，仅保留了比较关键的内容

InnoDB数据页

页是 InnoDB 管理存储空间的基本单位，一个页的大小一般是 16k。数据页中则存放着我们上面提到的一行行记录，现在我们知道记录之间是通过 next_record 字段串联形成一个单向链表。那么在一个数据页中要查找某条记录该怎么办呢？

最笨的办法是从第一条记录开始遍历一遍链表，那么第一条记录我们怎么知道是哪条呢？以及当数据很多时，遍历一遍的时间也是无法忽视的，MySQL是怎么优化的？下面我们来看一下 MySQL 中数据页的格式，如下图：

在上图中我们可以看到一个数据页中关键的几个东西：

  1. 页号：页号是唯一的，如同身份证号码一样，InnoDB 通过页号来唯一定位一个页
  2. 最小记录/最大记录：页面中的最小记录和最大记录，用于指向真实数据记录，相当于真实记录链表的头尾哨兵
  3. 槽（slot）：页目录，用于快速定位页面中的记录，加速查找过程（通过二分查找）。
    1. 将所有正常的记录（包括最大/最小记录）划分为几个组，一个组对应槽中的一位（对应图中黄色范围）
    2. 每组记录的最后一条记录中的记录头中会有一个 n_owned 属性表示该组内共有几条记录
    3. 将每个组中最后一条记录在页面中的偏移量单独提取出来（就是槽中的每一位均指向每组记录中最大的那条记录）

页目录（槽）

比如现在图中有5条记录，InnoDB 会把他们分成2个组，第一组只有一个「最小记录」（也就是头哨兵），第二组则是剩余的4条记录，一共两个组。因此对应着2个槽，每个槽中存放每个组中最大的那条记录在页面中的地址偏移量（即指向最大记录的指针）。每个分组中的记录条数都有规定，规定如下：

  1. 最小记录（头哨兵）所在的分组只能有一条记录
  2. 最大记录（尾哨兵）所在的分组拥有的记录数只能在1～8条之间
  3. 剩余的分组中记录的条数范围为4～8条之间

所以初始情况下只有最小/大记录，因此页目录（槽）中只有两个组。之后每插入一条记录，都会从页目录上找到对应记录的主键值比准备插入的主键值大，且差值最小（为了让主键顺序排列-从小到大）的槽，然后把该槽的 n_owned 值加一，表示添加了一条记录，直到该组记录中的记录数等于8个。8个后再插入则不满足第二条规则，因此会产生新的一个组，并将原有记录进行迁移，使得满足三条规则。

在数据页中定位记录

当前页面中记录太少，不好演示页目录如何加快查找速度的，为此我们往页面添加几条记录，添加后的数据页如下（为了清晰的展示槽与组之间的关系，我将记录之间的指针隐藏了，详细看上一张图片）：

因为记录的主键都是从小到大排列的，所以我们可以使用二分法快速查找记录，如图中所示一共有5个槽，接下来我们模拟一下在该表中找到「记录6」的过程：

  1. 根据槽的信息，可以得到最低的槽 low = 0，最高的槽 high=4（也就是二分查找的初始边界）
  2. 计算中间槽的位置：(0+4)/2 = 2，查看槽2对应记录为8，又因为 8 > 6，所以设置 high=2, low 保持不变
  3. 重新计算中间槽的位置：(0+2)/2 = 1，查看槽1对应组最大记录的主键值为4；又因为 4 < 6,所以设置 low=1, high 保持不变
  4. 因为 high-low = 1，所以确定主键值为6的记录在槽2对应的组中
  5. 此时我们只需从槽1的最大记录开始遍历每条记录（也就是从槽2的开头遍历），便能很快找到「记录6」了。

上面我们已经介绍过，每个组中包含的记录条数最多是8条，所以遍历一个组中的记录代价是很小的。因此我们可以将上面的步骤再提炼一下，总结成在一个数据页中查找元素的步骤：

  1. 在页目录中通过二分法确认记录所在的槽
  2. 通过记录的 next_record 属性遍历该槽所在的组中的各个记录

至此，我们已经知道了如何在数据页中快速查找到一条记录，而将这一个个数据页连接起来便能是我们存储的所有数据了。那么如何才能高效的在这么多数据页中查找记录，接下来就轮到“索引同志”登场了。

B+树索引

我们知道一个数据页的大小是 16K，而我们业务中一个表的数据动辄就上G，显然一个数据页是无法装下我们的数据的。那么在一个表中的数据页是怎么链接起来的？我们回到查询一条记录的语句上，要在这么多数据页中找到一条记录，最笨的方法便是遍历所有的数据页，那么为什么要遍历所有的数据页呢？我们不能有个聪明点的方法吗？原因是因为数据页之间是没有规律的，我们并不知道搜索调节会匹配哪些页的记录（因为没有规律，所有的数据页都有可能存在），因此不得不遍历所有数据页。

那么如何快速定位到记录在哪些数据页中？我们还记得在数据页里面为了快速定位一条记录，我们为页中的数据划分了组，并且为此建立了一个页目录（槽）。同样的我们也可以想办法为了「快速定位记录所在的页」而建立一个目录，在建立这个目录的过程中需要满足这几个条件（页与页之间的规定）：

  1. 下一个数据页中「真实记录」的主键值必须大于上一个页中「真实记录」的主键值（叶子节点）
  2. 数据页之间通过前后指针相连
  3. 给所有页建立一个目录项（内节点）

为此我们得到了一个简易版的索引方案，如下图：

为什么说这是简易版的索引呢？因为我们这么做的前提是假设了目录项是有连续的存储空间的，但实际并非如此，因此会引起下面的几个问题：

  1. InnoDB 使用页作为管理存储空间的基本单位，也就是只能保证16KB的连续存储空间
  2. 我们经常会对记录做增、删、改的操作，如果某个页中最后一条记录删除会导致该页被移除，为了紧凑设计会导致目录项中该页后面的所有记录都需要往前挪动

为此我们需要一种更灵活的方式来管理目录项，我们不难发现目录项与「真实记录」长的很像，只不过目录项中的两个列是主键与页号而已，为此我们可以复用存储用户记录的数据页来存储目录项，我们把这些用来表示目录项的记录称为目录项记录

那么我们把前面简易版本的索引方案修改后，便能得到下图所示的结构：

以查找记录9为例子，我们来看看是如何通过目录项加快查询速度的：

  1. 先到目录项记录所在的页（也就是页10）中通过二分法快速定位到对应的目录项记录，因为 1< 9 < 2，所以定位到对应的「真实记录」所在的页为页21
  2. 再到存储用户记录的页21中根据二分法快速定位到「记录9」

虽然说目录页中只存放主键值与页号，比用户记录所需要的空间要小很多，但因为一个页只有16K大小，因此能存放的目录项也是有限的。如果表中的数据太多了导致目录页存放不下，那么便会重新分配一个目录页。目录页与目录页之间也通过上述的办法进行复用（利用目录页定位目录页），从而减少单次二分查找的数量，提高效率。在插入很多数据后，整个结构便像下图一样：

上图所示的便是许多文章中提到的 B+树 了，无论是存放用户记录的数据页，还是存放目录项的数据页，我们都把它们存放到B+树这个数据结构中。从上图中我们也可以看出，我们的「真实记录」其实都存放在B+树最底层的节点上（叶子节点）。其余用来存放目录项的节点为非叶子节点或内节点。

我们来简单的计算一下，假设叶子节点所代表的数据页可以存放 100 条用户记录，而内节点可以存放1000条记录，那么：

  1. 如果该树有2层，则最多能存放 1000 x 100 = 100000 条用户记录
  2. 如果该树有3层，最多能存放 1000 x 1000 x 100 = 100,000,000 条用户记录
  3. 如果有4层，最多能存放 1000 x 1000 x 1000 x 100 = 100,000,000,000 条记录

所以在一般情况下，我们用到的B+树都不会超过3层。这样一来在通过主键去查找某条记录时，最多只需要进行4个页面内的查找（3个目录页与一个真实记录的页），又因为每个页中有页目录（槽），所以在页面内可以通过二分查找快速定位记录。因此我们可以看到这就是使用B+树查询高效的原因。

这种根据主键ID构建的B+树，我们称为「聚簇索引」，这也引申出来了 InnoDB 中所谓的“索引即数据，数据即索引”。

我们可以看到这里只有 ID 作为索引列，但我们平时使用的过程中还可以为其他列建立的索引，因此这就引申出二级索引与联合索引了。

二级索引与联合索引

无论是二级索引亦或是联合索引，其实都是基于上面提到的聚簇索引而引申出来的。我们先来看看二级索引与聚簇索引的区别：

  1. 聚簇索引是根据主键进行排序的，而我们刚刚提到无论是页面内还是页面之间都强调了一个有序（从小到大）的特性。因此二级索引也是需要进行排序的，但二级索引是根据索引列进行排序，排序的规则则是根据设置的字符集来排序
  2. 二级索引的叶子节点中只存放「索引列」与主键值，因此如果需要获取完整的记录，需要根据主键值到聚簇索引中查询（这个操作也叫回表）

二级索引如下图所示：

我们除了可以使用某一列进行索引外，还可以同时为多个列建立索引，而多个列建立的索引则称为「联合索引」。许多文章都会提到最左匹配等概念，而这也是与我们联合索引的结构息息相关的，比如我们想让B+树按照A和B列的大小进行排序，这里面就包含了两层含义：

  1. 先把各个记录和页按照A列进行排序（因为A在前面）
  2. 在A列相同的情况下，再根据B列进行排序

该索引如下图所示：

总结

在创建和使用索引时应该注意以下事项：

  1. 只为用于搜索、排序或分组的列创建索引
  2. 当列中不重复值的个数在总记录数中占比很大时，才值得建立索引
  3. 索引列的类型要尽可能的小
  4. 可以只为索引列创建前缀索引，减少索引占用的空间
  5. 尽量覆盖索引进行查询，避免出现回表
  6. 为了减少让聚簇索引出现页分裂的情况，主键最好要自增