MySQL 索引之道

1. 索引的介绍

索引是通过某种算法构建出一个数据模型用于快速找出某个列中有一特定值的行。

如果没有索引MySQL必须使用全表扫描方式从第一条记录开始读完整个表直到找到对应结果表越大查询所花的时间越多效率特别特别低。

如果有索引MySQL能够快速到达一个大概的位置再从一这个位置继续检索而不必查看所有数据。

索引是加在字段上的对于一个student表 执行如下SQL语句

select id, name from student where id = 10;

如果没有索引需要遍历全部学生直到找到学号为10的遍历次数为8.

如果给id字段加了索引假如加的是二叉搜索树那么这句SQL只需要遍历8、10遍历次数为2。

只有10条记录就能优化这么明显100条呢10000条呢10000000条呢

当然索引并不是二叉搜索树这么简单常见的索引结构如哈希、B+树这些结构都很复杂。

2. 索引的本质

**索引是数据的一种**MySQL数据库的数据是存储在磁盘中的所以索引也是以文件的形式存储在磁盘中的。

不过索引文件在磁盘中究竟以何种方式存储这是由索引的数据结构来决定的。同时由于索引机制最终是由存储引擎实现因此不同存储引擎下的索引文件其保存在本地的格式也并不相同。

因为索引是以文件形式保存在磁盘的对于一张很大的表创建索引时并不会像约束一样直接在原表操作而是重新在磁盘中创建新的文件来存储。假设表中有1000W​​条数据那创建索引时就需要将索引字段上的1000W​​个值全部拷贝到本地索引文件中同时做好排序并与表数据产生映射关系。

3. 索引的结构

‍

索引建立后也会在磁盘生成索引文件那每个具体的索引节点该如何在本地文件中存放呢这点是由索引的数据结构来决定的。比如索引的底层结构是数组那所有的索引节点都会以Node1→Node2→Node3→Node4....​​这样的形式存储在磁盘同一块物理空间中不过MySQL​​的索引不支持数组结构或者说数组结构不适合作为索引结构MySQL​​索引支持的数据结构如下

• Hash​​类型大部分存储引擎都支持字段值不重复的情况下查询最快无序。

• B+Tree​​类型MySQL​​中最常用的索引结构大部分引擎支持有序。

• R-Tree​​类型MyISAM​​引擎支持也就是空间索引的默认结构类型。

• T-Tree​​类型NDB-Cluster​​引擎支持主要用于MySQL-Cluster​​服务中。

在上述的几种索引结构中B+​​树和哈希索引是最常见的索引结构几乎大部分存储引擎都实现了对于后续两种索引结构在某些情况下也较为常见但除开列出的几种索引结构外MySQL​​索引支持的数据结构还有R+、R*、QR、SS、X​​树等结构。

‍

3.1 Hash

Hash是一种算法也叫散列算法如何使用Hash来实现索引呢

• 使用 算法 给加了索引的字段生成一个hashcode这个hashcode映射到具体数据的地址

假如有如下指令要执行

insert into student(id, name, age) value (1, '小王', 18);
insert into student(id, name, age) value (2, '小刚', 17);
insert into student(id, name, age) value (3, '小蓝', 21);

给字段id添加索引假如构建索引时hash使用的算法为哈希函数f()它返回下面的值

f(‘1’) = 2414

f(‘2’) = 4634

f(‘3’) = 8381

则哈希索引的结构如下

键值	槽(hashcode)	值
1	2414	指向第一行的指针
2	4634	指向第二行的指针
3	8381	指向第三行的指针

当查询时

select * from student where id = 2

依旧会根据2计算出hashcode得到指向第二行的指针直接得到数据。而不是傻傻的遍历。

Hash的优点

哈希算法时间复杂度为O(1)它是最快的磁盘IO花费少

Hash的缺点

Hash只能用到等值查询不能范围和模糊查询。

hash索引不能用于外排序hash索引存储的是hash码而不是键值所以无法用于外排序。

hash索引中的hash码的计算可能存在hash冲突

3.2 B+树

B+树是使用最多的索引在MySQL​​中创建索引时其默认的数据结构就为B+Tree​​。

