从二叉查找树到B*树,一文搞懂搜索树的演进!|金三银四系列

对于准备面试这篇再适合不过了!详细讲解了从BST、AVL、红黑树、B树、B+树最后到B*树的演进过程,以及各种结构的优劣。

点击上方“后端开发技术”,选择“设为星标” ,优质资源及时送达

在面试中,面试官很容易抛出这样的问题:为什么MySQL多种数据引擎要用B+树不用别的数据结构呢?为什么红黑树结构在计算机中内存中被广泛应用?

如果你没有这样体系性的思考过这些问题,那非常应该看这篇文章。

本文将从二分查找说起,详细讲解搜索树型结构针对特定问题而产生的演进,让你知其然更知其所以然。

二分查找

对于查找数据,不得不提的一种基础算法就是二分法,很多数据结构的查找算法核心思想都是二分法,其查找效率也经常会用来和二分法来做对比。二分法的时间复杂度为O(logN),这是一个非常优秀的时间复杂度,其效率仅次于常数时间复杂度 O(1)。

二分查找的实现思路是这样的:

  1. 对数据集进行排序

  2. 找到数据集的中间节点,判断是否为查找的值,等于直接返回。

  3. 根据与中间节点大小的比较结果,确定收缩查找区间范围是中间节点的左边还是右边。

  4. 重复上述 2、3 过程继续查找。

从其实现思路来看,有两个点很重要:一是可以保证数据的有序性,二是适合进行数据分段存储,方便缩小区间查找。所以根据这种思路,演化出了两个不同的路线,树和跳表两种数据结构。

二叉搜索树BST

二叉搜索树(BST,Binary Search Tree)(又叫二叉查找树)是一棵空树,或者是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值

  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值

  • 它的左、右子树也分别为二叉排序树。

7c1bff9807c62a53751236def2d4f334.png

二叉搜索树的问题

二叉搜索树符合了使用二分法查询数据的要求,但是有个问题:因为插入顺序的不同,二叉树的高度不稳定,极端情况下可能变成链表(就是插入的数据是有序的,递增或者递减)。这就成了线性查询,时间复杂度最多变成O(n),查询效率不稳定。

为了解决这个问题,就产生了各种树的平衡算法,保证树的节点高度不会差太多。所以就有了AVL树(平衡二叉树)和红黑树等新的数据结构。

AVL树

平衡二叉树全称叫做平衡二叉搜索(排序)树,AVL树是最早的平衡二叉树之一。

为了解决一般的二叉搜索树存在的问题,即根节点到叶子结点的高度相差太多,查询效率不问题,并且极端情况有成为链表的可能。所以AVL树具有以下特点:

  • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,

  • 左右两个子树 也都是一棵平衡二叉树。

在AVL树中,任何节点的两个子树的高度最大差别为 1 ,所以它也被称为平衡二叉树 。

6e12b88cac75347d8381b57fbd332883.png

AVL树查找、插入和删除在平均和最坏情况下都是O(LogN)。

AVL 什么意思 ?AVL 是大学教授 G.M. Adelson-Velsky 和 E.M. Landis 名称的缩写,他们提出的平衡二叉树的概念,为了纪念他们,将 平衡二叉树 称为 AVL树。

与普通二叉搜索树的区别的是,它在插入和删除节点的时候,会根据需要进行左旋或者右旋,来保证二叉树的平衡,示意图如下。这不是本文的讨论重点,感兴趣自己可以研究。

917ee754125db1ab064b0efd296c16e9.gif 7e338867648a7e395b331a0d06da2419.gif

AVL树的问题

AVL树高度的平衡情况固然很好,但这是有代价的。为了维持平衡,其旋转是非常耗时的。

AVL实现平衡的关键在于旋转操作:插入和删除可能破坏二叉树的平衡,此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时,最多只需要两次旋转(单旋转或双旋转);但是当删除数据时,会导致树失衡,AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡,旋转的量级为O(lgn)。

由于旋转的耗时,AVL树在删除数据时效率很低;在删除操作较多时,维护平衡所需的代价可能高于其带来的好处,因此AVL实际使用并不广泛。

场景:windows对进程地址空间的管理用到了AVL树。

针对于这种情况,红黑树对其做了优化。

红黑树RB-Tree

红黑树是一种自平衡的二叉查找树,是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明,在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率,它可在 O(logN) 时间内完成查找、增加、删除等操作。

