当前位置: 首页 > news >正文

B/B+树算法

B树

基本概述

B树又称多路平衡搜索树。一棵m阶B树,要么是空树,要么满足以下特性:

  • 每个节点最多有m棵子树
  • 根节点至少有两棵子树
  • 内部节点(除根和叶子节点以外的节点)至少有⌈m/2⌉棵子树
  • 关键字个数比子树个数少1
  • 终端节点(叶子节点)在同一层上,且不带任何信息(是空节点),通常称为失败节点

基本概念

B树的阶数为m,树高为h,关键字个数为k,节点个数为n。
在这里插入图片描述
阶是B树中,所有节点的子节点个数最大的那个数。如上图所示的树,其阶数为4。
树高是指树有几层,如上图,这个树就有2层,树高也就为2。
关键字个数,如上图,关键字个数为11
节点个数,如上图,节点个数为5
每个关键字头部指向所有比它小的关键字,尾部指向所有比它大的关键字

B树的排序

B树是有排序的,对应一个排序数组。
在具有k个关键字的B树中,查找失败有k+1种情况,且均为叶子节点。

最小树高和最小节点数

要让树高最小,那么每层的节点个数就要最大,即每个节点的子节点个数要最大,而m阶B树,其子节点的个数最大为m,那么我们让每个节点的子节点个数都为m,这样就能推导出最小树高。

第X层节点个数
01
1m
2m^2
3m^3
h - 1m^(h-1)
hm^h

失败节点个数为mh,则mh = k + 1
即:
h >= log(k + 1)
最小节点数:
n = k / (m - 1)

最大树高与最大节点数

与上面最小类似,最大只有让每个节点的子节点个数最小就好。

第X层节点个数
01
12
22⌈m / 2⌉
32⌈m / 2⌉^2
h - 12⌈m / 2⌉^(h-2)
h2⌈m / 2⌉^(h-1)

2⌈m / 2⌉^(h-1) = k + 1
所以:
h≤log_⌈m/2⌉ ⁡((k+1)/2)+1

根节点最少可以只有1个关键字,而其他节点最少需要⌈m/2⌉-1个关键字。考虑根节点补齐到⌈m/2⌉-1个关键字,则总关键字个数k需要增加⌈m/2⌉-2个。因此最大节点数为:
n≤(k+⌈m/2⌉-2)/(⌈m/2⌉-1)

B+树

B树中,每个节点都存有key-value,为了节省存储空间,可以采用B+树,在每个节点中,仅存储key即可。
B树有两种结构:
在这里插入图片描述
其中第2中结构比第一种结构更节省空间,且与B树更相似,因此也主要以第2种结构为主。第2种结构B+树的特征与B树相似,差别为:最后一层非叶子节点包含了全部的关键字,且节点间按升序顺序连接。

相关文章:

B/B+树算法

B树 基本概述 B树又称多路平衡搜索树。一棵m阶B树,要么是空树,要么满足以下特性: 每个节点最多有m棵子树根节点至少有两棵子树内部节点(除根和叶子节点以外的节点)至少有⌈m/2⌉棵子树关键字个数比子树个数少1终端节…...

vue3.2 + elementPlus + Windi CSS + ts创建一个好用的可兼容不同宽高的login页面

1.效果预览 2. 代码准备 导入windiCSS: npm i -D vite-plugin-windicss windicss windiCSS官网: https://cn.windicss.org/integrations/vite.html 使用vite创建好你的vue工程 sass版本为: 1.49.9 3.Windi CSS在页面中使用 apply 二次定义类名…...

Integer包装类详解加部分源码

【1】Java.lang直接使用&#xff0c;无需导包&#xff1a; 【2】类的继承关系&#xff1a; 【3】实现接口&#xff1a; Serializable&#xff0c;Comparable<Integer> 【4】这个类被final修饰&#xff0c;那么这个类不能有子类&#xff0c;不能被继承&#xff1a; 【5】…...

如何给侧边栏添加 Badge 计数标记

一、需求功能 给侧边菜单栏或及子菜单栏添加计数标记 el-badge 效果如下&#xff1a; 二、实现思路 结合 icon 图标渲染的思路&#xff0c;通过在layout 的 item.vue 中使用 vnodes.push 方法实现对 <el-badge /> 的渲染。在通过 Vuex 的状态管理将菜单栏需要的数据转…...

插槽slot复习

1.认识插槽 ◼ 在开发中&#xff0c;我们会经常封装一个个可复用的组件&#xff1a;  前面我们会通过props传递给组件一些数据&#xff0c;让组件来进行展示&#xff1b;  但是为了让这个组件具备更强的通用性&#xff0c;我们不能将组件中的内容限制为固定的div、span等等…...

【C++STL标准库】序列容器之deuqe与、orwa_list与list

基本概念这里就不再浪费时间去解释&#xff0c;这里给出deuqe与、orwa_list、list的基本使用方法&#xff1a; deque队列&#xff1a; #include <iostream> #include <deque>template <typename T> void print(T Begin, T End);int main() {std::deque<…...