谈到B+树必须要先说一下B树多路平衡查找树。

将999-1020插入到B树中如下

B树与二叉树的差别

结构	节点key数量	孩子数量
二叉树	每一个节点可以有多个key	每个节点可以有多个孩子
B树	每一个节点最多有一个key	每个节点最多有两个孩子

正是由于这些区别在二叉树中插入100个数据可能有10层在B树中插入可能只有3层。

接下来看看插入 999 - 1020到B+树会发生什么

会发现B+树中所有的数据都在叶子节点中出现并且所有叶子节点构成一个链表。

B树与B+树的区别

1. B+树所有的数据都在叶子节点中出现。
2. B+树的非叶子节点只有key叶子节点有key也有value
3. B+树所有叶子节点构成一个链表。

在进行如下SQL时

select * from student where id between 1006 and 1011;

使用B+树可以直接查找到1006和10111006和1011之间是链表结构直接返回。

MySQL又对B+树进行了优化在原有B+树的基础上增加了一个指向相邻叶子节点的链表指针形成了双向循环链表提高区间访问的性能。

3.3 常见面试题之为什么用B+树

Q 为什么用B+树而不用二叉树

1. 极端情况下二叉树可能形成链表再查询还是要遍历。
2. 相同数据量下二叉树的层级太高读取磁盘的次数太多浪费磁盘IO。

Q 为什么用B+树而不用Hash

1. Hash只支持等值查询不能范围和模糊查询。而B+树支持。
2. Hash可能出现Hash冲突极端情况下还是个链表。

Q 为什么用B+树而不用B树

1. B+树是B树的变种B树可以实现的B+树都可以实现。
2. B+树扫库、扫表能力更强因为B+树所有节点都形成了叶子节点并且所有叶子节点组成了双向链表。
3. B+树非叶子节点不存储数据每一页中存储的键值更多树的层级更少IO次数变少。
4. B+树永远是在叶子节点拿到数据更加稳定。

‍

4. 索引的分类

Q 请回答一下你知道的MySQL​​索引类型。

A 聚簇索引、非聚簇索引、唯一索引、主键索引、联合索引、全文索引、单列索引、多列索引、复合索引、普通索引、二级索引、辅助索引、次级索引、有序索引、B+Tree​​索引、R-Tree​​索引、T-Tree​​索引、Hash​​索引、空间索引、前缀索引…

如果你这样回答面试官可能笑笑不说话…

实际上MySQL​中真的有这么多索引类型吗其实并没有MySQL索引主要按照数据结构、字段数量、功能逻辑来分类。

当被问到 请回答一下你知道的MySQL​索引类型。

按照功能逻辑分类下的索引叙述即可 。

按照数据结构分类已经说过下面说一下按照功能与存储形式分类。

为什么不说按照字段数量的分类呢在一个字段上加索引称为单列索引在多个字段上加同一个索引叫做多列索引。功能逻辑分类中的唯一索引、主键索引…都是单列索引。

4.1 功能逻辑层次

可分为这几种

分类	含义	特点	关键字
普通索引	快速定位数据	可以有多个
主键索引	针对主键创建的索引	唯一主键默认加主键索引	PRIMARY
唯一索引	避免同一个表中的某一列出现重复值	可以有多个	UNIQUE
全文索引	全文索引查找的是文本中的关键词 类似ES的分词器	可以有多个
空间索引	快速检索空间数据类型	可以有多个

• 普通索引 给指定字段加索引单纯的提高这个字段的查询效率。
• 主键索引 一个表的主键默认加主键索引。
• 唯一索引 加了非空约束的字段默认加唯一索引。
• 全文索引 只能创建在CHAR、VARCHAR、TEXT​等这些文本类型字段上而且使用全文索引查询时条件字符数量必须大于3​才生效功能上类似ES的分词器。
• 空间索引 MySQL提供了几种空间类型 GEOMETRY、POINT、LINESTRING、POLYGON​空间索引则是基于这些类型的字段建立的也就是可以帮助我们快捷检索空间数据。

4.2 存储形式层次