红黑树是一种接近平衡的二叉树(说它是接近平衡因为它并没有像AVL树的平衡因子的概念,它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构,进而提升整体的性能,并没有严格的卡定某个平衡因子来维持绝对平衡)。

特性

一棵红黑树同时满足以下特性:

  • 节点是红色或黑色

  • 根是黑色

  • 叶子节点(外部节点,空节点)都是黑色,这里的叶子节点指的是最底层的空节点(外部节点),下图中的那些null节点才是叶子节点,null节点的父节点在红黑树里不将其看作叶子节点

  • 红色节点的子节点都是黑色

    • 红色节点的父节点都是黑色

    • 从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点

  • 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

70b5fea3a4e9e3a988c66a04fee7ae1c.png

红黑树的查找,插入和删除操作,时间复杂度都是O(logN)。

红黑树解决了AVL树什么问题

  1. AVL的左右子树高度差不能超过1,每次进行插入/删除操作时,几乎都需要通过旋转操作保持平衡

  2. 在频繁进行插入/删除的场景中,频繁的旋转操作使得AVL的性能大打折扣

  3. 红黑树通过牺牲严格的平衡,换取插入/删除时少量的旋转操作,整体性能优于AVL。红黑树插入时的不平衡,不超过两次旋转就可以解决;删除时的不平衡,不超过三次旋转就能解决

  4. 红黑树的红黑规则,保证最坏的情况下,也能在O(log 2N)时间内完成查找操作。

红黑树和AVL树的效率对比:

  1. 如果插入一个node引起了树的不平衡,AVL树和红黑树都是最多只需要2次旋转操作,即两者都是O(1);但是在删除node引起树的不平衡时,最坏情况下,AVL需要维护从被删node到root这条路径上所有node的平衡性,因此需要旋转的量级O(logN),而红黑树最多只需3次旋转,只需要O(1)的复杂度。

  2. 其次,AVL树的结构相较红黑树来说更为平衡,在插入和删除node更容易引起Tree的不平衡,因此在大量数据需要插入或者删除时,AVL需要rebalance的频率会更高。因此,红黑树在需要大量插入和删除node的场景下,效率更高。自然,由于AVL高度平衡,因此AVL的search效率更高。

  3. map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说,红黑树的统计性能是高于AVL的。

最坏情况下,AVL树有最多O(logN)次旋转,而红黑树最多三次。

场景:

红黑树的应用就很多了。

  • epoll在内核中的实现,用红黑树管理事件块。

  • nginx中,用红黑树管理timer等。

  • Java1.8版本后的的hashMap中使用链表+红黑树解决哈希冲突问题,Java中的TreeMap使用红黑树存储排序键值对。

  • 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。

红黑树的问题

虽然红黑树是一种已经被性能优化了的自平衡的二叉查找树,插入修改效率和查找销量得到了平衡,但他依然存在一些问题。

  1. 依旧在插入和删除时需要对节点进行旋转,频繁修改数据的场景影响效率。

  2. 红黑树毕竟是一种二叉树,当数据量很大时,树的高度会变得很大,查找时经过的节点过多,效率变低。

  3. 红黑树在内存中表现优秀,但因为树的高度的问题,当使用磁盘等辅助存储设备读写数据时(如MySQL等数据库),会导致数据在磁盘中散布分散,并且IO次数过多,效率变低。

  4. 适合单个查询,对于数据查询中常见的范围查询场景,无法很好支持。

针对于上述问题,有了天生为磁盘存储而生的B树。

B树

B树是一种多路搜索树,又名平衡多路查找树(查找路径不只两个),与二叉树相比,B树的每个非叶节点可以有多个子树。因此,当总节点数量相同时,B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”),磁盘IO次数大大减少。数据库索引技术里大量使用者B树和B+树的数据结构。

定义B树最重要的概念是阶数(Order),对于一颗m阶B树(就是一个节点最多包含几个子节点),需要满足以下条件:

  • 每个节点最多包含 m 个子节点。

  • 如果根节点包含子节点,则至少包含 2 个子节点;除根节点外,每个非叶节点至少包含 m/2 个子节点。

  • 拥有 k 个子节点的非叶节点将包含 k - 1 条记录。

  • 所有叶节点都在同一层中。

度数:在树中,每个节点的子节点(子树)的个数就称为该节点的度 (degree)。

阶数:阶(order)定义为一个节点最多可以有多少个元素。

