聚集索引

我们先建如下的一张表

CREATE TABLE `student` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '学号',
  `name` varchar(10) NOT NULL COMMENT '学生姓名',
  `age` int(11) NOT NULL COMMENT '学生年龄',
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`)
) ENGINE=InnoDB;

插入如下sql

insert into student (`name`, `age`) value('a', 10);
insert into student (`name`, `age`) value('c', 12);
insert into student (`name`, `age`) value('b', 9);
insert into student (`name`, `age`) value('d', 15);
insert into student (`name`, `age`) value('h', 17);
insert into student (`name`, `age`) value('l', 13);
insert into student (`name`, `age`) value('k', 12);
insert into student (`name`, `age`) value('x', 9);

数据如下

mysql是按照页来存储数据的，每个页的大小为16k。

在MySQL中可以通过执行如下语句，看到一个页的大小

show global status like 'innodb_page_size'

结果为16384，即16kb

在InnoDB存储引擎中，是以主键为索引来组织数据的。记录在页中按照主键从小到大的顺序以单链表的形式连接在一起。

可能有小伙伴会问，如果建表的时候，没有指定主键呢？

如果在创建表时没有显示的定义主键，则InnoDB存储引擎会按如下方式选择或创建主键。

1. 首先判断表中是否有非空的唯一索引，如果有，则该列即为主键。如果有多个非空唯一索引时，InnoDB存储引擎将选择建表时第一个定义的非空唯一索引作为主键
2. 如果不符合上述条件，InnoDB存储引擎自动创建一个6字节大小的指针作为索引

页和页之间以双链表的形式连接在一起。并且下一个数据页中用户记录的主键值必须大于上一个数据页中用户记录的主键值

假设一个页只能存放3条数据，则数据存储结构如下。

可以看到我们想查询一个数据或者插入一条数据的时候，需要从最开始的页开始，依次遍历每个页的链表，效率并不高。

我们可以给这页做一个目录，保存主键和页号的映射关系，根据二分法就能快速找到数据所在的页。但这样做的前提是这个映射关系需要保存到连续的空间，如数组。如果这样做会有如下几个问题

1. 随着数据的增多，目录所需要的连续空间越来越大，并不现实
2. 当有一个页的数据全被删除了，则相应的目录项也要删除，它后面的目录项都要向前移动，成本太高

我们可以把目录数据放在和用户数据类似的结构中，如下所示。目录项有2个列，主键和页号。

数据很多时，一个目录项肯定很多，毕竟一个页的大小为16k，我们可以对数据建立多个目录项目，在目录项的基础上再建目录项，如下图所示

图片来自《MySQL 是怎样运行的：从根儿上理解 MySQL》
这其实就是一颗B+树，也是一个聚集索引，即数据和索引在一块。叶子节点保存所有的列值

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。《MySQL实战45讲》

非聚集索引

非聚集索引叶子节点的值为索引列+主键

当我们查询name为h的用户信息时（学号，姓名，年龄），因为name上建了索引，先从name非聚集索引上，找到对应的主键id，然后根据主键id从聚集索引上找到对应的记录。

从非聚集索引上找到对应的主键值然后到聚集索引上查找对应记录的过程为回表

联合索引/索引覆盖

假设teacher表定义如下，在name和age列上建立联合索引

CREATE TABLE `teacher` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '教师编号',
  `name` varchar(10) NOT NULL COMMENT '教师姓名',
  `age` int(11) NOT NULL COMMENT '教师年龄',
  `ismale` tinyint(3) NOT NULL COMMENT '是否男性',
  PRIMARY KEY (`id`),
  KEY `idx_name_age` (`name`, `age`)
) ENGINE=InnoDB;

插入如下sql

insert into teacher (`name`, `age`, `ismale`) value('aa', 10, 1);
insert into teacher (`name`, `age`, `ismale`) value('dd', 12, 0);
insert into teacher (`name`, `age`, `ismale`) value('cb', 9, 1);
insert into teacher (`name`, `age`, `ismale`) value('cb', 15, 1);
insert into teacher (`name`, `age`, `ismale`) value('bc', 17, 0);
insert into teacher (`name`, `age`, `ismale`) value('bb', 15, 1);
insert into teacher (`name`, `age`, `ismale`) value('dd', 15, 1);
insert into teacher (`name`, `age`, `ismale`) value('dd', 12, 0);

对name和age列建立联合索引

目录页由name列，age列，页号这三部分组成。目录会先按照name列进行排序，当name列相同的时候才对age列进行排序。

数据页由name列，age列，主键值这三部分组成。同样的，数据页会先按照name列进行排序，当name列相同的时候才对age列进行排序。

当执行如下语句的时候，会有回表的过程

select * from student where name = 'aa';

当执行如下语句的时候，没有回表的过程

select name, age from student where name = 'aa';

为什么不需要回表呢？
因为idx_name_age索引的叶子节点存的值为主键值，name值和age值，所以从idx_name_age索引上就能获取到所需要的列值，不需要回表，即索引覆盖

索引下推

当执行如下语句的时候

select * from student where name like '张%' and age = 10 and ismale = 1;

在5.6版本之前的执行过程如下，先从idx_name_age索引上找到对应的主键值，然后回表找到对应的行，判断其他字段的值是否满足条件

在5.6引入了索引下推优化，可以在遍历索引的过程中，对索引中包含的字段做判断，直接过滤掉不满足条件的数据，减少回表次数，如下图

参考博客
《MySQL 是怎样运行的：从根儿上理解 MySQL》
图示算法
[0]https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[1]https://blog.csdn.net/qq_35190492/article/details/106915564
[2]https://blog.csdn.net/qq_35571554/article/details/82759668
联合索引
[3]https://www.cnblogs.com/rjzheng/p/12557314.html
原文链接：https://blog.csdn.net/zzti_erlie/article/details/110501008