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

B树和B+树

news 来源：原创 2025/9/19 13:13:14

1. B树

1.1 定义

B树是一种多路平衡查找树，具有以下性质：

每个节点最多包含 m 个子节点（m 阶 B树）。
根节点至少有两个子节点（除非它是叶子节点）。
每个内部节点（非根和非叶子节点）至少有 ⌈m/2⌉ 个子节点。
所有叶子节点位于同一层。
每个节点包含多个关键字，且关键字按升序排列。

1.2 操作

查找

从根节点开始，逐层比较关键字，找到目标值或确定目标值不存在。

插入

找到插入位置。
如果节点未满，直接插入。
如果节点已满，进行节点分裂：
- 将中间关键字提升到父节点。
- 分裂后的两个节点分别包含较小和较大的关键字。

删除

找到目标关键字。
如果关键字在叶子节点，直接删除。
如果关键字在内部节点，用后继关键字替换，然后删除后继关键字。
如果删除后节点关键字数少于 ⌈m/2⌉−1，需要进行合并或借用操作。

1.3 代码示例（伪代码）


class BTreeNode:def __init__(self, leaf=False):self.leaf = leafself.keys = []self.children = []class BTree:def __init__(self, t):self.root = BTreeNode(True)self.t = t  # 最小度数def search(self, k, x=None):if x is not None:i = 0while i < len(x.keys) and k > x.keys[i]:i += 1if i < len(x.keys) and k == x.keys[i]:return (x, i)elif x.leaf:return Noneelse:return self.search(k, x.children[i])else:return self.search(k, self.root)def insert(self, k):root = self.rootif len(root.keys) == (2 * self.t) - 1:temp = BTreeNode()self.root = temptemp.children.insert(0, root)self.split_child(temp, 0)self.insert_non_full(temp, k)else:self.insert_non_full(root, k)def insert_non_full(self, x, k):i = len(x.keys) - 1if x.leaf:x.keys.append(None)while i >= 0 and k < x.keys[i]:x.keys[i + 1] = x.keys[i]i -= 1x.keys[i + 1] = kelse:while i >= 0 and k < x.keys[i]:i -= 1i += 1if len(x.children[i].keys) == (2 * self.t) - 1:self.split_child(x, i)if k > x.keys[i]:i += 1self.insert_non_full(x.children[i], k)def split_child(self, x, i):t = self.ty = x.children[i]z = BTreeNode(y.leaf)x.children.insert(i + 1, z)x.keys.insert(i, y.keys[t - 1])z.keys = y.keys[t: (2 * t) - 1]y.keys = y.keys[0: t - 1]if not y.leaf:z.children = y.children[t: 2 * t]y.children = y.children[0: t - 1]

2. B+树

2.1 定义

B+树是 B树的一种变体，具有以下性质：

内部节点只存储关键字，不存储数据。
所有数据都存储在叶子节点中。
叶子节点通过指针连接，形成一个有序链表。

2.2 操作

查找

从根节点开始，逐层比较关键字，直到找到目标叶子节点。

插入

找到插入位置。
如果叶子节点未满，直接插入。
如果叶子节点已满，进行节点分裂：
- 将中间关键字提升到父节点。
- 分裂后的两个叶子节点分别包含较小和较大的关键字。

删除

找到目标关键字。
从叶子节点中删除关键字。
如果删除后节点关键字数少于 ⌈m/2⌉，需要进行合并或借用操作。

2.3 代码示例（伪代码）

