【MySQL】InnoDB存储引擎篇（二）索引结构

数据库的索引，相信大家都不陌生了。这篇文档我会从头到尾的把索引讲清楚，而不是死记硬背的八股模式。死记硬背固然可以应付面试，但其实不会对索引的理解很深刻。

我也是在深入学完索引的时候才感慨，还是加深对技术的理解，面试的时候才可以侃侃而谈，答出其他竞争者答不到的点，从而让面试官对你高看一眼（实话）。

下面我会从 B+树结构，聚簇索引，二级索引，联合索引的顺序展开。

1. B+树

我们先不直接讲 B+树的定义，而是通过讲 InnoDB 中页的存储方式上理解其结构。

前文我们说 InnoDB 引擎存储数据的基本单位是页，我们存储的一条一条记录都是存放到数据页里的。
那么 B+树上的每个节点其实就是页，是一个一个数据页组成的一棵树。但不是所有的页都存放用户记录。

我们简单的建一个表，先不建索引。

CREATE TABLE cs_user (
  id INT PRIMARY KEY,
  age INT,
  name VARCHAR(50),
);

INSERT INTO cs_user (`id`, `age`, `name`) VALUES (1, 22, '张三');
INSERT INTO cs_user (`id`, `age`, `name`) VALUES (2, 25, '李四');

SELECT * FROM cs_user;
SELECT * FROM cs_user WHERE id = 1;

先抛出两个问题：

创建了一张表并插入了两条记录，那么在我们不创建索引的情况下，进行查询操作的时候，数据库是如何快速找到指定的记录的呢？
InnoDB 引擎自动帮我们创建了一个聚簇索引（一会详细说），然后根据这个索引快速的定位。
我们知道在每个页中，有页目录可以通过二分法快速定位到要找的那条记录。但是每个页固定为 16KB，数据库很庞大的话，那么必然会有很多个页，这样又该如何快速找到指定的页呢？
这就要从 B+树的结构说起了，B+树是一个多叉树，在 InnoDB 引擎中，只有最后一层也就是叶子节点才存放用户记录，上面的那些层包括根节点其实都相当于是一个目录页，只不过越靠近根节点，囊括的范围越广。就比如说我想查找一个学生的班级，那么我肯定先查他是哪个学校的，再查他是哪个年级的，最后再查他是哪个班级的，如下图所示：只有叶子节点才存储数据（即班级）

2. 聚簇索引

同理，B+树前几层都是目录页，用于更快速的定位查询记录所在的页，然后一层一层向下查询，直到找到记录所在的数据页，再根据上一篇文档讲的页目录，查询到具体的记录。

下面这个是一个聚簇索引构成的 B+树，叶子节点存的是完整的记录。
这里引用下《MySQL是怎样运行的》图示，不知道 Infimum 和 Supremum 是啥的请看上一篇文档。

通过这张图片，可以看到：

不同页之间按照主键的大小顺序排成一个双向链表
不同记录之间按照主键的大小顺序排成一个单向链表
非叶子节点（也就是目录页），第二行的值是这个目录项记录指向的那个页第一条记录的主键值。比如第二层的页30，1 -> 5 -> 12 -> 200，1是页10的第一个主键值，5是页28的主键值...，以此类推。
非叶子节点，第三行的值是这个目录项记录指向的那个页的页号，图中显而易见。
叶子节点（也就是数据页），第一行是主键值(id)，第二行是年龄(age)，第三行是名字(name)，也就是说，聚簇索引的叶子节点包含一条记录完整的字段。

比如我执行这条语句：SELECT * FROM cs_user WHERE id = 8;

首先从根节点开始，由于 1 < 8 < 320，所以去页30查询
再查第二层目录，由于5 < 8 < 12，所以去页28查询
最后查叶子节点，从页28 id = 5 的记录向后查，查到下一个就是 id = 8 的记录

3. 二级索引

上面说的是我们通过主键 id 来查询记录，现在假如我们多了一个需求，需要频繁通过 age 来筛选用户。
如果我们没有对 age 设置索引，那么数据库查询的时候，就会进行全表扫描，从第一个记录开始一个一个遍历，这种方式当数据量很大的时候是很费性能的。所以应对这种需求，我们一般会为 age 添加一个索引（二级索引）这样再通过 age 查询用户的时候，就可以用这个索引来查询用户记录，效率直接翻xxx倍。

