初识MySQL · 索引

前言：

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

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

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

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

重温磁盘

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

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

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

好了，现在我们有一个认识：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，至于二叉平衡树就不用说了。

重谈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' 这个语句时：

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

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

我们前文提及了索引的作用就是为了减少系统的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都会创建对应的索引。

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

删除索引的操作有三种，一种是直接删除对应的主键，唯一键等。一种是alter table tablename drop index indexname.一种是drop index name on tablename。

对于全文索引这里不做讨论。