当前位置: 首页 > 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官方文档&#…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...