MySQL系列索引原理详解

MySQL索引概念详解

本文基于InnoDB存储引擎来介绍索引的相关知识

一、前置知识

在学习索引前需要提前了解的知识

1、页

1）概念
页是InnoDB存储数据记录的基本单位，也是数据库IO操作的最小单位，页的大小默认是16KB，一个页中存放了多条数据记录。

InnoDB将数据划分为若干个页存放到磁盘上，并且以页作为磁盘和内存之间交互的基本单位，也就是说一次IO操作最少会从磁盘中读取16KB的内容到内存中，一次最少会把内存中的16KB内容刷新到磁盘中。从使用角度来说，在InnoDB引擎环境下，不论是读取一行还是多行记录，都是将这些数据记录所在的页进行加载

2）分类
页按类型划分，常见的有 数据页（保存B+树节点）、系统表、Undo 页 和 事物数据页 等。数据页是我们最常使用的页。

2、区

区是比页大一级的存储结构，在InnoDB中，一个区内会分配64个连续的页，因此一个区的大小是64*16KB=1MB。

3、段

段是由至少一个区组成的，在段中不要求区与区之间连续。

段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。 当我们创建数据表、索引的时候，就会相应创建对应的段，比如创建一张表时会创建一个表段，创建一个索引时会创建一个索引段。

4、表空间

表空间只是一个逻辑容器，表空间存储的是一个或者多个段，一个段只能属于某一个表空间。

数据库由一个活多个表空间组成的，表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等。

二、为什么使用索引

索引是存储引擎用来提高数据查询效率的一种数据结构，就好比我们在图书馆查阅资料，先有一些终端机器提供目录导航，然后通过目录导航快速定位到需要的资料所在的书架，最后在书架上根据编号找到自己需要的书籍。

在MySQL数据库中也是类似的道理。假设在表中查询某条记录时，如果查询条件命中了索引，则可以根据索引实现快速查找。如果没有命中索引，则需要进行全表扫描，按行查找，直到找到符合查询条件的记录为止。

如上图所示，数据表在没有建立任何索引数据结构时，表记录在硬盘上的存放位置是随机的，摆臂需要前后摆动位置进行查询，这样非常消耗时间。假设表记录是按顺序存储的，也需要一行一行查找。假设需要查找col1=6的记录，也需要从col1=1开始查找，直到找到col1=6，这样也需要6次IO操作。如果表里有上千万条记录，最差情况要进行上千万次IO操作，这样是非常耗费时间的。

我们把数据行的数据存储结构改为二叉树结构，如下图所示：

如上图所示，假设我们需要查找col2=89的记录，遍历二叉树，先找到col=34的记录，发现要查找的目标记录比34大，就向右边继续查找，这样我们就能以更少的查询次数来找到需要的数据了。

对字段 Col 2 添加了索引，就相当于在硬盘上为 Col 2 维护了一个索引的数据结构，即这个 二叉搜索树。二叉搜索树的每个结点存储的是 (K, V) 结构，key 是 Col 2，value 是该 key 所在行的文件指针（地址）。比如：该二叉搜索树的根节点就是：(34, 0x07)。现在对 Col 2 添加了索引，这时再去查找 Col 2 = 89 这条记录的时候会先去查找该二叉搜索树（二叉树的遍历查找）。读 34 到内存，89 > 34; 继续右侧数据，读 89 到内存，89==89；找到数据返回。找到之后就根据当前结点的 value 快速定位到要查找的记录对应的地址。我们可以发现，只需要 查找两次 就可以定位到记录的地址，查询速度就提高了。

这就是我们为什么要建索引，目的就是为了 减少磁盘I/O的次数，加快查询速率。

三、索引简介

官方定义：索引（Index）是帮助MySQL高效获取数据的数据结构。

MySQL进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条一条地查找记录，直到找到与条件符合的记录。

索引的本质是一种特定的数据结构。我们可以简单把它理解为“排好序的快速查找数据结构”，满足特定查找算法。 这些数据结构以某种方式指向数据， 这样我们可以在这些数据结构的基础上实现各种查找算法提高数据查询效率。

索引是由底层存储引擎中提供实现的，具体实现方式和引擎本身有关系，每种存储引擎支持的索引不一定完全相同，存储引擎也可以定义每个表的最大索引数和最大索引长度。

四、索引的优缺点

索引的本质：索引是数据结构。可以简单理解为“排好序的快速查找数据结构”，如上一节提到的二叉搜索树，满足特定查找算法(如二分查找法)。 这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现 高级查找算法 。

1、优点

1）减少磁盘的IO次数，提高查找效率，这是索引的核心优势
2）通过创建唯一索引，可以保证表中每行数据记录的唯一性
3）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的消耗。

2、缺点

1）占用磁盘空间：创建索引需要占据存储空间，如果表中数据量巨大，索引数量多，索引文件可能比数据本身的文件会更快到达硬件限制。
2）降低表数据更新速度：增删改数据场景，索引会影响更新效率，因为在增删改数据时，不仅要修改数据本身，而且要对数据关联的索引进行重建，会影响更新表的整体速度

所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。

索引并不是越多越好，我们要根据具体业务场景合理创建索引，当我们更新超大表数据时，最好的办法是先删除表中的索引，然后插入数据，插入成功后重建索引

五、索引的演变

索引是由存储引擎来实现的，每个存储引擎对索引的实现方式存在差异。 这里以InnoDB为例，来谈一谈索引是如何演变的。

1、未建立索引的情况

先来看一个精确匹配的例子：

SELECT [fieldA,fieldB] FROM 表名 WHERE fieldA = xxx; 

在一个页中进行查找

假设目前表中数据量比较少，都存放在一个数据页中，在查询时按字段类型可以分为两种：

如果检索字段fieldA是主键： 可以在页目录中使用 二分法 快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定记录。

如果检索字段fieldA不是主键： 因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从 最小记录 开始 依次遍历单链表中的每条记录， 然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。

在多个页中进行查找

如果数据量比较大，一个页已经存储不下，则会分成多个页存储到硬盘上，多个页组成了一个双向链表。在多个页面中查找数据会分成两个步骤：

a. 从第一个页沿着双向链表 一直往下找，直到定位到记录所在的页。

b. 从所在的页内中根据查找相应的记录。查找方式和前面【在一个页中进行查找】的方式一样。

在没有建立索引的情况下，不论是根据主键列或者其他列的值进行查找，我们并不能快速的定位到记录所在的页，这种方式显然是 非常耗时 的。如果一个表有十亿条记录呢？此时 索引 闪亮登场！

2、索引的诞生

先创建一个测试表index_demo：

CREATE TABLE index_demo(
 c1 INT,
 c2 INT,
 c3 CHAR(1),
 PRIMARY KEY(c1)
 ) ROW_FORMAT = Compact;

这里我们新建了一个表index_demo，表中包含了两个int类型的字段c1、c2和一个char类型的字段c3，其中字段c1是主键索引， 这个表使用 Compact 行格式来实际存储记录的， 采用Compact格式存储的记录数据结构简化如下：

• record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记 录、 3 表示最大记录、 1 暂时还没用过，下面讲。
• next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头指向下一个地址。
• 各个列的值 ：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。
• 其他信息 ：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

将记录格式示意图的其他信息项暂时去掉并把它竖起来，然后加入到数据页中存放，示意图如下：

然后我们再来执行查询语句：

SELECT [fieldA,fieldB] FROM 表名 WHERE fieldA = xxx; 

执行上述查询语句会遍历所有的数据页，因为各个页中的记录并没有规律，我们并不知道我们的查询条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。

所以如果我们 想快速的定位到需要查找的记录在哪些数据页 中该咋办呢？我们可以为快速定位记录所在的数据页而建立一个目录 ，建这个目录必须符合下面的两条前置规则：

