MySQL底层数据结构选用B+树的原因
来源:脚本之家
时间:2022-12-31 20:43:08 155浏览 收藏
知识点掌握了,还需要不断练习才能熟练运用。下面golang学习网给大家带来一个数据库开发实战,手把手教大家学习《MySQL底层数据结构选用B+树的原因》,在实现功能的过程中也带大家重新温习相关知识点,温故而知新,回头看看说不定又有不一样的感悟!
我们都知道MySQL底层数据结构是选用的B+树,那为什么不用红黑树,或者其他什么数据结构呢?
红黑树是一种自平衡二叉查找树,Java8中的hashmap就用到红黑树来优化它的查询效率,可见,红黑树的查询效率还是比较高的,但是为什么MySQL的底层不用红黑树而用B+数呢?
下图是红黑树依次插入1,2,3,4,5,6之后的情况:
然后再在上面的红黑树中插入7:
可以看到,尽管红黑树经过了自平衡,数据整体仍然偏向树的右侧,如果继续添加更多数据,添加的数据上百万、千万之后,树的层级将会非常高,查询时每多经过一层,就会多进行一次io,树的层级多了之后查找效率就会很慢。这个时候可能就会有人问了,那为什么不用平衡性更好的AVL树呢?
AVL树在一次插入1,2,3,4,5,6,7之后是这样的:
的确变顺眼了很多,树的层数也变少了,可AVL仍然没有解决根本问题,当数据量达到百万、千万之后,树的层数仍然会比较大,先不说AVL树维护平衡所需的代价,单论AVL树的层数就无法达到我们的要求。
那么什么样的数据结构可以让数据量达到百万,千万,甚至更大的体量时,层数仍然很小呢?很显然,想要减少层数,就必须要让每层储存的数据数更多,二叉树不管平衡性再好也只能做到每个节点有两个分叉,每层的数据量从数据结构被限制住了,那么,我们就不能从二叉树中选。所以这个时候B树的优势就体现出来了,B树每个节点可以存储多个元素,每个元素之间可以都可以拥有一个分叉,下图是B树每个节点最多可以存储3个元素的情况:
可以看到树的层级减小到两层,如果说每次每个节点最多可以存储的元素个数足够大,那么就算数据量达到上千万的量级,也可以将树的层级控制在一个可以接受的范围内。
但B树还有一个问题,下图展示的是B树层级达到三层时的情况:
如果现在我需要取出5-10号元素,当我通过层层查询,找到5号元素,然后发现其他元素不在这个节点,还需要通过局部中序遍历查询其他元素,找到7之后还需如此操作找到8,9,10,这又会增加io次数,所以也就有了B+树。
B+树是对B树的优化,主要是从两个地方进行优化的:
第一个优化是在每个叶子节点之间加上了一个双向指针,指向相邻节点,这样就解决了刚才的范围查询问题,范围查询如果跨了多个节点,就可以通过这个双向指针快速找到相邻节点,而不需要通过局部的中序遍历,从而减少了io次数。下图演示的是B+树:
但如果要找的元素不在叶子节点上呢?别担心,B+树的另一个优化就是的叶子节点包含了这颗树的所有元素!B+树的非叶子节点不再保存元素的data数据或者指针了,只是作为冗余的索引构成完整的B+树来方便查询。可以看到上图的15号元素不仅仅存在于非叶子节点中,也存在于叶子节点中。这样的设计虽然带来了很多冗余的索引,但是却让范围查询时不再需要向上查找非叶子节点了,而且每一层可以保存的索引数量变多了,让数据库每次io可以查询到更多的索引元素,毕竟在正常情况下,数据占的空间比索引占的空间要大很多。(需要注意的是,InnoDB和MyISAM引擎虽然都是用的B+树,但InnoDB的聚簇索引和数据是保存在一起的,而MyISAM是将聚簇索引和相应数据的指针保存在一起的,索引和数据是分开的。MyISAM引擎下的B+树也只有叶子节点才保存数据的指针)
由上面的分析我们可以知道,选用B+树作为MySQL的底层是为了减少io次数,那我们为什么不直接极端一点,使用hash来保存数据或者索引呢?其实MySQL确实支持hash类型的索引。
但是hash索引一般都不用,主要是因为hash索引的储存的是hash码,储存的顺序与索引列的值大小无关,所以只有在进行精确查找时hash索引才能生效,范围查询时会进行全表扫描。同时,如果表中的数据量非常大的话,发生hash碰撞的次数会增多,单个查找的效率不一定比B+树高。
简单总结一下,B+树相比其他树来说,每个节点可以存储更多元素,可以大大减少查询时需要的io次数,非叶子节点不存储数据或指针的设计可以提高每个节点存储元素的数量,叶子节点具有的双向指针可以提高范围查询的效率。
到这里,我们也就讲完了《MySQL底层数据结构选用B+树的原因》的内容了。个人认为,基础知识的学习和巩固,是为了更好的将其运用到项目中,欢迎关注golang学习网公众号,带你了解更多关于mysql的知识点!
-
339 收藏
-
285 收藏
-
259 收藏
-
374 收藏
-
475 收藏
-
483 收藏
-
462 收藏
-
469 收藏
-
289 收藏
-
239 收藏
-
315 收藏
-
361 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 508次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习
-
- 疯狂的乌龟
- 这篇技术文章真及时,太全面了,真优秀,码起来,关注up主了!希望up主能多写数据库相关的文章。
- 2023-04-26 00:25:44
-
- 重要的鲜花
- 真优秀,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,看完之后很有帮助,总算是懂了,感谢楼主分享技术贴!
- 2023-03-04 12:51:54
-
- 爱撒娇的吐司
- 赞 👍👍,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,帮助很大,总算是懂了,感谢up主分享博文!
- 2023-02-27 03:40:02
-
- 受伤的跳跳糖
- 这篇文章内容真及时,太详细了,赞 👍👍,码起来,关注up主了!希望up主能多写数据库相关的文章。
- 2023-02-20 01:04:05
-
- 开放的薯片
- 这篇文章太及时了,好细啊,感谢大佬分享,已收藏,关注up主了!希望up主能多写数据库相关的文章。
- 2023-02-10 16:22:35
-
- 大气的鸵鸟
- 受益颇多,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,看完之后很有帮助,总算是懂了,感谢作者大大分享文章!
- 2023-01-27 00:26:47
-
- 朴实的棒球
- 很详细,已收藏,感谢楼主的这篇技术贴,我会继续支持!
- 2023-01-19 23:53:44
-
- 现实的睫毛膏
- 受益颇多,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,帮助很大,总算是懂了,感谢博主分享文章!
- 2023-01-14 18:51:53
-
- 美好的煎蛋
- 这篇技术文章真及时,好细啊,太给力了,已加入收藏夹了,关注楼主了!希望楼主能多写数据库相关的文章。
- 2023-01-13 23:50:43
-
- 感动的小懒猪
- 这篇技术文章真及时,老哥加油!
- 2023-01-13 18:56:02