当前位置: 首页 > 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,…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...