MySQL 索引的数据结构

时间：12-14来源：作者：点击数：

如果只有之前讲的数据页，虽然在页内可以实现根据主键快速定位记录，但我们可以看到在有很多页的情况下还是只能遍历。所以我们需要更强大的方式来定位数据。

索引的数据结构是一个 B+ 树，在非叶子节点上的目录项页，页中的每条目录项记录都存储了一个主键值和页号，这个主键值就是页号对应的页中的最小的主键值。在叶子节点上，则存储了完整的用户记录页。

上边介绍的，在叶子节点里存放完整的用户记录的索引，其实就是聚簇索引，也就是根据主键值进行排序的索引，并且在叶子节点存放了完整的用户记录。InnoDB存储引擎会自动的为我们创建聚簇索引。另外，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。

而我们还可以为一张表创建其他列的索引，叫做二级索引，特点是排序使用的条件就不是主键，而是指定的列（先按列的值排序，一样的情况下再用主键值排序），非叶子节点上存储的就是列值、主键值和页号，叶子节点上存储的不是完整的用户记录，而是只有列值和对应的主键值。

所以为了根据指定列的条件定位到用户记录，需要先根据这个二级索引的B+树定位到主键值，再根据主键值去聚簇索引上找到完整的用户记录，这个过程也叫做回表

我们也可以为一张表创建联合索引，本质上也是二级索引。比如我们为两个列c2和c3创建了联合索引(idx_c2_c3)，那么在索引B+树上排序的规则就是先根据c2列的值排序，相同的情况下再根据c3列的值排序。非叶子节点上记录的是c2列和c3列的值以及页号，叶子节点上存储的是c2和c3列的值以及主键值。

简单提一下 MyISAM 的索引方式，MyISAM 的索引和数据是分开存储的，叶子节点中存放的只有主键值和行号，之后根据行号再去快速定位到用户记录，因此 MyISAM 中建立的索引相当于全都是二级索引。

了解了索引的原理之后我们能看出来几件事情：

索引的代价

可以看出，索引虽然好用，但不能想建就建，还是有代价的，一个是空间上的代价，每个二级索引都需要一颗B+树去存储，第二是时间上的代价，创建更新和删除记录的时候索引的B+树也需要同步修改，性能自然也会受到影响。

联合索引的生效条件

最左匹配原则

字符串匹配

如果是为字符串类型的列创建的索引，在指定条件进行查询的时候，只有精确匹配或者前缀匹配的情况下才能使用到索引。因为字符串的大小比较是按照字符顺序逐个往后比较的。比如 select * from users where name like 'li%'可以用到name列的索引，但select * from users where name like '%li%'就无法使用name列的索引

排序和分组使用索引会更快

Order by 和 Group by 后面的列，如果不使用索引，那么就需要先回表读取到记录之后，再在内存或者磁盘中进行排序或分组（Filesort，文件排序），这样就意味着很慢。

回表的代价

什么是回表上面已经说过了。在根据主键id去聚簇索引上查找完整的用户记录时，由于这些主键id很大概率不是相连的，而在聚簇索引中记录是根据主键id值排列的，所以根据这些并不连续的id值到聚簇索引中访问完整的用户记录可能分布在不同的数据页中，这样读取完整的用户记录可能要访问更多的数据页，这种读取方式我们也可以称为随机I/O。一般情况下，顺序I/O比随机I/O的性能高很多。

当要回表的记录很多时，会造成大量的随机I/O，严重影响性能。因此，这种情况下，最好使用覆盖索引，即需要查询的列只包含索引列，比如我们有一个idx_name_age的联合索引，那么最好使用select name, age from users where ...，这样就避免了回表。