RocketMQ教程-(5)-功能特性-消息发送重试和流控机制

本文为您介绍 Apache RocketMQ 的消息发送重试机制和消息流控机制。 背景信息​ 消息发送重试 Apache RocketM Q的消息发送重试机制主要为您解答如下问题&#xff1a; 部分节点异常是否影响消息发送&#xff1f; 请求重试是否会阻塞业务调用&#xff1f; 请求重试会带来什…...

OpenCV笔记

opencv读取视频操作 import cv2video cv2.VideoCapture("./1.mp4")if video.isOpened():# video.read() 一帧一帧地读取# open 得到的是一个布尔值&#xff0c;就是 True 或者 False# frame 得到当前这一帧的图像open, frame video.read() else:open Falsewhile …...

Mysql基础(下)之函数,约束,多表查询,事务

&#x1f442; 回到夏天&#xff08;我多想回到那个夏天&#xff09; - 傲七爷/小田音乐社 - 单曲 - 网易云音乐 截图自 劈里啪啦 -- 黑马Mysql&#xff0c;仅学习使用 &#x1f447;原地址 47. 基础-多表查询-表子查询_哔哩哔哩_bilibili 目录 &#x1f982;函数 &#x1f3…...

Android 屏幕适配各种宽高比的手机

由于android 手机的屏幕宽高比样式太多了&#xff0c;在设计UI时&#xff0c;很多时候&#xff0c;会因为宽高比&#xff0c;分辨率不同会有展示上的差异。 我是这样解决的 在activity的onCreate方法前&#xff0c;调用&#xff1a; fun screenFit(context: Context) {val me…...

云计算——云计算与虚拟化的关系

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​ 目录 前言 一.虚拟化 1.什么是虚拟化 2.虚拟化技术作用 二.云计算与虚拟化的关系 三.虚…...

手机变局2023:一场瞄准产品和技术的“思维革命”

以折叠屏冲高端&#xff0c;已成为中国手机厂商们的共识。 在这个苹果未涉足的领域&#xff0c;国产手机厂商们加快脚步迭代推新&#xff0c;积极抢占机遇。但平心而论&#xff0c;虽然国产折叠屏机型众多&#xff0c;但市场上始终缺乏一款突破性的产品作为标杆&#xff0c;为…...

【Linux】自动化构建工具-make/Makefile详解

前言 大家好吖&#xff0c;欢迎来到 YY 滴 Linux系列 &#xff0c;热烈欢迎&#xff01;本章主要内容面向接触过Linux的老铁&#xff0c;主要内容含 欢迎订阅 YY 滴Linux专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; 订阅专栏阅读&#xff1a;YY的《…...

1 js嵌入html使用

1.1 直接在html内部使用js代码 使用script标签&#xff0c;在前后标签内部写的代码即为js代码。 <body><p id"p1">初始段落</p> <!--id是为了定位需要更改内容的标签--><button type"button" onclick"showNum()">…...

总结RoctetMQ

RoctetMQ 定义优缺点场景使用方式消息顺序问题死信幂等性可视化面板 定义 优缺点 场景 使用方式 消息顺序问题 死信 幂等性 可视化面板...

命名约定~

1.变量的命名约定 JavaScript 变量名称是区分大小写的&#xff0c;大写和小写字母是不同的。比如&#xff1a; let DogName Scooby-Doo; let dogName Droopy; let DOGNAME Odie; console.log(DogName); // "Scooby-Doo" console.log(dogName); // "Dro…...

Python基础-列表(list)和元组(tuple)

Python包含6种内建的序列&#xff1a;列表&#xff0c;元组&#xff0c;字符串&#xff0c;Unicode字符串&#xff0c;buffer对象&#xff0c;xrange对象&#xff0c;本文讨论列表和元组。 1.列表可以修改&#xff0c;元组则不能修改。 2.几乎在所有的情况下&#xff0c;列表…...

Dubbo介绍及使用

&#x1f353; 简介&#xff1a;java系列技术分享(&#x1f449;持续更新中…&#x1f525;) &#x1f353; 初衷:一起学习、一起进步、坚持不懈 &#x1f353; 如果文章内容有误与您的想法不一致,欢迎大家在评论区指正&#x1f64f; &#x1f353; 希望这篇文章对你有所帮助,欢…...

初阶C语言-分支和循环语句(下)

“花会沿途盛开&#xff0c;以后的路也是。” 今天我们一起来继续学完分支语句和循环语句。 分支和循环 3.循环语句3.4 do...while()循环3.4.1 do语句的用法 3.5关于循环的一些练习3.6 goto语句 3.循环语句 3.4 do…while()循环 3.4.1 do语句的用法 do循环语句;//当循环语句…...

pytorch工具——pytorch中的autograd

目录 关于torch.tensor关于tensor的操作关于梯度gradients 关于torch.tensor 关于tensor的操作 x1torch.ones(3,3) xtorch.ones(2,2,requires_gradTrue) print(x1,\n,x)yx2 print(y) print(x.grad_fn) print(y.grad_fn)zy*y*3 outz.mean() print(z,out)注意 atorch.randn(2,…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...