Mysql InnoDB索引原理

2018-10-14 本文已影响47人 ZackJiang

Mysql InnoDB索引原理

理解Mysql索引的原理和数据结构有助于我们更好的使用索引以及进行SQL优化，索引是在存储引擎层面实现的，所以不同的引擎实现的索引也有一定的区别，但是在生产环境中，我们最常用的就是InnoDB引擎和B树索引，OK，那本文要讨论的重点也同样是InnoDB引擎下的B树索引。

我们建立一个表来进行测试，表的DDL如下所示，我们要关注的是表t_book上的主键索引id和name author publish_date三列组成的索引test_index。

CREATE TABLE `t_book` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(50) NOT NULL,
  `author` varchar(50) NOT NULL,
  `publish_date` date NOT NULL,
  PRIMARY KEY (`id`),
  KEY `test_index` (`name`,`author`,`publish_date`)
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8;

B树数据结构

Mysql中的B树索引是使用B+树实现的，关于B+树的数据结构个人认为美团点评技术博客中Mysql索引原理及慢查询优化一文中介绍的非常详实，B+树的数据结构如下图所示。

btree.jpg

图中浅蓝色块即磁盘块，根节点磁盘块中存储17和35两个数据，其中指针P1指向小于17的数据，指针P2指向大于17小于35的数据，指针P3指向大于35的数据。显然通过B+树索引查询数据与B+树的高度有关，如上图的B+树索引查找一个叶子节点的数据只需要三次磁盘IO，对于Mysql来说三层的B+树可以索引上百万的数据，这对于查询效率的提升是巨大的。

总结起来Mysql中B树索引有以下关键特点：

真实数据存储在叶子节点上，例如根节点的磁盘块中17和35并不是真实数据
B树索引中的值是按顺序存储的，这一方面说明可以利用B树索引可以用于完成ORDER BY排序操作，当SQL可以使用索引排序时，EXPLAIN查看查询计划EXTRA列是不会出现USING FILESORT的（USING FILESORT为文件排序）；另一方面，这也解释了Mysql索引的最左前缀匹配原则。
Mysql在上图所示的B+树数据结构的基础上，为每一个叶子节点增加了指向下一个叶子节点的指针，用于方便叶子节点的范围遍历。

如果对以上介绍的特点有疑问，可以直接往下看，我们将在聚簇索引和二级索引的介绍中举例说明以上特点的原理。

Mysql中的B树索引有两种数据存储形式，一种为聚簇索引，一种为二级索引。

聚簇索引

InnoDB一般会使用表的主键来作为聚簇索引，如果一个表没有主键（不建议这么玩）InnoDB会选用一个唯一非空索引来代替，如果没有这样的索引，InnoDB会隐式建立一个聚簇索引。聚簇的含义即是数据行和相邻的键值紧凑的存储在一起，占据一块连续的磁盘空间，因此通过聚簇索引访问数据可以有效减少随机IO，通常使用聚簇索引查找比非聚簇索引查找速度更快。以我们建立的表t_book为例，聚簇索引即为自增主键id，其B树索引数据结构可以用下图来表示。

聚簇索引.jpg

聚簇索引有以下关键特点：

在InnoDB中聚簇索引即为表的存储结构，表的其他列数据也会存储到叶子节点中，从聚簇索引中获取数据比二级索引获取数据要快。
聚簇索引是按顺序存储的，因此Insert速度严重依赖于插入顺序，如果在聚簇索引的中间一行插入数据，会导致后面行都会被移动，可能面临页分裂的问题。所以，在插入频繁的表中不建议使用varchar类型的列作为主键，如果真的有这种情况，建议为表增加一个自增主键作为代理键，哪怕这个自增主键没有任何意义（最好避免不连续且值的范围分布很大的聚簇索引）。
由于把相关数据保存在连续的硬盘空间上，所以通过聚簇索引聚集数据只需要一次磁盘IO，可以有效加快查询速度。

图中仅画了叶子节点和和其父亲节点，第一个表格存储了id为1~10的数据，第二个表存储了id为11
~20的数据，注意，P1即为上文中提到的指向下一个叶子节点的指针。

二级索引

InnoDB的B树索引中除了聚簇索引，就都是二级索引了，二级索引的含义是索引的叶子节点除了存储了索引值，还存储了主键id，在使用二级索引进行查询时，查找到二级索引B树上的叶子节点后还需要去聚簇索引上去查询真实数据，但是这里有一种特殊情况，即查询所需的所有字段在二级索引中都可以获取，此时就不需要再去回表查数据了，这种情况就是索引覆盖（EXPLAIN中EXTRA列中会出现USING INDEX，本文只关注索引结构，不详细讨论索引覆盖等技术的使用，如果深入理解索引的数据结构，索引覆盖等技术也没有那么神秘）。

在我们的测试表t_book中，test_index即为二级索引，由于我们把除了主键id所有的列都作为一个联合索引，所以在这个表上的查询都可以使用索引覆盖技术，但是具体生产环境中也不建议总是采用这种做法，索引列的增加也会增大插入更新数据时的索引更新成本，具体的优化要视具体情况决策。t_book上的二级索引test_index的索引结构由下图表示。

二级索引.jpg

通过以上结构，我们可以推断出二级索引的以下关键特点：

InnoDB二级索引中存储主键值，当发生行移动时，不影响二级索引的维护工作
通过以上的索引结构我们现在可以非常清晰的理解B树索引的最左前缀匹配原则，例如，如果匹配以Book为后缀的书名，InnoDB引擎需要全量扫描索引test_index才能找到匹配的记录（EXPLAIN中Type列为Index，实际仍然是全表扫描），但是如果要搜索以Book为前缀的记录，则会直接命中索引找到查找的记录
另外特别特别特别重要的是，可以通过这个结构图可以理解索引的列前缀匹配原则，我们无法通过这个二级索引树去直接命中搜索作者为Brian Goetz的记录，同样，当我们搜索书名为Thinking in Java，作者名字为B开头的名字，出版时间为2008-3（好吧，这个例子不太合理，假如我们有N本书的书名叫Thinking in Java且作者名字都是B开头的），那我们可以使用二级索引的name和author字段，但是在查询出的N条记录中无法再使用索引中publish_date字段，即Where子句中如果使用了范围条件，后面的字段就无法再使用索引了，当然我们也不能跳过任何一个字段去使用索引（只用name和publish_date字段去搜索）。

索引覆盖：