网络上的讲述MySQL索引的文章太多了，我打算换个角度来说。我们尝试着从设计者的角度思考，索引为什么这么设计。

假如你是索引的设计者，你会如何设计索引。我们不妨以新华字典为例。如果我们要查询汉字爱是什么意思，我们有如下操作

• 确定拼音（假设你知道拼音，只是想要知道它的意思），ai
• 找到拼音索引页
• 找到字母A起始位置
• 定位到ai，以及对应的页码

字典的数据部分

字典正文部分的内容，我们可以看成是数据页。每一个数据页都拥有自己的编码，也就是唯一标识——id。每一页都有一个起始汉字、结束汉字。

字典的索引部分

要让用户快速定位需要查询的内容，如果内容本身无法被快速定位，可以采取从数据中，提取部分冗余信息，构建成索引。然后将索引和内容，通过键值对映射（K-V） 的方式进行对应。

字典则是从每个汉字中，提取拼音这个冗余信息，作为上一层索引；然后从拼音中提取第一个字母，作为拼音的索引；最后将每个字母汇总在同一个索引页层级下，得到完整的索引结构。

我们将字典索引绘制，可以得到下方图案

tip:

• 值得一提的是，在构建索引时，存在着非常多相同拼音的汉字。但索引目录不可能全部存储下。因此在构建索引时，只会存储最具代表性的那一个汉字，以及它所存在的页数
• 以ai为例，索引中所记录的页数是拥有ai这个拼音，第一个汉字出现的位置。所以严格意义上将，字典的拼音索引并不全面。只有下方图示的索引结构，才能覆盖所有汉字
  

---

现在，我们回到MySQL的设计中。我们需要解决两个问题：

• 如何存储
• 索引如何建立

不论是索引还是数据，我们都需要存储在文件中，我们不妨设计一个叫test.ibd的文件，用于存储我们的数据和索引。其中，test叫表名，.ibd为数据库表文件后缀。

我们可以把test.ibd看作现实世界中的《新华字典》。字典用一页页的纸张存储数据，我们test.ibd也可以划分出一页一页的空间来存放我们的表数据。

字典的每一页都有固定的大小。同样的，数据库的每一页我们也可以固定大小，就比如16K

tip:

• InnoDB在物理层面以页（Page）为基本单位进行数据的读写和管理。每个页大小默认是16KB，并且这个大小是可以配置的。
• 当InnoDB存储引擎需要分配新的空间来存储数据或者索引时，它会以页为单位进行分配。即使实际写入的数据不足一页（默认16KB），InnoDB也会完整地申请一个页的空间。
• 据此，我们可以发现我们的.ibd文件全部都是16的倍数
  
  

存储的问题解决了，现在我们将视角聚焦于每一页的内容上。

我们可以将页划分为两列，一类是专门用于存储索引的——索引页，另一类专门存储数据的——数据页。

我们先看数据页

数据页

按照直觉，我们很快就设计出了数据页的内容。首先，我们需要空间用来存用户数据，每一行用书数据都需要一个id作为唯一标识。另外我们需要页头存储页码信息。通过页码来唯一标识页。具体如下图所示

现在我们来思考一个问题。假设我们现在找到了一页数据，我们如何定位逻辑上相邻的下一页数据呢？

对于字典来说，每一页都是物理相邻的，找到一页后顺着翻过去，就得到了另外一页。

但对于计算机来说，每一页都可能存储在磁盘的任何位置。因为磁盘最终会被划分为若干个单元格，操作系统不可能每次申请空间都恰好连续。随着文件的创建和删除，总会出现磁盘空间碎片的现象。如果是申请连续的大空间，这件事情难度过大。

考虑到数据页可能会分配在不同的空间，因此我们设计的时候需要增加指针，允许数据页找到彼此逻辑相连的数据页。

我们修改一下页的设计，通过添加前后指针，为页提供找到相邻页的能力

---

现在的页结构相对比较可用了，我们再完善一下，增加页目录、页尾这部分信息

我们思考这样一个问题，按照原来的逻辑，寻找数据只能全页遍历，这样的时间复杂度是n，如果用户数据非常多，那么所耗费的时间会非常大。

我们不妨将用户数据信息分组。

• 第一组，最小记录（id）所在组，且改组只有一个数据
• 最后一组，最大记录（id）所在组，会有若干数据
• 其余组尽量平均分配每组数据，控制在一定量内

然后，我们在页目录中记录若干slot，每个slot槽指向对应组中，最大数据的偏移地址。通过页目录构造出的数据结构，我们可以对原先的全遍历优化，通过二分的方式降低时间复杂度。从$o(n)->o(lo{g}^n)$

另外，我们增加页尾，提供页数据完整性校验的功能。

索引页

在正式讲索引页前，我们用一个小案例引入

