您当前的位置:首页 > 电脑百科 > 数据库 > MYSQL

Mysql索引数据结构有多个选择,为什么一定要是B+树?

时间:2021-06-07 13:42:41  来源:  作者:Java技术那些事

MySQL索引数据结构

下面列举了常见的数据结构

  • 二叉树
  • 红黑树
  • Hash表
  • B-Tree(B树)

Select * from t where t.col=5

我们在执行一条查询的Sql语句时候,在数据量比较大又不加索引的情况下,逐行查询并进行比对,每次需要从磁盘上查找,每行数据可能在磁盘不同的位置,数据比较靠后的话,一千万数据可能要比对几百万,很耗费资源。

Mysql衡量查询效率的就是磁盘IO次数,那么Mysql中应该采用什么样的数据结构存储数据呢,以及为什么要使用那个数据结构呢。

二叉树

大多数人都知道,如果加上索引之后。把数据放在二叉树里面,查询会快很多,但是还有一种特殊的情况:

把一个递增列的索引放入二叉树中,列id作为等于5查询目标,就会从col为1开始搜索,**这样要搜索几次?**二叉树插入的数据如果大于本身,会放在父节点的右下角,小的会放在父节点的左下角,因此形成了这样像链表一样的结构,其实本质还是二叉树。

Mysql索引数据结构有多个选择,为什么一定要是B+树?

 

需要从根节点遍历,经过5次的查找,每个节点都存储在磁盘上,每查一个节点需要跟磁盘做一次IO交互,效率相比之前没加索引也没有太大提升,这显然不是Mysql的索引结构。

红黑树

HasMap的数据结构就是红黑树,原来是数组加链表,现在优化到了数组加红黑树。

Mysql索引数据结构有多个选择,为什么一定要是B+树?

 

红黑树本质还是二叉树,还有一个名字又叫平衡二叉树。当一边子节点比另一边高太多的时候,会自动旋转平衡。当数据量比较大的时候比如1000万,红黑树存储的高度就可能达到几十。如果数据量越大树的高度就会越高。每查一个节点要进行一次磁盘IO交互。树的高的越高查找效率越低,很显然红黑树也不是Mysql的数据结构,早期版本Mysql有用到红黑树,现在版本没有用到红黑树。那么能不能对红黑树做点改造。

B-Tree

树的高的越高查找效率越低,那么将树高缩小,比如限制在5层,把一层存放更多元素。把一个节点的数据在磁盘同一个区域全部查出来放到内存,只做一次IO查找,就可以查到很多索引信息。B树又叫平衡多叉树。

Mysql索引数据结构有多个选择,为什么一定要是B+树?

 

索引值和具体data都在每个节点里,而节点的位置不固定,最好的情况查找值就在第一层。

B树的特点就是每层节点数目非常多,层数很少,目的就是为了减少磁盘IO次数,B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题,由于节点内部每个 key 都带着 data 域,每次查找到具体节点还要和data进行顺序比对,如果查找某个范围内数据,又需要重新遍历。正是为了解决这个问题,B+树应运而生

B树遍历全部数据:

Mysql索引数据结构有多个选择,为什么一定要是B+树?

 

B+Tree

B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储,数据全部存储在叶子节,并且每一个节点之间用指针串联起来,形成链表,方便遍历,可以跨区间访问,这优点尤其突出在范围查询,不需要在一次从根节点到子节点遍历。

Mysql索引数据结构有多个选择,为什么一定要是B+树?

 

B+树遍历全部数据:

Mysql索引数据结构有多个选择,为什么一定要是B+树?

 

数据量大的情况下哪个更快,我想你应该知道了吧!



