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

4.B-树

news 来源：原创 2025/9/2 3:13:58

一、常见的查找方式 

顺序查找 O(N)

二分查找 O(logN)（要求有序和随机访问）

二叉搜索树 O(N)

平衡二叉搜索树(AVL树和红黑树) O(logN)

哈希 O(1)
考虑效率和要求而言，正常选用 平衡二叉搜索树 和 哈希 作为查找方式。

但这两种结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了。

如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？

可以考虑将 存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点 中。需要访问数据时，先取这个地址去磁盘访问数据。

分析效率的缺陷：

使用平衡二叉树搜索树的缺陷：
平衡二叉树搜索树的高度是 logN ，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，logN 次的磁盘访问，是一个难以接受的结果。
使用哈希表的缺陷：
哈希表的效率很高是 O(1) ，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的。
那如何加速对数据的访问呢？
1. 提高 IO 的速度 (SSD 相比传统机械硬盘快了不少，但是还是没有得到本质性的提升 )
2. 降低树的高度 --- 多叉树平衡树

二、B树概念

1970 年， R.Bayer 和 E.mccreight 提出了一种适合外查找的树，它是一种平衡的多叉树，称为 B 树。
一 棵 m 阶 (m>2) 的 B 树，是一棵平衡的 M 路平衡搜索树，可以是空树 或者满足一下性质：
1. 根节点至少有两个孩子
2. 每个分支节点都包含 k-1 个关键字和 k 个孩子，其中 ceil(m/2) ≤ k ≤ m  (ceil 是向上取整函数)
3. 每个叶子节点都包含 k-1 个关键字，其中 ceil(m/2) ≤ k ≤ m
4. 所有的叶子节点都在同一层
5. 每个节点中的关键字从小到大排列，节点当中 k-1 个元素正好是 k

相关文章：

4.B-树

一、常见的查找方式 顺序查找 O(N) 二分查找 O(logN)（要求有序和随机访问） 二叉搜索树 O(N) 平衡二叉搜索树(AVL树和红黑树) O(logN) 哈希 O(1) 考虑效率和要求而言，正常选用 平衡二叉搜索树 和 哈希 作为查找方式。 但这两种结构适合用于数据量相对不是很大，能够一次性…...

编程日记 2025/9/2 3:13:58

怎么看英文论文 pdf沉浸式翻译

https://arxiv.org/pdf/2105.09492 Immersive Translate Xournal打开...

编程日记 2025/8/27 0:28:57

计算机三级第一章：信息安全保障概述（以时间节点推进的总结）

淡蓝色为必背内容 第一阶段：电讯技术的发明19世纪30年代：电报电话的发明 1835年：莫尔斯（Morse）发明了电报 1837年：莫尔斯电磁式有线电报问世 1878年：人工电话交换局出现 1886年：马可尼发明了无线电报机 1876年：贝尔（Bell）发明了电话机 1892年，史瑞桥自动交换…...

编程日记 2025/9/2 3:11:57

车载软件架构 ---单个ECU的AUTOSAR开发流程

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 周末洗了一个澡，换了一身衣服，出了门却不知道去哪儿，不知道去找谁，漫无目的走着，大概这就是成年人最深的孤独吧! 旧人不知我近况，新人不知我过…...

编程日记 2025/9/2 3:10:03

【场景应用7】在TPU上使用Flax/JAX对Transformers模型进行语言模型预训练

在本笔记本中，我们将展示如何使用Flax在TPU上预训练一个🤗 Transformers模型。 这里将使用GPT2的因果语言建模目标进行预训练。 正如在这个基准测试中所看到的，使用Flax/JAX在GPU/TPU上的训练通常比使用PyTorch在GPU/TPU上的训练要快得多，而且也可以显著降低成本。 Fla…...

编程日记 2025/8/26 8:57:59

C++运算符重载全面总结