假设，我们需要从一下数据页中查找id = 11的数据。在数据量小的情况下，我们全表遍历没什么问题。从第一页开始，挨个遍历所有行。但数据量大了，这种方式肯定是需要被淘汰的。我们需要提高搜索效率，这就是索引出现的原因。

索引页的设计我们依然沿用数据页的设计，不同的地方是索引页存储的内容是索引，且只存索引，而数据页存的是数据。这么做有个好处，当页只存储索引，那么每一页能够容纳更多的索引信息，从而提高索引范围，从而提高了数据的容量。

那么索引页，我们该怎么存储索引信息呢？索引存储个啥呢？

在最开始我们提到，索引就是增加冗余信息。通过构建冗余信息来提高查询效率，这也算是空间换时间的一种具体实现。

我们将数据页的每一页最小的数据信息抽离出来，存储到索引页中。形成索引页，具体如下图

现在我们要查询id = 11的数据，我们先遍历索引页，发现11在9 ~ 12之间，因此定位到页3，然后在页3中根据页目录的信息进行二分，找到11号数据。引入索引页，我们能够更快的定位到数据信息。

此外，随着数据的引入，索引页的增长数量是非常缓慢的。按照上图所示逻辑，一份索引页能够索引到4张不同的页。假设我们是3层数结构，且全部填满。一、二两层用于存储索引页、三层用于存储数据页，我们可以容纳的数据量是$1\ast 4\ast 4\ast 4=64$行数据
$$\begin{gathered} 计算公式位n=z^{(h-1)}\ast y \\ 其中,n表示数据量,z表示索引页存储的数据 \\ y表示数据页存储数据量 \\ h表示树的高度 \end{gathered}$$
假设我们现在拥有5层的树高，且全部填满，带入公式可得，$n=1024$

我们用python将数据可视化

不难发现，随着h（树高）轻微的变化，n（数据量）指数式增长。这便是构建树形索引页的好处。

至此，我们的索引设计基本完成！

---

MySQL单表最大数据容量2000万？

有了上文所说的内容，这个数据的判断起始不难。

假设我们拥有三层满树结构，且页的大小默认为16K，除去其余的信息，索引页能够存储的索引信息只有15K，假设每一行数据占用空间12B，由$15\ast 1024/15=1280$ 可得，索引页在假设条件下可以索引1280页数据信息。

数据页同理，拥有15K的存储数据的空间，每行数据1K，那么数据页能够存储的数据为15行

带入上一节的公式$n=z^{(h-1)}\ast y$， 计算得到$n=24576000$，也就是2000万。

当然，这个数据不绝对。如果行数据大小小于1K，那么容量还得翻一番。

另外，值得一提的是，树的高度决定了磁盘IO的次数。

前文我们提到每一页都是存储在磁盘不同的位置。在通过索引查找数据时，遍历了多少页，就意味着进行了多少次IO操作。

---

MySQL为什么采用B+树？

B+树具有如下优点

• B+树是多叉树，每一层能够索引的节点量非常庞大。在树的层级确定的情况下，能够容纳更多的数据
• B+树索引部分只存储索引，不存储数据，因此能够存储更多的索引，从而容纳更多的数据（B树，会将一部分数据充当索引）
• B+树的所有数据都存储在叶子节点，并且通过指针顺序相连。因此B+树支持范围查询

聚簇索引 / 非聚簇索引

聚簇索引

我们直接看官方是怎么说的

Each InnoDB table has a special index called the clustered index that stores row data. Typically, the clustered index is synonymous with the primary key.

聚簇索引，叶子节点存储的是完整一行的数据，它和主键相关。

我们用图来演示

假设我们创建了test表，其中存储如下数据

我们为主键创建聚簇索引，create unique index jucu_index on test(id)

得到如下的索引图

叶子节点存放了完整一行的数据

非局促索引

Indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.

在innodb中，只要不是聚簇索引，就是非局促索引。非聚簇索引叶子节点包含了每一行的主键。innodb再用主键的值，在聚簇索引中查询整行信息

我们为age字段创建普通索引，create index nianning_index on test(age)

索引图如下

每个叶子节点存储的是主键，而不是每一行的信息

回表 / 索引覆盖

回表

回表是指当查询过程中根据非聚簇索引找到行的键值后，缺少需要列信息，所以需要根据主键再次回到聚簇索引的数据区去查找对应的完整行记录的过程

我们以上一节的例子为例

select * from test where age = 30; 这段SQL会走age的非聚簇索引。找到age = 30所对应的节点后，节点只存储了id信息，缺少了其他的信息。因此需要通过找到的id信息，返回聚簇索引中找到全部的信息。

覆盖索引

索引包含了查询所涉及的所有列，因此数据库可以直接从索引结构中检索所有需要的数据，无需进行额外的“回表”操作来读取磁盘上的实际数据行

依然以test数据库为例

select id, age from test where age = 30;这个SQL就是覆盖索引。因为在age上创建的索引就包含了需要查询的所有信息，无需进行回表