还是上面那张表，这次我们为年龄age 加一个索引

CREATE TABLE cs_user (
  id INT PRIMARY KEY,
  age INT,
  name VARCHAR(50)
  INDEX idx_age age;
);

INSERT INTO cs_user (`id`, `age`, `name`) VALUES (1, 22, '张三');
INSERT INTO cs_user (`id`, `age`, `name`) VALUES (2, 25, '李四');

SELECT * FROM cs_user;
SELECT * FROM cs_user WHERE id = 1;
SELECT * FROM cs_user WHERE age = 6;

二级索引整体结构上，和聚簇索引差不多，区别在于叶子节点上（数据页）。

原来聚簇索引中记录的所有字段（id, age, name），现在只有两个字段了（age, id）
第一行变成了年龄age，而主键退居后方到了第二行。

也就是说，二级索引会针对定义了索引的这个字段，构造一棵新的 B+树，这棵树的叶子节点，其每个记录的第一行都是定义索引的这个字段，二分法会根据这个索引字段的大小进行排序和查找。但是这个新的 B+树还是会携带上主键，这个主键的作用是为了回表（一会说）

比如我执行这条语句：SELECT * FROM cs_user WHERE age = 6;

首先从根节点开始，由于 2 < 6 < 9，所以去页42查询
再查第二层目录，由于5 < 6 < 7，所以去页36查询
最后查叶子节点，从页36 age = 5 的记录向后查，查到下一个就是 age = 6 的记录

记录排列顺序

读者请注意看，叶子节点的 页35，当索引字段 age 相同时（都等于4），又该怎么排序呢？

当然不是随便排，第一行相同，那就比第二行主键值的大小，发现 4 < 10，那么 id = 10 的就排在 id = 4 的后面

这样在我们插入 age = 4 时，主键值也是有序的，也是一种规范。不然会造成一种混乱，比如插入相同记录的时候，是该将 age = 4 的记录插入页34呢还是页35呢。
除此之外，这样按一层一层的大小顺序排布，查询的时候也是有讲究的，下一章会具体讲解。

回表

我们现在知道，二级索引中是不存储完整记录的。那当我们想查询这个年龄对应用户的完整记录，又该如何操作呢。答案是从二级索引的B+树中拿到主键值，再通过这个主键值去聚簇索引中查询完整记录。

也就是说，通过二级索引查询完整记录，我们需要走两次B+树的查询流程。

第一次走二级索引，查到 age = 6 对应的主键 id = 220
第二次走聚簇索引，查到 id = 220 对应的完整记录 cs_user(220, 6, 'i')

当然，如果我们只需要查询 age （或者同时查询主键值id 和 age）的话，那就不需要回表操作，因为二级索引的这棵B+树就包含了这两个字段。

4. 联合索引

假如傻x产品经理现在又多了一个需求，在筛选用户时，要通过用户的 name 和 age 一起查询。

我们现有的索引，聚簇索引（主键索引），age 的二级索引，都无法快速拿到这两个值。

聚簇索引的叶子节点（数据页），是以主键 id 大小排序的，二分法也是用 id 值快速查询，无法用二分法快速通过 age 和 name 查询到指定记录。
age 的二级索引里面，又没有 name 字段，查询还得通过回表再查一次聚簇索引。

所以，我们可以根据 age 和 name 建立一个联合索引

CREATE TABLE cs_user (
  id INT PRIMARY KEY,
  age INT,
  name VARCHAR(50)
  INDEX idx_age age;
  INDEX idx_age_name (age, name);
);

INSERT INTO cs_user (`id`, `age`, `name`) VALUES (1, 22, '张三');
INSERT INTO cs_user (`id`, `age`, `name`) VALUES (2, 25, '李四');

SELECT * FROM cs_user;
SELECT * FROM cs_user WHERE id = 1;
SELECT * FROM cs_user WHERE age = 6;
SELECT * FROM cs_user WHERE age = 4 AND name = 'o';

根据这两个字段建立联合索引后，InnoDB 引擎会再建一棵 B+树，叶子节点的顺序为 age - name - id

也就是先按 age 的大小排序，再按照 name 的大小排序，最后按照 id 的大小排序。