分类	含义	特点
聚集索引	将数据存储与索引放到了一块索引结构的叶子节点保存了行数据	必须有只能由一个
二级索引	将数据与索引分开存储索引结构的叶子节点关联的是对应的主键	可以有多个

在刚才我们说过索引的本质是数据。如果构建索引要给索引创建单独的文件存储。

聚集索引就是将数据与索引放到一起存储。

二级索引就是将数据与索引单独存储那么如何通过索引找到数据呢这就要说到回表查询。

使用上面的student表给id构建聚集索引name构建二级索引。

若执行如下SQL

select * from student where id = 3;

由于是聚集索引只要根据索引查找到数据就可以直接返回该数据。

若执行如下SQL

select * from student where name = '何';

由于是二级索引会触发回表查询

简单描述就是

二级索引的叶子节点关联主键需要先查出主键再拿着主键去聚集索引查行数据。

由于回表查询的存在根据主键查询数据比根据其他字段查询数据快。

5. 索引的失效

在了解索引失效前先来看看一个原理 最左前缀原则。

5.1 最左前缀原则

对于多列索引

1. 查询从索引的最左列开始并且不跳过索引中的列。如果跳过某一列索引将部分失效。
2. 若查询语句中出现范围查询范围查询后的所有字段都不走索引。

存在一个表 student对于 id、age、name 加多列索引 idx_id_age_name可知顺序是id -> age -> name。

以下SQL语句的索引使用情况如下

-- 全部索引都将生效
-- 可见: 最左前缀原则的失效情况是未出现对于顺序无要求.
select * from student where id = 1 and age = 14 and name = '小李';
select * from student where age = 14 and id = 1 and name = '小李';
select * from student where age = 14 and name = '小李' and id = 1;

-- id是第一个未出现则idx_id_age_name索引全部失效
select * from student where age = 14 and name = '小李';

-- age 未出现从age开始失效。只用到了id的索引
select * from student where id = 1 and name = '小李';

-- name未出现从name开始失效。只用到了id和age的索引
select * from student where id = 1 and age = 14;

对于范围查询导致索引失效的场景

-- id出现范围查询id后的所有字段索引失效。
select * from student where id > 10 and age = 10 and name = '小李';
select * from student where age = 10 and id > 10 and name = '小李';
select * from student where age = 10 and name = '小李' and id > 10;

注意 这两种索引失效称为最左前缀原则​只有多列索引​会这样。

5.2 索引失效的场景

前两种多列索引失效的场景已经谈及接下来列举一下其他的索引失效场景 假设举例中的所有字段都加了索引

1. 最左前缀原则导致索引失效。

2. 字符串类型使用时不加引号索引失效。

   -- 索引不失效:
   select * from user where phone = '0111';
   -- 索引失效:
   select * from user where phone = 0111;
   

3. 模糊查询时%​在最前面索引失效。

   -- 索引不失效:
   select * from user where phone like '187%';
   select * from user where phone like '187%2321';
   -- 索引失效:
   select * from user where phone like '%2321';
   

4. 加索引的字段不能计算。

   -- 索引不失效:
   select * from user where salary > 10000;
   -- 索引失效:
   select * from user where salary * 1.2 > 10000;
   

5. 使用or连接条件时只有两侧字段都加了索引才都生效有一方没加都会全部失效。

6. 索引常见面试题

本标题下的内容引自 https://juejin.cn/post/7003527396427038733

面试官我看你简历上写了MySQL对MySQL InnoDB引擎的索引了解吗

嗯嗯使用索引可以加快查询速度其实上就是将无序的数据变成有序有序就能加快检索速度

在InnoDB引擎中索引的底层数据结构是B+树

面试官那为什么不使用红黑树或者B树呢

MySQL的数据是存储在硬盘的在查询时一般是不能「一次性」把全部数据加载到内存中

红黑树是「二叉查找树」的变种一个Node节点只能存储一个Key和一个Value

B和B+树跟红黑树不一样它们算是「多路搜索树」相较于「二叉搜索树」而言一个Node节点可以存储的信息会更多「多路搜索树」的高度会比「二叉搜索树」更低。

