返回

MySQL深入浅出之索引

发布时间:2023-10-27 15:15:11 293


文章目录

  • ​​1. 简介​​
  • ​​2. 索引的常见模型​​
  • ​​2.1 哈希表​​
  • ​​2.2 有序数组​​
  • ​​2.3 二插搜索树​​
  • ​​2.4 多叉树(N叉树)​​
  • ​​2.5 B+树 真实的数据库索引结构​​
  • ​​3. InnoDB的索引模型​​
  • ​​3.1 主键索引和普通索引​​
  • ​​3.2 **基于主键索引和普通索引的查询区别?**​​
  • ​​3.3 索引维护​​
  • ​​3.4 字符串类型的身份证号,使用身份证号做主键还是自增做主键呢?​​
  • ​​3.5 什么场景适合用业务字段直接做主键?​​
  • ​​4. InnoDB 实战​​
  • ​​4.1 上述搜索需要执行几次树的搜索? 会搜索多少行?​​
  • ​​4.2 覆盖索引​​
  • ​​4.3 是否有必要将身份证号和姓名建立联合索引?​​
  • ​​4.4 联合索引(B+树)​​
  • ​​4.5 最左前缀原则​​
  • ​​4.6 索引下推​​
  • ​​总结:​​
  • ​​4. 索引失效​​

1. 简介

索引的出现是为了提高数据查询的效率, 就像书的目录一样, 给一本书创建目录, 就可以快速找到哪一页或哪一章.

2. 索引的常见模型

索引的出现是为了提高查询效率, 但是实现索引的方式有很多, 下面先介绍用于提高读写效率的数据结构

2.1 哈希表

哈希表是按照key-value的存储数据结构, 只需要输入待查的key, 就可以找到对应的value. 具体而言, 用一个哈希函数将key换算成一个确定的位置, 然后将value放到数组这个位置.

缺点: value存放位置 = func(key), 多个key值通过func可能得到相同的结果, 处理这种情况的一种方式是将value存放到链表中, 如下图所示

MySQL深入浅出之索引_索引

图中, User2和User4根据身份证号码计算的值都是N, 所以User4跟User2在一个链表上, 但由于不是有序的插入到链表中, 所以哈希索引如果做区间查询速度会变得超级慢.(查询ID_card_1,4)这个区间的所有用户, 就需要进行全局扫描了

优点: 插入快, 所以哈希表这种结构适合 等值查询的场景

2.2 有序数组

有序数组在等值查询的场景和范围查询的场景性能都很优秀

MySQL深入浅出之索引_联合索引_02

假设身份证号没有重复, 这个数组就是按照身份证号递增顺序保存, 这个时候如果要查询ID_card_n2对应的User, 利用二分法就可以实现, 时间复杂度O(log(N)), 很显然, 如果要查询身份证号一个范围, 则可以利用二分法找到起始User, 在向右遍历的得到最后一个User;

缺点: 更新数据较为麻烦, 比如要在中间插入一条数据, 后面的数据就需要向后挪动

因此有序数组索引只适用于静态存储引擎, 比如要保存2017年某城市所有人口信息, 这些信息因为不会再被更改, 这个时候就可以;

2.3 二插搜索树

MySQL深入浅出之索引_mysql_03

二插搜索树的特点:

左儿子小于父节点, 右儿子大于父节点; 所以在查询一个User的时候, 就是个二分法查找, 时间复杂度O(logn)

缺点: 比如上图我们要找User2的ID_card_ID, 我们需要依次遍历UserA->UserC->UserF->User2; 如果这个逻辑放到计算机中, 就是需要将UserA,C,F,2依次从硬盘读入到内存进行确定, 而这个硬盘到内存的过程称为IO, 而IO是巨费时间的行为, 如果能够尽可能能的少一些IO呢, 那我们需要继续读下去;

2.4 多叉树(N叉树)

