B树(B-tree、B-树)理论详解

这篇具有很好参考价值的文章主要介绍了B树(B-tree、B-树)理论详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

基本概念

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树
B树类似于红黑树,但它们在降低磁盘 I/O 操作数方面要更好一些。
许多数据库系统使用 B树或者 B树的变种来存储信息。
B树与红黑树的不同之处在于 B树的结点可以有很多孩子,从数个到数千个。也就是说,一个 B树的“分支因子”可以相当大,尽管它通常依赖于所使用的磁盘单元的特性。
B树类似于红黑树,就是每棵含有n个结点的 B树的高度为 O(lgn)。然而,一棵 B树的严格高度可能比一棵红黑树的高度要小许多,这是因为它的分支因子,也就是表示高度的对数的底数可以非常大。因此,我们也可以使用 B树在时间 O(lgn)内完成一些动态集合的操作。

3阶B树:子节点最多为3个
B树(B-tree、B-树)理论详解
4阶B树:子节点最多为4个
B树(B-tree、B-树)理论详解

n阶B树的性质(n>=2)

假设一个节点存储的元素个数为x,则
1、根节点:1<=x<=n-1
2、非根节点:ceil(n/2)-1<= x<= n-1 (ceil向上取整)

如果有子节点,子节点个数y=x+1,则
1、根节点: 2<=y<=n
2、非根节点:ceil(n/2) <= y<= n

比如n=3,2<= y <=3,因此可以称为(2,3)树、2-3树
比如n=4,2<= y <=4,因此可以称为(2,4)树、2-3-4树
比如n=5,3<= y <=5,因此可以称为(3,5)树
比如n=6,3<= y <=6,因此可以称为(3,6)树
比如n=7,4<= y <=7,因此可以称为(4,7)树

B树的搜索

B树的搜索跟二又搜索树的搜索类似,只不过分叉比二又搜索树更多
1、先在节点内部从小到大开始查找元素
2、如果找到了,查找结束
3、如果没有找到,再到对应的子节点继续查找元素,重复步骤1

B树元素的添加

新添加的元素必定是添加到叶子节点。

原始树:
B树(B-tree、B-树)理论详解
插入52:
B树(B-tree、B-树)理论详解
插入101:
B树(B-tree、B-树)理论详解
注意:假设再插入102,则最右边的叶子节点的元素个数将超过4阶B树的限制,这种现象我们称之为上溢出。

上溢出解决

n阶B树上溢节点的元素个数必然等于n。上溢的解决办法:
1、假设上溢节点最中间元素的位置为k,则可以:
a. 将k位置的元素向上与父节点合并
b. 将[Ok-1]和[k+1,n-1]位置的元素分裂成两个子节点,此时这两个子节点的元素个数,必然都不会低于最低限制(ceil(n/2)-1)
2、一次分裂完毕后,有可能导致父节点上溢,依然按照上述方法解决最极端的情况,有可能一直分裂到根节点。
如下图所示:
B树(B-tree、B-树)理论详解

删除

删除叶子节点

如果需要删除的元素在叶子节点中,那么可以直接删除元素。
B树(B-tree、B-树)理论详解
对上图删除56:
B树(B-tree、B-树)理论详解

删除非叶子节点

假如需要删除的元素在非叶子节点中。
1、先找到前驱或者后继元素,用前驱或者后继元素的值覆盖需要删除元素的值
2、再把前驱或后继元素删除
删除19:
B树(B-tree、B-树)理论详解
非叶子节点的前驱或后继元素,必定在叶子节点中
所以其实删除非叶子节点元素最终一定能转换成删除在叶子节点中的元素

删除——导致下溢出

B树(B-tree、B-树)理论详解
一颗5阶B树,要删除元素28
叶子节点被删掉一个元素后,元素个数可能会低于最低限制(>=ceil(n/2)-1)
这种现象称为:下溢

删除——解决下溢出方法一

下溢节点的元素数量必然等于ceil(n/2)-2
如果下溢节点临近的兄弟节点,有至少ceil(n/2)个元素,可以向其借一个元素
1、将父节点的元素b插入到下溢节点的0位置最小位置)
2、用兄弟节点的元素a(最大的元素)替代父节点的元素b
这种操作其实就是:旋转
B树(B-tree、B-树)理论详解

删除——解决下溢出方法二

如果下溢节点临近的兄弟节点,只有ceil(n/2)-1个元素
1、将父节点的元素b挪下来跟左右子节点进行合并
2、合并后的节点元素个数等于ceil(n/2) + ceil(n/2) – 2,不超过n-1
这个操作可能会导致父节点下溢,依然按照上述方法解决,下溢现象可能会一直往上传播
B树(B-tree、B-树)理论详解

MongoDB

MongoDB就是使用的B树实现。

ps:计划每日更新一篇博客,今日2023-05-04,日更第十八天。
昨日更新:

剑指Offer II 052——展平二叉搜索树文章来源地址https://www.toymoban.com/news/detail-433319.html

到了这里,关于B树(B-tree、B-树)理论详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 决策树(Decision Tree)原理解析:从基本概念到建立模型

    决策树是一种常用的机器学习算法,用于解决分类和回归问题。它基于树形结构进行决策,通过一系列的分裂和判断条件来预测目标变量的值。本文将详细解析决策树的原理,从基本概念到建立模型的过程 决策树由节点和边组成,其中节点表示特征或属性,边表示特征的取值

    2024年02月10日
    浏览(48)
  • 《误差理论与数据处理》——基本概念和随机误差处理

    复习整理《误差理论与数据处理》 一、基本公式 (真值可以用高一等级精度的标准所测得的量值称之为实际值) 误差= 测得值 - 真值 绝对误差 = 测得值 - 真值 相对误差 = 绝对误差 / 真值 示值误差 = 测得值 - 真值 引用误差 = 示值误差 / 测量范围上限值 (可用以判断仪表精

    2024年02月16日
    浏览(37)
  • 【矩阵论】7. 范数理论——基本概念——向量范数与矩阵范数

    矩阵论的所有文章,主要内容参考北航赵迪老师的课件 [注]由于矩阵论对计算机比较重要,所以选修了这门课,但不是专业搞数学的,所以存在很多口语化描述,而且对很多东西理解不是很正确与透彻,欢迎大家指正。我可能间歇性忙,但有空一定会回复修改的。 矩阵论 1

    2023年04月23日
    浏览(44)
  • 理论:(1)卡方分布、非中心卡方分布详解 (概念、求阈值方法、非中心化参数求解办法等)

    //======================================================================// GNSS/INS紧组合导航系统完好性监测(理论和c++代码)专栏,后续会开源全部代码 https://blog.csdn.net/hltt3838/category_12207970.html?spm=1001.2014.3001.5482 //======================================================================// 一、相关概念 1、卡方

    2024年02月01日
    浏览(49)
  • TCP/IP详解——网络基本概念

    网络最开始是为了数据通信。 以前通过ARPA网络,卫星来实现几个计算机的互相通信。 IBM推出自己的网络协议,这时网络没有标准。 1977年:TCP/IP标准。 1980年:ARPAnet全面向TCP/IP迁移。 1984年:ISO-网络标准,国籍标准化组织机构-定制各行各业的标准。 OSI开放式系统互联,同时

    2024年02月05日
    浏览(44)
  • HTTPS协议详解:基本概念与工作原理

    个人主页: insist--个人主页​​​​​​ 本文专栏 :网络基础——带你走进网络世界 本专栏会持续更新网络基础知识,希望大家多多支持,让我们一起探索这个神奇而广阔的网络世界。 目录 一、HTTPS协议的基本概念

    2024年02月10日
    浏览(44)
  • 详解RDD基本概念、RDD五大属性

            RDD(Resilient Distributed Dataset)叫做弹性分布式数据集,是Spark中最基本的数据抽象,它代表一个不可变、可分区、里面的元素可并行计算的集合。 RDD是spark core的底层核心 。 Dataset : RDD 可以不保存具体数据, 只保留创建自己的必备信息, 例如依赖和计算函数; RDD 也

    2023年04月08日
    浏览(35)
  • HTTP协议详解:基本概念与工作流程

    HTTP(Hypertext Transfer Protocol,超文本传输协议)是一种用于在计算机网络上进行数据交换的通信协议。它是互联网上最常用的协议之一,被广泛应用于Web浏览器和服务器之间的通信。本文将深入探讨HTTP协议的基本概念和工作流程,帮助读者更好地理解这个重要的通信协议。

    2024年02月10日
    浏览(45)
  • 什么是机器学习?监督学习的定义、概率论的基本概念以及模型选择、过拟合与欠拟合的问题。常见的监督学习算法,包括朴素贝叶斯(Naive Bayes)、决策树(Decision Tree)支持向量机随机森林

    作者:禅与计算机程序设计艺术 什么是机器学习?从定义、发展历程及目前的状态来看,机器学习由3个主要分支组成:监督学习(Supervised Learning),无监督学习(Unsupervised Learning)和强化学习(Reinforcement Learning)。这三类学习都可以使计算机系统根据输入数据自动分析和改

    2024年02月09日
    浏览(53)
  • 深入浅出 Spring:核心概念和基本用法详解

    个人主页:17_Kevin-CSDN博客 收录专栏;《Java》 在 Java 企业级应用开发中,Spring 框架已经成为了事实上的标准。它提供了一种轻量级的解决方案,使得开发者能够更轻松地构建灵活、可扩展的应用程序。在本文中,我们将探讨 Spring 框架的一些核心概念和基本用法,以此更好地

    2024年03月20日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包