mysql索引(二)索引的数据结构B+TREE

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
云数据库 RDS MySQL,高可用系列 2核4GB
简介: 索引本质上是一种数据结构,让我们在查询数据的时候尽量减少磁盘I/O。前边大概看了索引的原理。数据库的复杂性,以及读取磁盘时,磁盘I/O等。任何一种数据结构都不是凭空产生的,一定会有它的背景和使用场景,我们现在总结一下,我们需要这种数据结构能够做些什么,其实很简单,那就是:每次查找数据时把磁盘IO次数控制在一个很小的数量级,最好是常数数量级。

QQ图片20220424164246.jpg

索引本质上是一种数据结构,让我们在查询数据的时候尽量减少磁盘I/O

前边大概看了索引的原理。数据库的复杂性,以及读取磁盘时,磁盘I/O等。任何一种数据结构都不是凭空产生的,一定会有它的背景和使用场景,我们现在总结一下,我们需要这种数据结构能够做些什么,其实很简单,那就是:每次查找数据时把磁盘IO次数控制在一个很小的数量级,最好是常数数量级。


那么我们就想到如果一个高度可控的多路搜索树是否能满足需求呢?就这样,b+树应运而生


QQ图片20220424164248.jpg


B+树大概就是上边这个玩意。


如上图,是一颗b+树,最上层是树根,中间的是树枝,最下面是叶子节点,关于b+树后边会看到,这里只说一些重点,浅蓝色的块我们称之为一个磁盘块或者叫做一个block块,这是操作系统一次IO往内存中读的内容,一个块对应四个扇区,可以看到每个磁盘块包含几个数据项(深蓝色所示,一个磁盘块里面包含多少数据,一个深蓝色的块表示一个数据,其实不是数据,后面有解释)和指针(黄色所示,看最上面一个,p1表示比上面深蓝色的那个17小的数据的位置在哪,看它指针指向的左边那个块,里面的数据都比17小,p2指向的是比17大比35小的磁盘块),如磁盘块1包含数据项17和35,包含指针P1、P2、P3,P1表示小于17的磁盘块,P2表示在17和35之间的磁盘块,P3表示大于35的磁盘块。


真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。


非叶子节点只不存储真实的数据,只存储指引搜索方向的数据项,如17、35并不真实存在于数据表中。


B+树的查找过程


如图所示,如果要查找数据项29,那么首先会把磁盘块1由磁盘加载到内存,此时发生一次IO,在内存中用二分查找确定29在17和35之间,锁定磁盘块1的P2指针,内存时间因为非常短(相比磁盘的IO)可以忽略不计,通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存,发生第二次IO,29在26和30之间,锁定磁盘块3的P2指针,通过指针加载磁盘块8到内存,发生第三次IO,同时内存中做二分查找找到29,结束查询,总计三次IO。


真实的情况是,3层的b+树可以表示上百万的数据,如果上百万的数据查找只需要三次IO,性能提高将是巨大的,如果没有索引,每个数据项都要发生一次IO,那么总共需要百万次的IO,显然成本非常非常高。


b+树性质


1.索引字段要尽量的小:


通过上面的分析,我们知道IO次数取决于b+数的高度h或者说层级,这个高度或者层级就是你每次查询数据的IO次数,假设当前数据表的数据为N,每个磁盘块的数据项的数量是m,则有h=㏒(m+1)N,当数据量N一定的情况下,m越大,h越小;而m = 磁盘块的大小 / 数据项的大小,磁盘块的大小也就是一个数据页的大小,是固定的,如果数据项占的空间越小,数据项的数量越多,树的高度越低。


这就是为什么每个数据项,即索引字段要尽量的小,比如int占4字节,要比bigint8字节少一半。


这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点,一旦放到内层节点,磁盘块的数据项会大幅度下降,导致树增高。当数据项等于1时将会退化成线性表。


2:索引的最左匹配特性:


简单来说就是你的数据来了以后,从数据块的左边开始匹配,在匹配右边的,知道这句话就行啦,我们继续学下面的内容。当b+树的数据项是复合的数据结构,比如(name,age,sex)的时候,b+数是按照从左到右的顺序来建立搜索树的,比如当(张三,20,F)这样的数据来检索的时候,b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候,b+树就不知道下一步该查哪个节点,因为建立搜索树的时候name就是第一个比较因子,必须要先根据name来搜索才能知道下一步去哪里查询。


比如当(张三,F)这样的数据来检索时,b+树可以用name来指定搜索方向,但下一个字段age的缺失,所以只能把名字等于张三的数据都找到,然后再匹配性别是F的数据了, 这个是非常重要的性质,即索引的最左匹配特性。


B-Tree索引的特点


1、B-tree索引可以加快数据的查询速度


存储引擎不需要进行全表扫描来获得需要的数据,取而代之的是从索引的根节点开始进行搜索。然后根据指针逐层向下查找,通过比较节点页的值和有目标值就可以找到合适的指针进入下层节点,而这些指针实际上定义了子节点页中值的上限和下限。

 

2、B-tree索引更适合进行范围查询


因为前面说过,B-tree对索引是顺序组织存储的,所以就很适合进行查找范围数据。   

B-tree索引的使用场景


1、 全值匹配的查询


指的是和索引中的所有列进行匹配,比如查询字段 name = ‘tom’;   


2、匹配最左前缀的查询


比如为a列和b列设置联合索引,只要联合索引的第一列(a列)符合查询条件,索引就会被用到,若只是第二列(b列)符合条件则不会被用到该索引。

  

3、匹配列前缀的查询


只匹配某一列的值的开头部分   


4、匹配范围值


5、精准匹配某一列并范围匹配另外一列 


6、只访问索引的查询


在这里指的就是覆盖索引,即只需要访问索引,而无需访问数据行   

 

7、用于查询中的order by 操作


索引树中的节点是有序的。一般来说,若B-Tree可以按照某种方式查找到该值,那么也可以用这种方式用于排序。所以,如果 order by 子句中满足前面列出的几种查询类型,则这个索引也可以满足对应的排序需求。


B-Tree索引的限制


1、 若不是按照索引的最左列开始查找,则无法使用该索引


比如建立联合索引(name 、phone_num),若搜索phone_num则无法使用该索引   

2、使用索引时,不能跳过索引中的列


比如建立联合索引(name 、phone_num 、addr),若搜索name和addr 则无法使用该索引只能使用那么过滤


3、not in 和 <> 操作无法使用该索引


4、若查询中有某个列的范围查询,则其右边的所有列都无法使用索引


注意:存储引擎用不同的方式使用B-Tree索引,性能也各有不同,各有优劣。例如,MyISAM使用前缀压缩的技术使得索引更小,但InnoDB则按照原数据格式进行存储。 MyISAM索引通过数据的物理位置引用被索引的行,而InnoDB则根据逐渐引用被索引的行


以上大概简单的了解了一下索引的B+树数据结构。



