前言：

重温磁盘

认识索引

为什么这么做，怎么做

重谈page

聚簇索引VS非聚簇索引

回表查询

索引分类

前言：

前文我们主要是介绍了MySQL的一些基本操作，增删查改一类的操作都介绍了，并且因为大多数情况下，查询的频率远远高于其他操作，所以我们在查询上面，也是花费了一番功夫的。

那么本文，我们来介绍查询背后的机制——索引，大多数同学第一次接触到索引的时候，第一感觉肯定是：索引？我们C语言平常学习的索引吗？类似于数组下标一类的？实则不然，在MySQL的索引大有不同。

我们在平时构建算法的时候，影响效率的不止有算法本身，实际上还有对数据的组织方式，比如同样是增删查改，对于顺序表和堆来说，二者对于这四个操作的效率肯定大不相同。那么我们在优化算法的时候，就可以着手于对数据的组织方式进行优化。索引的存在就是优化数据的组织方式的。

所以，索引既然是优化的数据的组织方式的，那么，索引不就是数据结构吗？

重温磁盘

对于MySQL来说，我们有着和Linux中“万物皆文件”的一样的概念，即“一切皆表”，也就是说我们认为MySQL的所有数据都是一张一张的表构成的，不管是我们创建的，还是查询等操作产生的中间表，我们认为都是表。

即便我们从文件的角度来看，每次当我们创建了表之后，我们在MySQL的目录也能看到对应的文件生成：

类似于这个，目前我的MySQL版本是8.0的，如果有的同学的MySQL版本是5.7，那么还会看到生成了对应的表结构定义文件.frm，但是不幸的是.frm文件在8.0之后已经被弃用了，原因大致如下：

问题	解释
一致性差	`.frm` 是单文件，容易与 `.ibd` 不一致
不支持事务	表结构变更不具备事务能力
不支持原子性	DDL 操作不可回滚
无法跨平台	`.frm` 二进制结构与平台、版本强耦合
不利于统一管理	数据、索引、结构分散在多个文件中

好了，现在我们有一个认识：MySQL中不管是创建数据库，还是创建表，都在会实际的文件系统中创建真实的目录和文件。

那么不就意味着，当我们在MySQL创建表的时候，是要和磁盘等外设打交道的，既然是要和磁盘等外设打交道，那么就要考虑IO的问题了，但是我们同时都知道的，根据冯诺依曼结构体系，处于应用层的MySQL是不能直接和硬盘打交道的，能和硬盘等外设打交道的只有OS，所以问题从MySQL如何和磁盘打交道转变为了MySQL如果通过OS，间接的和磁盘打交道。

那么我们这个小标题，要解决的问题是OS如何和磁盘打交道的。

基本的磁盘长什么样我们都知道，由多个盘片摞在一起，并且每个面都有一个磁头，一个盘片我们可以分出磁道，扇区等单位出来，磁道是一个一个的同心圆，多个磁道构成一个盘面，每个磁道被划分为一个一个的区域段，这个区域段我们就称为扇区。

那么有了磁头Heads，柱面Cylinder（等价于磁道），扇区（Sector），我们就能精准的找到磁盘中的某一个区域，这种磁盘数据定位方式叫做CHS，但是我们要知道，这是早期做法，因为它的数量有严格的限制，最多8.4GB左右，所以现在OS早已通过LBA，即Logical Block Addressing 这种逻辑寻址方式进行寻址。不过在早期的时候，磁盘控制器要求只能通过CHS进行访问，所以早期的时候是有LBA向CHS进行转换的，不过在当今的时代，基本上已经抛弃了CHS的做法。

但是我们清楚的时候，在第一次介绍文件系统的时候，我们清楚的知道OS和硬盘的数据交互一次性是4KB，也就是说如果我们只是修改一个字节，OS也要在磁盘中给你找到这1字节周围的4KB数据，然后再修改，这实际上用到了局部性原理，为了提高效率的。

现在我们就清楚了OS和磁盘打交道的基本单位是4KB，那么疑问来了，MySQL通过OS和磁盘打交道的基本单位是多少呢？

答案是：16KB。也就是说MySQL作为应用层服务来说，要交互一次数据，至少都是16KB起步，那么当交互的时候，OS怎么搬来的16KB数据MySQL不管，它只管要就可以了。那么我们如何验证MySQL交互数据的基本单位是16KB呢？我们可以通过命令show global status like 'innode_page_size'进行查看：

可以看到确实是16KB。

所以我们可以将MySQL和磁盘交互数据的时候应该是这样的：

其中的buffer pool是MySQL自己申请的缓冲区，相当于TCP中read也有自己的缓冲区一样。

那么我们从这里得出结论：MySQL通过OS和磁盘交互的基本数据单位是16KB。

认识索引

前文我们花费些许功夫，通过磁盘的CHS，引出了操作系统的LBA，并且结合了OS与磁盘的基本交互是4KB，引出了MySQL和磁盘的交互单位是16KB，但是实际上，事实远远没有这么简单。那么16KB为什么不简单我们后面介绍。