如下图,这是一个2阶3度的B树。

e2265044bc91043b5eff354cf4a126e2.png

场景:MongoDB索引。

B树的优势

B树相对平衡二叉树在节点空间的利用率上进行改进,B树在每个节点保存更多的数据,减少了树的高度,从而提升了查找的性能。

B树的优势除了树高小,还有对访问局部性原理的利用。

所谓局部性原理,是指当一个数据被使用时,其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点,当访问其中某个数据时,数据库会将该整个节点读到缓存中;当它临近的数据紧接着被访问时,可以直接在缓存中读取,无需进行磁盘IO;换句话说,B树的缓存命中率更高。

在数据库应用中,B树的每个节点存储的数据量大约为4K, 这是因为考虑到磁盘数据存储是采用块的形式存储的,每个块的大小为4K,每次对磁盘进行IO数据读取时,同一个磁盘块的数据会被一次性读取出来,所以每一次磁盘IO都可以读取到B树中一个节点的全部数据。

对于顺数插入的数据,B树的结构优势可以使其在内存中顺序排列,存贮到同一个磁盘页中,顺序插入对磁盘的利用率和读取效率都非常友好。

场景:MySQL的InnbDB 索引。

B树的问题

B树虽然解决了磁盘存储的问题,但是在查询范围数据时依旧不够优秀,比如你要查询1-5的数据,必须按照树的中顺遍历来访问各个节点。

对于这个问题,B+树对其进行了优化。

B+树

B+树是在B树的基础上又一次的改进,其主要对两个方面进行了提升,一方面是查询的稳定性,另外一方面是在数据排序方面更友好。

B+树也是多路平衡查找树,其特性主要有以下4点:

  • B树中每个节点(包括叶节点和非叶节点)都存储真实的数据,B+树中只有叶子节点存储真实的数据,非叶节点只存储键。在MySQL中,这里所说的真实数据,可能是行的全部数据(如Innodb的聚簇索引),也可能只是行的主键(如Innodb的辅助索引),或者是行所在的地址(如MyIsam的非聚簇索引)。

  • B树中一条记录只会出现一次,不会重复出现,而B+树的键则可能重复重现——一定会在叶节点出现,也可能在非叶节点重复出现。

  • B+树的叶节点之间通过双向链表链接。B+树叶子节点的关键字从小到大有序排列,左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的,所以B+树对于数据的排序有着更好的支持。

  • B+树非叶子节点的子节点数=关键字数,或者非叶节点的关键字数=子节点数-1(这里有两种算法的实现方式),虽然他们数据排列结构不一样,但其原理还是一样的Mysql 的B+树是用第一种方式实现)。

第一种算法:

389d5fc1408bcf4cc3ce1de0c025693c.png

第二种算法:

3bcac9c7e2ca723280ea09b7e2b0050f.png

B+树和B树的对比

1、B+树的层级更少:相较于B树B+每个非叶子节点存储的关键字数更多,所以每个磁盘块存储的数据更多,树的层级更少所以查询数据更快

2、B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定

3、B+树天然具备排序功能:所有关键字都出现在叶子结点的链表中(稠密索引),B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。

4、B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

B树相对于B+树的优点是,如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。

5、B+树更适合文件索引系统

B+树的缺点

在B+树的构建过程中,为了保持树的平衡,节点的合并拆分是比较耗费时间的,所以B*树就是在如何减少构建中节点合并和拆分的次数,从而提升树的数据插入、删除性能。

B*树

相对于B+树,B*树的不同之处如下:

(1)首先是关键字个数限制问题,B+树初始化的关键字初始化个数是cei(m/2),b树的初始化个数为(cei(2/3m))

(2)B+树节点满时就会分裂,而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),如果兄弟节点未满则向兄弟节点转移关键字,如果兄弟节点已满,则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来;

  • B*树 与B+树对比

在B+树的基础上因其初始化的容量变大,使得节点空间使用率更高,而又存有兄弟节点的指针,可以向兄弟节点转移关键字的特性使得B*树额分解次数变得更少。

348294e9d0325cdf7177e9029842daed.png

总结

对于上述的演进过程,这里给出一个简要总结,如下图。建议收藏!

7a0689ec3c7e880adb1918134d272037.png

加入讨论群是升职加薪第一步!

回复:加群

28aebedcc42a4995efd0b598e88fc6ff.jpeg

点赞是一种美德,如对您有帮助,欢迎评论和分享,感谢阅读!