相关实践学习
如何在云端创建MySQL数据库
开始实验后,系统会自动创建一台自建MySQL的 源数据库 ECS 实例和一台 目标数据库 RDS。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心,利用清洁计算为万物互联的新世界提供源源不断的能源动力,目前开服的区域包括中国(华北、华东、华南、香港)、新加坡、美国(美东、美西)、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程,来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品:云服务器ECS 云服务器 ECS(Elastic Compute Service)是一种弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
目录
相关文章
|
10天前
|
缓存 关系型数据库 MySQL
在Linux中,如何优化MySQL性能,包括索引优化和查询分析?
在Linux中,如何优化MySQL性能,包括索引优化和查询分析?
|
11天前
|
SQL 关系型数据库 MySQL
MySQL索引你用对了吗?
本文从遇到的问题出发,分析了tddl优化器、MySQL索引、分表拆分键的选择相关知识。
|
12天前
|
存储 关系型数据库 MySQL
MySQL bit类型增加索引后查询结果不正确案例浅析
【8月更文挑战第17天】在MySQL中,`BIT`类型字段在添加索引后可能出现查询结果异常。表现为查询结果与预期不符,如返回错误记录或遗漏部分数据。原因包括索引使用不当、数据存储及比较问题,以及索引创建时未充分考虑`BIT`特性。解决方法涉及正确运用索引、理解`BIT`的存储和比较机制,以及合理创建索引以覆盖各种查询条件。通过`EXPLAIN`分析执行计划可帮助诊断和优化查询。
|
15天前
|
SQL 存储 关系型数据库
mysql加索引真的会锁表吗?揭秘背后的技术细节与规避策略
【8月更文挑战第16天】在数据库管理中,添加索引能大幅提升查询效率。MySQL执行此操作时的锁定行为常引起关注。文章详细解析MySQL中索引添加时的锁定机制及其原理。不同存储引擎及SQL语句影响锁定策略:MyISAM需全表锁定;InnoDB提供更灵活选项,如使用`ALTER TABLE... LOCK=NONE`可在加索引时允许读写访问,尽管可能延长索引构建时间。自MySQL 5.6起,在线DDL技术可进一步减少锁定时间,通过`ALGORITHM=INPLACE`和`LOCK=NONE`实现近乎无锁的表结构变更。合理配置这些选项有助于最小化对业务的影响并保持数据库高效运行。
30 4
|
15天前
|
SQL JavaScript 关系型数据库
Mysql索引不当引发死锁问题
本文通过真实案例解析了MySQL在高并发环境下出现死锁的问题。数据库表`t_award`包含多个索引,但在执行特定SQL语句时遭遇索引失效,导致更新操作变慢并引发死锁。分析发现,联合索引`(pool_id, identifier, status, is_redeemed)`因`identifier`允许为空值而导致索引部分失效。此外,`pool_id`上的普通索引产生的间隙锁在高并发下加剧了死锁风险。为解决此问题,文中提出了调整索引顺序至`(pool_id, status, is_redeemed, identifier)`等方案来优化索引使用,进而减轻死锁现象。
|
17天前
|
缓存 NoSQL Redis
一天五道Java面试题----第九天(简述MySQL中索引类型对数据库的性能的影响--------->缓存雪崩、缓存穿透、缓存击穿)
这篇文章是关于Java面试中可能会遇到的五个问题,包括MySQL索引类型及其对数据库性能的影响、Redis的RDB和AOF持久化机制、Redis的过期键删除策略、Redis的单线程模型为何高效,以及缓存雪崩、缓存穿透和缓存击穿的概念及其解决方案。
|
1天前
|
SQL 关系型数据库 MySQL
深入探索MySQL索引策略
本文旨在深入探讨MySQL(8.0.26)数据库中索引的设计与优化方法。
|
2月前
|
存储 SQL 关系型数据库
(六)MySQL索引原理篇:深入数据库底层揭开索引机制的神秘面纱!
《索引原理篇》它现在终于来了!但对于索引原理及底层实现,相信大家多多少少都有了解过,毕竟这也是面试过程中出现次数较为频繁的一个技术点。在本文中就来一窥`MySQL`索引底层的神秘面纱!
137 5
|
8天前
|
SQL 算法 关系型数据库
MySQL索引看这篇就行
MySQL索引看这篇就行
13 0
|
2月前
|
SQL 存储 关系型数据库
(五)MySQL索引应用篇:建立索引的正确姿势与使用索引的最佳指南!
在本篇中,则重点讲解索引应用相关的方式方法,例如各索引优劣分析、建立索引的原则、使用索引的指南以及索引失效与索引优化等内容。
104 0
下一篇
云函数