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

数据结构 —— B树

数据结构 —— B树

  • B树
  • B树的插入操作
    • 分裂
      • 孩子分裂
      • 父亲分裂

我们之前学过了各种各样的树,二叉树,搜索二叉树,平衡二叉树,红黑树等等等等,其中平衡二叉树和红黑树都是控制树的高度来控制查找次数。

但是,这都基于内存能放的下

平衡二叉树和红黑树等数据结构确实是为了在内存中高效处理动态数据集而设计的。它们的主要目标是在各种操作(如查找、插入和删除)中保持对数时间复杂度O(log n),其中n是树中节点的数量。这意味着随着数据集的增长,操作时间不会线性增长,而是以较慢的速度增长,保持较高的性能。
在设计上,平衡二叉树和红黑树假设整个数据集能够被加载到内存中,这是因为这些树的算法和操作需要频繁地遍历树的不同部分。磁盘I/O操作比内存访问要慢得多,因此如果数据集太大而不能完全装入内存,使用这些数据结构将大大降低效率。

但是,直接在磁盘上实现平衡二叉树或红黑树通常不是最有效的方法,因为磁盘访问的成本高,而这类树的许多操作涉及多次磁盘读写。因此,对于大规模数据集,更常见的做法是使用专门针对磁盘访问优化的数据结构,如B树或B+树,它们在设计上考虑了磁盘I/O的特性,可以更有效地处理大量数据

B树