为了查询少读硬盘, 查询过程尽量少访问数据库, 所以这里利用N叉树, 每个叶子节点作为一个数据块; 以InnoDB的一个整数字段索引为例, N=1200; 当这棵树h=4, 则可以存 MySQL深入浅出之索引_mysql_04, 考虑到树根的数据块一直在内存中, 一个10亿行的表, 查找一个值最多只需要访问3次磁盘, 所以N叉树在读写上的性能优点, 适合磁盘访问模式, 已经广泛应用于数据块引擎中了.

MySQL深入浅出之索引_mysql_05

2.5 B+树 真实的数据库索引结构

MySQL深入浅出之索引_B树_06

  • B+树的优点: 像B树查找一样, logN查找时间, 又可以在对范围查找时, 根据单向链表进行从查找
  • 非叶子节点跟叶子节点的不同: 非叶子节点只存储key, 叶子节点存储key-val, 这样就能保证非叶子节点能存储更多的数据, 而叶子节点就能更快地找到对应的value
  • 注意: B+树比B树会多查找一次

3. InnoDB的索引模型

在MySQL中, 索引是在存储引擎层实现的, 所以并没有统一的索引标准, 即不同存储引擎的索引工作方式不一样, 而即使多个存储引擎支持同一种类型的索引, 底层实现也可能不同. 由于InnoDB存储引擎在MySQL中使用最为广泛, 因此下面按照InnoDB为例, 分析其中的索引模型

在InnoDB中, 表都是根据主键顺序, 按照索引的形式进行存放的, 这种存放方式的表称为索引组织表, 前面提到的多叉树(B+ 树)就是其数据的存储格式

每个索引在InnoDB中对应一棵B+树

3.1 主键索引和普通索引

下面我们以主键列ID, 表中字段k, k包含索引, 创建表的语句是:

create table T(
id int primary key, # 设置主键为id
k int not null,
name varchar(16),
index(k) # 给k上个索引
) engine=InnoDB; # 默认存储引擎是InnoDB

MySQL深入浅出之索引_索引_07

两棵树的示意图如上所述:

主键索引 ID

非主键索引 k

非叶子节点都存的ID值

非叶子节点存的是k

叶子节点存的是整行数据

叶子节点存的是k-ID

被称为聚簇索引 Clustered index

二级索引Secondary Index

根据上面索引结构, 这里讨论

3.2 基于主键索引和普通索引的查询区别?

  • 如果语句select * from T where id=500; 主键查询, 只需要搜索id这棵B+树
  • 如果语句select * from T where k=5; 普通索引查询方式, 需要先搜索k索引树, 得到ID=500, 在到ID索引搜索一次(回表)

3.3 索引维护

B+树维护索引有序性, 在插入新值时必须做必要的维护.

如上图所示, 如果插入新行ID=700, 则只需要在R5后面插入一条新的记录; 如果插入的值ID为400, 就需要逻辑上挪动后面的数据, 空出位置; 如果R5所在行数据页满了, 根据B+树算法, 这时候需要新申请一个新的数据页, 然后将部分数据挪动到新的数据页, 空出新位置给新数据, 这个过程称之为页分裂;

又分裂自然有合并, 相邻两个页数据删除, 利用率很低, 此时会进行数据页合并, 合并过程被认为是分裂的逆过程;

自增主键 插入新纪录不需要指定ID值, 系统会在当前ID+1作为下一条ID值; 这样做会实现: 每次插入一条新记录, 都是追加操作, 不涉及到挪动其他记录, 也不会触发叶子节点分裂;

3.4 字符串类型的身份证号,使用身份证号做主键还是自增做主键呢?

由于每个非主键索引的叶子节点都是主键的值. 如果用身份证做主键, 那么二级索引叶子节点占用约20字节, 而如果用整形做主键,则只需要4个字节, 显然主键长度越小, 普通索引叶子节点就越小, 普通索引占用空间也就越小; 所以从性能和存储空间方面考量, 自增主键往往更合理;

3.5 什么场景适合用业务字段直接做主键?

  1. 只有一个索引
  2. 该索引必须唯一索引

4. InnoDB 实战

