Question

什么是索引

MySQL 官方对索引的定义为: 索引 （Index）是帮助 MySQL 高效获取数据的 数据结构 。在 InnoDB 中，索引的形式为 B+树。

这里所谓的高效，是指当我们从磁盘中读取数据时，应该尽可能地 减少磁盘 IO 次数 。

之前我们讲过 InnoDB 中，磁盘与内存交互的基本单位是页。可以想象一下，如果我们需要从 MySQL 中查找一条数据，应该如何查找？

朴素的思想:将数据页（或者区）读取到内存，然后再在内存中通过页目录，查询所需要的数据；如果未查询到，又需要进行一次磁盘 IO，读取新的数据页到内存中。试想一下，如果一个表中有百万、千万条数据，即使我们每次进行磁盘 IO 的时候都尽量读取很多的数据页到内存中进行查询，但是产生的磁盘 IO 次数也还是会非常多。

这时就需要一种 数据结构 来 快速找到数据存在的那个数据页 ，从而 减少磁盘 IO 次数 。这个数据结构就是 B+树 。

如果还未了解 B+树，可以参考: 什么是 B+树？（详细图解）_初念初恋的博客-CSDN 博客_b+树

索引的设计方案

现在，假设现在一张表中有这么几条数据（为了演示方便，假设一个页中最多只有三条数据、每次磁盘 IO 只能读取一个页）。

此时，假设我们需要查询 主键（黄色字段）=20 的行数据，就会遇到刚才说的问题:需要先读取页 10，再读取页 28，再读取页 9，最终找到数据，可以想象一下如果数据量很大，必然会产生很多次磁盘 IO。

解决方案就是我们设计一个目录项:

目录项中有两个字段:

• page_no:这个目录项所表示的数据页的编号
• key:这个目录项所表示的数据页的中最小的数据的 主键值

有了目录项，就可以先把目录项都读取到内存中，通过二分法查找，根据目录项中 key 的范围找到目标数据在哪个数据页中，然后直接读取那个数据页即可。

但是，随着数据量的增大，数据页会越来越多，相应的， 目录项也会越来越多 ，直到需要多次磁盘 IO 才能把目录项全部读入内存中，这样又退化到我们设计目录项之前的状态了。同时，目录项还缺乏一个具体的存储结构来管理。

于是，我们可以 将目录项用数据页来存储 。并且，给存放目录项的数据页再设计一个数据页用来存放其目录项，简称套娃。

目录项记录 和普通的 用户记录 的 不同点 :

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

相同点 :两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录） ，从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。

像这样的数据结构，就是 B+树:

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

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

而每多一层 B+树只会增加一次磁盘 IO。一般来说，三层 B+树索引足以存放百万级别的数据，而它的磁盘 IO 次数只有三次。

索引的分类

聚簇索引

上面的例子中，我们是根据数据的 主键 来对数据进行排序的，这种索引就称为 主键索引/聚簇索引/一级索引 。这种索引只能针对查询条件是主键的查询进行索引优化。

特点:

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

  所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

我们把具有这两种特性的 B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在 MySQL 语句中显式的使用 INDEX 语句去创建，InnDB 存储引擎会自动的为我们创建聚簇索引。

优点:

• 数据访问更快 ，因为聚簇索引将索引和数据保存在同一个 B+树中，因此从聚簇索引中获取数据比非聚簇索引更快。
• 聚簇索引对于主键的 排序查找 和 范围查找 速度 非常快 。
• 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的 io 操作。

缺点:

• 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于 InnoDB 表，我们一般都会定义一个自增的 ID 列为主键。
• 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于 InnoDB 表，我们一般定义 主键为不可更新 。

非聚簇索引

在实际的使用场景中，很显然不可能总是用主键作为查询条件。这时就需要对不同的 查询字段 按需建立索引了。这种索引就称为 非聚簇索引/二级索引/辅助索引 。

非聚簇索引和聚簇索引最大的区别就在于，它的叶子节点并不存放完整的数据，而是只存放 建立索引的字段 和 主键值 。因此当我们通过非聚簇索引查找数据时，找到的其实只是主键值，此时需要拿主键值，再去聚簇索引中找到完整的数据。这就称为 回表查询 。