【MySQL 进阶之路】索引概述

第06章_索引

1.什么是索引

索引是存储引擎用于快速找到数据记录的一种数据结构，就好比一本教科书的目录部分，通过目录中找到对应文章的页码，便可快速定位到需要的文章。MySQL中也是一样的道理，进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条一条地查找记录，直到找到与条件符合的记录。

当数据库中没有索引时，数据会随机存储在硬盘的不同位置。具体来说，假设我们要查找 Col 2 = 89 的记录，如果没有索引，数据库引擎必须从第一行开始逐行读取并比较 Col 2 的值。例如，从 Col 2 = 34 开始，发现不匹配，继续读取下一行，直到找到 Col 2 = 89 的记录。对于一个包含上千万条记录的大表，这种线性扫描的方式意味着需要进行数百万次的磁盘I/O操作，在这个过程中，最耗时的部分是磁盘I/O操作，因此在没有索引的情况下，查询性能会受到严重影响。

假如给数据使用 二叉树 这样的数据结构进行存储，如下图所示

对字段 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的次数，加快查询速率。

2. 索引及其优缺点

2.1 索引概述

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

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

索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。同时，存储引擎可以定义每个表的 最大索引数和 最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。

2.2 优点

（1）高数据检索的效率，降低 数据库的IO成本 。通过创建唯一索引，可以保证数据库表中每一行 数据的唯一性 。

（2）在实现数据的 参考完整性方面，可以 加速表和表之间的连接 。换句话说，对于有依赖关系的子表和父表联合查询时， 可以提高查询速度。

（3）在使用分组和排序子句进行数据查询时，可以显著 减少查询中分组和排序的时间 ，降低了CPU的消耗。

2.3 缺点

（1）创建索引和维护索引要 耗费时间 ，并 且随着数据量的增加，所耗费的时间也会增加。

（2）索引需要占 磁盘空间 ，除了数据表占数据空间之 外，每一个索引还要占一定的物理空间， 存储在磁盘上 ，如果有大量的索引，索引文件就可能比数据文 件更快达到最大文件尺寸。

（3）虽然索引大大提高了查询速度，同时却会 降低更新表的速度 。当对表 中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。

3.B+Tree的理解（InnoDB）

B+Tree 概念图

一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层， 之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页 最多存放3条记录 ，存放目录项 记录的页 最多存放4条记录 。

一般情况下，我们用到的 B+树都不会超过4层 ，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的 Page Directory （页目录），所以在页面内也可以通过 二分法 实现快速 定位记录。

B+树的形成和运行：B+树的形成是自底向上的，即从叶子节点开始，随着数据的插入和分裂，逐渐向上形成内部节点和根节点。而在运行过程中，查找数据是自顶向下的，从根节点开始，根据键值范围逐层向下查找，直到找到目标数据所在的叶子节点。

3.1 索引图解

新建一个表：

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

这个新建的 index_demo 表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键， 这个表使用 Compact 行格式来实际存储记录的。这里我们简化了index_demo表的行格式示意图：

record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记 录、 3 表示最大记录、。
各个列的值 ：这里只记录在 index_demo 表中的三个列，分别是 c1 、 c2 和 c3 。

3.2 常见索引的概念

聚簇索引（Clustered Index）

• 定义：聚簇索引决定了表中数据的物理存储顺序。也就是说，数据的实际存储顺序会按照索引的顺序进行组织。每个表只能有一个聚簇索引，因为数据只能有一个存储顺序。
• 主键与聚簇索引：通常情况下，数据库会自动将表的主键（PRIMARY KEY）作为聚簇索引。如果你没有显式地定义聚簇索引，那么数据库会选一个唯一且非空的列作为聚簇索引。注意，如果你指定了一个非主键的列作为聚簇索引，主键会变成一个二级索引。

在InnoDB中，聚簇索引的每个叶子节点存储了完整的数据记录。目录项（非叶子节点）包含了指向叶子节点的指针和最小主键值，用于引导查找过程。聚簇索引的叶子节点是双向链表，这使得在叶子节点内可以进行高效的数据遍历。

目录项记录 和普通的 用户记录 的不同点：

• 目录项记录 的 record_type 值是1，而 普通用户记录 的 record_type 值是0。
• 目录项记录只有 主键值和页的编号 两个列，而普通的用户记录的列是用户自己定义的，可能包含 很多列 ，另外还有InnoDB自己添加的隐藏列。

相同点：两者用的是一样的数据页，都会为主键值生成 Page Directory （页目录），从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。

问题：如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？

回答：

那就为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子。

如图，我们生成了一个存储更高级目录项的 页33 ，这个页中的两条记录分别代表页30和页32，如果用 户记录的主键值在 [1, 320) 之间，则到页30中查找更详细的目录项记录，如果主键值 不小于320 的 话，就到页32中查找更详细的目录项记录。

二级索引（Secondary Index）

• 定义：二级索引是指除了聚簇索引之外，基于表中的其他列（非主键列）建立的索引。 二级索引的目录项和聚簇索引类似，包含了指向叶子节点的指针和最小索引值。因此，二级索引实际上间接指向了表中的数据行。

分析一下！

1. 叶子节点的内容：
   • 在二级索引的B+树中，叶子节点存储的并不是完整的用户记录，而是C2列+主键这两个列的值。这意味着叶子节点不包含除索引列和主键之外的其他列值。
2. 目录项记录的结构：
   • 目录项记录中不再是主键+页号的搭配，而是C2列+页号的搭配。这意味着在非叶子节点中，每个目录项记录存储的是索引列的值和指向下一个目录项或叶子节点的页号。
3. 记录的完整性：
   • 在二级索引的B+树中，所有记录都不包括主键之外的其他列值。这意味着在叶子节点中，每个记录只包含索引列的值和主键值，而不包含完整的用户记录。

二级索引的B+树结构与聚簇索引的B+树的区别，主要体现在叶子节点的内容、目录项记录的结构和记录的完整性上。 二级索引的叶子节点只包含索引列的值和指向主键的指针，而不包含完整的用户记录。

回表概念

我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，如果我们想根 据c2列的值查找到完整的用户记录的话，仍然需要到 聚簇索引 中再查一遍，这个过程称为 回表 。也就是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树！

问题：为什么我们还需要一次 回表 操作呢？直接把完整的用户记录放到叶子节点不OK吗？

回答：

如果把完整的用户记录放到叶子结点是可以不用回表。但是太占地方了，相当于每建立一课B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。

因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引，或者辅助索引。由于使用的是c2列的大小作为B+树的排序规则，所以我们也称这个B+树为c2列简历的索引。

非聚簇索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个非聚簇索引。

小结：聚簇索引与非聚簇索引的原理不同，在使用上也有一些区别：

1. 聚簇索引的叶子节点存储的就是我们的数据记录, 非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序。
2. 一个表只能有一个聚簇索引，因为只能有一种排序存储的方式，但可以有多个非聚簇索引，也就是多个索引目录提供数据检索。
3. 使用聚簇索引的时候，数据的查询效率高，但如果对数据进行插入，删除，更新等操作，效率会比非聚簇索引低。