InnoDB存储引擎的索引是如何实现的？

1. 索引的概念

1.1. 什么是索引？

索引^[1]（Index）是一种数据结构，用来加快查询的速度。如果表中的记录较少时，不创建索引也能满足查询的需求，但如果表中的记录较多时，如果不建立索引查询的速度会很慢。索引本质上是一种空间换时间的策略。

可以通过show index from <table_name>命令可以查看指定表中建立的索引。

1.2. 什么是索引组织表？

索引组织表（Index Organized Table，IOT）是指在InnoDB存储引擎中，每张表都会维护一个主键索引（Primary Key），表中的记录会存放在主键索引树的叶子节点上。主键的选用策略有以下几种：

• 选用表中显式指定的主键。
• 否者，选用表中首个非空唯一索引列作为主键。
• 否者，选用隐藏列ROWID作为主键。

索引组织表本质上就是索引就是数据，数据就是索引。

1.3. 索引的分类有哪些？

• 按照主键和非主键来划分：主键索引（也叫做聚簇索引）和二级索引（也叫做辅助索引）。
• 按照索引中列的个数来划分：单列索引和多列索引^[2]（也叫做组合索引）。
• 按照索引中列的唯一性来划分：唯一索引和非唯一索引（也叫做普通索引）。

1.4. 索引有哪些优点和缺点？

创建索引带来了以下几个优点：

• 加快查询的速度。
• 加快排序的速度。
• 加快分组的速度。
• 加快连表查询的速度等。

创建索引也带来了以下几个缺点：

• 每个索引都对应着一棵索引树，存储索引树需要占用磁盘空间。
• 对记录进行变更时需要同步维护索引树，会消耗一定的性能。

上面我们可以看到创建索引有利有弊，能够创建合适的索引才能充分发挥索引的作用，扬长避短。

2. 索引的实现

2.1. 索引需要满足的需求有哪些？

索引需要满足以下几个功能性需求：

• 支持等值查询。
• 支持范围查询。
• 支持排序。
• 支持分组等。

索引也需要满足以下几个非功能性需求：

• 占用更小的磁盘空间。
• 更快的查询速度。

2.2. 实现索引的数据结构选型？

2.2.1. 使用哈希表实现索引

通过哈希函数对数据进行计算得到哈希值并存放到哈希表中，如果出现哈希冲突可以通过链表法等方法解决。哈希表进行等值查询的时间复杂度理想情况下为O(1)。

使用哈希表实现的索引，能够满足等值查询的需求，但不能满足范围查询等需求。

哈希索引底层是基于哈希表实现的，能够进行快速的等值查询。

2.2.2. 使用二叉查找树实现索引

二叉查找树中每个节点最多有两个子节点，左子树中节点的值均小于当前节点的值，右子树中节点的值均大于当前节点的值。二叉查找树查找的时间复杂度和树高相关，理想情况下为Olog(n)。

使用二叉查找树实现的索引，能够满足等值查询的需求，但不能满足范围查询等需求，且存在以下几个问题：

• 二叉查找树随着数据的变更可能会变得不平衡，最坏情况下会退化为链表，查找的时间复杂度为O(n)。
• 二叉查找树中每个节点最多有两个子节点，当数据很多时，树会很高，进行查找时需要多次访问磁盘，是磁盘不友好的。

2.2.3. 使用红黑树实现索引

红黑树是一种近似平衡的二叉查找树，在对树中数据进行变更时，会同步维持树的平衡。红黑树查找的时间复杂度和树高相关，为Olog(n)。

使用红黑树实现的索引，解决了二叉查找树不平衡的问题，但仍存在当数据很多时，树会很高，进行查找时需要多次访问磁盘的问题。

2.2.4. 使用B树实现索引

B树是一种多叉树，每个节点有多个子节点，左子树节点的值均小于当前节点的值，右子树节点的值均大于当前节点的值。B树的非叶子节点和叶子节点存储的是整条记录。

使用B树实现的索引，相比于二叉查找树，相同数量的数据有更低的层高，进行查找时需要访问更少次的磁盘，但存在以下几个问题：

• B树不能满足范围查询的需求。
• B树中每个节点存储的是整条记录，所以一个数据页中存储的节点不会很多，当数据很多时，树会很高，进行查找时仍需要多次访问磁盘。

• 可以通过show variables like 'innodb_page_size'命令查看InnoDB存储引擎中数据页的大小。
• 可以通过alter table <table_name> engine = InnoDB命令重建指定表的索引，去除索引碎片，降低索引占用的磁盘空间。

2.2.5. 使用B+树实现索引

和B树类似，B+树也是一种多叉树，每个节点有多个子节点，左子树节点的值均小于当前节点的值，右子树节点的值均大于当前节点的值，叶子节点通过链表连接。对于主键索引来说，B+树的非叶子节点存储的是主键和页号，叶子节点存储的是主键和整条记录；对于二级索引来说，B+树的非叶子节点存储的是索引列和页号，叶子节点存储的是索引列和主键。

使用B+树实现的索引，相比于B树，有更低的层高，进行查找时需要访问更少次的磁盘，通过链表连接叶子节点也可以满足范围查询的需求。InnoDB存储引擎的索引基于B+树实现。

2.3. InnoDB存储引擎的索引和MyISAM存储引擎的索引有什么区别？