class BPlusTreeNode:def __init__(self, leaf=False):self.leaf = leafself.keys = []self.children = []self.next = None  # 指向下一个叶子节点class BPlusTree:def __init__(self, t):self.root = BPlusTreeNode(True)self.t = t  # 最小度数def search(self, k, x=None):if x is not None:i = 0while i < len(x.keys) and k > x.keys[i]:i += 1if x.leaf:if i < len(x.keys) and k == x.keys[i]:return xelse:return Noneelse:return self.search(k, x.children[i])else:return self.search(k, self.root)def insert(self, k):root = self.rootif len(root.keys) == (2 * self.t) - 1:temp = BPlusTreeNode()self.root = temptemp.children.insert(0, root)self.split_child(temp, 0)self.insert_non_full(temp, k)else:self.insert_non_full(root, k)def insert_non_full(self, x, k):i = len(x.keys) - 1if x.leaf:x.keys.append(None)while i >= 0 and k < x.keys[i]:x.keys[i + 1] = x.keys[i]i -= 1x.keys[i + 1] = kelse:while i >= 0 and k < x.keys[i]:i -= 1i += 1if len(x.children[i].keys) == (2 * self.t) - 1:self.split_child(x, i)if k > x.keys[i]:i += 1self.insert_non_full(x.children[i], k)def split_child(self, x, i):t = self.ty = x.children[i]z = BPlusTreeNode(y.leaf)x.children.insert(i + 1, z)x.keys.insert(i, y.keys[t - 1])z.keys = y.keys[t: (2 * t) - 1]y.keys = y.keys[0: t - 1]if not y.leaf:z.children = y.children[t: 2 * t]y.children = y.children[0: t - 1]else:z.next = y.nexty.next = z

3. B树与 B+树的比较

特性	B树	B+树
数据存储	内部节点和叶子节点都存储数据	只有叶子节点存储数据
叶子节点连接	无	通过指针连接成有序链表
查找性能	适用于随机查找	适用于范围查找
磁盘 I/O	较高	较低

B树和B+树

1. B树 1.1 定义 B树是一种多路平衡查找树，具有以下性质： 每个节点最多包含 m 个子节点（m 阶 B树）。根节点至少有两个子节点（除非它是叶子节点）。每个内部节点（非根和非叶子节点&#xff…...

编程日记 2025/9/19 13:13:14

分布式事务核心理论：CAP与BASE

一、引言：分布式系统的挑战在互联网应用中，随着业务规模的扩大，单机数据库已无法满足高并发和海量数据存储需求。分布式系统将数据拆分到不同节点，但随之带来了数据一致性的难题。CAP与BASE理论为分布式事务提供了重要的设计指导…...

编程日记 2025/9/16 20:25:45

【UCB CS 61B SP24】Lecture 4 - Lists 2: SLLists学习笔记

本文内容为重写上一节课中的单链表，将其重构成更易于用户使用的链表，实现多种操作链表的方法。 1. 重构单链表SLList 在上一节课中编写的 IntList 类是裸露递归的形式，在 Java 中一般不会这么定义，因为这样用户可能需要非常了解…...

编程日记 2025/9/19 0:15:44

记录一个ES分词器不生效的解决过程

问题背景商城项目,其中商品查询检索使用的是ES, 但存在某些商品查询不到的问题例如:某商品名包含AA_BBB这样的关键词,但是搜索"AA"不能查询到该商品,但是将商品名修改为AA BBB后就能查询到了. 怀疑是分词的问题,但看代码,在创建ES索引时在对应字段上也定义了分词器…...

编程日记 2025/9/19 11:19:23

Jeecg+vue3去掉JInput组件默认模糊查询的配置方式

遇见的问题：input查询带**号情况1、使用schemas配置的表单项添加type""属性，默认type为like，去掉模糊则配置为空文档链接 jeecg文档说明JInput 2、直接调用组件则在属性上直接添加type""属性...

编程日记 2025/9/16 18:59:22

Could not initialize class io.netty.util.internal.Platfor...

异常信息： Exception in thread "main" java.lang.NoClassDefFoundError: Could not initialize class io.netty.util.internal.PlatformDependent0 Caused by: java.lang.ExceptionInInitializerError: Exception java.lang.reflect.InaccessibleObjec…...

编程日记 2025/9/19 5:03:53

什么是业务流程分类框架

业务流程分类框架是一个用于组织和系统化地分类业务流程的结构化方法。它旨在帮助企业理解、管理、分析和改进其运营流程。可以把它想象成一个图书馆的图书分类系统，帮助快速找到和理解不同类型的书籍。对于业务流程来说，分类框架帮助快速了解不同类型的…...

编程日记 2025/9/19 4:19:45

向量的点乘的几何意义

