您当前的位置:首页 > 电脑百科 > 程序开发 > 架构

什么是B+树,这下懂了... | 干货分享

时间:2021-09-07 11:20:02  来源:今日头条  作者:老张聊架构
什么是B+树,这下懂了... | 干货分享

 


什么是B+树,这下懂了... | 干货分享

 


什么是B+树,这下懂了... | 干货分享

 


什么是B+树,这下懂了... | 干货分享

 

B+树是很基础的概念,也是面试里面的常考题,一定要掌握。今天我们就来聊聊这个话题。

要弄明白B+数,首先要了解B-树

B-树就是B树,中间的横线不是减号。千万别念成:B减树,那就丢人现眼了

什么是B+树,这下懂了... | 干货分享

 


什么是B+树,这下懂了... | 干货分享

 

既然这样,为什么索引不直接使用二叉树来实现呢?二叉树的查询复杂度是O(logN),性能已经足够高,难道B-树可以更快?

其实从算法上进,二叉树确实可以。但是,我们不得不考虑一个现实问题:

什么是B+树,这下懂了... | 干货分享

 

数据库索引是存储在磁盘上的,当数据量比较大时,索引的大小可能有几个G,甚至更多。

当我们利用索引查询时,不可能把索引全部加载到内存里。只能逐一加载每一个磁盘页。这里的磁盘页对应着索引树的节点。

什么是B+树,这下懂了... | 干货分享

 

如果我们使用二叉树,会怎么样呢?假设树的高度是4,要查找的值是10,那么流程如下:

什么是B+树,这下懂了... | 干货分享

 

第1次磁盘IO:

什么是B+树,这下懂了... | 干货分享

 

第2次磁盘IO:

什么是B+树,这下懂了... | 干货分享

 

第3次磁盘IO:

什么是B+树,这下懂了... | 干货分享

 

第4次磁盘IO:

什么是B+树,这下懂了... | 干货分享

 

我们可以看到:磁盘的IO次数,是由树的高度决定的

既然如此,为了减少磁盘IO次数,我们就需要把原本“瘦高”的树,变得“矮胖”一些,这就是B-树。

什么是B+树,这下懂了... | 干货分享

 

B树是一种多路平衡查找树,它的一个节点最多包含K个孩子,K称为树的阶。这里,K的大小取决于磁盘页的大小。

下面具体介绍一下B-树(Balance Tree),一个K阶的B-树具有以下几个特征:

(1)根结点至少有两个孩子。

(2)每个中间节点都包含m-1个元素和m个孩子,其中 k/2 <= m <= k

(3)每一个叶子节点都包含m-1个元素,其中 k/2 <= m <= k

(4)所有的叶子结点都位于同一层。

(5)每个节点中的元素从小到大排列,节点当中m-1个元素正好是m个孩子包含的元素的值域分划。

什么是B+树,这下懂了... | 干货分享

 

我们以一个3阶的B-数为例,来看一下B-树的具体结构。树中的具体元素和刚才的二叉树一样。

什么是B+树,这下懂了... | 干货分享

 

我们重点看一下(2, 6)这个节点。该节点有2和6两个元素。又有3个孩子:1,(3, 5)和8。其中 1 < 2,(3, 5)在2, 6之间,8大于(3, 5)。刚好符合上面的几条特征。

什么是B+树,这下懂了... | 干货分享

 


什么是B+树,这下懂了... | 干货分享

 

假设要查询的值是5:

第1次磁盘IO:

什么是B+树,这下懂了... | 干货分享

 

在内存中定位(和9比较):

什么是B+树,这下懂了... | 干货分享

 

第2次磁盘IO:

什么是B+树,这下懂了... | 干货分享

 

在内存中定位(和2,6比较):

什么是B+树,这下懂了... | 干货分享

 

第3次磁盘IO:

什么是B+树,这下懂了... | 干货分享

 

在内存中定位(和3,5比较):

什么是B+树,这下懂了... | 干货分享

 

可以看出,B-树在查找中的比较次数其实不比二叉数少,尤其是当单一节点中的元素数量很多时。但是,相对比磁盘IO的速度,内存的比较耗时可以忽略不计。所以,只要数的高度足够低,IO次数足够少,就可以提高查找性能!

至于节点内部的元素数量,多一点无非是多几次内存计算,只要不超过磁盘页大小就可以。这就是B-树最核心的思想!

什么是B+树,这下懂了... | 干货分享

 


什么是B+树,这下懂了... | 干货分享

 

B-树主要应用于文件系统,另外非关系型数据库MongoDB,就使用了B-树来做索引。

而大部分关系型数据库,比如MySQL,则使用B+树来做索引,关于B+树,我们明天接着聊!