面试官:会SQL调优,那你知道索引合并吗?|金三银四系列

2023-03-21

a6dd17c0f07f1cfb7274836625152f71.jpeg

CAP、BASE理论真的很重要!|分布式事务系列(一)

2023-03-17

2a55ee793f1bf3ec5ad9df68d6de475a.jpeg

面试官:你是如何预防多线程死锁的?|金三银四系列

2023-03-16

7fad7585c66cad34e77d04396e098a0d.jpeg

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/4499.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java设计模式-2、⼯⼚模式

⼯⼚模式 工厂模式是对简单工厂的一个衍生,解决了许多简单工厂模式的问题。 一、说⼀说简单⼯⼚模式 简单⼯⼚模式指由⼀个⼯⼚对象来创建实例,客户端不需要关注创建逻 辑,只需提供传⼊⼯⼚的参数。 适⽤于⼯⼚类负责创建对象较少的情况&a…

wait讲解

hello啊,今天为大家带来wait的相关介绍 开始正题之前,我们要先进行一点知识点的补充 上一期我们更新了一期关于线程安全的知识,对于volatile在这里在做出一些补充 有些文章上说线程修改一个变量的时候,从主内存读取到工作内存上,在工作内存上修改完以后再返回主内存 由于t1线程…

[数据库原理与应用]educoder-MySQL 单表查询(一)

目录 第1关:用like匹配字符串 第2关:用BETWEEN AND表达查询范围 第3关:空值的判断 第4关:集合运算符IN的应用 第5关:消除重复结果 第6关:聚合函数应用 第7关:分组查询 第8关&#xf…

基于GPT3.5实现本地知识库解决方案-利用向量数据库和GPT向量接口-实现智能回复并限制ChatGPT回答的范围...

标题有点长,但是基本也说明出了这篇文章的主旨,那就是利用GPT AI智能回答自己设置好的问题 既能实现自己的AI知识库机器人,又能节省ChatGPT调用的token成本费用。 代码仓库地址 document.ai: 基于GPT3.5的通用本地知识库解决方案 下面图片是整…

【数据分析实战】基于python对Airbnb房源进行数据分析

文章目录📚引言📖数据加载以及基本观察📃缺失值观察及处理🔖缺失值观察以及可视化🔖缺失值处理📃异常值观察及处理📖数据探索💡哪个区域的房源最受欢迎?💡哪种…

完全二叉树的4种遍历方式

一张二叉树的图 1&#xff0c;二叉树的特点 每个点p的左儿子是p*2,右儿子是p*21&#xff0c;可以分别表示为p<<1与p<<1|1节点的序号是从左到右&#xff0c;从上到下增加的每个点至多2个儿子&#xff08;屁话&#xff08;bushi&#xff09;&#xff09; 2&#xff…

C语言自定义数据类型(六)使用枚举类型

目录 一、定义 二、详解 三、举例说明 一、定义 如果一个变量只有几种可能的值&#xff0c;则可以定义为枚举 (enumeration) 类型&#xff0c;所谓 “ 枚举 ” 就是指把可能的值一一列举出来&#xff0c;变量的值只限于列举出来的值的范围内。 声明枚举类型用 enum 开头。…

UR5 D-H信息 | UR5结构图 | UR5连杆名关节名 | UR5模型信息 | UR5 UDFR信息

这个问题遇到好多次了&#xff0c;不管是仿真还是可视化&#xff0c;都需要我清楚的掌握ur5的URDF信息。但是看官网的Ur5.urdf真的是看的迷迷糊糊的&#xff0c;总是无法把ur5机器人的某个部位和她的名字对应起来。之前都搞不太明白&#xff0c;今天好好整理一下&#xff0c;分…

工赋开发者社区 | 做好生产线的规划与布局,能给工厂带来什么好处?

导读工厂规划布局就是对设备、工作台、物料、工装、半成品、水、电、气等的综合配置&#xff0c;主要是研究工序之间、车间之间以及工厂整体配置的合理性&#xff0c;以达到整个生产系统的人流与物流畅通化、搬运最优化、流程最优化、效率最大化的目标。“想优化工厂空间&#…

NIO Reactor模型(含代码)

概览 我们知道NIO就是调用系统内核的的select/poll/epoll方法来实现&#xff0c;这些系统内核方法会扫描或监控IO&#xff0c;每次将所有的IO的状态返回给NIO线程。让NIO线程可以选择处理读取可读状态的IO流&#xff0c;也可以选择继续监控轮询监控IO的其它状态。 reactor模型也…

