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

小恐龙 等级 664 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,如有侵权,请联系删除。

收藏
评论区

相关推荐

彻底搞懂系列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树当中每个节点存储
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo
B
B-Tree ------ B-Tree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对2-3查找树的一种扩展。 一个m阶的B-Tree有以下性质 1. 每个节点最多有m个子节点; 2. 每个非叶子节点(根节点除外)至少含有m/2个子节点; 3.
B树与B+树的区别?
1.B树简介 ------ B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下: 1.1每个节点最多有m-1个关键字 1.2根节点最少有1个关键字 1.3非根节点至少有m/2个关键字 1.4每个节点的关键字都是按照从小到大的顺序排列,每个关键字的左子树中的关键字都小于它,而右子树中所有关键字都大于它。 1.5所有的叶子节点都处于同
MySQL知识体系——索引
    本文直切主题,针对InnoDB引擎描述索引及优化策略。在开始之前,需要读者了解:1)二叉查找树(包括2-3查找树、红黑树等数据结构)2)MySQL的InnoDB引擎基础知识 索引初探 ==== 要了解索引,当然要了解其数据结构。树有很多应用,流行的用法之一是包括UNIX和DOS在内的许多常用操作系统中的目录结构,二叉查找树又是Java中两种集合
MySQL索引底层:B+树详解
### 前言 当我们发现SQL执行很慢的时候,自然而然想到的就是加索引。对于范围查询,索引的底层结构就是B+树。今天我们一起来学习一下B+树哈~ 公众号:**「捡田螺的小男孩」** * 树简介、树种类 * B-树、B+树简介 * B+树插入 * B+树查找 * B+树删除 * B
MySQL索引(二)B+树在磁盘中的存储
MySQL索引(二)B+树在磁盘中的存储 ==================== 回顾 -- ![w200](https://oscimg.oschina.net/oscnet/bb8c395de7ffd25b8826c09d6cfe97ebbc0.jpg) 上一篇文章[《MySQL索引为什么要用B+树》](https://www.oschina.
MySQL调优系列——MySQL B+Tree索引和Hash索引的区别?🔥
1、B+Tree索引 ---------- ![](https://oscimg.oschina.net/oscnet/up-d956cc992de6df62c8502441583bb210ea4.png) > 1、B+Tree首先是有序结构,为了不至于树的高度太高,影响查找效率,在叶子节点上存储的不是单个数据,提高了查找效率; > > 为了更好的支持
MySQL面试(二)
1、为什么索引遵循最左匹配原则?   当B+树的数据项是符合的数据结构,比如(name,age,sex)的时候,B+树是按照从左到右的顺序建立搜索树的。比如当(张三,20,F)这样的数据来检索的时候,b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候
mysql面试题
MySQL面试 ======= 索引相关 ---- 1. **什么是索引?** 索引是一种数据结构,可以帮助我们快速的进行数据的查找. 1. **索引是个什么样的数据结构呢?** 索引的数据结构和具体存储引擎的实现有关, 在MySQL中使用较多的索引有Hash索引,B+树索引等,而我们经常使用的InnoDB存储引擎的默认索引实现为:B+树索引.
B+树原理以及Java代码实现
最初查找二叉树,由于树的高度会随着有序序列输入而急剧增长,后来出现平衡二叉树,红黑树。B树可以海量数据的快速查询检索,B树主要分为B树(B-树),B+树,B\*树等。 **B树(B-树)** M路搜索树,参数M定义节点的分支个数; 对于根节点孩子数目为\[2,M\],对于其余节点孩子数目为\[M/2,M\]; 每个节点含有关键字属性,至少M/2-1
DAT (Double Array Trie) 多模式匹配算法
**一、简介:** **1.1、字典树trie:**     字典树trie 搜索关键码的时间和关键码自身及其长度有关,最快是0(1),,即在第一层即可判断是否搜索到,最坏的情况是0(n), n为Trie树的层数。由于很多时候Trie树的大多数结点分支很少,因此Trie树结构空间浪费比较多。     关键码检索策略可以根据关键码是否可以动态变化
MongoDB索引存储BTree与LSM树(转载)
**1、为什么 MongoDB 使用B-树,而不是B+树** ------------------------------ MongoDB 是一种 nosql,也存储在磁盘上,被设计用在数据模型简单,性能要求高的场合。性能要求高,我们看B-树与B+树的区别: _**B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。
Sorry!Hbase的LSM Tree就是可以为所欲为!
我们先抛出一个问题: ![file](https://oscimg.oschina.net/oscnet/up-d5d01172c006977f680f3d99ad039ce7279.png) LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们