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

数据结构——B-树、B+树、B*树

一、B-树

1. 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)。Ai(0<=i<=n)为指向子树根节点的指针,且Ai所指子树所有节点中的关键字均小于Ki+1。n为节点中关键字的个数,满足ceil(m/2)-1 <=n <= m-1。

2. B树的插入

        采用m为3的一棵三叉B树的插入过程进行演示。根据B树性质可知,m为3,则每个节点最多有三个孩子(m-1个),每个节点包含k-1个关键字,2<=k<=3。注意:插入只能插入到叶子节点

(1)首先插入两个值20,30

(2)插入第三个值25,由于每个节点最多有2个关键字,所以此时会进行分裂来维持B树平衡。

2.1 B树分裂规则

        创建一个兄弟节点,拷贝当前节点内右半区间的数据到兄弟节点中,保留当前节点中左半区间的数据,将该节点内的中位数提到父节点中(若没有父节点,则创建新的父节点)。

(3)插入35

(4) 插入40

        此时根节点的右侧孩子内数据超过2个,则按照B树分裂规则分裂后如下:

 (5)插入33

(6)插入34

        此时根节点的中间孩子内数据超过2两个,进行分裂,当提取33到父节点后,根节点内数据也超过了2个,则根节点也会进行分裂,此时没有父节点,则会创建新的父节点,结构如下:

三、B+树

1. B+树概念

        B+树是B树的变形,它是在B树基础上进行优化的多路平衡搜索树,B+树的规则和B树基本类似,但在其基础上进行了以下优化:

        (1)分支节点的子树指针与关键字个数相同;

        (2)分支节点的子树指针p[i]指向关键字值大小在[k[i], k[i+1]]之间;

        (3)所有叶子节点增加一个链接指针链接在一起;

        (4)所有关键字及其映射数据都在叶子节点出现。

优点:

(1)简化了B树孩子币关键字多一个的规则,由多一个变成相等。

(2)所有值都在叶子节点中,且叶子节点通过指针链接起来,方便遍历。

2. B+树的插入

        B+树的插入过程与B树基本类似,区别在于:

        (1)第一次插入两层节点,一层做分支,一层做根;

        (2)B+树在分裂时,是将左半部分的数据保留,右半部分的数据放入新建兄弟节点中,并将新建节点中的最小值更新到父节点中。

三、B*树

1. B*树概念

        B*树又是B+树的变形,做了以下改动:

        (1)在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

        (2)节点在分裂时,保证每个节点中值的数量至少为2/3 * M,最多为M个,也就是从1/2提高到了2/3,提高空间利用率。

 2. B*树的插入

        B*树的插入与B+树基本类似,区别主要在于分裂规则,B*树的分裂规则:

        如果它的下一个兄弟节点未满,则将一部分数据移到兄弟节点中,再在原节点中插入关键字,最后修改父节点中兄弟节点的关键字(因为兄弟节点的关键字范围发生了变化);

        如果兄弟节点也满了,则在原节点与兄弟节点之间添加新节点,并各复制1/3的数据到新节点中,最后在父节点中添加新节点的指针。

四、B树系列的优缺点

1. 优点

        (1)高效的查找操作:B树系列的数据结构通过将数据分布在多层节点上,使用索引快速导航到目标元素所在的叶子节点,从而实现了高效的查找操作。其时间复杂度通常为O(log_{M}^{N})

        (2)适应大规模数据集:B树系列的数据结构能够充分利用磁盘块的大小,减少磁盘I/O操作的次数,提高存储和访问效率。它们被广泛应用于数据库索引、文件系统等需要处理大规模数据集的场景。

        (3)自平衡特性:B树系列的数据结构通过节点的分裂和合并来自动保持树的平衡,保证了各个节点的高度相对较小,从而维持了高效的操作性能。

        (4)支持范围查询:由于B树系列的数据结构中数据是按照键的大小顺序进行排序,因此可以很方便地进行范围查询操作。

2. 缺点

        (1)空间利用率低,消耗高。

        (2)插入删除数据、分裂合并节点,都必然存在数据挪动。

        (3)虽然B树系列的高度更低,但是在内存中和哈希、平衡搜索树的查找效率处于同一量级。

相关文章:

数据结构——B-树、B+树、B*树

一、B-树 1. B-树概念 B树是一种适合外查找的、平衡的多叉树。一棵m阶&#xff08;m>2&#xff09;的B树&#xff0c;是一棵平衡的M路平衡搜索树&#xff0c;它可以是空树或满足以下性质&#xff1a; &#xff08;1&#xff09;根节点至少有两个孩子。 &#xff08;2&#…...

2023国赛数学建模思路 - 案例:FPTree-频繁模式树算法

文章目录 算法介绍FP树表示法构建FP树实现代码 建模资料 ## 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法&#xff0c;就是频繁模式树算法&#xff0c…...

GPT系列总结

1.GPT1 无监督预训练有监督的子任务finetuning https://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf 1.1 Unsupervised pre-training &#xff08;1&#xff09;基于一个transformer decoder&#xff0c;通过一个窗口的输入得…...

【福建事业单位-综合基础知识】05民法典

这里写自定义目录标题 一、民法概述概念原则总结 二、自然人概念总结 三、民事法律行为总结 民法考察2-4题&#xff08;重点总则篇&#xff09; 一、民法概述 概念原则 总结 二、自然人 概念 总结 三、民事法律行为 总结...

微服务篇

微服务篇 springcloud 常见组件有哪些 面试官&#xff1a; Spring Cloud 5大组件有哪些&#xff1f; 候选人&#xff1a; 早期我们一般认为的Spring Cloud五大组件是 Eureka&#xff1a;注册中心Ribbon&#xff1a;负载均衡Feign&#xff1a;远程调用Hystrix&#xff1a;…...