1）下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

假设：每个数据结构最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。

INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');

那么这些记录会在数据页中按照主键值的大小串联成一个单向链表，如图所示：

从图中可以看出来， index_demo 表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入一条记录

INSERT INTO index_demo VALUES(4, 4, 'a');

由于默认一个数据页只能放3条记录，现在插入的记录已经放不下了，需要再建立一个数据页：

注意：新分配的 数据页编号不保证连续。页与页之间通过维护者上一个页和下一个页的编号而建立了 链表 关系。

页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5>4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，
所以在插入主键值为4的记录的时候需要把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程其实就是面试常问到的页分裂，示意图如下：

2）给所有的数据页建立一个页目录，每个数据页就是页目录中的一个目录项

由于数据页的 编号不保证连续 的，所以在向 index_demo 表中插入许多条记录后，可能是这样的效果：

我们需要给它们做个 目录，每个页对应一个目录项，每个目录项包括下边两个部分：

1）页的用户记录中最小的主键值，我们用 key 来表示。

2）页号，我们用 page_on 表示。

如上图所示，目录项1中的key就是代表数据页10中的记录的最小主键id，而page_no就代表这个目录项指向的数据页码了。其他目录项以此类推，多个目录项又可以组成一个双向链表。

利用上述结构，我们就可以根据主键值快速查找到数据了，比如：查找主键值为 20 的记录，具体查找过程分两步：
1）先在目录项中根据二分法搜索，`12大于20大于209，因此先确定范围在目录项3中。
2）根据步骤1得到目录项3对应的数据页码是9，去数据页9中再根据前边说的在页中查找记录的方式定位具体的记录。

至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为 索引！

3、InnoDB中的索引结构

InnoDB中的索引结构也分为三种情况：

1）多个目录项组成一个目录页
数据少的情况，将前面提到的目录项放到一个页面中组成一个目录页

2）多个目录项组成多个目录页

当数据增长时，若原先存储目录项的页的容量已满（我们前边假设每个目录页只能存储4条目录项记录），则需要创建一个新的目录页来存放新的目录项

3）目录项记录页组成的目录页
如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？那就为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

上面的索引结构的抽象模型其实就是下面的结构：

上面这个图其实就是B+树的原型。

B+树的特点：

• 节点可以分有N层
  最底层的每个叶子节点都是存放用户数据记录的，也就是前面提到的数据页，这一层是第1层，基于这层之上的都叫做目录页，再往上的层就是目录项组成的目录页，大目录套小目录，理论上可以无限套娃(N层)。

B+树能存放的数据量预估：
在我们的真实生产环境中，一个数据页(叶子节点)能存放的记录条数限制是非常大的，我们假设单个数据页最多能存放100条数据记录，每个存放目录项记录的节点最多能存放1000条目录项记录，那么：

• 如果B+树只有1层，也就是只有一个用于存放数据记录的节点(数据页)，最多能存储100条数据记录。
• 如果B+树有2层，第1层叶子节点是存放数据记录的，第二层是目录项组成的目录页，最多能存放1000*100=100000条记录
• 如果B+树有3层，第1层叶子节点存放数据记录，第二层是目录项目组成的目录页，第3层是目录项组成的目录页再组成的目录项的目录页(这里有点绕，想想套娃的概念..)，最多能存放10001000100=10000,0000条记录
• 如果B+树有4层，则最多能存放100010001000*100=1000,0000,0000条记录
• 如果B+树有N层，则能存放1000^(n-1)*100条记录

从上述推算可以得出，随着B+树的层次越深，能存储的记录数量是指数型增长！

一个B+树只需要很少的层级就可以轻松存储数亿条记录，查询速度相当不错！这是因为B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录，直到最后访问到存储真实数据的目录。

其实一般情况下，数据库索引对应的B+树都不会超过4层，因此我们通过主键值去查找某条数据记录最多只需要做4个页面内的查找(3个目录项页和一个数据记录)。

六、索引的常见面试问题

1、索引的分类

从 功能逻辑 上说，索引主要有 4 种，分别是普通索引、唯一索引、主键索引、全文索引、空间索引。

按照 物理实现方式 ，索引可以分为 2 种：聚簇索引和非聚簇索引。

按照 作用字段个数 进行划分，分成单列索引和联合索引。

普通索引：
这类索引可以创建在任何数据类型中，其值是否唯一和非空，是由字段本身的完整性约束条件决定。

普通索引只是用于提高查询效率，例如在表user的字段user_name上建立一个普通索引，查询记录时就可以根据该索引进行查询。

语法：

（1）alter table 表名 add index 索引名称(列名);
（2）create index 索引名称 on 表名(列名);

唯一索引：
使用UNIQUE参数可以设置索引为唯一索引，在创建唯一索引时，限制了该索引的值在表中必须是全局唯一的，可以有空值，在一张表中允许同时建立多个唯一索引

语法：

（1）alter table 表名 add unique index 索引名称(列名);
（2）create unique index 索引名称 on 表名(列名);

主键索引：primary key

主键索引也是一种特殊的唯一索引，在唯一索引的基础上增加了不允许为空的约束，也就是说主键索引的约束条件是UNIQUE+NOT NULL，一张表中最多只能有一个主键索引。

将某个字段设定为primarykey 主键后，数据库自动建立主键索引，InnoDB中的主键索引也是聚簇索引。

语法：

#建表时，主键默认为索引
create table user(
    id varchar(11) primary key,
    name varchar(20),
    age int
)

全文索引：
全文索引（也称为全文检索）是目前搜索引擎使用的关键技术。主要是利用【分词技术】等多种算法智能分析出文本中关键词的频率和重要性，然后按照一定的算法规则智能地筛选出我们想要的搜索结果。 全文索引非常适合大型数据集，对于小的数据集，它的用处不大。

使用参数FULLTEXT（MySQL5.6.4之前，只有MYISAM存储引擎引擎支持全文索引）可以设置索引为全文索引。
全文索 在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。全文索引只能在CHAR、VARCHAR或TEXT类型及其系列类型的字段 上创建。，查询数据量较大的字符串类型的字段时，使用全文索引可以提高查询速度。

例如，表user的字段remark是TEXT类型，该字段包含了很多文字信息，在该字段上建立全文索引后，可以显著提高查询该字段的速度。

随着各种大数据技术的出现，关系型数据库应对全文索引的需求已力不从心，逐渐被solr、ElasticSearch等专业的搜索引擎组件所替代了。

空间索引：
使用参数SPATIAL可以设置索引为空间索引。空间索引只能建立在空间数据类型上。

MySQL的空间数据类型有GEOMETRY、POINT、LINESTRING和POLYGON等，目前只有MyISAM存储引擎支持空间索引，对于初学者来说，这类索引基本很少会用到。

多列索引：
一个索引可以包含多个列，多个列共同构成一个多列索引。 多列索引也被称为复合索引。

语法：

//复合索引
create index name_age_index on user(name,age);

满足复合索引的查询的两大原则：
1.最左前缀原则
2.动态调整顺序原则：当条件中的字段全部达到复合索引中的字段时，MySQL引擎可以动态调整字段顺序，使其满足最前左缀原则

2、聚簇索引和非聚簇索引的区别

索引按照物理实现方式，分为了聚簇(聚集)索引和非聚簇(非聚集)索引，非聚簇索引又被称为二级索引或者辅助索引。

1）聚簇索引
叶子节点上存储了完整的数据记录(完整的数据记录是指存储了单条记录中所有列的值)，通过主键找到了索引也就找到了数据(索引即数据，数据即索引)。

特点：

• 单个数据页内的记录是按照主键大小顺序链接成一个单向链表
• 每个数据页之间是根据页内数据记录的主键大小顺序排成一个双向链表
• 存放目录项记录的目录项页分为不同的层次，同一层中的不同目录项页也是根据页内目录项记录的主键大小顺序排成一个双向链表

优点

• 数据访问快：由于数据和索引在一起存放，从聚簇索引中获取数据比非聚簇索引更快。
• 对于主键的排序查找和范围查找速度非常快

缺点

• 插入速度严重依赖插入顺序： 对于使用InnoDB作为存储引擎的表，我们一般都定义一个自增ID列作为主键，因为按照主键的顺序插入是最快的方式，否则将容易出现页分列(记录重新移动)
• 更新主键代价非常高：更新主键会导致页分裂现象，因此对于InnoDB表，我们定义主键为不可更新
• 二级索引访问需要两次索引查找：第一次根据二级索引定位到主键值，第二次根据主键值找到行的完整数据。

聚簇索引并不需要开发者在MYSQL语句中使用INDEX语句去创建，nneDB会自动为我们创建好聚簇索引

2）非聚簇索引

非聚簇索引也被称为二级索引、辅助索引。

很多业务场景中，我们需要根据非主键列进行数据的检索，此时又不能一行一行全表查一遍，因为这样性能极差！

因此数据库的研发者想出了一种办法：多建立几棵B+树，其中只有一颗B+树是用主键建立的，这颗树的叶子节点包含了主键索引和完整的数据记录。其他的B+树的叶子节点存放的是对应的非主键列+主键值

例如用户表user中有两个字段id和user_name，id是主键列，user_name是非主键列，此时我们需要根据user_name检索数据：select id，user_name from user;
为了提高查询效率，可以针对user_name这一列建立非聚簇索引（构建一颗B+树），该树的叶子节点存放的是user_name以及对应记录中的主键ID值，然后先查找该B+树，找到对应的主键ID，最后根据主键ID去聚簇索引的B+树中再次查询从而获取完整的数据记录（这就是回表的概念，根据user_name列的值查询一条完整的用户记录需要使用到 2 棵B+树！）

上面提到了回表的概念，此时面试官刨根问底：为啥还需要一次回表的操作呢？直接把完整的数据记录存放到user_name的索引对应的叶子节点中不行吗？

回答：

如果把完整的数据记录放到user_name索引对应的叶子结点是可以不用回表。但是太浪费空间了，相当于每建立一棵B+树都需要把所有的数据记录再都复制存储一份，这有点浪费存储空间。

正因为这种类型的索引需要查找2棵B+树才可以得到最终的查询结果，因此被称为二级索引！

一张表中可以有多个非聚簇索引，但是只能有一个聚簇索引：

3）联合索引
我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按 照 c2和c3列 的大小进行排序，这个包含两层含义：

• 先把各个记录和页按照c2列进行排序。
• 在记录的c2列相同的情况下，采用c3列进行排序

为c2和c3建立的索引的示意图如下：

联合索引 本质上也是一个二级索引。如上图建立的联合索引与分别为c2和c3列分别建立索引的含义是不同的，不同点如下：

• 建立 联合索引 只会建立如上图一样的1棵B+树。

• 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。

3、B+树的形成过程

1）每当为某个表创建一个B+树索引（聚簇索引不是人为创建的，默认就有）的时候，都会为这个索引创建一个 根结点 页面。最开始表中没有数据的时候，每个B+树索引对应的 根结点 中即没有用户记录，也没有目录项记录。
2）随后向表中插入用户记录时，先把用户记录存储到这个根节点 中。
3）当根节点中的可用 空间用完时 继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如 页a 中，然后对这个新页进行 页分裂 的操作，得到另一个新页，比如页b 。这时新插入的记录根据键值（也就是聚簇索引中的主键值，二级索引中对应的索引列的值）的大小就会被分配到 页a 或者 页b 中，而 根节点 便升级为存储目录项记录的页。

七、参考资料

《尚硅谷MySQL入门到高级-宋红康版-高级篇》