源自AI 向量的点乘（Dot Product）在几何和图形学中有重要的意义。它不仅是数学运算，还可以用来描述向量之间的关系。以下是点乘的几何意义及其应用： 1. 点乘的定义对于两个向量 a 和 b，它们的点乘定义为：…...

编程日记 2025/9/19 11:35:11

达梦数据库应用开发_JDBC接口介绍_yxy

达梦数据库应用开发_JDBC接口介绍 1 JDBC是什么？2 JDBC主要类或接口介绍2.1 建立与 DM 数据库的连接2.2 转接发送 SQL 语句到数据库2.3 处理并返回语句执行结果 3 JDBC基本使用3.1 前期准备3.2 增删改查代码示例3.3 绑定变量操作示例3.4 大字段操作示例 1 JDBC是什么…...

编程日记 2025/9/17 1:12:49

在ubuntu上用Python的openpyxl模块操作Excel的案例

文章目录安装模块读取Excel数据库取数匹配数据和更新Excel数据在Ubuntu系统的环境下基本职能借助Python的openpyxl模块实现对Excel数据的操作。安装模块本次需要用到的模块需要提前安装(如果没有的话) pip3 install openpyxl pip3 install pymysql在操作前，需…...

编程日记 2025/9/17 1:12:47

RabbitMQ介绍以及基本使用

文章目录一、什么是消息队列？ 二、消息队列的作用（优点） 1、解耦 2、流量削峰 3、异步 4、顺序性三、RabbitMQ基本结构四、RabbitMQ队列模式 1、简单队列模式 2、工作队列模式 3、发布/订阅模式 4、路由模式 5、主题模式 6、…...

编程日记 2025/9/18 12:23:44

搭建 Hadoop 3.3.6 伪分布式

搭建 Hadoop 3.3.6 伪分布式 IP 192.168.157.132 初始化操作更改yum源 # 1_1.安装Wget yum install wget# 1_2.备份CentOS-Base.repo文件 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo_bak# 2.下载阿里yum源配置 wget -O /etc/yum.repos.d/Cen…...

编程日记 2025/9/18 2:01:12

进程控制（靠原语实现）

什么是进程控制？ 进程控制的主要功能是：对系统中的所有进程实施有效管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。简化理解：进程控制就是要实现进程状态转换。知识一览： 如何实现进程控制&#…...

编程日记 2025/9/17 1:12:42

linux5-多任务--进程fork（）

一.多任务：让系统具备同时处理多个任务的能力 1.如何实现多任务 1.1进程：操作系统上正在运行的程序，需要消耗内存和CPU 1.1.1 进程的生存周期：创建、调度、消亡 1.1.1.1进程的创建：每个进程被创建时，操作…...

编程日记 2025/9/17 19:24:50

【蓝桥】二分法

1、简介 1.1 定义： 通过将问题的搜索范围一分为二，迭代地缩小搜索范围，直到找到目标或确定目标不存在 1.2 适用： 有序数据集合，且每次迭代可以将搜索范围缩小一半 1.3 本质： 枚举：利用数据结构…...

编程日记 2025/9/17 1:12:38

linux查看程序占用的本地端口

ss是Socket Statistics的缩写，用来替代旧的netstat工具，功能更强大，执行更快。它用于查看系统的网络连接情况，包括TCP、UDP等协议的信息。一. 命令解析： sudo ss -tulwnpss (Socket Statistics)：替代 ne…...

编程日记 2025/9/18 21:49:20

统计函数运行时间的python脚本

这是一个统计函数运行时间的实用脚本，其中用到了函数的嵌套、链式传输参数，以及修饰器。 import time# 定义一个装饰器timer，用于计算被装饰函数的运行时间 def timer(func):print("执行了timer")def wrapper(*args, **kwargs):st…...

编程日记 2025/9/17 1:12:33

百度搜索和文心智能体接入DeepSeek满血版——AI搜索的新纪元

在当今数字化时代，搜索引擎作为互联网信息获取的核心工具，正经历着前所未有的变革。据悉，2025年2月16日，百度搜索和文心智能体平台宣布全面接入DeepSeek和文心大模型的最新深度搜索功能，搜索用户可免费使用DeepSeek和文…...

编程日记 2025/9/17 1:12:31

快速入门Springboot+vue——MybatisPlus快速上手

学习自哔哩哔哩上的“刘老师教编程”，具体学习的网站为：6.MybatisPlus快速上手_哔哩哔哩_bilibili，以下是看课后做的笔记，仅供参考。第一节 ORM介绍 ORM对象关系映射，为了解决面向对象与关系数据库存在的互补匹配现象…...

编程日记 2025/9/17 1:12:29

在C#中动态访问对象属性时,用表达式树可以获得高效性能

在C#中如何用表达式树动态访问对象属性的问题。用户可能已经知道反射的基本用法，但想用表达式树来提高性能，因为表达式树编译后的委托执行速度比反射快。首先，表达式树的基本概念。表达式树允许在运行时构建代码，并编译成可执行的…...

编程日记 2025/9/17 1:12:28

性能：React 实战优化技巧之函数闭包

子组件使用了 React.memo ，为什么 “prop 值未发生改变”，子组件依然被重新渲染了？ 🚧 示例：点击子组件中按钮，获取 input 数据进行提交（常见于表单） index.tsx import Author f…...

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

蓝桥杯学习大纲

（致酷德与热爱算法、编程的小伙伴们） 在查阅了相当多的资料后，发现没有那篇博客、文章很符合我们备战蓝桥杯的学习路径。所以，干脆自己整理一篇，欢迎大家补充！ 一、蓝桥必备高频考点我们以此为重点学习…...

编程日记 2025/9/16 11:31:20

Windows11切换回Windows10风格右键菜单

参考文章：Win11新版右键菜单用不惯？一键切换回Win10经典版！-CSDN博客以管理员权限运行命令行cmd 切换为经典旧版右键菜单，执行 reg.exe add “HKCU\Software\Classes\CLSID\{86ca1aa0-34aa-4e8b-a509-50c905bae2a2}\InprocServe…...

编程日记 2025/9/16 4:05:09

Python 爬虫selenium

1.selenium自动化 selenium可以操作浏览器，在浏览器页面上实现：点击、输入、滑动等操作。不同于selenium自动化，逆向本质是： 分析请求，例如：请求方法、请求参数、加密方式等。用代码模拟请求去实现同等…...

编程日记 2025/9/17 1:12:20

Linux常用操作

软件安装 CentOS系统使用： yum [install remove search] [-y] 软件名称 install 安装 remove 卸载 search 搜索 -y，自动确认 Ubuntu系统使用 apt [install remove search] [-y] 软件名称 install 安装 remove 卸载 search 搜索 -y，自动确认 yum 和 apt 均需要root权限 syste…...

编程日记 2025/9/18 15:45:08

Note25022001_Excel表格如何在文字的中间或者后边插入当前日期

Excel表格如何在文字的中间或者后边插入当前日期关键字： EXCEL；当前日期；文字中间如图所示： 其中一种实现方法如下： 打开表格，在某一个表格中输入： "项目计划管理表（厂内&…...

编程日记 2025/9/17 1:12:16

Django5 实用指南（四）URL路由与视图函数

4.1 Django5的URL路由系统 Django 的 URL 路由系统是其核心组件之一，它负责将用户的 HTTP 请求（即 URL）映射到相应的视图函数上。每当用户在浏览器中访问某个 URL 时，Django 会根据项目的 URL 配置文件（urls.py&#…...

编程日记 2025/9/19 5:56:21

Unity3D 基于 GPU 动画和 Compute Shader 的大批量动画渲染详解

引言在现代游戏开发中，渲染大量动画角色是一个常见的需求，尤其是在大规模战斗场景、开放世界游戏或 VR/AR 应用中。传统的 CPU 动画计算和渲染方式在面对大批量角色时，往往会遇到性能瓶颈。为了优化性能，开发者可以利用 GPU 的强…...

编程日记 2025/9/19 3:54:29

遥感影像目标检测：从CNN（Faster-RCNN）到Transformer（DETR）

