MySQL索引详解

索引是一种用于快速查询和检索数据的数据结构，其本质可以看成是一种排序好的数据结构。

文章共6,292字 · 阅读需要大约21分钟

一键AI生成摘要，助你高效阅读

问答

北~笙

3618人浏览 · 2023-06-10 22:53:31

北~笙 · 2023-06-10 22:53:31 发布

1.什么是mysql索引？

索引是一种用于快速查询和检索数据的数据结构，其本质可以看成是一种排序好的数据结构。

索引的作用就相当于书的目录。打个比方: 我们在查字典的时候，如果没有目录，那我们就只能一页一页的去找我们需要查的那个字，速度很慢。如果有目录了，我们只需要先去目录里查找字的位置，然后直接翻到那一页就行了。

索引底层数据结构存在很多种类型，常见的索引结构有: B 树， B+树和 Hash、红黑树。在 MySQL 中，无论是 Innodb 还是 MyIsam，都使用了 B+树作为索引结构。

1.1 索引原理

索引的存储原理大致可以概括为一句话：以空间换时间。

一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往是存储在磁盘上的文件中的（可能存储在单独的索引文件中，也可能和数据一起存储在数据文件中）。

数据库在未添加索引进行查询的时候默认是进行全文搜索，也就是说有多少数据就进行多少次查询，然后找到相应的数据就把它们放到结果集中，直到全文扫描完毕。

1.2 索引的优缺点

优点：

大大提高数据查询速度。
可以提高数据检索的效率，降低数据库的IO成本，类似于书的目录。
通过索引列对数据进行排序，降低数据的排序成本降低了CPU的消耗。
被索引的列会自动进行排序，包括【单例索引】和【组合索引】，只是组合索引的排序需要复杂一些。
如果按照索引列的顺序进行排序，对order by语句来说，效率就会提高很多。

缺点：

索引会占据磁盘空间。
索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改查操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件。
维护索引需要消耗数据库资源。

但是，使用索引一定能提高查询性能吗?

大多数情况下，索引查询都是比全表扫描要快的。但是如果数据库的数据量不大，那么使用索引也不一定能够带来很大提升。

1.3 索引的分类

主键索引：primary key

设定为主键后，数据库自动建立索引，InnoDB为聚簇索引，主键索引列值不能为空（Null）。

唯一索引：

索引列的值必须唯一，但允许有空值（Null），但只允许有一个空值（Null）。

复合索引：

一个索引可以包含多个列，多个列共同构成一个复合索引。

全文索引：

Full Text（MySQL5.7之前，只有MYISAM存储引擎引擎支持全文索引）。
全文索引类型为FULLTEXT，在定义索引的列上支持值的全文查找允许在这些索引列中插入重复值和空值。全文索引可以在Char、VarChar 上创建。

空间索引：

MySQL在5.7之后的版本支持了空间索引，而且支持OpenGIS几何数据模型，MySQL在空间索引这方年遵循OpenGIS几何数据模型规则。

前缀索引：

在文本类型为char、varchar、text类列上创建索引时，可以指定索引列的长度，但是数值类型不能指定。

1.4 创建索引的基本操作

创建主键索引：

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

#查看user表中的索引
show index from user;

创建单列索引：

#创建单列索引，只能包含一个字段
create index name_index on user(name);

创建唯一索引：

#创建唯一索引，只能有一个列
create unique index age_index on user(age);

创建复合索引：

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

满足复合索引的查询的两大原则：
假如创建的复合索引为三个字段，按顺序分别是(name,age,sex)
在查询时能利用复合索引的查询条件如下：

1、最左前缀原则(如下四种都满足条件)

select * from user where name = ? 
select * from user where name = ? and age = ?
select * from user where name = ? and sex = ?
select * from user where name = ? and age = ? and sex = ?

2、如下是不满足最前左缀的条件（但是不是全部都不生效，如下第2原则解释）

select * from user where name = ? and sex = ? and age = ?
select * from user where age = ? and sex = ? and name = ?
select * from user where sex = ? and age = ? and name = ?
select * from user where age = ? and sex = ?
…………等等