对于索引，是通过改变数据的组织方式然后提高MySQL的效率的，所以它的本质，其实就是数据结构，那么我们来理解MySQL的索引是如何工作的。

首先我们建立一张表，这里我们最好加上主键约束：

注意我们不是按照id的大小插入数据的，我们是随机插入的，但是当我们一查看数据的时候，我们发现：

它默认为我们进行了排序。

那么从这个现象，我们引出两个问题：这个操作是谁做的，为什么要这么做？重谈16KB。

为什么这么做，怎么做

先给结论：MySQL自己做的，这么做的目的是为了方便引出目录。

对于数据库来说，它的基本数据单位16KB都是要管理起来的，在源码中，它的基本管理方式是使用链表，就像这样：

那么现在，我们清楚每个16KB里面有数据，还有前后指针，并且在应用层是通过双向链表管理起来的，还发现每个16KB，被称呼为page。

对于每个page来说，它里面有大量的数据，不同的page链接在一起，但是这样的数据组织方式是双向链表，数据查找的时候，仍然是线性的，可以说在大量数据的时候，这种模式下MySQL会一个一个遍历的每个page，按照顺序遍历，找到了直接返回即可。

这不就是一个一个的查嘛？那么时间复杂度就是O(N)，这个N在实际的数据中，可能是几百万，可能是几亿，那你让如此脆弱的MySQL完成这么个操作，那它一天啥事也不用干了，光崩溃就可以了。

所以这里，我们引入了目录：

首先在每个page里面，引入一个目录：比如一号目录映射到了1，二号目录映射到了3，那么我要查2号数据的时候，通过目录1，找到了1号数据，然后往下走一步，就是2号数据了。这个过程的思想就是通过目录，一次性干掉大部分数据。通过目录，能一次性筛选掉其他目录的所有的指向数据，这个操作实际上就是我们平时读书的时候，查阅目录的方式是一样的。

但是这种操作实际上并不能很好解决问题，它的本质还是线性遍历的，因为你要使用目录，但是前置条件是你能遍历到目录的那个page，这不还是链表的遍历吗？

所以在page内已有目录的基础之上，我们的解决思路也是简单的，我们给page也指定目录，也就是说在数据有目录的基础之上，我们对不同的page，也指定上目录，图大致是这样的：

这样，就能通过第一层目录，快速定位到对应数据的page的附近，然后遍历到page再次通过目录，快速定位到数据的附近，运气好可以直接命中，这效率提高的就非常多了。

那么现在就可以回答刚才的问题了：MySQL为什么要自己排序？因为目录指代的顺序不能错乱了，错乱了目录无法正确定位。

现在还可以回答一个问题，为什么要使用主键约束？不使用可以吗？

答案是可以，如果我们不使用主键，也没有唯一键和Not null的列，InnoDB 会自动生成一个隐藏的6字节的row id作为主键，并建立聚簇索引。

所以实际上的page的组织结构就是这样的，反正遍历某个目录的时候，如果太花时间了，再来一个目录就行，而如果我们仔细一看这个结构，不就是传说中的B+树吗！！所以得出结论，存储引擎innnodb采取的索引方式是B+树。那么其他结构为什么不行，比如hash，它不支持范围查找，因为查找它需要映射，比如红黑树，红黑树和AVL树都是近似平衡或者绝对平衡，这就意味着每一层都会有节点，也就是说它很高，而B+树是矮胖的，层高越低，和系统磁盘交互的次数就很少，所以红黑树也pass，至于二叉平衡树就不用说了。

特性 / 数据结构	B+树	红黑树	AVL树	Hash
是否支持范围查询	✅ 是，效率高（叶子节点有序且链表连接）	❌ 不直接支持（需中序遍历）	❌ 不直接支持	❌ 不支持
节点扇出（分支数量）	高（每页存多个key）	低（每节点2个子节点）	低	N/A
树高度（影响IO次数）	矮（logₘN）	较高（log₂N）	更高（比红黑树高）	无树结构
适合数据规模	大数据量、磁盘存储	小数据量、内存结构	小数据量、内存结构	精确查询、大数据量
插入/删除性能	中等，代价为平衡和分裂	快速，近似平衡	较慢（频繁旋转）	快（无排序要求）
是否顺序存储	✅ 叶子节点有序、链表相连	❌ 否	❌ 否	❌ 否
磁盘友好性	✅ 高，每个节点可对应一个磁盘页	❌ 差，节点少无法利用页空间	❌ 差	❌ 差
典型应用场景	数据库索引（如 InnoDB）	操作系统调度/平衡集合	编译器语法树等	缓存（如 Redis）、哈希索引

重谈page

前文我们提及，MySQL的Innodb是通过page这个基本单位来和磁盘进行交互的，那么在如果构建索引的部分，我们发现这个基本单位里面有前后指针，有目录结构，有各种数据，那么交互的单位真的单纯只是一个内存块的话，是不太能执行这样的操作，所以对于16KB，我们仍然是：先描述再组织。

