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. 一条查询语句的执行过程是怎样的?
结合索引来看,一条查询语句的执行过程如下:
- 优化器根据查询条件确定使用的索引。
- 如果使用的是主键索引,则在主键索引树上找到记录并返回。
- 如果使用的是二级索引,则在二级索引树上找到记录的主键,然后回表找到记录并返回。
- 如果没有使用索引,则进行全表扫描。