Tags:Mysql索引   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
Mysql索引数据结构下面列举了常见的数据结构 二叉树 红黑树 Hash表 B-Tree(B树)Select * from t where t.col=5我们在执行一条查询的Sql语句时候,在数据量比较大又不加索引的情...【详细内容】
2021-06-07  Tags: Mysql索引  点击:(90)  评论:(0)  加入收藏
聊聊Mysql索引和redis跳表 ---redis的有序集合zset数据结构底层采用了跳表原理 时间复杂度O(logn)(阿里)redis使用跳表不用B+数的原因是:redis是内存数据库,而B+树纯粹是为了m...【详细内容】
2021-02-05  Tags: Mysql索引  点击:(190)  评论:(0)  加入收藏
本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题。特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引...【详细内容】
2020-08-16  Tags: Mysql索引  点击:(55)  评论:(0)  加入收藏
为了能让索引能有更直观的效率,我在一张表里扔进了百万条数据(光靠这些数据,生成数据代码写了一个小时,解决MySQL8的文件导入权限问题解决了两个小时,导入数据花费了一个小时,我...【详细内容】
2020-08-05  Tags: Mysql索引  点击:(66)  评论:(0)  加入收藏
概述随着电商的发展,使用数据库的业务越来越复杂,除了掌握哪些场景可以使用索引,哪些场景适合使用索引,还需要掌握索引在运行过程中的一些使用规则,特别是组合索引的使用。比如索...【详细内容】
2020-07-06  Tags: Mysql索引  点击:(54)  评论:(0)  加入收藏
1 初识索引索引在MySQL中也叫是一种“键”,是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键,尤其是当表中的数据量越来越大时,索引对于性能的影响愈发...【详细内容】
2019-11-18  Tags: Mysql索引  点击:(95)  评论:(0)  加入收藏
概述在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页...【详细内容】
2019-09-12  Tags: Mysql索引  点击:(130)  评论:(0)  加入收藏
在我们使用MySQL的过程中,随着数据量越来越大,查询显得有些吃力,这时候就要针对查询就行优化,针对查询优化,通过给字段添加索引可以提高数据的读取速度,提高项目的并发能力和抗压...【详细内容】
2019-09-07  Tags: Mysql索引  点击:(100)  评论:(0)  加入收藏
索引是一种用于快速查询行的数据结构,就像一本书的目录就是一个索引,如果想在一本书中找到某个主题,一般会先找到对应页码。在mysql中,存储引擎用类似的方法使用索引,先在索引中...【详细内容】
2019-09-05  Tags: Mysql索引  点击:(277)  评论:(0)  加入收藏
索引目的索引的目的在于提高查询效率,可以类比字典,如果要查“mysql”这个单词,我们肯定需要定位到m字母,然后从下往下找到y字母,再找到剩下的sql。如果没有索引,那么你可能需要把...【详细内容】
2019-08-29  Tags: Mysql索引  点击:(186)  评论:(0)  加入收藏
▌简易百科推荐
作者:雷文霆 爱可生华东交付服务部 DBA 成员,主要负责Mysql故障处理及相关技术支持。爱好看书,电影。座右铭,每一个不曾起舞的日子,都是对生命的辜负。 本文来源:原创投稿 *爱可生...【详细内容】
2021-12-24  爱可生    Tags:MySQL   点击:(6)  评论:(0)  加入收藏
生成间隙(gap)锁、临键(next-key)锁的前提条件 是在 RR 隔离级别下。有关Mysql记录锁、间隙(gap)锁、临键锁(next-key)锁的一些理论知识之前有写过,详细内容可以看这篇文章...【详细内容】
2021-12-14  python数据分析    Tags:MySQL记录锁   点击:(17)  评论:(0)  加入收藏
binlog 基本认识 MySQL的二进制日志可以说是MySQL最重要的日志了,它记录了所有的DDL和DML(除了数据查询语句)语句,以事件形式记录,还包含语句所执行的消耗的时间,MySQL的二...【详细内容】
2021-12-14  linux上的码农    Tags:mysql   点击:(13)  评论:(0)  加入收藏
为查询优化你的查询 大多数的MySQL服务器都开启了查询缓存。这是提高性最有效的方法之一,而且这是被MySQL的数据库引擎处理的。当有很多相同的查询被执行了多次的时候,这些查...【详细内容】
2021-12-09  元宇宙iwemeta    Tags:mysql   点击:(15)  评论:(0)  加入收藏
测试的目的和原因,公司有很多程序员,每个程序员对数据库和表结构都有自己的理解。而且每个程序员的理解往往是以效率考虑。既然都是为了效率考虑,那么我就来测试一下究竟哪种使...【详细内容】
2021-12-08  吴彬的分享    Tags:Mysql数据库   点击:(14)  评论:(0)  加入收藏
当你们考虑项目并发的时候,我在部署环境,当你们在纠结使用ArrayList还是LinkedArrayList的时候,我还是在部署环境。所以啊,技术不止境,我在部环境。今天这篇文章缕一下在同一台服...【详细内容】
2021-12-08  秃头码哥    Tags:MySQL数据库   点击:(16)  评论:(0)  加入收藏
对于数据分析来说,MySQL使用最多的是查询,比如对数据进行排序、分组、去重、汇总及字符串匹配等,如果查询的数据涉及多个表,还需要要对表进行连接,本文就来说说MySQL中常用的查询...【详细内容】
2021-12-06  笨鸟学数据分析    Tags:MySQL   点击:(19)  评论:(0)  加入收藏
在学习SQL语句之前,首先需要区分几个概念,我们常说的数据库是指数据库软件,例如MySQL、Oracle、SQL Server等,而本文提到的数据库是指数据库软件中的一个个用于存储数据的容器。...【详细内容】
2021-11-24  笨鸟学数据分析    Tags:SQL语句   点击:(23)  评论:(0)  加入收藏
概述以前参加过一个库存系统,由于其业务复杂性,搞了很多个应用来支撑。这样的话一份库存数据就有可能同时有多个应用来修改库存数据。比如说,有定时任务域xx.cron,和SystemA域...【详细内容】
2021-11-05  Java云海    Tags:分布式锁   点击:(31)  评论:(0)  加入收藏
MySQL的进阶查询 一、 按关键字排序 使用ORDERBY语句来实现排序排序可针对一个或多个字段ASC:升序,默认排序方式 【升序是从小到大】DESC:降序 【降序是从大到小】ORDER BY的...【详细内容】
2021-11-05  Java热点    Tags:SQL语句   点击:(27)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条