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

小恐龙
• 阅读 1787

平衡二叉树

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

(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,如有侵权,请联系删除。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
白茶清欢 白茶清欢
3年前
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树.....不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。你将会获得:1.如何使用js实现二叉查找树。2.学会前、中、后序遍历。3.了解相关实现原理阅读时长5min,可选择直接调试代码特点    二叉查找树中序遍历后
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
B+树原理以及Java代码实现
最初查找二叉树,由于树的高度会随着有序序列输入而急剧增长,后来出现平衡二叉树,红黑树。B树可以海量数据的快速查询检索,B树主要分为B树(B树),B树,B\树等。B树(B树)M路搜索树,参数M定义节点的分支个数;对于根节点孩子数目为\2,M\,对于其余节点孩子数目为\M/2,M\;每个节点含有关键字属性,至少M/21
Stella981 Stella981
3年前
LeetCode(110):平衡二叉树
Easy!题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树_每个节点_的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树 3,9,20,null,null,15,73/\920/
Wesley13 Wesley13
3年前
MySQL面试(二)
1、为什么索引遵循最左匹配原则?  当B树的数据项是符合的数据结构,比如(name,age,sex)的时候,B树是按照从左到右的顺序建立搜索树的。比如当(张三,20,F)这样的数据来检索的时候,b树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候
Stella981 Stella981
3年前
Android蓝牙连接汽车OBD设备
//设备连接public class BluetoothConnect implements Runnable {    private static final UUID CONNECT_UUID  UUID.fromString("0000110100001000800000805F9B34FB");
Wesley13 Wesley13
3年前
B
BTreeBTree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对23查找树的一种扩展。一个m阶的BTree有以下性质1.每个节点最多有m个子节点;2.每个非叶子节点(根节点除外)至少含有m/2个子节点;3.
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这
小恐龙
小恐龙
Lv1
步月如有意,情来不自禁。
文章
5
粉丝
0
获赞
0