我国高分辨率对地观测系统重大专项已全面启动，高空间、高光谱、高时间分辨率和宽地面覆盖于一体的全球天空地一体化立体对地观测网逐步形成，将成为保障国家安全的基础性和战略性资源。未来10年全球每天获取的观测数据将超过10PB，遥感大数据时…...

编程日记 2025/9/17 1:12:11

什么是DeFi (去中心化金融)

DeFi (去中心化金融) 概述 💰 1. DeFi 基础概念 1.1 什么是 DeFi？ DeFi 是建立在区块链上的金融服务生态系统，它： 无需中心化中介开放且透明无需许可即可参与代码即法律 1.2 DeFi 的优势开放性：任何人都可以参与…...

编程日记 2025/9/19 6:51:40

深入解析 sudo -l 命令的输出内容

在 Linux 系统中，sudo 命令允许普通用户以超级用户（root）权限执行命令。sudo -l 命令用于查看当前用户在 sudoers 配置文件中的权限，以及与 sudo 相关的安全策略。本文将详细解析 sudo -l 输出的各个部分，包括用户权限…...

编程日记 2025/9/18 14:34:34

DeepSeek 助力 Vue 开发：打造丝滑的瀑布流布局（Masonry Layout）

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏关注哦 💕 目录 Deep…...

编程日记 2025/9/19 11:37:54

linux学习【7】Sourc Insight 4.0设置+操作

目录 1.Source Insight是什么？2.需要哪些配置？3.怎么新建项目4.一些问题的解决1.中文乱码问题按照这个设置就可以了，下面的设置会标明设置理由。 1.Source Insight是什么？ 阅读源码，编辑源码，不能编译&am…...

编程日记 2025/9/18 19:33:10

OpenCV形态学操作

1.1. 形态学操作介绍初识： 形态学操作是一种基于图像形状的处理方法，主要用于分析和处理图像中的几何结构。其核心是通过结构元素（卷积核）对图像进行扫描和操作，从而改变图像的形状和特征。例如： 腐蚀&…...

编程日记 2025/9/19 9:12:47

使用Python中的`gensim`库构建LDA（Latent Dirichlet Allocation）模型来分析收集到的评论

下面为你详细介绍如何使用Python中的gensim库构建LDA（Latent Dirichlet Allocation）模型来分析收集到的评论。LDA是一种主题模型，它可以将文档集合中的文本按照主题进行分类。步骤概述数据预处理：对收集到的评论进行清洗、分词…...

编程日记 2025/9/17 1:12:03

【STM32】外部时钟|红外反射光电开关

1.外部时钟单片机如何对外部触发进行计数？先看一下内部时钟，内部时钟是接在APB1和APB2时钟线上的，APB1,APB2来自stm32单片机内部的脉冲信号，也叫内部时钟。我们用来定时。同样我们可以把外部的信号接入单片机，来对其…...

编程日记 2025/9/18 19:31:34

Visual Studio Code 集成 Baidu Comate

文章目录安装Baidu Comate插件安装Baidu Comate插件从左主侧栏中点击【扩展】这个图标，然后在上方输入栏中输入 baidu comate —>选中列出的Bai Comate —>点击【安装】按钮，等待安装完毕…...

编程日记 2025/9/17 1:11:59

数据结构者

数据（data）：可被计算机接受处理的符号总称数据元素（data element）：数据的基本单位，常作为一个整体进行考虑和处理一个数据元素可以由若干个数据项（data item）组成数…...

编程日记 2025/9/18 3:10:49

论文阅读 DOES END-TO-END AUTONOMOUS DRIVING REALLY NEED PERCEPTION TASKS?

端到端的强势来袭，好久了~~~ 简单翻译：端到端真的需要感知任务嘛？ code https://github.com/PeidongLi/SSR. https://arxiv.org/pdf/2409.18341 1. 摘要端到端自动驾驶（E2EAD）方法通常依赖于监督式感知任务来提取显…...

编程日记 2025/9/18 12:50:55

总结UML类图几种关系画法