Tags:B+树   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
B+树是很基础的概念,也是面试里面的常考题,一定要掌握。今天我们就来聊聊这个话题。要弄明白B+数,首先要了解B-树B-树就是B树,中间的横线不是减号。千万别念成:B减树,那就...【详细内容】
2021-09-07  Tags: B+树  点击:(80)  评论:(0)  加入收藏
Mysql索引数据结构下面列举了常见的数据结构 二叉树 红黑树 Hash表 B-Tree(B树)Select * from t where t.col=5我们在执行一条查询的Sql语句时候,在数据量比较大又不加索引的情...【详细内容】
2021-06-07  Tags: B+树  点击:(90)  评论:(0)  加入收藏
上一次吊打各种树这篇文章 堂主柠檬带大家学习一遍数据结构中的各种树,对数据结构还不够熟悉的同学,那篇文章可以作为基础入门,我画了很多图理解起来不困难,建议回头先学习下那...【详细内容】
2020-11-23  Tags: B+树  点击:(130)  评论:(0)  加入收藏
索引是一种用于快速查询行的数据结构,就像一本书的目录就是一个索引,如果想在一本书中找到某个主题,一般会先找到对应页码。在mysql中,存储引擎用类似的方法使用索引,先在索引中...【详细内容】
2019-09-05  Tags: B+树  点击:(277)  评论:(0)  加入收藏
▌简易百科推荐
为了构建高并发、高可用的系统架构,压测、容量预估必不可少,在发现系统瓶颈后,需要有针对性地扩容、优化。结合楼主的经验和知识,本文做一个简单的总结,欢迎探讨。1、QPS保障目标...【详细内容】
2021-12-27  大数据架构师    Tags:架构   点击:(3)  评论:(0)  加入收藏
前言 单片机开发中,我们往往首先接触裸机系统,然后到RTOS,那么它们的软件架构是什么?这是我们开发人员必须认真考虑的问题。在实际项目中,首先选择软件架构是非常重要的,接下来我...【详细内容】
2021-12-23  正点原子原子哥    Tags:架构   点击:(7)  评论:(0)  加入收藏
现有数据架构难以支撑现代化应用的实现。 随着云计算产业的快速崛起,带动着各行各业开始自己的基于云的业务创新和信息架构现代化,云计算的可靠性、灵活性、按需计费的高性价...【详细内容】
2021-12-22    CSDN  Tags:数据架构   点击:(10)  评论:(0)  加入收藏
▶ 企业级项目结构封装释义 如果你刚毕业,作为Java新手程序员进入一家企业,拿到代码之后,你有什么感觉呢?如果你没有听过多模块、分布式这类的概念,那么多半会傻眼。为什么一个项...【详细内容】
2021-12-20  蜗牛学苑    Tags:微服务   点击:(8)  评论:(0)  加入收藏
我是一名程序员关注我们吧,我们会多多分享技术和资源。进来的朋友,可以多了解下青锋的产品,已开源多个产品的架构版本。Thymeleaf版(开源)1、采用技术: springboot、layui、Thymel...【详细内容】
2021-12-14  青锋爱编程    Tags:后台架构   点击:(20)  评论:(0)  加入收藏
在了解连接池之前,我们需要对长、短链接建立初步认识。我们都知道,网络通信大部分都是基于TCP/IP协议,数据传输之前,双方通过“三次握手”建立连接,当数据传输完成之后,又通过“四次挥手”释放连接,以下是“三次握手”与“四...【详细内容】
2021-12-14  架构即人生    Tags:连接池   点击:(16)  评论:(0)  加入收藏
随着移动互联网技术的快速发展,在新业务、新领域、新场景的驱动下,基于传统大型机的服务部署方式,不仅难以适应快速增长的业务需求,而且持续耗费高昂的成本,从而使得各大生产厂商...【详细内容】
2021-12-08  架构驿站    Tags:分布式系统   点击:(23)  评论:(0)  加入收藏
本系列为 Netty 学习笔记,本篇介绍总结Java NIO 网络编程。Netty 作为一个异步的、事件驱动的网络应用程序框架,也是基于NIO的客户、服务器端的编程框架。其对 Java NIO 底层...【详细内容】
2021-12-07  大数据架构师    Tags:Netty   点击:(16)  评论:(0)  加入收藏
前面谈过很多关于数字化转型,云原生,微服务方面的文章。虽然自己一直做大集团的SOA集成平台咨询规划和建设项目,但是当前传统企业数字化转型,国产化和自主可控,云原生,微服务是不...【详细内容】
2021-12-06  人月聊IT    Tags:架构   点击:(23)  评论:(0)  加入收藏
微服务看似是完美的解决方案。从理论上来说,微服务提高了开发速度,而且还可以单独扩展应用的某个部分。但实际上,微服务带有一定的隐形成本。我认为,没有亲自动手构建微服务的经历,就无法真正了解其复杂性。...【详细内容】
2021-11-26  GreekDataGuy  CSDN  Tags:单体应用   点击:(35)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条