3、MySQL 引擎在执行查询时，为了更好地利用索引，在查询过程中会动态调整查询字段的顺序！(也就是说，当条件中的字段全部达到复合索引中的字段时，可以动态调整字段顺序，使其满足最前左缀)

#可以使用复合索引：索引中包含的字段数都有，只是顺序不正确，在执行的时候可以动态调整为最前左缀
select * from user where sex = ? and age = ? and name = ?
select * from user where age = ? and sex = ? and name = ?

#不可以使用复合索引：因为缺少字段，并且顺序不正确
select * from user where sex = ? and age = ? 
select * from user where age = ? and name = ?
select * from user where age = ?
select * from user where sex = ?

2.索引的数据结构

索引数据结构部分借鉴敖丙哥文章：一文搞懂MySQL索引所有知识点（建议收藏）_敖丙的博客-CSDN博客

MySQL索引使用的数据结构主要有BTree索引和hash索引。

对于hash索引来说，底层的数据结构就是哈希表，因此在绝大多数需求为单条记录查询的时候，可以选择哈希索引，查询性能最快；其余大部分场景建议选择BTree索引。

2.1 Hash 表

哈希表是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。

为何能够通过 key 快速取出 value 呢？ 原因在于 哈希算法。通过哈希算法，我们可以快速找到 key 对应的 index，找到了 index 也就找到了对应的 value。

但是！哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。

为了减少 Hash 冲突的发生，一个好的哈希函数应该“均匀地”将数据分布在整个可能的哈希值集合中。

既然哈希表这么快，为什么 MySQL 没有使用其作为索引的数据结构呢？ 主要是因为 Hash 索引不支持顺序和范围查询。假如我们要对表中的数据进行排序或者进行范围查询，那 Hash 索引可就不行了。并且，每次 IO 只能取一个。

试想一种情况:

SELECT * FROM tb1 WHERE id < 500;

在这种范围查询中，优势非常大，直接遍历比 500 小的叶子节点就够了。而 Hash 索引是根据 hash 算法来定位的，难不成还要把 1 - 499 的数据，每个都进行一次 hash 计算来定位吗?这就是 Hash 最大的缺点了。

2.2 二叉查找树(BST)

二叉查找树（Binary Search Tree）是一种基于二叉树的数据结构，它具有以下特点：

左子树所有节点的值均小于根节点的值。
右子树所有节点的值均大于根节点的值。
左右子树也分别为二叉查找树。

当二叉查找树是平衡的时候，也就是树的每个节点的左右子树深度相差不超过 1 的时候，查询的时间复杂度为 O(log2(N))，具有比较高的效率。然而，当二叉查找树不平衡时，例如在最坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为 O（N）。

也就是说，二叉查找树的性能非常依赖于它的平衡程度，这就导致其不适合作为 MySQL 底层索引的数据结构。

2.3 AVL 树

AVL 树的特点是保证任何节点的左右子树高度之差不超过 1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。

就上述平衡二叉树的特点来看，其实是我们理想的状态下，然而其实内部还是存在一些问题：

时间复杂度和树的高度有关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘的IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。磁盘每次寻道的时间为10ms，在数据量大时，查询性能会很差。
平衡二叉树不支持范围查询快速查找，范围查询需要从根节点多次遍历，查询效率不高。

2.4 B树：改造二叉树

MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO操作非常耗时，所以我们优化的重点就是尽量减少磁盘的IO操作。访问二叉树的每个节点都会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。

那如何降低树的高度呢？

假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间为（8+4*2=16）。

因为在MySQL的InnoDB引擎的一次IO操作会读取一页的数据量（默认一页大小为16K），而二叉树一次IO操作的有效数据量只有16字节，空间利用率极低。为了最大化的利用一次IO操作空间，一个解决方法就是在一个节点处存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的分叉树，将树的体型从高瘦变成了矮胖。构建1百万条数据，树的高度需要2层就可以（1000*1000=1百万），也就是说只需要两次磁盘IO操作就可以查询到数据，磁盘IO操作次数变少了，查询数据的效率整体也就提高了。