InnoDB存储引擎的索引是聚簇索引，索引和数据都存储在索引树上；而MyISAM存储引擎的索引是非聚簇索引，索引和数据分开存储，相当于InnoDB存储引擎中的二级索引。

3. 组合索引

3.1. 什么是组合索引？

组合索引^[2]是指对表中多个列建立一个索引，来加快查询的速度。相比于建立多个单列索引，多个列建立一个组合索引能够节省磁盘空间。使用组合索引进行查询时需要满足最左前缀匹配原则，即查询条件中前面的索引列是等值查询时，后面的索引列才能使用上索引。

3.2. 组合索引失效的场景有哪些？

当查询条件不满足最左前缀匹配时，组合索引会失效。下面以为a，b，c三个列建立组合索引为例：

• 当查询条件为a = 1 and b = 1 and c > 1时：a列，b列，c列能使用索引。
• 当查询条件为a = 1 and b > 1 and c > 1时：a列，b列能使用索引。
• 当查询条件为a = 1 and c = 1时：只有a列能使用索引。
• 当查询条件为a > 1 and b = 1时：只有a列能使用索引。
• 当查询条件为b = 1 and c = 1时：没有列能使用索引。

还有一些通用的索引失效场景，组合索引也会失效，详见下文。

4. 索引优化

4.1. 什么是回表？

回表是指根据非主键列在二级索引树上查找到主键后，再根据主键在主键索引树上查找完整记录的过程。可以使用覆盖索引避免回表，使用索引条件下推减少回表的次数。

如上图所示，为表t建立了普通索引(name)，当执行select * from t where name = 'bar'时，首先会在二级索引树中查询name等于bar的记录，其主键为3；再从主键索引树中查找主键为3的完整记录并返回，这个过程就叫做回表。

4.2. 什么是覆盖索引？

覆盖索引是指二级索引树中包含查询结果中的所有列，无需进行回表，可以加快查询的速度。

如上图所示，为表t建立了组合索引(name, age)，当执行select age from t where name = 'bar'时，会在二级索引树中查询name等于bar的记录，并直接返回记录中age的值，无需回表，这个过程就叫做覆盖索引。

4.3. 什么是索引条件下推？

索引条件下推^[3]（Index Condition Pushdown，ICP，于MySQL5.6版本引入）是指在组合索引中，不能使用索引的索引列可以参与到存储引擎层的查询条件的判断中，用于减少回表的次数，可以加快查询的速度。

如上图所示，为表t建立了组合索引(name, age)，当执行select * from t where name > 'bar' and age > 60时，只有name索引列可以使用索引。

• 如果开启了索引条件下推，则可以在存储引擎层判断age的条件是否满足，如果不满足则无需回表，直接进行下一条记录的判断。
• 如果关闭了索引条件下推，则需要回表在服务层判断age的条件是否满足。

可以使用show variables like 'optimizer_switch'命令查看是否开启了索引条件下推。

4.4. 什么是前缀索引？

前缀索引^[4]是指对字符串字段的前缀进行索引，而非对整个字段进行索引，能够节省磁盘空间。

4.5. 为什么推荐使用递增唯一列作为主键？

InnoDB存储引擎中的索引是基于B+树实现的，当新插入数据时，需要在主键索引相应的数据页上插入该数据，并同步在二级索引相应的数据页上插入数据。

• 如果主键是离散的（如UUID），插入数据时可能会导致页分裂，降低插入的效率。
• 二级索引树的叶子节点存储的是索引列和主键，使用递增唯一列作为主键占用更小的磁盘空间。

4.6. 如何创建合适的索引？

创建合适的索引能够加快查询的速度，反之则会占用磁盘空间以及会降低更新的速度。创建合适的索引有以下几种实践：

• 频繁出现在查询条件中的列以及参与排序和分组的列可以创建索引，以加快查询，排序和分组的速度。
• 频繁出现在查询结果中的列可以创建索引，使用覆盖索引避免回表，以加快查询的速度。
• 出现在连接条件中的列可以创建索引，以提高连接查询的速度。
• 组合索引优于多个单列索引，占用更小的磁盘空间。
• 区分度不高的列不建议创建索引，如性别等。
• 数据量较少的表不建议创建索引。
• 单个表的索引不能过多，以避免降低更新的速度。

• 可以使用show index from <table_name>命令查看指定表中各列的区分度。
• 可以使用analyze table <table_name>命令重新统计指定表中各列的区分度。

4.7. 索引失效有哪些场景？

索引失效有以下几种场景：

• 对索引列进行函数计算，如where age + 1 = 10，where upper(name) = 'FOO'等。
• 对索引列进行隐式函数计算，如 where name = 123等。
• 对索引列使用or，not，!=，like '%...'等查询条件。
• 组合索引的索引列不满足最左前缀匹配原则。
• 优化器基于成本选择了其他索引或全表扫描等。

5. 一条查询语句的执行过程是怎样的？

结合索引来看，一条查询语句的执行过程如下：

• 优化器根据查询条件确定使用的索引。
• 如果使用的是主键索引，则在主键索引树上找到记录并返回。
• 如果使用的是二级索引，则在二级索引树上找到记录的主键，然后回表找到记录并返回。
• 如果没有使用索引，则进行全表扫描。

6. 参考文档