# 表初始化
create table T(
ID int primary key,
k int not NULL default 0,
s varchar(16) not NULL default '',
index k(k)
) engine=InnoDB;
insert into T values (100,1,'aa'), (200,2,'bb'),(300,3,'cc')(500,5,'ee'),(600,6,'ff')(700,7,'gg')

select * from T where k between 3 and 5

4.1 上述搜索需要执行几次树的搜索? 会搜索多少行?

MySQL深入浅出之索引_索引_08

如图所示, 查看​​select * from T where k between 3 and 5​​ 执行流程:

  • k索引树找到 ​​k=3​​​ , 读取 ​​ID=300​
  • 回到ID索引树, 读取 ​​ID=300​​对应的R3
  • 在k索引树找到 ​​k=5​​​ , 读取 ​​ID=500​
  • 回到ID索引树, 读取 ​​ID=500​​对应的R4
  • k索引树找到 ​​k=3​​​下一个值​​k=6​​ , 不满足条件, 循环结束

在上述过程中, 主键搜索过程两次(回表), 查询k索引树3次

4.2 覆盖索引

根据上述过程, 我们思考, 如果我们的命令是​​select ID from T where k between 3 and 5​​ 这样子就不用在回表了, 因为当查找K索引树时, 其内容就是ID值, 因此可以直接提供查询结果, 不需要回表

覆盖索引可以减少树的搜索过程, 能够显著提高查询性能, 所以使用覆盖索引是一个常用的优化手段

注意: 虽然引擎内部使用覆盖索引k上其实只读了三个记录, R3-R5, 但是对于MySql的server层来说, 他就是找索引拿了两条记录, 因此mySql描述的是扫描行数=2

4.3 是否有必要将身份证号和姓名建立联合索引?

