B-树的删除过程介绍

上文https://www.jb51.net/article/154157.htm我们介绍了B-树的插入过程，本文我们来介绍B-树的删除过程。

在B-树中删除节点时，可能会发生向兄弟节点借元素，和孩子节点交换元素，甚至节点合并的过程。

我们以下面的树为基础，进行删除操作。

首先明确一下这个树的定义。它是一个5阶树。所以，每个节点内元素个数为2~4个。

我们依次删除8、16、15、4这4个元素。

首先删除8，因为删除8后，不破坏树的性质，所以直接删除即可。得到如下

然后删除16，这导致该节点只剩下一个13节点，不满足节点内元素个数为2~4个的要求了。所以需要调整。这里可以向孩子借节点，把17提升上来即可，得到下图。这里不能和兄弟节点借节点，因为从3，6节点中把6借走后，剩下的3也不满要求了。另外，也不能把孩子中的15提升上来，那样会导致剩下的14不满足要求。

然后删除15，删除15后同样需要调整。调整的方式是，18上升，17下降到原来15的位置，得到下图。

然后删除元素4，删除4后该节点只剩下5，需要调整。可是它的兄弟节点也都没有多余的节点可借，所以需要进行节点合并。节点合并时，方式会有多种，我们选择其中的一种即可。这里，我们选择父节点中的3下沉，和1，2，以及5进行合并，如下图。

但这次调整，导致6不符合要求了。另外，6非根节点，但只有2个孩子，也不符合要求。需要继续调整。调整的方式是，将10下沉，和6，以及13，18合并为根节点，如下图。

结束。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

赞 (0)

