关于InnoDB索引的底层实现和实际效果

一、索引底层实现

MySQL有多种存储引擎的实现，

SHOW ENGINES;

其中，InnoDB和MyISAM存储引擎应用最普遍，

默认是InnoDB，唯独InnoDB支持事务。是否支持事务，这也是任凭系统瓶颈往往就在数据库，以及任凭各种高性能非关系数据库应用得如何广泛，而关系数据库始终占有重要地位的因素。

不管是RDBMS还是NoSQL，都是为了查取数据，伴随着数据量越来越大，查询压力也越来越大，所以多种RDBMS和NoSQL都有索引，来保障快速查到数据。

索引的本质就是一种数据结构，InnoDB的索引有两种实现，B+树以及hash表。hash表便于快速定位到一条数据，前提是hash冲突少，而B+树的适用场景更广泛，支持包括部分模糊匹配的各种范围查询。

这里主要讨论InnoDB中B+树结构的索引。

1.1、局部性原理

最原始，每插入一条数据就放进一个链表里，并要根据主键排序，查询一条数据的办法就是逐条查找匹配，每一次匹配就是一次磁盘IO，当数据越来越多，查询效率就很低。为了减少IO次数，可以借用操作系统中页的概念，每次查询可以多返回一些数据到内存，而且访问某些数据通常也会访问它附近的数据，所以都包含进一个页里，一次性IO读取。这就是局部性原理。

页可以认为是一次IO的最小单位，操作系统一般4kB，arm64已经支持8kB、16kB。

getconf PAGE_SIZE

查询MySQL默认的页大小，

SHOW GLOBAL STATUS LIKE 'Innodb_page_size';  --16384

InnoDB将所有记录存储在一个固定大小的单元中，该单元通常称为“页面”（尽管 InnoDB有时将其称为“块”）。这也是为什么查看数据表和索引的数据长度大小，都是16kB的整数倍。

接着，借鉴字典前面的目录，试图对这一大批数据分组（比如根据主键），这样每次查询先用二分法等匹配目录中的位置，然后再定位到具体某一组查询，效率更高。

当一个页面的数据已经塞满了，需要开辟新一页，页面越来越多，也要维持数据的有序性，所以页面之间要有前后指针便于关联，为了进一步提升查询效率，可以使用B树将这些数据页串起来。

MySQL中页的属性：https://dev.mysql.com/doc/internals/en/innodb-fil-header.html

1.2、B树和B+树

随着数据量的进一步增长，需要对B树优化为B+树，B+树相比B树：

• B树所有节点都保存数据，B+树只有叶子节点保存数据，非叶子节点只保存索引字段值。所以同一个节点的占用空间内，B+树的非叶子节点可以存放更多索引信息，使树的高度更低，意味着IO次数更少，查询效率更高。
• B+树的叶子节点是有序的，支持直接遍历叶子节点进行范围查询。

B+树的磁盘IO次数更少，更适合用作基于磁盘的存储系统。

更多数据结构和算法演示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

这样一路推演得来B+树的索引，同时也是一个基于主键的聚簇索引，所以InnoDB表必须要有主键，否则没办法将数据用B+树串起来。若未主动创建主键，InnoDB内部也会自动加一个rowId作为隐藏的主键。而且主动创建主键最好保持自增或具有单调性，一方面便于索引排序比对，另一方面插入新数据时对索引结构的影响最小。

二、索引实际效果

2.0、准备数据

MySQL5.7.21，建一张表并初始化数据，

