彻底搞懂系列B-树、B+树、B-树、B*树

小恐龙 等级 304 0 0

平衡二叉树

  • 概念
    平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构;
  • 特点
    平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程有以下规则:

(1)非叶子节点只能允许最多两个子节点存在。

(2)每一个非叶子节点数据分布规则为左边的子节点小当前节点的值,右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的,比如hash值);

彻底搞懂系列B-树、B+树、B-树、B*树

平衡树的层级结构:因为平衡二叉树查询性能和树的层级(h高度)成反比,h值越小查询越快、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡,实现了这种算法的有比如Treap、红黑树,使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1.,通过这样避免树形结构由于删除增加变成线性链表影响查询效率,保证数据平衡的情况下查找数据的速度近于二分法查找;

彻底搞懂系列B-树、B+树、B-树、B*树
总结平衡二叉树特点:
(1)非叶子节点最多拥有两个子节点;
(2)非叶子节值大于左边子节点、小于右边子节点;
(3)树的左右两边的层级数相差不会大于1;
(4)没有值相等重复的节点;

B树

注意:之前有看到有很多文章把B树和B-tree理解成了两种不同类别的树,其实这两个是同一种树;

  • 概念
    B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),数据库索引技术里大量使用者B树和B+树的数据结构,让我们来看看他有什么特点;

  • 规则
    (1)排序方式:所有节点关键字是按递增次序排列,并遵循左小右大原则;
    (2)子节点数:非叶节点的子节点数>1,且<=M ,且M>=2,空树除外(注:M阶代表一个树节点最多有多少个查找路径,M=M路,当M=2则是2叉树,M=3则是3叉);
    (3)关键字数:枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
    (4)所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;
    最后我们用一个图和一个实际的例子来理解B树(这里为了理解方便我就直接用实际字母的大小来排列C>B>A)彻底搞懂系列B-树、B+树、B-树、B*树

  • B树查询流程
    如上图我要从上图中找到E字母,查找流程如下

(1)获取根节点的关键字进行比较,当前根节点关键字为M,E<M(26个字母顺序),所以往找到指向左边的子节点(二分法规则,左小右大,左边放小于当前节点值的子节点、右边放大于当前节点值的子节点);
(2)拿到关键字D和G,D<E<G 所以直接找到D和G中间的节点;
(3)拿到E和F,因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null);

  • B树插入节点流程
    定义一个5阶树(平衡5路查找树;),现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

遵循规则:

(1)节点拆分规则:当前是要组成一个5路查找树,那么此时m=5,关键字数必须<=5-1(这里关键字数>4就要进行节点拆分);
(2)排序规则:满足节点本身比左边节点大,比右边节点小的排序规则;
先插入 3、8、31、11
彻底搞懂系列B-树、B+树、B-树、B*树
再插入23、29
彻底搞懂系列B-树、B+树、B-树、B*树
再插入50、28
彻底搞懂系列B-树、B+树、B-树、B*树
-B树节点删除
规则:
(1)节点合并规则:当前是要组成一个5路查找树,那么此时m=5,关键字数必须大于等于ceil(5/2)(这里关键字数<2就要进行节点合并);

(2)满足节点本身比左边节点大,比右边节点小的排序规则;

(3)关键字数小于二时先从子节点取,子节点没有符合条件时就向向父节点取,取中间值往父节点放;
彻底搞懂系列B-树、B+树、B-树、B*树

特点:

B树相对于平衡二叉树的不同是,每个节点包含的关键字增多了,特别是在B树应用到数据库中的时候,数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的,每个块的大小为4K,每次IO进行数据读取时,同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围;把树的节点关键字增多后树的层级比原来的二叉树少了,减少数据查找的次数和复杂度;

B+树

  • 概念
    B+树是B树的一个升级版,相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定;我们先看看两者的区别

  • 规则
    (1)B+跟B树不同B+树的非叶子节点不保存关键字记录的指针,只进行数据索引,这样使得B+树每个非叶子节点所能保存的关键字大大增加;
    (2)B+树叶子节点保存了父节点的所有关键字记录的指针,所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样;
    (3)B+树叶子节点的关键字从小到大有序排列,左边结尾数据都会保存右边节点开始数据的指针。
    (4)非叶子节点的子节点数=关键字数(来源百度百科)(根据各种资料 这里有两种算法的实现方式,另一种为非叶节点的关键字数=子节点数-1(来源维基百科),虽然他们数据排列结构不一样,但其原理还是一样的Mysql 的B+树是用第一种方式实现);
    彻底搞懂系列B-树、B+树、B-树、B*树百度百科示意图
    彻底搞懂系列B-树、B+树、B-树、B*树维基百科示意图

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

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