相关推荐

  • bitmap 索引和 B-tree 索引在使用中如何选择

    现在,我们知道优化器如何对这些技术做出反应,清楚地说明 bitmap 索引和 B-tree 索引各自的最好应用. 在 GENDER 列适当地带一个 bitmap 索引,在 SAL 列上创建另外一个位图索引,然后执行一些查询.在这些列上,用 B-tree 索引重新执行查询. 从 TEST_NORMAL 表,查询工资为如下的男员工: 1000 1500 2000 2500 3000 3500 4000 4500 因此: SQL> select * from test_normal 2 where s

  • 浅谈MySQL的B树索引与索引优化小结

    浅谈MySQL的B树索引与索引优化小结

    MySQL的MyISAM.InnoDB引擎默认均使用B+树索引(查询时都显示为"BTREE"),本文讨论两个问题: 为什么MySQL等主流数据库选择B+树的索引结构? 如何基于索引结构,理解常见的MySQL索引优化思路? 为什么索引无法全部装入内存 索引结构的选择基于这样一个性质:大数据量时,索引无法全部装入内存. 为什么索引无法全部装入内存?假设使用树结构组织索引,简单估算一下: 假设单个索引节点12B,1000w个数据行,unique索引,则叶子节点共占约100MB,整棵树最多20

  • B-Tree的性质介绍

    B-Tree的性质介绍

    B-树是一种常见的数据结构.和他一起的还有B+树. 在这里,需要澄清一下概念.B树,B-树,B+树有什么区别?他们有什么关系呢? 其实,从数据结构来讲只有2种,也就是B-树和B+树.有时候,B-树又称为B树,他们是一个东西.请注意,B-树中间的"-"是连字符,而不是"减号".英文中是B-Tree,翻译成中文后,也就是B树,有的翻译喜欢把连字符"-"也带着,于是就成了B-树,而B-树被有些读者误读为B减树. 介绍B-树之前,首先看一下一个重要的概念

  • B-树的插入过程介绍

    B-树的插入过程介绍

    上文https://www.jb51.net/article/154153.htm我们介绍了B-树的性质,本文我们来介绍一下B-树的插入过程. 插入过程和树的构建过程本质是一致的,即都是进行插入操作,并对插入后的B-树进行调整. 我们设定B-树的阶为5.用关键字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}来构建一棵B-树. 因为树的阶为5,那么,每个节点最多有5个子节点,每个节点内的关键字个数为3~4个. 于是,第一步是插入1,2,

  • c语言B树深入理解

    c语言B树深入理解

    B树是为磁盘或其他直接存储设备设计的一种平衡查找树.如下图所示.每一个结点箭头指向的我们称为入度,指出去的称为出度.树结构的结点入度都是1,不然就变成图了,所以我们一般说树的度就是指树结点的出度,也就是一个结点的子结点个数.有了度的概念我们就简单定义一下B树(假设一棵树的最小度数为M):1.每个结点至少有M-1个关键码,至多有2M-1个关键码:2.除根结点和叶子结点外,每个结点至少有M个子结点,至多有2M个子结点:3.根结点至少有2个子结点,唯一例外是只有根结点的情况,此时没有子结点:4.所有叶

  • 基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    B-树 1 .B-树定义 B-树是一种平衡的多路查找树,它在文件系统中很有用. 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:⑴树中每个结点至多有m 棵子树:⑵若根结点不是叶子结点,则至少有两棵子树: ⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树:⑷所有的非终端结点中包含以下信息数据: (n,A0,K1,A1,K2,-,Kn,An)其中:Ki(i=1,2,-,n)为关键码,且Ki<Ki+1, Ai 为指向子树根结点的指针(i=0,1,-,n),且指针Ai-1 所指子

  • 完整B树算法Java实现代码

    完整B树算法Java实现代码

    定义 在计算机科学中,B树(英语:B-tree)是一种自平衡的树,能够保持数据有序.这种数据结构能够让查找数据.顺序访问.插入数据及删除的动作,都在对数时间内完成. 为什么要引入B树? 首先,包括前面我们介绍的红黑树是将输入存入内存的一种内部查找树. 而B树是前面平衡树算法的扩展,它支持保存在磁盘或者网络上的符号表进行外部查找,这些文件可能比我们以前考虑的输入要大的多(难以存入内存). 既然内容保存在磁盘中,那么自然会因为树的深度过大而造成磁盘I/O读写过于频繁(磁盘读写速率是有限制的),进而导

  • SQLite中的B-Tree实现细节分析

    SQLite在存储在外部的数据库是以B-Tree来组织的.关于B-tree的细节,参考 ** ** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3: ** "Sorting And Searching", pages 473-480. Addison-Wesley ** Publishing Company, Reading, Massachusetts. ** 基本思想是文件包含的每一页都包括N个数据库入口和N+1

  • MySQL Hash索引和B-Tree索引的区别

    MySQL Hash索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引. 可 能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree 高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊

  • B-树的删除过程介绍

    B-树的删除过程介绍

    上文https://www.jb51.net/article/154157.htm我们介绍了B-树的插入过程,本文我们来介绍B-树的删除过程. 在B-树中删除节点时,可能会发生向兄弟节点借元素,和孩子节点交换元素,甚至节点合并的过程. 我们以下面的树为基础,进行删除操作. 首先明确一下这个树的定义.它是一个5阶树.所以,每个节点内元素个数为2~4个. 我们依次删除8.16.15.4这4个元素. 首先删除8,因为删除8后,不破坏树的性质,所以直接删除即可.得到如下 然后删除16,这导致该节点只剩下

  • C# Lambda表达式及Lambda表达式树的创建过程

    C# Lambda表达式及Lambda表达式树的创建过程

    每次写博客,第一句话都是这样的:程序员很苦逼,除了会写程序,还得会写博客!当然,希望将来的一天,某位老板看到此博客,给你的程序员职工加点薪资吧!因为程序员的世界除了苦逼就是沉默.我眼中的程序员大多都不爱说话,默默承受着编程的巨大压力,除了技术上的交流外,他们不愿意也不擅长和别人交流,更不乐意任何人走进他们的内心! 题外话说多了,咱进入正题: 上一节中,我们讲到:在 2.0 之前的 C# 版本中,声明委托的唯一方法是使用命名方法.C# 2.0 引入了匿名方法,而在 C# 3.0 及更高版本中,La

  • Centos6.5升级glibc过程介绍

    目录 场景需求 glibc版本 glibc安装 glibc软链 场景需求 默认的Centos6.5 glibc版本最高为2.12, 而在进行Nodejs开发时项目所依赖的包往往需要更高版本的glibc库支持, 因此在不升级系统的前提下, 需要主动更新系统glibc库. 一般遇到错误libc.so.6: version GLIBC_2.14 not found时表示需要对glibc进行升级了. glibc版本 查看系统glibc库版本可使用如下命令: $ strings /lib64/libc.s

  • 银河麒麟4.0.2（Ubuntu）扩展boot分区过程介绍

    银河麒麟4.0.2（Ubuntu）扩展boot分区过程介绍

    目录 前言 1.准备新的分区 2.复制boot分区 3.修改fstab文件 4.更新grub 前言 在一些场合(如开发内核模块)我们需要安装多个版本的内核,这时候容易出现boot分区空间不够的问题,本文介绍如何扩展银河麒麟(4.0.2)的boot分区. 由于boot分区通常位于磁盘的第一个分区,直接扩展难度较大,因此采取新分区替换原分区的方式间接实现boot分区的扩展.请注意,替换boot分区有风险,请评估完风险后,谨慎操作. 1.准备新的分区 如何是虚拟机,可以直接添加一块虚拟磁盘,如果是物理

  • linux环境下安装mysql8.0过程介绍

    linux环境下安装mysql8.0过程介绍

    目录 前言 一.linux更改yum源(如果MYSQL安装慢可以试) 二.版本 三.安装 四.查看临时密码 五.配置外网可以访问 六.测试 七. 数据库卸载 八. 问题 总结 前言 借助同事写得笔记和自己在配置过程中遇到的坑,做一下记录. 一.linux更改yum源(如果MYSQL安装慢可以试) 简介:因为是官方yum,可能会导致安装比较慢,我们切换到国内的源. 第一步:进入yum配置文件目录 cd /etc/yum.repos.d/ 第二步:备份配置文件(如果后续出现了问题就可以恢复): mv

  • Android证书安装过程介绍

    目录 一.证书在源码中的路径 二.证书在固件中的路径 三.手动安装流程 四.c层 五.为什么要锁屏密码 一.证书在源码中的路径 5.1系统证书(命名是 openssl x509 -subject_hash_old -in filename) libcore/luni/src/main/files/cacerts 7.1及以后系统证书 /system/ca-certificates/files 二.证书在固件中的路径 /system/etc/security/cacerts 三.手动安装流程 设置

  • 银河麒麟4.0.2(Ubuntu)扩展boot分区过程介绍

    银河麒麟4.0.2(Ubuntu)扩展boot分区过程介绍

    目录 前言 1.准备新的分区 2.复制boot分区 3.修改fstab文件 4.更新grub 前言 在一些场合(如开发内核模块)我们需要安装多个版本的内核,这时候容易出现boot分区空间不够的问题,本文介绍如何扩展银河麒麟(4.0.2)的boot分区. 由于boot分区通常位于磁盘的第一个分区,直接扩展难度较大,因此采取新分区替换原分区的方式间接实现boot分区的扩展.请注意,替换boot分区有风险,请评估完风险后,谨慎操作. 1.准备新的分区 如何是虚拟机,可以直接添加一块虚拟磁盘,如果是物理

  • jQuery删除一个元素后淡出效果展示删除过程的方法

    本文实例讲述了jQuery删除一个元素后淡出效果展示删除过程的方法.分享给大家供大家参考.具体分析如下: 当我们删除一个元素时希望能看到删除的过程,这个效果通过对元素进行淡出展示动态化删除过程. $("#myButton").click(function() { $("#myDiv").fadeTo("slow", 0.01, function(){//fade $(this).slideUp("slow", function

  • CentOS环境使用NFS远程目录挂载过程介绍

    CentOS环境使用NFS远程目录挂载过程介绍

    目录 一.NFS简介 二.NFS搭建 1. NFS服务端搭建 2. NFS客户端端搭建 3. 测试 一.NFS简介 在前面的文章中讲解K8s中有提到NFS来统一存储不同Pod产生的文件,在K8s中的数据卷直接就支持NFS,直接指定NFS服务器的ip和目录即可,本篇文章我们要学下NFS远程目录的挂载,将不同服务器上的指定目录挂在到NFS服务器中,类似于windows的共享文件夹,可以使得不同的服务器之间共享数据.下面我们一起体验下NFS. NFS 是Network File System的缩写,中

随机推荐