C运算符重载全面总结 运算符重载是C中一项强大的特性，它允许程序员为自定义类型定义运算符的行为。以下是关于C运算符重载的详细总结： 一、基本概念 1. 什么是运算符重载 运算符重载是指为自定义类型（类或结构体）重新定义或重…...

编程日记 2025/9/1 14:58:45

PTA | 实验室使用排期

目录 题目： 输入格式： 输出格式： 输入样例： 输出样例： 样例解释： 代码： 无注释版： 有注释版： 题目： 受新冠疫情影响，当前大家的活动都…...

编程日记 2025/9/2 3:13:30

3.7 字符串基础

字符串 （str）：和列表用法基本一致 1.字符串的创建 -str转换(字符串，可用于将其他字符类型转换为字符串) -单引号 双引号 三引号 2.索引 3.字符串的切片 4.字符串的遍历 5.字符串的格式化 6.字符串的运算符 7.字符串的函数 #…...

编程日记 2025/9/2 3:10:04

《 C++ 点滴漫谈： 三十三 》当函数成为参数：解密 C++ 回调函数的全部姿势

一、前言 在现代软件开发中，“解耦” 与 “可扩展性” 已成为衡量一个系统架构优劣的重要标准。而在众多实现解耦机制的技术手段中，“回调函数” 无疑是一种高效且广泛使用的模式。你是否曾经在编写排序算法时，希望允许用户自定义排序规则&a…...

编程日记 2025/8/26 13:28:35

16bit转8bit的常见方法（图像归一化）

文章目录 16-bit转8-bit的常用方法一、数据类型转换：image.astype(np.uint8) —— 若数值 x 超出 0-255 范围，则取模运算。如：x 600 % 256 88二、截断函数：np.clip().astype(np.uint8) —— 若数值 x 超出 0-255 范围&#xff0…...

编程日记 2025/9/2 3:11:27

消息中间件kafka,rabbitMQ

在分布式系统中，消息中间件是实现不同组件之间异步通信的关键技术。Kafka 和 RabbitMQ 是两个非常流行的消息中间件系统，它们各自有着不同的特点和应用场景。下面将分别介绍 Kafka 和 RabbitMQ，并讨论它们在消息队列中的使用。 一、Kafka (Apache Kafka) 主要特点: 高吞吐…...

编程日记 2025/8/26 18:11:54

C语言编译预处理3

条件编译&#xff1a;是对源程序的一部分指定编译条件&#xff0c;满足条件进行编译否则不编译。 形式1 #indef 标识符 程序段1 #else 程序段2 #endif 标识符已经被定义用#ifdef #include <stdio.h>// 可以通过注释或取消注释下面这行来控制是否定义 DEBUG 宏 // …...

编程日记 2025/8/27 9:32:03

数据结构·树

树的特点 最小连通图 无环 有且只有 n − 1 n-1 n−1 条边 树的建立方式 顺序存储 只适用于满n叉树&#xff0c;完全n叉树 1<<n 表示结点 2 n 2^n 2nP4715 【深基16.例1】淘汰赛 void solve() {cin >> n;for (int i 0; i<(1<<n); i) {cin >&g…...

编程日记 2025/9/2 3:11:25

队列的各种操作实现（数据结构C语言多文件编写)

