InnoDB中的B+树索引

前言

InnoDB 中的 B+ 树索引分为三种：聚簇索引、二级索引、联合索引。

聚簇索引

聚簇索引有下面两个特点：

1. 使用记录主键值的大小进行记录和页的排序，这包含3个方面的含义：
   1. 页（包含叶子节点和内节点）内的记录按照主键的大小顺序排成一个单向链表，页内的记录被划分成若干个组，每个组中主键值最大的记录在页内的偏移量会被当作槽依次存放在页目录中，我们可以在页目录中通过二分法快速定位到主键列等于某个值的记录。
   2. 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
   3. 存放目录项记录的页分为不同层级，在同一层级中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
2. B+ 树的叶子节点存储的是完整的用户记录。所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

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

在 InnoDB 存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的“索引即数据，数据即索引”。

二级索引

聚簇索引只能在搜索条件是主键值时才能发挥作用。
如果想以别的列A作为搜索条件，需要再建一颗 B+ 树，我们称这种 B+ 树为二级索引或辅助索引。
这个 B+ 树与聚簇索引有几处不同：

1. 使用列A的大小进行记录和页的排序，这包含3个方面的含义：
   1. 页（包含叶子节点和内节点）内的记录是按照列A的大小顺序排成一个单向链表，页内的记录被划分为若干个组，每个组中列A值最大的记录在页内的偏移量会被当作槽依次存放在页目录中，我们可以在页目录中通过二分法快速定位到列A等于某个值的记录。
   2. 各个存放用户记录的页也是根据页中记录的列A值大小顺序排成一个双向链表。
   3. 存放目录项记录的页分为不同的层级，在同一层级中的页也是根据页中目录项记录的列A值大小顺序排成一个双向链表。
2. B+ 树的叶子节点存储的并不是完整的用户记录，而只是 列A值 + 主键 这两个列的值。
3. 目录项记录中不再是 主键 + 页号 的搭配，而变成了 列A值 + 页号 的搭配。

查找数据时，在二级索引 B+ 树的叶子节点处定位到第一条符合条件的那条数据记录之后，我们需要根据该记录中的主键信息到 聚簇索引 中查找到完整的用户记录。这个通过携带主键信息到聚簇索引中重新定位完整的用户记录的过程也称为 回表。

因为这种以 非主键列 的大小为排序规则而建立的 B+ 树需要执行回表操作才可以定位到完整的用户记录，所以这种 B+ 树也称为二级索引（Secondary Index）或辅助索引。

联合索引

我们也可以同时以多个列（如列A、列B）的大小作为排序规则，也就是同时为多个列建立索引。

假设我们想让 B+ 树按照 列A 和 列B 的大小进行排序，这里面包含两层含义：

• 先把各个记录和页按照 列A 进行排序；
• 在记录的 列A值 相同的情况下，再采用 列B 进行排序。

以 列A 和 列B 值的大小为排序规则建立的 B+ 树称为联合索引，也称为复合索引或多列索引。
它本质上也是一个二级索引，它的索引列包含 列A、列B。