CREATE TABLE `tuser` (
`id` int(11) NOT NULL,
`id_card` varchar(32) DEFAULT NULL,
`name` varchar(32) DEFAULT NULL,
`age` int(11) DEFAULT NULL,
`ismale` tinyint(1) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `id_card` (`id_card`),
KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

如果有根据身份证号查询市民信息的需求, 我们只需要在身份证号上建立索引就可以

如果有高频请求, 需要根据视频身份证号查询姓名, 那这个(身份证号,姓名)的联合索引就有意义了, 因为在这个请求上, 可以利用覆盖索引, 不需要回表查询整行记录, 减少语句的执行时间.

​​联合索引详解​​

4.4 联合索引(B+树)

联合索引是值对一张表上的多列进行索引, 而这个B+树的键值书来那个不是1, 而是大于等于2, 如下图所示

MySQL深入浅出之索引_mysql_09


假定上图联合索引为​​(a,b)​​​, 联合索引也是一棵​​B+​​​树, 不同的是​​B+​​​树在对索引​​a​​​排序的基础上, 对索引​​b​​​排序, 所以数据按照​​(1,1)(1,2)...​​进行排序;

  1. 对于​​select * from table where a=XX and b=XX​​​, 显然是可以用​​(a,b)​​联合索引的
  2. 对于​​select * from table where a=XX​​​ 也是可以使用​​(a,b)​​联合索引的, 因为在上述两种情况下, 叶子节点中的数据都是有序的.
  3. 但是对于​​select * from table where b=XX​​​ 这种b查询, 是不可以使用这棵​​B+​​​树的, 可以发现叶子节点b值是​​1,2,1,4,1,2​​​, 显然不是有序的, 因此不能使用​​(a,b)​​联合索引

注意: ​​select * from table where b=XX and a=XX​​​ 这里是可以使用B+树的联合索引的, 这是因为啥呢, 因为mysql包含优化器, 它会判断这条sql语句该按照什么样的顺序执行效率最高, 最后才真正的执行;
优化: 将联合索引中, 选择性最高的列放前面, 如经常需要用到姓名和年龄查询身份证号, 就建立(name/age)

4.5 最左前缀原则

如果为每一种查询都设计一种索引, 索引是不是太多了, 如果按照市民身份证号去查他家的家庭地址, 或者按照身份证号去查他的学历等信息? 虽然该查询业务出现的概率不高, 但是总不能让他走全表扫描吧, 但是反过来讲, 建立这些索引又有点浪费, 应该怎么做呢?

这里先看结论: B+树这种索引结构, 可以利用索引的"最左前缀", 来定位记录

接下来我们用(name, age)这个联合索引来分析

MySQL深入浅出之索引_B树_10

可以看到, 索引项按照索引定义里面出现的字段顺序排序的, 当逻辑需求是查所有名字为 “张三” , 可以快速定位到ID4, 然后向后遍历得到所有需要的结果

如果你要查的是所有名字第一个字为 “张”, ​​where name like "张%"​​ , 这时可以利用上面这个索引, 查找到第一个符合条件记录的ID3, 然后向后遍历, 直到不满足为止;

因此可以看到, 只要满足最左前缀, 就可以利用索引加速检索, 这个最左前缀可以联合索引的最左N个字段, 也可以是字符串索引的最左M个字符

基于上面对最左前缀的说明, 接下来讨论一个问题:

  • 在建立联合索引的时候, 如何安排索引内的字段顺序?

这里的评估标准是 索引的复用能力, 因为可以支持最左前缀, 所以当已经有了(a, b)联合索引之后, 就不需要在单独建立a上索引了; 所以在这里, 第一原则 如果通过调整顺序, 可以少维护一个索引, 那么这个顺序往往是需要优先被采用考虑的

所以上面提到高频请求创建(身份证号 , 姓名) 这个联合索引, 并用联合索引支持 “根据身份证号查询地址的需求”

如此, 如果既有联合索引, 也有a, b各自的查询呢, 此时如果查询条件只有b, 那就无法使用(a, b)联合索引了, 这时候就要维护(a, b)和(b)这两个索引; 这个时候我们要考虑的是空间, 如果name字段比age字段大, 那就建议建立一个(name, age)和(age)字段, 这样能减少空间

4.6 索引下推

如果不符合最左前缀的部分怎么处理, 比如检索出表中名字第一个字是张, 年龄是10的所有男孩

​select * from tuser where name like '张%' and age=10 and ismale=1;​

根据最左前缀规则, 这个语句在搜索索引树时, 只能用 “张” , 找到第一个满足条件ID3, 然后呢?

MySql5.6之前, ID3需要回表, 主键找到数据行, 与字段值​​age=10? ismale=1?​​进行比较

MySql5.6引入了索引下推优化(index condition pushdown), 可以在索引遍历过程中, 对索引包含字段进行判断, 直接过滤掉不满足条件的记录, 减少回表次数

MySQL深入浅出之索引_主键_11


MySQL深入浅出之索引_B树_12

总结:

适当的创建索引, 会大大提高查找效率
比如日报系统里面的(name, repor)联合索引, 当老师查看name等于zjq的时候, 只需要
​​​select report * from T where name="zjq"​​ 利用这个联合索引, 避免了全局遍历 ,避免了回表查询(覆盖索引)

4. 索引失效

MySQL深入浅出之索引_mysql_13


全局来看:

  • a是有顺序的: 1,1,2,2,3,3
  • b是无顺序的: 1,2,1,4,1,2
  • 当a确定时, b是有顺序的 1,2 1,4 1,2
select * from T where a=1 and b=1;  # 会直接使用联合索引, 根据(1,1)确定主键ID, 在回表查找
select * from T where a>1 and b=1; # 索引失效, 因为当a>1时, b是无序的, 所以无法定位b=1的情况, 就会进行全表扫描
select * from T where a=1 and b>1; # 会直接使用联合索引, 因为当a=1时, b是有序的, 所以可以定位b
select * from T where a>1 and b>1; # 索引失效, 因为当a>1, b无序的, 所以无法定位b>1的情况, 就会进行全表扫描
select * from T where b=1; # 索引失效, 因为最左前缀原则, 首先需要确定a, 才能确定b
select * from T where a=1; # 会直接使用联合索引, 根据(1,x)确定所有主键ID, 在回表查找

所以这里就能解释like为何会失效的原因了

  • ​where a like %1​​就不行
  • ​where a like 1%​​可能可以
  • ​where a like %1​​就不行


特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线