即对于每个page都要存入相关信息，然后在buffer pool里面对它们进行一个管理，buffer pool就是MySQL的存储引擎Innodb的缓冲区，我们也可以在MySQL的配置文件里看到，如果有的时候没看到也不代表它没有，MySQL有对应的默认行为的。

那么重归到Page里面，我们可以非常非常粗略地认为page是这样的：

struct InnoDBPage {byte file_header[38];       // 文件头byte page_header[56];       // 页头信息Record infimum;             // 最小记录Record supremum;            // 最大记录Record user_records[];      // 用户插入的数据记录byte free_space[];          // 空闲空间byte page_directory[];      // 槽指针（指向记录）byte file_trailer[8];       // 文件尾部校验InnoDBPage* next;InnoDBpage* prev;
};

所以MySQL中的索引，实际上是某个存储引擎，基于某种特定的组织方式进行的数据排列而已。

聚簇索引VS非聚簇索引

根据上文的描述，我们很明显能够发现Innodb的索引的数据本身都是放在最后一层的，目录都是在其他层，这种数据本身和目录放在统一结构的索引，我们称为聚簇索引，对于MyIsam来说，它同样使用的是B+树作为索引，但是它和Innodb不同的是它的叶节点存储的是数据记录的地址，

也就是说MyIsam的叶结构指向的是数据的地址，那么它的数据本身没有和目录放在一起，所以哦我们称呼这种索引为非聚簇索引。

回表查询

对于主键索引来说，我们发现一个点就是，索引好像只有主键才有？那么我们查其他字段怎么办？能不能给其他列建立一个辅助索引？

当然是可以的，我们可以通过命令create index index_name on table_name(对应列名）来创建对应的辅助索引，就像这样：

然后我们就可以通过show index from test_3查看对应的索引信息了：

在 InnoDB 中，如果我们通过辅助索引（二级索引）来查询数据，且查询的字段不在辅助索引中，就会发生“回表操作”。
假设有三个列：A（主键）、B、C，其中我们对 C 建了索引，A 是主键。
当我们执行 SELECT B FROM test_table WHERE C = 'xxx' 这个语句时：

MySQL 会先通过 idx_C（C 列上的辅助索引）定位满足条件的记录的主键 A；
再通过主键 A 回到聚簇索引中查找完整的数据行，拿到 B 的值。

因为在 InnoDB 中，辅助索引结构只包含：被索引的列 + 主键列，不包含其它字段，所以我们必须“回表”才能拿到未包含的字段（如 B）。

优点	缺点
利用辅助索引快速定位主键	回表需要额外查询，性能下降
辅助索引占用空间小	增加查询的 I/O 操作
支持多种查询条件	查询字段不在索引中时必须回表

我们前文提及了索引的作用就是为了减少系统的IO次数，那么，回表无疑增加了IO次数，所以我们可以通过覆盖索引解决回表查询的缺点：

CREATE TABLE test (id INT PRIMARY KEY,name VARCHAR(50),age INT,email VARCHAR(100),INDEX idx_name_age (name, age)
);

SELECT name, age FROM test WHERE name = 'Tom';

即我们让查询的数据都在一起，不去主键索引里面找就可以了。那么针对于辅助索引来说Innodb是不会所有的叶子节点额外加数据的，因为太浪费空间了。

不过如果使用了覆盖索引，我们查询的时候会看到两个索引，但是实际上是一个：

索引分类

索引分为主键索引，唯一键索引，普通索引，全文索引。其中普通索引我们已经通过回表查询简单的介绍了，其实普通索引有多种创建方式分别是：

create table user8(id int primary key,name varchar(20),email varchar(30),index(name) --在表的定义最后，指定某列为索引
);

create table user9(
id int primary key,
name varchar(20),
email varchar(30));
alter table user9 add index(name); --创建完表以后指定某列为普通索引

create table user10(
id int primary key,
name varchar(20),  
email varchar(30));-- 创建一个索引名为 idx_name 的索引    
create index idx_name on user10(name);

这种方式都可以成功创建一个辅助索引。

而对于主键索引和唯一键索引我们可以理解为：创建主键索引和唯一键索引实际上是创建主键和唯一键，不管是哪种方式，创建表的时候就指定了主键或者创建完之后新增主键，Innodb都会创建对应的索引。

不过实际上唯一键索引它就是辅助索引，不过多了唯一性约束而已。

类型	是否唯一	是否聚簇	自动建索引	特点
主键（PRIMARY）	✅ 是	✅ 是	✅ 是	一张表只能有一个，行按主键排序存储
唯一键（UNIQUE）	✅ 是	❌ 否	✅ 是	可有多个，索引中也包含主键列作为引用
普通索引（INDEX）	❌ 否	❌ 否	手动创建	可有多个，用于优化查询