B树的性质和插入过程

server/2024/12/21 14:16:58/

性质

  1. 平衡性:所有叶子节点都在同一层
  2. 多路:m 阶 B 树
    最多: m 个分支,m-1 个元素
    最少: 根节点 2 个分支 1个元素
    其他节点 ⌈ m / 2 ⌉ \lceil m/2\rceil m/2 个分支 ⌈ m / 2 ⌉ \lceil m/2\rceil m/2 − 1 -1 1 个元素
  3. 有序:结点内有序,左子树<根<右子树

插入过程

  1. 定位插入点:从根节点开始,逐层向下遍历B树,找到要插入的键值应该插入的位置。

  2. 在插入点插入后,检查叶子节点是否已满。如果已满,则需要进行分裂操作。

  3. 分裂操作:如果叶子节点已满(m 个点即满),将其分裂。中间的点(第 ⌈ m / 2 ⌉ \lceil m/2\rceil m/2 个点)上升为子树根节点(插入到未分裂前的根节点当中),中间点左右两端的点变为中间点的键值所在点的左右子树。若未分裂前的根节点被插入后满了,继续重复该操作

定位插入点
是否已满
分裂操作
正常插入操作

![[Pasted image 20241217225421.png]]


http://www.ppmy.cn/server/151959.html

相关文章

【GCC】2015: draft-alvestrand-rmcat-congestion-03 机器翻译

腾讯云的一个分析,明显是看了这个论文和草案的 : 最新的是应该是这个 A Google Congestion Control Algorithm for Real-Time Communication draft-ietf-rmcat-gcc-02 下面的这个应该过期了: draft-alvestrand-rmcat-congestion-03

云原生是什么

云原生是一种构建和运行应用程序的方法&#xff0c;它充分利用了云计算的优势。它不仅仅是指在云上运行应用程序&#xff0c;更重要的是指应用程序的设计、开发、部署和运维方式都充分考虑了云环境的特性&#xff0c;从而能够更好地利用云的弹性、可扩展性和灵活性。 更详细地…

uni-app开发商品详情页面实现

目录 一:功能描述 二:功能实现 一:功能描述 商品详情页主要展示商品的图片,基础信息,详细描述信息,以及销量,库存信息等。 首先在顶部以轮播图形式展示图片信息,下面展示商品价格和商品名称和描述信息,然后显示商品的关键卖点信息,最后展示商品详情信息。 二:功…

leetcode:3285. 找到稳定山的下标(python3解法)

难度&#xff1a;简单 有 n 座山排成一列&#xff0c;每座山都有一个高度。给你一个整数数组 height &#xff0c;其中 height[i] 表示第 i 座山的高度&#xff0c;再给你一个整数 threshold 。 对于下标不为 0 的一座山&#xff0c;如果它左侧相邻的山的高度 严格大于 thresho…

Android13 系统/用户证书安装相关分析总结(四) 遇到的问题整理

一、前言 这一篇文章主要整理一下&#xff0c;笔者在解决问题的过程中遇到的问题&#xff0c;当然不一定是非常常见的问题&#xff0c;因为需求还在测试过程中&#xff0c;所以一段时间内&#xff0c;这篇文章会有更新。如果读到的小伙伴发现写得有问题还请指出&#xff0c;感…

蓝桥杯刷题——day7

蓝桥杯刷题——day7 题目一题干题目解析代码 题目二题干题目解析代码 题目一 题干 输入一个整数P&#xff0c;输出P进制下的乘法表。P进制中大于等于 10 的数字用大写字母A、B、C等表示。 示例一&#xff1a; 输入&#xff1a; 4 输出&#xff1a; 111 212 2210 313 3212 332…

字节跳动Java开发面试题及参考答案(综合篇)

HTTP 与 HTTPS 的区别? HTTP(超文本传输协议)和 HTTPS(超文本传输安全协议)主要有以下区别。 从安全性角度看,HTTP 是明文传输协议,数据在网络中传输时是以原始文本的形式发送的。这就好比在信件传递过程中没有进行密封,任何中间节点(如路由器、代理服务器等)都可以查…

Spark-Streaming性能调优

一、概览 从集群上的Spark Streaming应用程序中获得最佳性能需要一些调整。一般会考虑2个因素&#xff1a; 通过高效利用集群资源&#xff0c;减少每批数据的流转时长设置正确的批量大小&#xff0c;以便批量数据可以在接收到时尽快处理&#xff08;即数据处理跟上数据摄取&a…