MySQL深入浅出之索引
文章目录
- 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存放到链表中, 如下图所示
图中, User2和User4根据身份证号码计算的值都是N, 所以User4跟User2在一个链表上, 但由于不是有序的插入到链表中, 所以哈希索引如果做区间查询速度会变得超级慢.(查询ID_card_1,4)这个区间的所有用户, 就需要进行全局扫描了
优点: 插入快, 所以哈希表这种结构适合 等值查询的场景
2.2 有序数组
有序数组在等值查询的场景和范围查询的场景性能都很优秀
假设身份证号没有重复, 这个数组就是按照身份证号递增顺序保存, 这个时候如果要查询ID_card_n2对应的User, 利用二分法就可以实现, 时间复杂度O(log(N)), 很显然, 如果要查询身份证号一个范围, 则可以利用二分法找到起始User, 在向右遍历的得到最后一个User;
缺点: 更新数据较为麻烦, 比如要在中间插入一条数据, 后面的数据就需要向后挪动
因此有序数组索引只适用于静态存储引擎, 比如要保存2017年某城市所有人口信息, 这些信息因为不会再被更改, 这个时候就可以;
2.3 二插搜索树
二插搜索树的特点:
左儿子小于父节点, 右儿子大于父节点; 所以在查询一个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, 则可以存 , 考虑到树根的数据块一直在内存中, 一个10亿行的表, 查找一个值最多只需要访问3次磁盘, 所以N叉树在读写上的性能优点, 适合磁盘访问模式, 已经广泛应用于数据块引擎中了.
2.5 B+树 真实的数据库索引结构
- B+树的优点: 像B树查找一样, logN查找时间, 又可以在对范围查找时, 根据单向链表进行从查找
- 非叶子节点跟叶子节点的不同: 非叶子节点只存储key, 叶子节点存储key-val, 这样就能保证非叶子节点能存储更多的数据, 而叶子节点就能更快地找到对应的value
- 注意: B+树比B树会多查找一次
3. InnoDB的索引模型
在MySQL中, 索引是在存储引擎层实现的, 所以并没有统一的索引标准, 即不同存储引擎的索引工作方式不一样, 而即使多个存储引擎支持同一种类型的索引, 底层实现也可能不同. 由于InnoDB存储引擎在MySQL中使用最为广泛, 因此下面按照InnoDB为例, 分析其中的索引模型
在InnoDB中, 表都是根据主键顺序, 按照索引的形式进行存放的, 这种存放方式的表称为索引组织表, 前面提到的多叉树(B+ 树)就是其数据的存储格式
每个索引在InnoDB中对应一棵B+树
3.1 主键索引和普通索引
下面我们以主键列ID, 表中字段k, k包含索引, 创建表的语句是:
两棵树的示意图如上所述:
主键索引 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 什么场景适合用业务字段直接做主键?
- 只有一个索引
- 该索引必须唯一索引
4. InnoDB 实战
4.1 上述搜索需要执行几次树的搜索? 会搜索多少行?
如图所示, 查看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 是否有必要将身份证号和姓名建立联合索引?
如果有根据身份证号查询市民信息的需求, 我们只需要在身份证号上建立索引就可以
如果有高频请求, 需要根据视频身份证号查询姓名, 那这个(身份证号,姓名)的联合索引就有意义了, 因为在这个请求上, 可以利用覆盖索引, 不需要回表查询整行记录, 减少语句的执行时间.
联合索引详解
4.4 联合索引(B+树)
联合索引是值对一张表上的多列进行索引, 而这个B+树的键值书来那个不是1, 而是大于等于2, 如下图所示
假定上图联合索引为(a,b)
, 联合索引也是一棵B+
树, 不同的是B+
树在对索引a
排序的基础上, 对索引b
排序, 所以数据按照(1,1)(1,2)...
进行排序;
- 对于
select * from table where a=XX and b=XX
, 显然是可以用(a,b)
联合索引的 - 对于
select * from table where a=XX
也是可以使用(a,b)
联合索引的, 因为在上述两种情况下, 叶子节点中的数据都是有序的. - 但是对于
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)这个联合索引来分析
可以看到, 索引项按照索引定义里面出现的字段顺序排序的, 当逻辑需求是查所有名字为 “张三” , 可以快速定位到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), 可以在索引遍历过程中, 对索引包含字段进行判断, 直接过滤掉不满足条件的记录, 减少回表次数
总结:
适当的创建索引, 会大大提高查找效率
比如日报系统里面的(name, repor)联合索引, 当老师查看name等于zjq的时候, 只需要
select report * from T where name="zjq"
利用这个联合索引, 避免了全局遍历 ,避免了回表查询(覆盖索引)
4. 索引失效
全局来看:
- a是有顺序的: 1,1,2,2,3,3
- b是无顺序的: 1,2,1,4,1,2
- 当a确定时, b是有顺序的 1,2 1,4 1,2
所以这里就能解释like为何会失效的原因了
-
where a like %1
就不行 -
where a like 1%
可能可以 -
where a like %1
就不行