3、B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。
4、B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。

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

B* 树

  • 规则
    B*树是B+树的变种,相对于B+树他们的不同之处如下:

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

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

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

B树总结

1、相同思想和策略
从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的,都是采用二分法和数据平衡策略来提升查找数据的速度;

2、不同的方式的磁盘空间利用
不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变,每一次演变都是为了让节点的空间更合理的运用起来,从而使树的层级减少达到快速查找数据的目的;
如果还没理解的话推荐以下资料描叙的很详细:

本文转自 https://blog.csdn.net/chai471793/article/details/99563704,如有侵权,请联系删除。

收藏
评论区

相关推荐

4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下 PriorityQueue 的原理 以最大堆为例来介绍 1. PriorityQueue是用一棵完全二叉树实现的。 2. 不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大 3. PriorityQueue底层是用数组来保存这棵完全二叉树的。 如下图,是一棵最大堆。
前端学数据结构与算法:二叉树的四种遍历方式及其应用
前言 上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这
JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:) (https://imghelloworld.osscnbe
彻底搞懂系列B-树、B+树、B-树、B*树
(https://blog.csdn.net/chai471793/article/details/99563704)平衡二叉树 概念 平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构; 特点 平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大
算法笔记:B树
B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树: btree(https://imghelloworld.osscnbeijing.aliyuncs.com/imgs/ae3caa193bc4c55f0519114b15313721.png) B树当中每个节点存储
二叉树题集(持续更新中)
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。 1\. 求二叉搜索树最大深度输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。输入样例:8 6 8 5 10 9 11 0输出样例:4常规的求二叉搜索树深度的做法是递
【Flutter实战】布局类组件简介
4.1 布局类组件简介布局类组件都会包含一个或多个子组件,不同的布局类组件对子组件排版(layout)方式不同。我们在前面说过Element树才是最终的绘制树,Element树是通过Widget树来创建的(通过Widget.createElement()),Widget其实就是Element的配置数据。在Flutter中,根据Widget是否
二叉树创建后,如何使用递归和栈遍历二叉树?
0. 前言前文主要介绍了树的相关概念和原理,本文主要内容为二叉树的创建及遍历的代码实现,其中包括递归遍历和栈遍历。 1. 二叉树的实现思路 1.0. 顺序存储——数组实现前面介绍了满二叉树和完全二叉树,我们对其进行了编号——从 0 到 n 的不中断顺序编号,而恰好,数组也有一个这样的编号 —— 数组下标,只要我们把二者联合起来,数组就能存储二叉树了。那么非满
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树..... 不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。 你将会获得: 1.如何使用js实现二叉查找树。 2.学会前、中、后序遍历。 3.了解相关实现原理 阅读时长5min,可选择直接调试代码 特点    二叉查找树中序遍历后
线索二叉树的原理及创建
【系列推荐阅读】 1. 为什么要用到线索二叉树?我们先来看看普通的二叉树有什么缺点。下面是一个普通二叉树(链式存储方式):乍一看,会不会有一种违和感?整个结构一共有 7 个结点,总共 14 个指针域,其中却有 8 个指针域都是空的。对于一颗有 n 个结点的二叉树而言,总共会有 n+1 个空指针域,这个规律使用所有的二叉树。这么多的空指针域是不
用C语言的递归写个二叉搜索树(二叉排序树)
不会递归的程序员不是好程序员,虽然鄙人尚未毕业,是个无知的大学生。但这追去真理的上进心不可小量。二叉树的每一个节点,与其左右子树都可以组成一个二叉树,利用这思路,可以写个递归形式的二叉树。cinclude<stdio.hinclude<stdlib.htypedef struct treeNode int data; struct treeNode Left
动图图解二叉查找树的基本原理及其实现
本文为系列专题的第 12 篇文章。1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1. 是什么?二叉查找树(Binary Search Tree)必须满足以下特点: 若左子树不为空,则左子树的所有结点值皆小于根结点值 若右子树不为空,则右子树的所有结点值皆大于根结点值 左右子树也是二叉排序树如下图,是一颗二叉查找树:如果你对二叉查找树进行中序
Vue - diff 算法
diff是什么?diff就是比较两棵树,render会生成两颗树,一棵新树newVnode,一棵旧树oldVnode,然后两棵树进行对比更新找差异就是diff,全称difference,在vue里面 diff 算法是通过patch函数来完成的,所以有的时候也叫patch算法⏳ diff 发生的时机diff发生在什么时候呢?当然我们可以说在数据更新的时候发生d
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo