概述

简单来说，索引的出现是为了提高查询效率，就像书的目录一样。MySQL 的索引是在「存储引擎」层实现的，因此没有统一的标准，同一种类型的索引，在不同存储引擎之间实现可能也不同。本文主要分析 InnoDB 存储引擎的索引结构。

索引模型

索引模型就是索引的实现形式（也可以理解为索引的数据结构），常见的索引模型有下面三种：

1. 哈希表（散列表）

键值对形式（类似 Java 中的 HashMap）

    优点：新增速度快；

    缺点：无序，区间查询速度很慢（全表扫描）。

    适用场景：只有等值查询的情况（例如 Memcached 等一些 NoSQL 引擎）。

2. 有序数组

    优点：等值查询和范围查询速度都很快。

    缺点：更新成本太高（插入的记录在中间时，需要移动后面的所有记录，可类比在数组中间位置插入元素的操作）。

    适用场景：静态存储引擎（比如不再修改的历史数据）。

3. 搜索树（N 叉树）

    优点：读写快，适配磁盘的访问模式。

    B+ 树就是其中的一种，也是 InnoDB 存储引擎的索引模型。

InnoDB 记录的存储结构

数据页

在 InnoDB 引擎中，会将数据划分为若干个「页」，「页」是磁盘和内存之间交互的基本单位，页的大小一般为 16KB。即：一般情况下，一次最少从磁盘中读取 16KB 的数据到内存中，一次至少把内存中 16KB 的数据刷新到磁盘中。

向一个数据页中插入记录的过程如图所示：

数据页中分为几个部分，其中 User Records 部分为存储记录的空间（其他部分存储数据页的其他信息，这里暂不详述），插入过程大致如下：

1. 未插入记录时，User Records 部分不存在；

2. 当插入记录时，会从 Free Space 部分划分出空间存储记录；

3. 当 Free Space 空间用完时，也就是该数据页的空间用完了，需要分配新的数据页存储（页分裂）。

记录的结构

在 InnoDB 引擎中，一条记录的存储结构如图所示：

PS: 其中橙色部分 (c1, c2, c3) 是表中的列，且 c1 为主键，下图亦是如此。

也就是说，数据页中记录的数据，除了一条记录本身，还有变长字段列表、NULL 值列表、记录头信息等其他信息，这样才是在数据页中的一条完整记录。

数据页中多条记录之间的关系示意图：

即，每个页中保存了许多条记录，并且每条记录指向下一条记录（根据主键顺序，类似单链表结构）。此外还记录了该页中的最小和最大记录（也是根据主键顺序）。

不仅如此，这些记录还会几条（1~8）分为一个组，并且把组内最大的主键值提取到一个槽（slot）中，用来实现快速（二分）查找，示意图如下：

页内查找记录

以上面的数据页为例，若要查找主键值为 5 的记录，过程如下（二分查找）：

1. 计算中间槽的位置：(0+4)/2=2，因此查找槽 2，而它对应记录的主键为 8，5<8，重新计算；

2. 重新计算，(0+2)/2=1，查找槽 1，对应记录的主键值为 4，5>4，因此查找的记录在槽 2 中；

3. 遍历槽 2 对应的分组，查找主键为 5 的记录。

因此在一个数据页中查找指定主键值的记录过程大致分为两步：

1. 通过二分查找确定记录所在的槽；

2. 遍历该槽所在组中的各个记录（通过记录的 next_record）。

由于槽内数据很少（不超过 8 条），因此遍历的成本较低。

聚簇索引&二级索引

根据叶子节点的内容，索引类型可分为「聚簇索引」（Clustered Index）和「二级索引」（Secondary Index）。

1. 聚簇索引

在 InnoDB 存储引擎中，聚簇索引也称为「主键索引」，表都是根据主键顺序组织存放的，这种存储方式的表称为索引组织（Index Organized Table）表（索引即数据，数据即索引）。一张表只能有一个主键索引。

聚簇索引的示意图如下（该结构就是一棵 B+ 树）：

图中结构分为三层，其中上面的两层（即非叶子节点，页 33、页 30 和页 32）为索引层，保存的是索引信息；第三层（叶子节点）为数据层。在主键索引中，叶子节点保存的是完整的记录（以数据页为单位）。

PS: 存储节点的空间可能是不连续的，但是，同一层的节点是有前后顺序的，它们之间以「双向链表」的形式连接。

在索引树中查找一条记录的大致过程如下（仍以查找主键值为 5 的记录为例）：

1. 先查找根节点，即页 33，页 30 中的主键范围是 [1, 320)，而页 32 中主键大于等于 320，因此定位到 页 30；

2. 再查找页 30，同样的方法定位到页 28；

3. 根据上面「页内查找记录」的方式在页 28 中查找。

2. 二级索引

InnoDB 中，二级索引的叶子节点存储的是主键的值。二级索引也称为「非聚簇索引」、「非主键索引」。一张表可以有多个二级索引。其中，以单列作为二级索引的又称「单列索引」，以多列作为索引的又称「联合索引」或者「组合索引」。

二级索引的示意图如下：

该结构与聚簇索引类似，也是一棵 B+ 树。

与聚簇索引的不同之处主要在于第三层，也就是叶子节点，在二级索引中，叶子节点保存的是主键的值。

二级索引中的查找过程与聚簇索引中查找类似。

不同的是，由于二级索引保存的是索引列和主键列，若查找的数据包含索引和主键之外的内容，则需要先找出主键值，然后再根据主键的值到聚簇索引中查找完整记录，该过程称为「回表」。

值得注意的是，上述查找都是在有索引的情况下进行的，如果没有索引呢？则会进行全表扫描，这样当数据量较大时，效率会非常低。这也是索引出现的主要原因。

区别与联系（InnoDB 存储引擎）

1. 聚簇索引和二级索引都需要占用磁盘空间，每一个索引都对应一棵索引树；

2. 二者都是 B+ 树结构，数据都存储在叶子节点（非叶子节点不保存数据）；

3. 聚簇索引的叶子节点保存的是完整记录，二级索引保存的是主键的值；

4. 在一张表中，聚簇索引只能有一个，二级索引可以有多个（即多个索引树）。

根据这几点比较也可以发现，索引虽然可以提高查找效率，但也有缺点。如果有多个索引，当修改数据时索引也要同步进行更新，这样会降低操作的效率；而且索引也会占用磁盘空间。因此，索引并非越多越好。

InnoDB 引擎主键选择

在 InnoDB 中，每张表都有个主键（Primary Key），如果在建表时没有显式地定义主键，则 InnoDB 引擎会按照如下方式选择或创建主键：

1. 首先判断表中是否有非空的唯一索引（Unique NOT NULL），若有，则该列即为主键（当表中有多个非空唯一索引时，InnoDB 存储引擎将选择建表时第一个定义的非空唯一索引为主键）；

2. 若不符合上述条件，InnoDB 存储引擎自动创建一个 6 字节大小的隐藏列（row_id）作为主键。

因此，建表时最好显式指定主键。

索引优缺点

主要优缺点如下（可通过上述存储结构分析理解）：

优点

1. 可以提高数据检索效率，降低数据库 IO 成本；

2. 对记录进行排序，降低 CPU 消耗（被索引的列会自动进行排序），可以提高排序和分组查询的效率。

缺点

1. 索引会占用磁盘空间；

2. 降低更新效率（更新操作会同步更新索引）。

索引使用场景

需要创建索引的场景

1. 主键自动建立唯一索引；

2. 频繁作为查询条件的字段应该创建索引；

3. 多表关联查询中，关联字段应该创建索引（ON 两边都要创建）；

4. 查询中排序的字段，应该创建索引；

5. 统计或者分组。

不需要使用索引的场景

1. 表记录太少；

2. 频繁更新；

3. 查询字段使用频率不高。

PS: 这里只是概括了一些常见的优缺点和使用场景，可以根据前面对索引的结构和特点的分析对比理解。

小结

简单来说，索引可以理解为书的目录。

索引的主要作用是为了提高查找效率；但索引也有缺点，并非越多越好，需要根据实际情况决定如何创建合适的索引。

主要参考资料：

1. 掘金小册「MySQL 是怎样运行的：从根儿上理解 MySQL」

2. 极客时间专栏「MySQL实战45讲」