1970年,R.Bayer和E.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树,称为B树(后面有一个B的改进版本B+树,然后有些地方的B树写的的是B-树,注意不要误读成"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个孩子包含的元素的值域划分
  6. 每个结点的结构为:(n,A0,K1,A1,K2,A2,… ,Kn,An)其中,Ki(1≤i≤n)为关键字,且Ki<Ki+1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。

说白了,我们以前的树中,一个结点包含的数据量只能有一个
在这里插入图片描述B树的基本思想就是一个结点可以携带多个数据

在这里插入图片描述
但是每个结点也有自己的要求:一个结点要包括数据和孩子

假设我们是一棵3阶的B树,规定每个结点的孩子最多有3个,而数据个数比孩子个数小1

在这里插入图片描述但是我们数据个数为偶数的话,后面的分裂操作不好操作,所以我们会多开一个数据空间,但是不会装入任何数据,同时会增加一个孩子:
在这里插入图片描述

B树的插入操作

我们这里以3阶的B树为例:

int a[] = {53, 139, 75, 49, 145, 36, 101} //构建b树

在这里插入图片描述
下面我们要插入75:
在这里插入图片描述这个时候数据个数已经超过了两个,需要进行分裂

分裂

这个时候75被提出来:
在这里插入图片描述在这里插入图片描述
接下来我们插入49,145:
在这里插入图片描述

孩子分裂

接着我们插入36
在这里插入图片描述

在这里插入图片描述

父亲分裂

我们这样一直插入,插入到139:

在这里插入图片描述
在这里插入图片描述
B树的插入过程是反人类的,是先有孩子,再有父亲,其中孩子会分裂,父亲也会分裂

我们来看看代码,大家能看懂多少看多少:

#pragma once
#include <iostream>
using namespace std;// B-树节点模板定义
template<class K, size_t M>
struct BTreeNode
{// 键数组,存储节点的关键字K _keys[M];// 子节点数组,存储指向子节点的指针BTreeNode<K, M>* _Children[M + 1];// 指向父节点的指针BTreeNode<K, M>* _Parent;// 节点中的实际关键字数量size_t _n;// 构造函数,初始化节点BTreeNode(){// 初始化所有键为空for (int i = 0; i < M; i++){_keys[i] = K();_Children[i] = nullptr;}// 初始化最后一个子节点指针为空_Children[M] = nullptr;_Parent = nullptr;_n = 0; // 节点中实际关键字数量为0}
};// B-树模板类定义
template<class K, size_t M>
class BTree
{typedef BTreeNode<K, M> _Node;public:// 查找键的函数pair<_Node*, int> Find(const K& key){_Node* cur = _root; // 从根节点开始查找_Node* parent = nullptr;while (cur){size_t i = 0;// 在当前节点中查找键while (i < cur->_n){if (key < cur->_keys[i]){break; // 键小于当前键,应该在左子树}else if (key > cur->_keys[i]){i++; // 键大于当前键,检查下一个键}else{return make_pair(cur, i); // 找到键,返回节点和键的索引}}// 移动到下一个子节点parent = cur;cur = cur->_Children[i];}// 没有找到键,返回父节点和-1return make_pair(parent, -1);}// 插入键到节点中的函数void InsertKey(_Node* node, const K& key, _Node* child){int end = node->_n - 1;// 找到插入位置并移动键和子节点while (end >= 0){if (key < node->_keys[end]){node->_keys[end + 1] = node->_keys[end];node->_Children[end + 2] = node->_Children[end + 1];end--;}else{break;}}// 插入新的键和子节点node->_keys[end + 1] = key;node->_Children[end + 2] = child;node->_n++;}// 插入键的主函数bool Insert(const K& key){if (_root == nullptr){// 如果树为空,创建根节点并插入键_root = new _Node();_root->_keys[0] = key;_root->_n++;return true;}pair<_Node*, int> ret = Find(key);if (ret.second >= 0){// 键已存在,返回falsereturn false;}_Node* parent = ret.first;K newkey = key;_Node* child = nullptr;while (1){// 在父节点中插入键InsertKey(parent, newkey, child);if (parent->_n < M){// 如果父节点未满,插入成功return true;}else{// 父节点已满,需要分裂size_t mid = M / 2;// 创建一个新节点,并将父节点的一部分键和子节点移动到新节点中_Node* brother = new _Node;size_t j = 0;size_t i = mid + 1;for (; i <= M - 1; i++){brother->_keys[j] = parent->_keys[i];brother->_Children[j] = parent->_Children[i];if (parent->_Children[i]){parent->_Children[i]->_Parent = brother; //父节点分裂,分裂出了父亲的brother}j++;parent->_keys[i] = K();}// 处理新节点的最后一个右孩子节点brother->_Children[j] = parent->_Children[i];if (parent->_Children[i]){parent->_Children[i]->_Parent = brother;}brother->_n = j;parent->_n -= j + 1;// 将父节点的中间键提升到新节点newkey = parent->_keys[mid];child = brother;if (parent->_Parent == nullptr){// 如果父节点是根节点,则创建新的根节点_root = new _Node();_root->_keys[0] = parent->_keys[mid];_root->_Children[0] = parent;_root->_Children[1] = brother;_root->_n = 1;parent->_keys[mid] = K();parent->_Parent = _root;brother->_Parent = _root;break;}else{// 继续向父节点的父节点插入分裂后的节点newkey = parent->_keys[mid];parent->_keys[mid] = K();child = brother;parent = parent->_Parent;}}}return true;}// 中序遍历树的函数void InOrder(){_InOrder(_root);}// 递归实现的中序遍历void _InOrder(_Node* pRoot){if (nullptr == pRoot)return;for (size_t i = 0; i < pRoot->_n; ++i){_InOrder(pRoot->_Children[i]);cout << pRoot->_keys[i] << " ";}_InOrder(pRoot->_Children[pRoot->_n]);}private:// 树的根节点_Node* _root = nullptr;
};// 测试函数
void Test()
{int a[] = { 53, 139, 75, 49, 145, 36, 101, 34, 1, 9, 41 };BTree<int, 3> t;for (auto e : a){t.Insert(e);}t.InOrder();
}

我们可以测试,如果打印的顺序是升序,说明我们代码的逻辑没问题:
在这里插入图片描述
写代码要注意几点:

  1. 插入新结点,有可能改变父子关系(是第一个数据的孩子,插入后有可能会变成第二个数据的孩子)。
  2. 分裂结点也有可能改变父子关系(变成父亲兄弟的孩子)

相关文章:

数据结构 —— B树

数据结构 —— B树 B树B树的插入操作分裂孩子分裂父亲分裂 我们之前学过了各种各样的树&#xff0c;二叉树&#xff0c;搜索二叉树&#xff0c;平衡二叉树&#xff0c;红黑树等等等等&#xff0c;其中平衡二叉树和红黑树都是控制树的高度来控制查找次数。 但是&#xff0c;这都…...

Redis 深度历险:核心原理与应用实践 - 读书笔记

目录 第一章 基础应用篇Zset并发问题 - 分布式锁再谈分布式锁客户端在请求时加锁失败策略redis异步队列位图Hyperloglog布隆过滤器GeoHashscan 命令字典结构rehash扩容大 key 扫描 第二章 原理篇线程IO模型RESP 序列化协议持久化管道事务PubSub内存管理 第三章 集群篇CAP主从同…...

微服务重启优化kafka+EurekaNotificationServerListUpdater

由于遇到服务重启导致的业务中断等异常&#xff0c;所以计划通过kafkaeureka实现服务下线通知&#xff0c;来尽可能规避这类问题。 如果可以升级spring&#xff0c;则可以考虑nacos等更为方便的方案&#xff1b; 程序优化&#xff1a; 1.默认启用的为 PollingServerListUpdater…...

removeIf 方法设计理念及泛型界限限定

ArrayList 中的 removeIf 方法是 Java 8 中引入的集合操作方法之一。它使用了 Predicate 接口作为参数&#xff0c;以便根据指定的条件移除集合中的元素。以下是对 removeIf 方法入参设计的详细解释&#xff1a; Predicate 接口 Predicate 是一个函数式接口&#xff0c;定义了…...

kubernetes集群部署elasticsearch集群,包含无认证和有认证模式

1、背景&#xff1a; 因公司业务需要&#xff0c;需要在测试、生产kubernetes集群中部署elasticsearch集群&#xff0c;因不同环境要求&#xff0c;需要部署不同模式的elasticsearch集群&#xff0c; 1、测试环境因安全性要求不高&#xff0c;是部署一套默认配置&#xff1b; 2…...

Java 随笔记: 集合与泛型

文章目录 1. 集合框架概述2. 集合接口2.1 Collection 接口2.2 List 接口2.3 Set 接口2.4 Map 接口 3. 集合的常用操作3.1 添加元素3.2 删除元素3.3 遍历元素3.4 判断大小3.5 判断是否为空 4. 迭代器4.1 迭代器的作用4.2 迭代器的使用4.3 迭代器与增强 for 循环4.4 迭代器的注意…...

SurrealDB:高效构建实时Web应用的数据库

SurrealDB&#xff1a;数据驱动&#xff0c;实时协同。用SurrealDB简化你的开发流程- 精选真开源&#xff0c;释放新价值。 概览 SurrealDB&#xff0c;一款专为现代Web应用设计的云原生数据库&#xff0c;以其创新的架构和功能&#xff0c;为开发者提供了一个强大的工具。它整…...

SQL Server查询计划阅读及分析

​​​​​​6.4.5. 查询计划阅读及分析 SQL Server中,SQL语句的查询计划可能会包含多个节点,每个节点除了包含和对应一个操作符外,还包含节点及操作符相关的其他信息,其细节与具体的操作符相关。SQL Server查询计划与Oracle执行计划中,虽然每个节点所包含内容的具体称谓…...

SAP Fiori 实战课程(二):新建页面

课程回顾 上一课中,利用Visual studio Code 新建、并运行了一个Demo工程。可以实现对项目的启动,启动后进入一个List清单。 那么本次课程的目前就是在上一节Demo的基础上,从零开始新建一个完整的页面。实现从首页清单,选择行后,鼠标点击,进入下一个页面。 准备工作 在开…...

【Rust光年纪】超越ORM:探索Rust语言多款数据库客户端库的核心功能和使用场景

数据库操作新选择&#xff1a;从异步操作到连接管理&#xff0c;掌握Rust语言数据库客户端库的全貌 前言 在现代软件开发中&#xff0c;与数据库进行交互是一个常见的任务。Rust语言作为一种高性能、内存安全的编程语言&#xff0c;拥有丰富的生态系统来支持各种数据库操作。…...

解决:事件监听器 addEventListener 被多次调用

背景&#xff1a; 给一个元素添加了事件监听&#xff0c;click 会触发 然而在实际场景中&#xff0c;点击一次&#xff0c;事件会被触发两次 阻止冒泡也没有用 解决&#xff1a; 使用API&#xff1a;event.stopImmediatePropagation() stopImmediatePropagation() 方法可防止…...

配置RIPv2的认证

目录 一、配置IP地址、默认网关、启用端口 1. 路由器R1 2. 路由器R2 3. 路由器R3 4. Server1 5. Server2 二、搭建RIPv2网络 1. R1配置RIPv2 2. R2配置RIPv2 3. Server1 ping Server2 4. Server2 ping Server1 三、模拟网络攻击&#xff0c;为R3配置RIPv2 四、在R…...

前端调试技巧:动态高亮渲染区域

效果&#xff1a; 前端界面的渲染过程、次数&#xff0c;会通过高亮变化来显示&#xff0c;通过这种效果排除一些BUG 高亮 打开方式 F12进入后点击ESC&#xff0c;进入rendering&#xff0c;选择前三个即可&#xff08;如果没有rendering&#xff0c;点击橘色部分勾选上&…...

深克隆与浅克隆的区别与实现

在软件开发中&#xff0c;克隆对象是一个常见需求。克隆的方式主要有两种&#xff1a;深克隆&#xff08;Deep Clone&#xff09;和浅克隆&#xff08;Shallow Clone&#xff09;。了解它们的区别及其实现方法&#xff0c;对于编写高效、安全的代码非常重要。 深克隆与浅克隆的…...

【学习笔记】无人机系统(UAS)的连接、识别和跟踪(六)-无人机直接C2通信

目录 引言 5.4 直接C2通信 5.4.1 概述 5.4.2 A2X直接C2通信服务的授权策略 5.4.3 USS使用A2X直接C2通信服务的C2授权程序 5.4.4 直接C2通信建立程序 引言 3GPP TS 23.256 技术规范&#xff0c;主要定义了3GPP系统对无人机&#xff08;UAV&#xff09;的连接性、身份识别…...

认识和安装R的扩展包,什么是模糊搜索安装,工作目录和空间的区别与设置

R语言以其强大的功能和灵活的扩展性,成为了无数数据分析师和研究者的首选工具。R的丰富功能和海量扩展包直接相关,但如何高效管理这些扩展包,进而充分发挥R的强大潜力?本文将为您揭示这些问题的答案。 一、R的扩展包 R的包(packages)是由R函数、数据和预编译代码组成的一…...

解决STM32开启定时器时立即进入一次中断程序问题

转自 解决STM32开启定时器时立即进入一次中断程序问题_stm32f407定时器初始化自动进入一次-CSDN博客 配置STM32定时器时&#xff0c;定时器中断使能、定时器使能、清除更新中断标志位&#xff0c;三者不同顺序程序执行时有不同效果&#xff0c;具体如下&#xff1a; TIM_Clea…...

Unity UGUI 之EventSystem

本文仅作学习笔记与交流&#xff0c;不作任何商业用途 本文包括但不限于unity官方手册&#xff0c;唐老狮&#xff0c;麦扣教程知识&#xff0c;引用会标记&#xff0c;如有不足还请斧正 1.EventSystem是什么&#xff1f; 有需要请查看手册&#xff1a;Unity - 手册&#xff1…...

USB转多路UART - USB 基础

一、 前言 断断续续做了不少USB相关开发&#xff0c;但是没有系统去了解过&#xff0c;遇到问题就很被动了。做这个USB转UART的项目就是&#xff0c;于是专门花了一天的时间学习USB及CDC相关&#xff0c;到写这文章时估计也忘得差不多了&#xff0c;趁项目收尾阶段记录一下&am…...

接近50个实用编程相关学习资源网站

Date: 2024.07.17 09:45:10 author: lijianzhan 编程语言以及编程相关工具等实用性官方文档网站 C语言文档&#xff1a;https://learn.microsoft.com/zh-cn/cpp/c-languageMicrosoft C、C和汇编程序文档&#xff1a;https://learn.microsoft.com/zh-cn/cppJAVA官方文档&#…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...