这种数据结构我们称之为B树，==B树是一种多叉平衡查找树==，如下图主要特点：

B树的节点中存储这多个元素，每个内节点有多个分叉。
节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点中都存储数据。
父节点当中的元素不会出现在子节点中。
所有的叶子节点都位于同一层，叶子节点具有相同的深度，叶子节点之间没有指针连接。

B树数据结构大致如下：

举个简单的例子，在B树中查询数据的情况：

假如我们要查询key等于10对应的数据data，根据上图我们可知在磁盘中的查询路径是：磁盘块1->磁盘块2->磁盘块6

第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，10<15，走左子树，到磁盘中寻址到磁盘块2。
第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，10>7，走右子树，到磁盘中寻址到磁盘块6。
第三次磁盘IO：讲磁盘块6加载到内存中，在内存中从头遍历比较，10=10，找到key=10的位置，取出对应的数据data，如果data存储的是行记录，直接取出数据，查询结束；如果data存储的是行磁盘地址，还需要根据磁盘地址到对应的磁盘中取出数据，查询结束。

相比较二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是对于磁盘IO的次数会大大减少，同时，由于我们是在内存中进行的数据比较，所以比较数据所消耗的时间可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。

过程如下图所示：

看到上面的情况，觉得B树已经很理想了，但是其中还是存在可以优化的地方：

B树不支持范围查询的快速查找，例如：仍然根据上图，我们想要查询10到35之间的数据，查找到10之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
如果data存储的是行记录，行的大小随着列数的增加，所占空间会变大，这时一页中可存储的数据量就会减少，树相应就会变高，磁盘IO次数就会随之增加，有待优化。

2.5 B+树：改造B树

B+树，作为B树的升级版，MySQL在B树的基础上继续进行改造，使用B+树构建索引。B+树和B树最主要的区别在于==非叶子节点是否存储数据==的问题。

B树：叶子节点和非叶子节点都会存储数据。
B+树：只有叶子节点才会存储数据，非叶子节点只存储键值key；叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。

B+树的大致数据结构：

B+树的最底层叶子节点包含了所有的索引项。从上图可以看出，B+树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。所以在查询数据的情况下每次的磁盘IO次数跟树的高度有直接的关系；但是从另一方面来说，由于数据都被存放到了叶子节点，所以存放索引的磁盘块，所存放的的索引数量会随之增加，所以相对于B树来说，B+树的树高理论情况下是比B树树高要矮的。
但是也存在索引覆盖查询的情况，在索引中数据满足了查询语句所需要的全部数据，此时只需要找到索引即可立刻返回，不需要检索到最底层的叶子节点。

等值查询实例：

假如我们要查询key为9对应的数据data，查询路径为：磁盘块1->磁盘块2->磁盘块6。

第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，9<15，走左子树，到磁盘寻址定位到磁盘块2。
第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<9<12，到磁盘中寻址定位到磁盘块6。
第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头遍历比较，在第三个索引中找到9，取出对应的数据data，如果data存储的是行记录，直接取出data，查询结束；如果存储的是磁盘地址，还需要根据磁盘地址再次寻址定位到指定磁盘取出数据，查询终止。

范围查询实例：

假如我们想要查找9和26之间的数据，查找路径为：磁盘块1->磁盘块2->磁盘块6->磁盘块7

前三次磁盘IO：首先查找到键值为9对应的数据（定位到磁盘块6），然后缓存大结果集中。这一步和前面等值查询流程一样，发生了三次磁盘IO。
继续查询，查找到节点15之后，底层的所有叶子节点是一个有序列表，我们从磁盘块6中的键值9开始向后遍历筛选出所有符合条件的数据。
第四次磁盘IO：根据磁盘块6的后继指针到磁盘中寻址定位到磁盘块7，将磁盘块7加载到内存中，在内存中从头遍历比较，9<25<26，9<26<=26，将数据data缓存到结果集中。
逐渐具备唯一性（后面不会再有<=26的数据），不需要再向后查找，查询结束，将结果集返回给用户。