了解了区别之后其实就很容易发现在数据不能一次加载至内存的场景下数据需要被检索出来选择B或B+树的理由就很充分了一个Node节点存储信息更多相较于二叉搜索树树的高度更低树的高度影响检索的速度

B+树相对于B树而言它又有两种特性。

一、B+树非叶子节点不存储数据在相同的数据量下B+树更加矮壮。这个应该不用多解释了数据都存储在叶子节点上非叶子节点的存储能存储更多的索引所以整棵树就更加矮壮

二、B+树叶子节点之间组成一个链表方便于遍历查询遍历操作在MySQL中比较常见

​

我稍微解释一下吧你可以脑补下画面

我们在MySQL InnoDB引擎下每创建一个索引相当于生成了一颗B+树。

如果该索引是「聚集(聚簇)索引」那当前B+树的叶子节点存储着「主键和当前行的数据」

如果该索引是「非聚簇索引」那当前B+树的叶子节点存储着「主键和当前索引列值」

比如写了一句sqlselect * from user where id >=10那只要定位到id为10的记录然后在叶子节点之间通过遍历链表(叶子节点组成的链表)即可找到往后的记录了。

由于B树是会在非叶子节点也存储数据要遍历的时候可能就得跨层检索相对麻烦些。

基于树的层级以及业务使用场景的特性所以MySQL选择了B+树作为索引的底层数据结构。

对于哈希结构其实InnoDB引擎是「自适应」哈希索引的hash索引的创建由InnoDB存储引擎引擎自动优化创建我们是干预不了

面试官嗯…那我了解了顺便想问下你知道什么叫做回表吗

所谓的回表其实就是当我们使用索引查询数据时检索出来的数据可能包含其他列但走的索引树叶子节点只能查到当前列值以及主键ID所以需要根据主键ID再去查一遍数据得到SQL 所需的列

举个例子我这边建了给订单号ID建了个索引但我的SQL 是select orderId,orderName from orderdetail where orderId = 123

SQL都订单ID索引但在订单ID的索引树的叶子节点只有orderId和Id而我们还想检索出orderName所以MySQL 会拿到ID再去查出orderName给我们返回这种操作就叫回表

​

想要避免回表也可以使用覆盖索引能使用就使用因为避免了回表操作。

所谓的覆盖索引实际上就是你想要查出的列刚好在叶子节点上都存在比如我建了orderId和orderName联合索引刚好我需要查询也是orderId和orderName这些数据都存在索引树的叶子节点上就不需要回表操作了。

面试官既然你也提到了联合索引我想问下你了解最左匹配原则吗

嗯说明这个概念还是举例子比较容易说明

如有索引 (a,b,c,d)查询条件 a=1 and b=2 and c>3 and d=4则会在每个节点依次命中a、b、c无法命中d

先匹配最左边的索引只能用于查找key是否存在相等遇到范围查询 (>、<、between、like左匹配)等就不能进一步匹配了后续退化为线性查找

这就是最左匹配原则

​

面试官嗯嗯我还想问下你们主键是怎么生成的

主键就自增的

面试官那假设我不用MySQL自增的主键你觉得会有什么问题呢

首先主键得保证它的唯一性和空间尽可能短吧这两块是需要考虑的。

另外由于索引的特性有序如果生成像uuid类似的主键那插入的的性能是比自增的要差的

因为生成的uuid在插入时有可能需要移动磁盘块比如块内的空间在当前时刻已经存储满了但新生成的uuid需要插入已满的块内就需要移动块的数据

不使用主键自增因为索引用的是B+树插入数据时可能会移动数据。使用主键自增插入数据时按照顺序往右边插入不会移动数据​

面试官OK…

​

‍

7. 总结及参考文献

OK~在本篇中就对MySQL​的索引机制有了全面认知从索引的介绍、索引本质、索引结构、索引分类、索引失效、索引面试题等内容进行了全面概述相信本章看下来足够让你对MySQL​索引机制有一个系统化的体系那么我们下篇再见。

https://juejin.cn/post/7147609139974242317

https://juejin.cn/post/7003527396427038733

‍