1.先创建queue.h声明文件(Linux命令&#xff1a;touch queue.h)。编写函数声明如下(打开文件 Linux 操作命令&#xff1a;vim queue.h): //头文件 #ifndef __QUEUE_H__ #define __QUEUE_H__ //队列 typedef struct queue{int* arr;int in;int out;int cap;int size; }queue_t;…...

编程日记 2025/9/2 3:11:56

48V/2kW储能电源纯正弦波逆变器详细设计方案-可量产

48V/2kW储能电源纯正弦波逆变器详细设计方案 1.后级驱动电路图 2.前级驱动电路图 3.功率表电路原理图 4.功率板BOM: 5.后级驱动BOM 6.前级驱动BOM...

编程日记 2025/8/27 6:42:00

[redis进阶二]分布式系统之主从复制结构(2)

目录 一 redis的拓扑结构 (1)什么是拓扑 (2)⼀主⼀从结构 (3)⼀主多从结构 (4)树形主从结构 (5)三种拓扑结构的优缺点,以及适用场景 二 redis的复制原理 (1)复制过程 (2)数据同步psync replicationid/replid (复制id)(标注同步的数据来自哪里:数据来源) offset (偏移…...

编程日记 2025/8/28 0:20:47

Playwright多语言生态：跨Python_Java_.NET的统一采集方案

一、问题背景&#xff1a;爬虫多语言割裂的旧时代 在大规模数据采集中&#xff0c;尤其是学术数据库如 Scopus&#xff0c;开发者常遇到两个经典问题&#xff1a; 技术语言割裂&#xff1a;Python开发人员使用Selenium、requests-html等库&#xff1b;Java阵营使用Jsoup或Htm…...

编程日记 2025/9/2 3:13:58

day30 第八章 贪心算法 part04

452. 用最少数量的箭引爆气球 先排序&#xff0c;再算重叠区间 class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points)0:return 0points.sort(keylambda x:x[0])result 1for i in range(1, len(points)):if points[i][0] > point…...

编程日记 2025/9/2 1:07:29

java操作redis库，开箱即用

application.yml spring:application:name: demo#Redis相关配置redis:data:# 地址host: localhost# 端口&#xff0c;默认为6379port: 6379# 数据库索引database: 0# 密码password:# 连接超时时间timeout: 10slettuce:pool:# 连接池中的最小空闲连接min-idle: 0# 连接池中的最…...

编程日记 2025/8/28 5:56:20

clickhouse中的窗口函数

窗口函数 边界核心参数 窗口边界通过 ROWS、RANGE 或 GROUPS 模式定义，语法为： ROWS BETWEEN AND 基于 ​物理行位置 定义窗口，与排序键的实际值无关，适用于精确控制窗口行数 – 或 RANGE BETWEEN AND 基于 ​排序键的数值范围 定义窗口，适用于时间序列或连续数值的场景（…...

编程日记 2025/8/28 0:19:50

YZ系列工具之YZ02:字典的多功能应用

我给VBA下的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套一部VBA手册&#xff0c;教程分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的…...

编程日记 2025/9/2 3:13:57

金山科技在第91届中国国际医疗器械博览会CMEF 首发新品 展现智慧装备+AI

4月8日—11日&#xff0c;国家会展中心&#xff08;上海&#xff09;&#xff0c;第91届中国国际医疗器械&#xff08;春季&#xff09;博览会&#xff08;以下简称“CMEF 2025”&#xff09;举办。金山科技在盛会上隆重推出年度新品——全高清电子内镜光学放大镜与肛肠测压系统…...

编程日记 2025/9/2 3:13:29

STM32 BOOT设置，bootloader，死锁使用方法

目录 BOOT0 BOOT1的配置含义 bootloader使用方法 芯片死锁解决方法开发调试过程中&#xff0c;由于某种原因导致内部Flash锁死&#xff0c;无法连接SWD以及JTAG调试&#xff0c;无法读到设备&#xff0c;可以通过修改BOOT模式重新刷写代码。修改为BOOT01&#xff0c;BOOT10…...

编程日记 2025/9/2 3:10:03

机器学习：让数据开口说话的科技魔法

在人工智能飞速发展的今天&#xff0c;「机器学习」已成为推动数字化转型的核心引擎。无论是手机的人脸解锁、网购平台的推荐系统&#xff0c;还是自动驾驶汽车的决策能力&#xff0c;背后都离不开机器学习的技术支撑。那么&#xff0c;机器学习究竟是什么&#xff1f;它又有哪…...

编程日记 2025/9/2 3:13:29

PDF解析示例代码学习

以下是结合多种技术实现的PDF解析详细示例&#xff08;Python实现&#xff09;&#xff0c;涵盖文本、表格和扫描件处理场景&#xff1a; 一、环境准备与依赖安装 # 核心依赖库 pip install pdfplumber tabula-py pytesseract opencv-python mysql-connector-python 二、完整…...

编程日记 2025/9/2 3:11:25

【云平台监控】安装应用Ansible服务

安装应用Ansible服务 文章目录 安装应用Ansible服务资源列表基础环境一、安装Ansible1.1、部署Ansible1.2、配置主机清单1.2.1、方法11.2.2、方法2 二、Ansible命令应用基础2.1、ping模块2.2、command模块2.3、user模块2.4、group模块2.5、cron模块2.6、copy模块2.7、file模块2…...

编程日记 2025/9/2 3:11:25

项目执行中的目标管理：从战略到落地的闭环实践

——如何让目标不“跑偏”、团队不“掉队”&#xff1f; 引言&#xff1a;为什么目标管理决定项目成败&#xff1f; 根据PMI研究&#xff0c;47%的项目失败源于目标模糊或频繁变更。在复杂多变的项目环境中&#xff0c;目标管理不仅是制定KPI&#xff0c;更是构建“方向感-执行…...

编程日记 2025/9/2 3:11:56

如何优雅地处理 API 版本控制？

API 会不断发展&#xff0c;而用户的需求也会随之变化。那么&#xff0c;如何确保你的 API 在升级时不会影响现有用户&#xff1f;答案就是&#xff1a;API 版本控制。就像你更新了一个应用程序&#xff0c;引入了新功能&#xff0c;但旧功能仍然保留&#xff0c;让老用户继续愉…...

编程日记 2025/9/2 3:09:09

如何通过Radius认证服务器实现虚拟云桌面安全登录认证：安当ASP身份认证系统解决方案

引言&#xff1a;虚拟化时代的安全挑战 随着云计算和远程办公的普及&#xff0c;虚拟云桌面&#xff08;如VMware Horizon、Citrix&#xff09;已成为企业数字化办公的核心基础设施。然而&#xff0c;传统的用户名密码认证方式暴露了诸多安全隐患&#xff1a;弱密码易被暴力破…...

编程日记 2025/9/2 3:09:11

自然语言处理spaCy

spaCy 是一个流行的开源 自然语言处理&#xff08;NLP&#xff09; 库&#xff0c;专注于 高效、易用和工业化应用。它由 Explosion AI 开发&#xff0c;广泛应用于文本处理、信息提取、机器翻译等领域。 zh_core_web_sm 是 spaCy 提供的一个小型中文预训练语言模型&#xff0…...

编程日记 2025/8/31 4:10:11

大语言模型（LLMs）中的强化学习（Reinforcement Learning, RL）

第一部分&#xff1a;强化学习基础回顾 在深入探讨LLMs中的强化学习之前&#xff0c;我们先快速回顾一下强化学习的核心概念&#xff0c;确保基础扎实。 1. 强化学习是什么&#xff1f; 强化学习是一种机器学习范式&#xff0c;目标是让智能体&#xff08;Agent&#xff09;…...

编程日记 2025/8/25 21:32:52

数字后端实现Innovus DRC Violation之如何利用脚本批量解决G4:M7i DRC Violation

大家在跑完物理验证calibre DRC之后&#xff0c;会发现DRC里面存在一种G4:M7i的DRC违例&#xff0c;这种违例一般都是出现在memory的边界。今天教大家如何利用脚本来批量处理这一类DRC问题的解决。 首先&#xff0c;我们需要把calibre的DRC结果读取到innovus里面来&#xff0c…...

编程日记 2025/8/26 10:38:43

Java版企业电子招标采购系统源业码Spring Cloud + Spring Boot +二次开发+ MybatisPlus + Redis

功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查看所…...

编程日记 2025/8/28 7:29:44

CTF web入门之文件上传

知识点 产生文件上传漏洞的原因 原因： 对于上传文件的后缀名（扩展名）没有做较为严格的限制 对于上传文件的MIMETYPE(用于描述文件的类型的一种表述方法) 没有做检查 权限上没有对于上传的文件目录设置不可执行权限，（尤其是对于shebang类型的文件） 对于web server对于上传…...

编程日记 2025/8/31 9:51:25

ArmSoM Sige5 CM5：RK3576 上 Ultralytics YOLOv11 边缘计算新标杆

在计算机视觉技术加速落地的今天&#xff0c;ArmSoM 正式宣布其基于 ​​Rockchip RK3576​​ 的旗舰产品 ​​Sige5 开发板​​ 和 ​​CM5 核心板​​ 全面支持 Ultralytics YOLOv11 模型的 RKNN 部署。这一突破标志着边缘计算领域迎来新一代高性能、低功耗的 AI 解决方案&am…...

编程日记 2025/8/27 22:26:00

游戏引擎学习第224天

回顾游戏运行并指出一个明显的图像问题。 回顾一下之前那个算法 我们今天要做一点预加载的处理。上周刚完成了游戏序章部分的所有剪辑内容。在运行这一部分时&#xff0c;如果观察得足够仔细&#xff0c;就会注意到一个问题。虽然因为视频流压缩质量较低&#xff0c;很难清楚…...

编程日记 2025/8/31 13:25:24

PN1-S25系列ProfiNet网关模组产品方案

PN1-S25系列ProfiNet网关模组是一款专为工业通信环境设计的先进设备&#xff0c;旨在实现ProfiNet与Modbus RTU协议之间的无缝转换&#xff0c;从而优化工业自动化系统中的数据传输效率。以下是对该系列ProfiNet网关模组产品的详细介绍&#xff1a; 一、ProfiNet网关模组功能特…...

编程日记 2025/8/29 12:41:44

提示工程指南学习记录（三）

提示词示例 文本概括 Explain the above in one sentence&#xff08;用一句话解释上面的信息&#xff09;&#xff1a; 提示词工程是一种用于自然语言处理的任务&#xff0c;目的是通过给定的文本或语音输入来生成相应的输出。它基于预训练的大型语言模型&#xff0c;例如通…...

编程日记 2025/8/28 8:27:21

04 GE - 钳制属性，等级

1.PostGameplayEffectExecute 1.作用&#xff1a;在这里对生命值进行最后的钳制防止越界。 2.参数中有什么&#xff1a; FGameplayEffectModCallbackData //传进来的值 {EffectSpec; //GESpecTargetASC //目标ASCFGameplayModifierEvaluatedData& EvaluatedData{Magni…...

编程日记 2025/8/26 15:37:04

【机器学习】机器学习笔记

1 机器学习定义 计算机程序从经验E中学习&#xff0c;解决某一任务T&#xff0c;进行某一性能P&#xff0c;通过P测定在T上的表现因经验E而提高。 eg&#xff1a;跳棋程序 E&#xff1a; 程序自身下的上万盘棋局 T&#xff1a; 下跳棋 P&#xff1a; 与新对手下跳棋时赢的概率…...

编程日记 2025/8/27 21:51:00

使用SSE实现实时消息推送并语音播报：从后端到前端的完整指南

前言 在现代Web应用中&#xff0c;实时消息推送已成为提升用户体验的关键功能。无论是即时聊天、通知提醒还是实时数据更新&#xff0c;都需要一种高效的服务器到客户端的通信机制。本文将详细介绍如何使用Server-Sent Events (SSE)技术实现后端向前端的实时消息推送&#xff…...

编程日记 2025/8/30 20:17:58

交通运输部4项网络与数据安全标准发布

近日&#xff0c;交通运输部审查通过并发布《交通运输数据安全风险评估指南》《交通运输行业网络安全实战演练工作规程》《交通运输电子证照数据交换与应用要求》《冷藏集装箱智能终端技术规范》等 4 项交通运输行业标准&#xff08;2025 年第 3 批&#xff09;。 ​其中&#…...

编程日记 2025/8/28 12:44:53

HarmonyOS-ArkUI V2装饰器： @Monitor装饰器：状态变量修改监听

Monitor作用 Monitor的作用就是来监听状态变量的值变化的。被Monitor修饰的函数，会在其对应监听的变量发生值的变化时，回调此函数，从而可以让您知道是什么值发生变化了，变化前是什么值，变化后是什么值。 V1版本的装饰器，有个叫@Watch的装饰器，其实也有监听变化的能力，…...

编程日记 2025/9/1 14:12:26

在Ubuntu系统中运行Windows程序

在Ubuntu系统中运行Windows程序可通过以下方法实现&#xff0c;根据使用场景和需求选择最适合的方案&#xff1a; 一、使用Wine兼容层&#xff08;推荐轻量级场景&#xff09; 原理&#xff1a;通过模拟Windows API环境直接运行.exe文件&#xff0c;无需安装完整系统。 步骤&a…...

编程日记 2025/9/1 19:22:04

七大数据库全面对比：ClickHouse、ES、MySQL等特性、优缺点及使用场景

七大数据库全面对比：ClickHouse、ES、MySQL等特性、优缺点及使用场景 引言 在数字化时代，数据库的选择对于业务的成功至关重要。本文将通过表格形式，对ClickHouse、Elasticsearch（ES）、MySQL、SQL Server、MongoDB、HBase、Cassandra这七大数据库进行特性、优缺点及使用…...

编程日记 2025/8/31 12:58:47

循环神经网络 - 门控循环单元网络之参数学习

GRU&#xff08;门控循环单元&#xff09;的参数学习与其他循环神经网络类似&#xff0c;主要依赖于梯度下降和反向传播通过时间&#xff08;BPTT&#xff09;算法。下面我们通过一个简单例子来说明 GRU 参数是如何在训练过程中“自适应”调整的。 一、GRU参数学习 假设我们的…...

编程日记 2025/9/1 9:09:55

Java并发编程面试题：内存模型（6题）

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…...

编程日记 2025/9/1 14:27:26

SpringBoot Starter自定义：创建可复用的自动配置模块

文章目录 引言一、自定义Starter基础知识二、创建自动配置模块2.1 项目结构搭建2.2 配置属性类2.3 服务接口及实现2.4 自动配置类2.5 spring.factories文件2.6 Maven依赖配置 三、创建Starter模块3.1 项目结构3.2 Maven依赖配置 四、使用自定义Starter4.1 添加依赖4.2 配置属性…...

编程日记 2025/8/31 0:06:02

服务器风扇故障导致过热问题的解决方案

# 服务器风扇故障导致过热问题的解决方案 ## 一、故障诊断与确认 ### 1. 确认风扇故障现象 bash # 检查系统日志中的硬件错误 dmesg | grep -i fan journalctl -b | grep -i thermal # 查看传感器数据&#xff08;需要安装lm-sensors&#xff09; sudo sensors-detect sudo …...

编程日记 2025/8/27 14:30:18

[OS] vDSO + vvar（频繁调用的处理） | 存储：寄存器(高效)和栈（空间大）| ELF标准包装规范（加速程序加载）

vDSO vvar 一、社区公告板系统&#xff08;类比 vDSO vvar&#xff09; 想象你住在一个大型社区&#xff0c;管理员&#xff08;内核&#xff09;需要向居民&#xff08;用户程序&#xff09;提供实时信息&#xff08;如天气预报、社区活动时间等&#xff09;。直接让每个居…...

编程日记 2025/8/27 4:20:11