C++ 的关键字(保留字)完整介绍

1. asm asm (指令字符串)&#xff1a;允许在 C 程序中嵌入汇编代码。 2. auto auto&#xff08;自动&#xff0c;automatic&#xff09;是存储类型标识符&#xff0c;表明变量"自动"具有本地范围&#xff0c;块范围的变量声明&#xff08;如for循环体内的变量声明…...

C#小轮子:MiniExcel,快速操作Excel

文章目录 前言环境安装功能测试普通读写读新建Excel表格完全一致测试&#xff1a;成功大小写测试&#xff1a;严格大小写别名读测试&#xff1a;成功 写普通写别名写内容追加更新模板写 其它功能xlsx和CSV互转 前言 Excel的操作是我们最常用的操作&#xff0c;Excel相当于一个…...

Ribbon负载均衡

Ribbon与Eureka的关系 Eureka的服务拉取与负载均衡都是由Ribbon来实现的。 当服务发送http://userservice/user/xxxhtt://userservice/user/xxx请求时&#xff0c;是无法到达userservice服务的&#xff0c;会通过Ribbon会把这个请求拦截下来&#xff0c;通过Eureka-server转换…...

LeetCode--HOT100题(33)

目录 题目描述&#xff1a;148. 排序链表&#xff08;中等&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;148. 排序链表&#xff08;中等&#xff09; 给你链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 LeetCode做题链接&#xff1…...

【docker练习】

1.安装docker服务&#xff0c;配置镜像加速器 看这篇文章https://blog.csdn.net/HealerCCX/article/details/132342679?spm1001.2014.3001.5501 2.下载系统镜像&#xff08;Ubuntu、 centos&#xff09; [rootnode1 ~]# docker pull centos [rootnode1 ~]# docker pull ubu…...

韦东山-电子量产工具项目:业务系统

代码结构 所有代码都已通过测试跑通&#xff0c;其中代码结构如下&#xff1a; 一、include文件夹 1.1 common.h #ifndef _COMMON_H #define _COMMON_Htypedef struct Region {int iLeftUpX; //区域左上方的坐标int iLeftUpY; //区域左下方的坐标int iWidth; //区域宽…...

React(6)

1.React插槽 import React, { Component } from react import Child from ./compoent/Childexport default class App extends Component {render() {return (<div><Child><div>App下的div</div></Child></div>)} }import React, { Compon…...

RabbitMq-2安装与配置

Rabbitmq的安装 1.上传资源 注意&#xff1a;rabbitmq的版本必须与erlang编译器的版本适配 2.安装依赖环境 //打开虚拟机 yum install build-essential openssl openssl-devel unixODBC unixODBC-devel make gcc gcc-c kernel-devel m4 ncurses-devel tk tc xz3.安装erlan…...

论文笔记:Continuous Trajectory Generation Based on Two-Stage GAN

2023 AAAI 1 intro 1.1 背景 建模人类个体移动模式并生成接近真实的轨迹在许多应用中至关重要 1&#xff09;生成轨迹方法能够为城市规划、流行病传播分析和交通管控等城市假设分析场景提供仿仿真数据支撑2&#xff09;生成轨迹方法也是目前促进轨迹数据开源共享与解决轨迹数…...

redis实战-缓存数据解决缓存与数据库数据一致性

缓存的定义 缓存(Cache),就是数据交换的缓冲区,俗称的缓存就是缓冲区内的数据,一般从数据库中获取,存储于本地代码。防止过高的数据访问猛冲系统,导致其操作线程无法及时处理信息而瘫痪&#xff0c;这在实际开发中对企业讲,对产品口碑,用户评价都是致命的;所以企业非常重视缓存…...

【排序】选择排序

文章目录 选择排序时间复杂度空间复杂度稳定性 代码 选择排序 以从小到大为例进行说明。 选择排序就是定义出一个最小值下标&#xff0c;然后遍历整个剩下的数组选择出最小的放进最小值下标的位置。 时间复杂度 O(N) 遍历一次即可 空间复杂度 O(1) 稳定性 不稳定 代码 p…...

深入浅出Pytorch函数——torch.nn.init.trunc_normal_

分类目录&#xff1a;《深入浅出Pytorch函数》总目录 相关文章&#xff1a; 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...

探索高级UI、源码解析与性能优化,了解开源框架及Flutter,助力Java和Kotlin筑基,揭秘NDK的魅力!

课程链接&#xff1a; 链接: https://pan.baidu.com/s/13cR0Ip6lzgFoz0rcmgYGZA?pwdy7hp 提取码: y7hp 复制这段内容后打开百度网盘手机App&#xff0c;操作更方便哦 --来自百度网盘超级会员v4的分享 课程介绍&#xff1a; &#x1f4da;【01】Java筑基&#xff1a;全方位指…...

国外服务器怎么有效降低延迟

国外服务器怎么有效降低延迟?在全球化网络环境下&#xff0c;越来越多的企业和个人选择使用国外服务器来托管网站、应用程序或数据。然而&#xff0c;由于地理位置、网络连接等因素&#xff0c;使用国外服务器时可能会遇到延迟较高的问题。高延迟不仅影响用户体验&#xff0c;…...

AI百度文心一言大语言模型接入使用(中国版ChatGPT)

百度文心一言接入使用&#xff08;中国版ChatGPT&#xff09; 一、百度文心一言API二、使用步骤1、接口2、请求参数3、请求参数示例4、接口 返回示例 三、 如何获取appKey和uid1、申请appKey:2、获取appKey和uid 四、重要说明 一、百度文心一言API 基于百度文心一言语言大模型…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...