CREATE TABLE `t` (
  `a` int(10) NOT NULL,
  `b` int(10) DEFAULT NULL,
  `c` int(10) DEFAULT NULL,
  `d` int(10) DEFAULT NULL,
  `e` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
INSERT INTO t VALUES(4,1,1,1,'d');
INSERT INTO t VALUES(1,1,1,1,'a');
INSERT INTO t VALUES(8,8,8,8,'h');
INSERT INTO t VALUES(2,2,2,2,'b');
INSERT INTO t VALUES(5,2,3,5,'e');
INSERT INTO t VALUES(3,3,2,2,'c');
INSERT INTO t VALUES(7,4,5,5,'g');
INSERT INTO t VALUES(6,6,4,4,'f');

全查数据，

SELECT * FROM t;

全表扫描，对主键索引的叶子节点逐个扫描，时间复杂度O(n)。执行计划explain的type=ALL。

type效率：ALL<index<range<ref<eq_ref<const<system。

SELECT * FROM t WHERE a=4;

避免了全表扫描，explain的type=const，possible_keys=PRIMARY（估算走主键索引），key=PRIMARY（用到了主键索引，实际是从上到下走主键索引树，缩小了查询范围），时间复杂度O(logn)。

2.1、联合索引和最左前缀匹配

前面是针对InnoDB的主键索引（聚簇索引），除了主键索引还有辅助索引（即非主键索引，也是非聚簇索引，包含唯一索引、普通索引、联合索引、全文索引），叶子节点存的数据只是主键，不需要冗余其他字段值，其他字段值去回表查主键索引树。比如对b、c、d三列加联合索引，

create index idx_bcd on t(b, c, d);

联合索引就是把三个字段值按顺序拼在一起作为整体，在B+树里进行排序放置。一般要使联合索引生效就要遵循最左前缀匹配原则。

2.2、全表扫描一定比使用索引慢？

select * from t where b>1;

这条sql是符合最左前缀匹配规则的，推测执行计划会用到索引，explain一下，

possible_keys=idx_bcd，执行计划推测可能用到联合索引，但实际查询中，会做优化，不用索引，type=ALL进行了全表扫描，但效率比用到联合索引要高（因为select *所以需要回表再查主键索引树），IO次数更少，因为全表总共就8条数据，而且b字段值大于1的占绝大部分，意味着全表扫描后再进行过滤就很高效，filtered=75代表最终返回的记录数和总共扫描的记录数rows=8的百分比，数字越大越好，表示索引生效或本次查询扫描的匹配性很高，所以直接去主键索引树遍历叶子节点就够了。

所以，全表扫描不一定比使用到索引慢，而且key也不一定是possible_keys的子集。

而改查询条件b>1为b>5，就又用到了联合索引，

select * from t where b>5;

type=range，possible_keys=key=idx_bcd，用到了联合索引树。

所以执行计划内部往往会根据实际情况做查询优化的调整。

2.3、覆盖索引和回表查询

继续上面where b>1，这次不去select *，只select b/c/d，就会用到联合索引，不必回表查主键索引树。

select b from t where b>1;

Extra=Using index，覆盖索引生效，在索引树中就可以查到所需数据，避免了回表扫描主键索引的表数据文件。这种一般性能不错。

去掉where条件，全查联合索引上已有的b/c/d字段值，

select b,c from t;

possible_keys=NULL，推测不用索引；type=index，key=idx_bcd，实际用到了联合索引，只需要遍历这个覆盖索引即可，不用遍历主键索引树。

这个案例也证明了key不一定是possible_keys的子集。

MySQL内部访问数据，很多时候都会认为覆盖索引的效率比主键索引高。所以有时候默认排序都优先用覆盖索引而不是主键：主键索引排序失效。

2.4、排序order by和using filesort

不满足最左前缀匹配规则，所以用不到索引，

SELECT * FROM t ORDER BY b,d;

排序order by若用不到索引，就会type=ALL全表扫描，Using filesort额外在文件内存中排序，因为本身具有排序的B+树索引都用不到。

order by的Using filesort的逻辑：

• 开辟sort buffer排序内存空间，show variables like 'sort_buffer_size'；
• 将需要的字段都放进去，select *一般就是所有，select b的话会自动把d也放进去，因为虽然不查d但是要用d排序；
• 快速排序。

Using filesort当内存不够时可能会用临时文件排序，都是一回事。

另外Extra还有个Using temporary，代表查询有使用临时表，一般出现于排序、分组和多表join，查询效率不高，建议优化。

Using filesort和Using temporary一般都建议对排序字段加索引。

若是order by a，a是主键，已有索引中的顺序，就用不到filesort，也就不需要上面那三步了。order by b,c,d也一样不会filesort。

2.5、MySQL8之前只支持索引ASC升序

上面是针对MySQL5.7，给表t加了联合索引idx_bcd，如果对b/c/d三列排序时是有降序的，因为实际场景中往往有很多的查询是根据某个业务时间字段降序排的。

SELECT b,c,d FROM t ORDER BY b ASC,c DESC,d DESC;

那就需要改变之前的索引idx_bcd，因为在创建索引时未指定升降序，就是默认ASC升序的，

那么要支持c/d字段降序的联合索引，可以删掉旧索引idx_bcd，

drop index idx_bcd on t;

再重建一个新顺序的联合索引，

create index idx_bcd on t(b asc, c desc, d desc);

但是再去explain，

Using index和type=index只是因为只需要用到idx_bcd这一个联合索引就够了，毕竟不需要回表查别的字段

Using filesort还是证明了联合索引在排序中未生效，再去查看表的索引，发现Collation还都是A。

这是因为在MySQL5.7中只是语法上支持创建自定义顺序的索引，但实际上总是用默认的升序。所以升级到实际支持的MySQL8再试试，

可以看到Collation已经支持降序D了，再explain一下，

已经没有Using filesort了。

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。