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，6，7作为一个节点。

然后插入11，得到1，2，6，7，11. 因为节点个数超过4，所以需要对该节点进行拆分。选取中间节点6，进行提升，提升为父节点，于是得到：

有一个规则是新插入的节点总是出现在叶子节点上，接着插入4，8，13，直接插入即可，得到

然后插入10. 得到

因为最右下的节点内有5个元素，超过最大个数4了，所以需要进行拆分，把中间节点10进行提升，上升到和6一起，形成如下结构。

然后插入5，17，9，16，得到如下

之后插入20，插入20后，最右下节点内元素个数为5个，超过最大个数4个，所以，需要把16进行提升，形成如下结构

之后插入3、12、14、18、19，后，形成如下结构。

然后插入15，会导致13提升到根节点，这时，根节点会有5个节点，那么，根节点中的10会再次进行提升，形成如下结构。

结束。

总结

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

赞 (0)

相关推荐

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

    完整B树算法Java实现代码

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

  • B-树的删除过程介绍

    B-树的删除过程介绍

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

  • 基于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 所指子

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

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

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

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

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

  • 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

  • B-Tree的性质介绍

    B-Tree的性质介绍

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

  • c语言B树深入理解

    c语言B树深入理解

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

  • 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

  • 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,

  • MySQL 处理插入过程中的主键唯一键重复值的解决方法

    MySQL 处理插入过程中的主键唯一键重复值的解决方法

    本篇文章主要介绍在插入数据到表中遇到键重复避免插入重复值的处理方法,主要涉及到IGNORE,ON DUPLICATE KEY UPDATE,REPLACE:接下来就分别看看这三种方式的处理办法. IGNORE 使用ignore当插入的值遇到主键(PRIMARY KEY)或者唯一键(UNIQUE KEY)重复时自动忽略重复的记录行,不影响后面的记录行的插入, 创建测试表 CREATE TABLE Tignore (ID INT NOT NULL PRIMARY KEY , NAME1 INT )d

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

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

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

  • java二叉树的数据插入算法介绍

    目录 例题: 对于二叉树的遍历有三种方式 二叉树插入数据的原理/思路是什么? 代码实现 整体代码 全部代码 例题: leetcode 第701题 二叉树插入数据 题目: 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树. 返回插入后二叉搜索树的根节点. 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同. 对于二叉树的遍历有三种方式 前序遍历:根左右 的顺序 中序遍历:左根右 的顺序 后序遍历:左右根 的顺序 二叉树插入数据的原理/思路是什么? 二叉树的左侧的数会比右

  • Linux下防火墙的简单配置与插入规则介绍

    查看当前的防火墙设置 iptables -L INPUT -n --line-numbers 删除一条策略,例如第4行策略 iptables -D INPUT 4 -A:在尾部插入 -I (insert)在指定链中插入一条新规则,为指明插入到第几行 (如:在第七行插入) iptables -I INPUT 7 -p tcp -m state --state NEW -m tcp --dport 81 -j ACCEPT 然后保存 service iptables save 然后重启 servic

  • 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

  • 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的缩写,中

  • 银河麒麟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

随机推荐