最近在公司需要画类图，有些遗忘，于是重新学习并并总结了一下： 继承：实线空心三角箭头。A继承B，A指向B。A是一种B。实现：虚线空心三角箭头。A实现B，A指向B。A实现B接口。关联：实线普…...

编程日记 2025/9/17 1:11:53

python-leetcode 40.二叉树的层序遍历

题目： 给定二叉树的根节点root,返回其节点值得层序遍历（即逐层从左到右访问所有节点） 方法：广度优先搜索 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val0, leftNone, rightNon…...

编程日记 2025/9/16 12:59:27

安利：外文文献翻译插件

沉浸式翻译好用吹爆！！！！！！！！ 任务 2.谷歌学术复制外文的标题搜索 3.进入文献所在，登录对应机构 4.可以看到都翻译好了 5.然后复制到文档，改改格式巴…...

编程日记 2025/9/18 20:24:27

Python——生成AIGC图像

文章目录一、背景介绍二、效果图展示三、完整代码四、分步解释五、实用建议 1）提示词技巧 2）性能优化 3）常见问题处理 4）扩展功能建议六、注意事项 1. 硬件要求 2. 法律合规 3. 模型安全一、背景介绍 AIGC&a…...

编程日记 2025/9/16 23:40:37

OpenGL（2）基于Qt做OpenGL开发

文章目录一、基于Qt做OpenGL开发1、环境准备2、创建OpenGL窗口3、绘制基本图形一、基于Qt做OpenGL开发 1、环境准备确保你已经安装了 Qt 开发环境（包含 Qt Creator），并且支持 OpenGL 开发。在创建 Qt 项目时，选择 “Qt Widget…...

编程日记 2025/9/18 14:35:37

【Windows软件 - HeidiSQL】导出数据库

HeidSQL导出数据库软件信息具体操作示例文件选项分析选项（1） 结果（1） -- -------------------------------------------------------- -- 主机: 127.0.0.1 -- 服务器版本: …...

编程日记 2025/9/17 23:36:43

用deepseek学大模型04-模型可视化与数据可视化

deepseek.com: pytorch可视化工具生成神经网络图在 PyTorch 中，可视化神经网络结构的常用工具和方法有以下几种，以下将详细介绍它们的用法： 1. TensorBoard (PyTorch 官方集成) PyTorch 通过 torch.utils.tensorboard 支持 TensorBoard&a…...

编程日记 2025/9/16 23:40:32

rust笔记8-Deref与隐式解引用强制转换

Rust 的智能指针和 Deref Trait 是 Rust 中非常重要的概念，它们使得 Rust 的引用和指针操作更加灵活和安全。下面我们将深入介绍 Deref Trait、Deref 与 &、* 运算符的关系，以及 Rust 的隐式解引用强制转换（Deref Coercion）。 1. 智能指针与 Deref Trait 智能指针（如…...

编程日记 2025/9/16 22:59:35

Debian软件包重构

Explore projects GitLab 1. apt-get build-dep <pkg> ## 安装编译依赖包 2. apt source <pkg> ## 下载 <pkg> 包的源码 3. 创建 git ，打补丁 4. dpkg-buildpackage -b -uc -us -d ## 重新打包编译 # 解压出包中的文件到 extract 目…...

编程日记 2025/9/16 23:40:28

学习 `@PreDestroy`：Java EE/Jakarta EE 生命周期回调

学习 PreDestroy：Java EE/Jakarta EE 生命周期回调前言1. 什么是 PreDestroy？2. PreDestroy 的用途3. 使用 PreDestroy 的条件4. 代码示例运行结果： 5. PreDestroy 的调用时机6. 注意事项7. 实际应用场景场景 1：数据库连接管理场…...

编程日记 2025/9/18 4:20:57

JDK最详细安装教程，零基础入门到精通，收藏这篇就够了

目录一、下载与安装二、配置环境三、验证是否配置成功一、下载与安装 1、下载地址 http://www.oracle.com/technetwork/java/javase/downloads/index.html 2、选择自己想要的版本下载，并且选择自己电脑对应的版本下载 3、下载完成之后，双击打开然后…...

编程日记 2025/9/16 23:40:25