【web前端开发】超详细讲解CSS盒子模型

文章目录1.盒子模型介绍2.内容3.边框4.内边距5.⭐盒子大小计算6.⭐内减模式7.外边距外边距的合并外边距的塌陷行内元素的垂直外边距8.⭐清除默认样式9.⭐版心居中1.盒子模型介绍 所有HTML元素可以看作盒子,CSS盒模型本质上是一个盒子&#xff0c;封装周围的HTML元素&#xff0c…

C#多线程锁

背景&#xff1a;再一次测试中用户和我几乎同一时刻&#xff08;不知道谁先谁后&#xff0c;估计间隔在毫秒级&#xff09;操作了系统。 用户那边反馈显示的操作日志是我登录的信息。于是开始查找问题。首先排除了全局变量先后操作被覆盖的原因。首先A账户登录&#xff0c;然后…

基于stm32mp157 linux开发板ARM裸机开发教程3:Cortex-A7 架构与工作模式(连载中)

前言&#xff1a; 目前针对ARM Cortex-A7裸机开发文档及视频进行了二次升级持续更新中&#xff0c;使其内容更加丰富&#xff0c;讲解更加细致&#xff0c;全文所使用的开发平台均为华清远见FS-MP1A开发板&#xff08;STM32MP157开发板&#xff09; 针对对FS-MP1A开发板&…

用 ChatGPT 尝试 JavaScript 交互式学习体验,有用但不完美

很好&#xff0c;但还不能取代专家导师&#xff0c;有时还会犯错&#xff01;ChatGPT 教小狗编程&#xff08; Midjourney 创作&#xff09;GPT-4刚刚发布&#xff0c;相较于GPT-3.5&#xff0c;它有显著的增强功能。其中之一是它在更长时间的交互和更大的提示下&#xff0c;能…

Pytorch环境配置 完整流程 从CUDA和cuDNN到Torch安装

目录1. 安装CUDA2. 安装cuDNN3. 安装Pytorch1. 安装CUDA 确认需要的CUDA版本 nvidia-smi 下载CUDA.exe CUDA下载地址 结合自己电脑的情况下载对印度个版本 安装 双击后安装&#xff0c;可以修改安装路径&#xff0c;我安装在了D盘 安装方式选择自定义 全部勾选 这里如果电脑没…

nnAudio的简单介绍

官方实现 https://github.com/KinWaiCheuk/nnAudio&#xff1b; 论文实现&#xff1a; nnAudio: An on-the-Fly GPU Audio to Spectrogram Conversion Toolbox Using 1D Convolutional Neural Networks&#xff1b; 以下先对文章解读&#xff1a; abstract 在本文中&#x…

美国站针对磁铁产品新政策16 CFR 1262详解

近日&#xff0c;亚马逊美国站公布磁铁产品&#xff08;不包括玩具&#xff09;的新政策更新公告&#xff0c;公告如下&#xff1a; 公告显示&#xff0c;由于美国消费品安全委员会&#xff08;US Consumer Product Safety Commission&#xff09;出台了新的安全规定&#xff…

海王算法(看完不会变成海王)

&#x1f4a7;学了海王算法会变成海王吗&#xff0c;它又能解决什么样的问题呢&#xff1f;&#x1f4a7; &#x1f337; 仰望天空&#xff0c;妳我亦是行人.✨ &#x1f984; 个人主页——微风撞见云的博客&#x1f390; &#x1f433; 数据结构与算法专栏的文章图文…

内存池解释及线程池(Linux)实现

1.内存池1.什么是内存池内存池是一种内存分配方式。在真正使用内存之前&#xff0c;先申请分配一定数量的、大小相等的内存块留作备用。当有新的内存需求时&#xff0c;就从内存池中分出一部分内存块&#xff0c;若内存块不够再继续申请新的内存。使用内存池的优点有&#xff1…

Pyspark_SQL3

Pyspark 注&#xff1a;大家觉得博客好的话&#xff0c;别忘了点赞收藏呀&#xff0c;本人每周都会更新关于人工智能和大数据相关的内容&#xff0c;内容多为原创&#xff0c;Python Java Scala SQL 代码&#xff0c;CV NLP 推荐系统等&#xff0c;Spark Flink Kafka Hbase Hi…
最新文章