不少的书或博客,在介绍InnoDB引擎索引原理的时候,都会给出如下类似的两幅图(比如参考博客2和3):
由图可知,主键索引和辅助索引(二级索引)分别是一棵B-树和B+树。其中主键索引的非叶子节点只存储主键信息,只有叶子节点会存储完整的数据行记录。整个数据表就是按照主键索引的大小顺序存储的,因而主键索引又叫聚簇索引。而对于辅助索引,非叶子节点只存储辅助索引对应的索引字段,而叶子节点的data字段存储主键索引的值。所以当我们需要根据辅助索引查找行记录时,需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。
我们知道,当往表中插入新数据时,主键索引和辅助索引文件都会发生调整,以保证索引的顺序性。那我们考虑这样一个场景:当我们连续地插入两条辅助索引值相同,但主键值不同的两条数据记录时,辅助索引会怎么排列这两条记录的顺序呢?比如我再插入一条记录(17,"Alice", 30),那在辅助索引这幅图中,(Alice,17)这个节点最终是会在(Alice,18)这个节点的左边还是右边呢?
为了验证这个问题,我们看下面这样一个示例:
先创建一张如下的测试表:
CREATE TABLE `test` (
`a` int(20) NOT NULL,
`b` int(20) NOT NULL,
`c` int(20) NOT NULL,
PRIMARY KEY (`a`,`b`),
KEY `c` (`c`)
) ENGINE=InnoDB;
插入以下数据:
insert into test values(1,1,2),(3,2,1),(2,2,1),(2,1,1),(3,3,1);
执行以下查询操作:
select * from test where c >= 1;
返回的结果如下:
+---+---+---+
| a | b | c |
+---+---+---+
| 2 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 2 | 1 |
| 3 | 3 | 1 |
| 1 | 1 | 2 |
+---+---+---+
5 rows in set (0.00 sec)
可以看到,尽管插入的时候不管从辅助索引角度看,还是从主键索引角度看,插入的记录都是乱序的。但当我们按照辅助索引查询时,查询的结果是先按按辅助索引从小到大排序,辅助索引值相同时则是按主键索引从小到大排序。那InnoDB是如何做到这一点的呢?这就涉及到本文要讲的辅助索引的索引扩展特性。
在MySQL官网有这么一段话:
InnoDB automatically extends each secondary index by appending the primary key columns to it.
CREATE TABLE t1 (
i1 INT NOT NULL DEFAULT 0,
i2 INT NOT NULL DEFAULT 0,
d DATE DEFAULT NULL,
PRIMARY KEY (i1, i2),
INDEX k_d (d)
) ENGINE = InnoDB;
This table defines the primary key on columns (i1, i2). It also defines a secondary index k_d on column (d), but internally InnoDB extends this index and treats it as columns (d, i1, i2).
Now consider this query:
EXPLAIN SELECT COUNT(*) FROM t1 WHERE i1 = 3 AND d = '2000-01-01'
When the optimizer takes index extensions into account, it treats k_d as (d, i1, i2). In this case, it can use the leftmost index prefix (d, i1)to produce a better execution plan:
mysql> EXPLAIN SELECT COUNT(*) FROM t1 WHERE i1 = 3 AND d = '2000-01-01'\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: t1
type: ref
possible_keys: PRIMARY,k_d
key: k_d
key_len: 8
ref: const,const
rows: 1
Extra: Using index
也就是说,我们定义的辅助索引会被InnoDB引擎给自动扩展成由”辅助索引字段“+”主键索引字段“构成的完整索引。当我们执行的查询语句的where条件中同时包含辅助索引字段和主键索引字段时,扩展索引可以发挥作用,而不用回表查询。
其实看到这里我比较好奇的是,扩展之后,辅助索引的非叶子节点会不会和叶子节点一样,同时存储了辅助索和主键索引的值?这很重要,因为这关系到上面右图的正确性。从参考博客4、5、6、7来看,感觉辅助索引的非叶子节点和叶子节点一样,同时存储了辅助索引值和主键索引值。尤其是博客6在MySQL官网给出的t1表的基础上建立了一张对比表:
CREATE TABLE `tt1` (
`i1` int(11) NOT NULL DEFAULT '0',
`i2` int(11) NOT NULL DEFAULT '0',
`d` date DEFAULT NULL,
PRIMARY KEY (`i1`,`i2`),
KEY `k_d` (`d`,`i1`,`i2`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin;
对比表中直接建立了一个包含(d, i1, i2)的索引,在两张表中插入同样内容的数据之后,发现两张表的索引大小完全一样。但到这里我又困惑了:如果辅助索引的非叶子节点和叶子节点存储的数据完全一样,那叶子节点存在的意义又是什么呢?百思不得其解。
其实换个角度想,不管InnoDB是否做索引扩展,上面右图的存储结构都能满足其功能要求。具体来说就是,上面右图的存储方式保证了辅助索引先按照辅助索引字段进行排序,当辅助索引字段相同时按主键索引排序。这样的保证对于被扩展索引所覆盖的查询同样不需要回表。而从存储空间利用率的角度考虑,非叶子节点不存储主键索引值会带来较大的存储空间利用率的提升。
参考博客: