[Collection与数据结构] B树与B+树

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (93平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀线程与网络(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
🍃 Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
🎃Redis(97平均质量分)https://blog.csdn.net/2301_80050796/category_12777129.html?spm=1001.2014.3001.5482
🐰RabbitMQ(97平均质量分) https://blog.csdn.net/2301_80050796/category_12792900.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~
在这里插入图片描述

目录

  • 1. 常见的基本搜索结构
  • 2. B树的概念
  • 3. B树的插入分析
  • 4. B树的插入实现
    • 4.1 B树的结点设计
    • 4.2 插入key的过程
    • 4.4 B树的性能分析
    • 4.5 B树的删除
  • 5. B+树和B*树
    • 5.1 B+树
    • 5.2 B*树

1. 常见的基本搜索结构

在这里插入图片描述
以上的结构适合用于数量不是很大的情况,如果数量非常巨大,一次性无法加载到内存中,使用上述结构就不是很方便,比如: 使用平衡树搜索一个大文件.
在这里插入图片描述
上面方法其实只在内存中保存了每一项数据信息中需要查询的字段以及数据在磁盘中的位置,整体的数据实际也在磁盘中.
缺陷:

  1. 树的高度比较高,查找的时候最差情况之下要比较树的高度次.
  2. 数据量如果特别大的时候,树的结点可能无法一次性加载到内存中,需要多次硬盘IO,这时候就会拖慢查找的速度.
    那如何提高对数据访问的速度呢?
  3. 提高IO的速度
  4. 降低树的高度,即使用多叉平衡树.

2. B树的概念

B树是一种平衡的多叉树,称为B树(有些地方可能写的是B-树,注意不要读作"B减数").一棵M阶(M>2)的B树,是一棵平衡的M路搜索平衡搜索树,可以是空树或者满足一下的性质:

  1. 根结点至少有两个孩子
  2. 每个非根结点至少有M/2-1(向上取整)个关键字,至多有M-1个关键字,并且以升序的方式排列.
  3. 每个非根节点至少有M/2(向上取整)个孩子,至多有M个孩子.
  4. 孩子结点永远比关键字多一个.
    在这里插入图片描述
  5. key[i]和key[i+1]之间的孩子结点的值介于key[i],key[i+1]之间.
  6. 所有的叶子结点都在同一层.

非根节点中至少有M/2-1(向上取整)个关键字和M/2(向上取整)个孩子是因为在每次节点满了之后都会拷走一半,这和节点的分裂有关,我们后续介绍.

3. B树的插入分析

为了简单起见,假设M=3,即是一棵三叉树,每个节点中保存两个数据,两个数据可以将区间分为三个部分,因此结点应该有三个孩子,为了后续实现简单起见,结点的结构如下.上一层存储的书该结点的数据,下一层存储的是孩子结点的地址.
在这里插入图片描述
我们之前规定的是3叉树,这里之所以要把4叉树当做3叉树来看待是因为数据满了之后,需要先进行插入再进行分裂,如果数据只有两个存储空间的话,新数据无法插入结点,也就无法正常进行分裂.下面我们来解释一下结点的分裂:

在我们插入的过程当中,有可能结点是需要分裂的.
前提是:
当前这棵树是一个M叉树,当一个关键字插入之后,关键字数目>M-1就要对结点进行拆分.拆分的规则是,把中间的元素提出来,放到父节点上(如果分裂的是根结点,则父节点不存在,需要新建一个结点),中间元素左边的的元素单独构成一个结点(保留在原来的结点中),中间元素右边的元素单独构成一个结点(这个结点一半不存在,需要新建).
比如我们使用53,139,75,49,145,36,101构建B树的过程如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这里我们发现,B树的分裂是横向的分裂,新老结点在同一层,也就是不会使得树的高度增加,正是因为结点的横向分裂,所以B树才是天然平衡的.只有在分裂根节点的时候,高度才会增加.
在这里插入图片描述
在这里插入图片描述
注意在对根节点分裂的时候,139的两个孩子结点也要跟着139这个结点一起复制过来.
在这里插入图片描述
插入过程总结:

  1. 如果树为空,直接插入新结点中,该结点为树的根节点.
  2. 树非空,找待插入元素在树中的位置(注意:找到插入结点的位置一定在叶子结点上)
  3. 树中的key唯一,即该元素已经存在的时候则不插入.
  4. 按照插入顺序的思想将该元素插入到找到的结点中
  5. 检测该结点是否满足B树的性质: 即该结点中的元素个数是否<=M-1.
  6. 如果插入结点后结点不满足B树的性质,需要对该结点进行分裂:
    • 申请新的结点
    • 找到该结点的中间位置
    • 将该结点的中间位置右侧的元素以及其孩子搬移到新结点中.
    • 将中间位置元素以往该结点的双亲节点中插入.之后调整树的连接方式,把分裂出去的数据的孩子一起调整走.
  7. 如果向上分裂已经到了根结点的位置,插入结束.
  8. 如果更节点在插入之后也是满的,则要继续重复上述步骤分裂根节点.

4. B树的插入实现

4.1 B树的结点设计

结点需要包含这几部分:

  • 一个是存储数据的数据域
  • 一个是存储孩子结点的地址域
  • 为了方便分裂中中间元素向上插入,我们还要记录当前结点的双亲节点.
  • 记录有效数据的size.
  • 最后在给构造方法的时候注意要多给一个数据域和指针域.
public class BTreeNode {public int[] keys;//存储数据public BTreeNode[] subs;//存储孩子结点public BTreeNode parents;//存储双亲public int size;//有效数据个数public BTreeNode(int M){//M叉树this.keys = new int[M];//多给一个位置this.subs = new BTreeNode[M+1];this.size = 0;}
}

4.2 插入key的过程

  • 首先判断该树是否是一棵空树,如果是空树,则需要新建一棵树,并让根节点数据域的第一个元素为key;
  • 之后寻找该树中是否存在该数据,如果存在,直接返回,如果不存在,则继续下一步的插入逻辑
  • 在最终找到的叶子结点中进行数据的插入
  • 看看叶子结点是否为满
  • 如果满了,需要进行下一步的分裂操作.

我们在判断结点中是否存在指定的值的时候,如果直接返回一个结点,我们无法判断直接判断这个节点返回的是未找到数据最终到达的叶子结点还是找到数据的结点,所以我们必须通过一个Integer来标记这个数据是否真的存在.我们定义一种数据类型叫做Pair,前面存放结点,后面存放整形以判断这个值是否存在.

//键值对
public class Pair <K,V>{public K key;public V val;public Pair(K key, V val) {this.key = key;this.val = val;}
}

插入逻辑

public class Insert {public BTreeNode root;//定义根节点public final int M = 3;//定义的是一个三叉树public boolean insert(int key){//查看root是否为空if (root == null){root = new BTreeNode(M);root.keys[0] = key;root.size = 1;return true;}//接下来寻找元素在树中是否存在Pair<BTreeNode,Integer> pair = find(key);//如果返回的不是-1,证明是存在的if (pair.val != -1){return false;}BTreeNode cur = pair.key;//拿到当前结点之后进行数据插入int index = cur.size-1;for (;index > 0;index--){if (cur.keys[index] > key){cur.keys[index+1] = cur.keys[index];} else if (cur.keys[index] < key) {break;}}cur.keys[index+1] = key;cur.size++;//之后查看是否需要分裂节点if (cur.size < M){return true;//不需要分裂,直接返回}else {split(cur);//不满足B树性质,需要分裂return true;}}/*** 寻找key在树中是否存在* @param key 需要寻找的key* @return 返回键值对*/private Pair<BTreeNode,Integer> find(int key){BTreeNode cur = root;BTreeNode parent = null;while (cur != null){//在整棵树中遍历int i = 0;while (i != cur.size){//在当前结点中遍历if (cur.keys[i] == key){return new Pair<>(cur,cur.keys[i]);}else if (cur.keys[i] < key){i++;}else {break;}}parent = cur;//如果最后没有找到,parent记录的是叶子结点cur = cur.subs[i];//如果最后没有找到,这个结点记录的是null}//走到了最后证明没有找到return new Pair<>(parent,-1);}/*** 分裂当前结点* @param cur 需要分裂的结点*/private void split(BTreeNode cur){BTreeNode newNode = new BTreeNode(M);//保存中间数据右边数据的结点BTreeNode parent = cur.parents;//记录该结点的父节点,把中间的数据提到父节点上去int mid = cur.size/2;int j = 0;int i = mid+1;for (;i < cur.size;i++){newNode.keys[j] = cur.keys[i];//数据复制走newNode.subs[j] = cur.subs[i];//孩子一起复制走//如果孩子不为空,就把孩子的父亲改成newNodeif (newNode.subs[j] != null){newNode.subs[j].parents = newNode;}j++;}//孩子还需要再复制一次newNode.keys[j] = cur.keys[i];//数据复制走newNode.subs[j] = cur.subs[i];//孩子一起复制走//如果孩子不为空,就把孩子的父亲改成newNodeif (newNode.subs[j] != null){newNode.subs[j].parents = newNode;}//更改newNode的size和原结点的sizenewNode.size = j;cur.size = cur.size-j-1;//包括复制走的数据和提到父节点上的数据if (cur.parents == null){//如果该结点是根结点root = new BTreeNode(M);root.keys[0] = cur.keys[mid];root.subs[0] = cur;cur.parents = root;root.subs[1] = newNode;newNode.parents = root;root.size = 1;return;}//如果该结点不是根结点newNode.parents = parent;int end = parent.size-1;int midVal = cur.keys[mid];//进行数据的插入for (;end > 0;end--){if (parent.keys[end] > midVal){parent.keys[end+1] = parent.keys[end];parent.subs[end+2] = parent.subs[end+1];//把数据和孩子都复制过去}else if (parent.keys[end] < midVal){break;}}parent.keys[end+1] = midVal;//把中间值移动过来parent.subs[end+2] = newNode;//把新节点连接到root上parent.size++;if (parent.size >= M){//如果根结点满了,继续分裂split(parent);}}
}

4.4 B树的性能分析

对于一棵结点为N度为M的B树,查找和插入需要logM-1N到logM/2N次比较,证明如下:对于度为M的B树,每个节点的子节点个数为M/2到(M-1)之间,因此树的高度应该要在logM-1N和logM/2N之间,在定位到该节点之后,每个节点中的数据个数一般非常有限,再采用二分查找的方式可以很快定位到该元素,时间复杂度可以近似看做O(1).
B-树的效率是很高的,对于N = 62*1000000000个节点,如果度M为1024,则
logM/2N<= 4,即在620亿个元素中,如果这棵树的度为1024,则需要小于4次即可定位到该节点,然后利用二分查找可以快速定位到该元素,大大减少了读取磁盘的次数.

4.5 B树的删除

参考<<算法导论>>或者<<数据结构-严蔚敏版>>.

5. B+树和B*树

5.1 B+树

B+树为B树的升级版,也是一种多路搜索树,它通常被用于数据库中建立索引以加快查找的速度.我们在MySQL的索引章节也有所介绍.
B+树的性质如下:

  1. 非叶子结点的子树指针域的个数和关键字的个数相同.
  2. 非叶子结点的子树指针p[i],指向关键字属于[k[i],k[i+1])的子树.也就是它的孩子中一定存在一个元素k[i].
  3. 为所有叶子结点增加一个链指针.把所有的叶子结点都串联起来,都指向自己的下一个兄弟节点,是一个链表,且链表中的节点数据都是有序的.
  4. 所有的真正的数据都在叶子结点出现.非叶子结点的关键字不是实际的数据记录,而是一种索引信息,用来引导搜索路径.
  5. 查找的次数相对于B树来说更加稳定,因为不管数据是多少,每次都要遍历到叶子结点.

在这里插入图片描述
B+树的搜索方式与B树基本相同,区别是B+树只有到达叶子结点才会命中数据,而B树有可能在非叶子结点就可以命中.
下面是B+树的分裂方式:
首先是叶子结点分裂:

  • 当一个结点满的时候,分配一个新的结点,并将原结点中1/2的数据(较大的那1/2)复制到新的结点
  • 原结点的下一个兄弟节点的指针指向新的结点.
  • 更新父节点的指针信息,使得父节点正确指向分裂之后的两个结点.

其次是非叶子结点的分裂:

  • 当为叶子结点插入数据的操作导致某个非叶子结点满,就需要对非叶子结点进行分裂.
  • 对于非叶子结点,同样选择中间的位置进行分裂,它左边的键值和指针留在原节点,右边的键值和指针移动到新节点.
  • 更新父节点的指针信息,使得父节点正确指向分裂之后的两个结点.
  • 如果父节点满,则继续上述的步骤,直到不再产生分裂或者是到根节点
  • 如果根节点发生了分裂,则创建一个新的根节点,将原根节点分裂后的两个节点作为新根节点的子节点,将分裂点键值放入新根节点.

5.2 B*树

B*树是B+树的变形,在B+树的非根和非叶子结点在增加了指向兄弟节点的指针.
在这里插入图片描述
分裂方式如下:
当一个结点满的时候,如果他的下一个兄弟节点未满,那么将一部分数据移动到他的兄弟节点中,再在原结点中插入关键字,最后修改父节点中兄弟节点的关键字(兄弟节点的数据发生了改变).如果兄弟节点也满了,则需要进行分裂,这里和B+树类似,不再赘述,唯一不同的是在非叶子结点分裂的时候,也需要修改兄弟节点指针的指向.

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/10629.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

ROS应用之SwarmSim在ROS 中的协同路径规划

ROS应用之SwarmSim在ROS 中的协同路径规划

SwarmSim 在 ROS 中的协同路径规划 前言 在多机器人系统&#xff08;Multi-Robot Systems, MRS&#xff09;中&#xff0c;SwarmSim 是一个常用的模拟工具&#xff0c;可以对多机器人进行仿真以实现复杂任务的协同。除了任务分配逻辑以外&#xff0c;SwarmSim 在协同路径规划方…
阅读更多...
新鲜速递：DeepSeek-R1开源大模型本地部署实战—Ollama + MaxKB 搭建RAG检索增强生成应用

新鲜速递：DeepSeek-R1开源大模型本地部署实战—Ollama + MaxKB 搭建RAG检索增强生成应用

在AI技术快速发展的今天&#xff0c;开源大模型的本地化部署正在成为开发者们的热门实践方向。最火的莫过于吊打OpenAI过亿成本的纯国产DeepSeek开源大模型&#xff0c;就在刚刚&#xff0c;凭一己之力让英伟达大跌18%&#xff0c;纳斯达克大跌3.7%&#xff0c;足足是给中国AI产…
阅读更多...
【Rust自学】15.5. Rc＜T＞：引用计数智能指针与共享所有权

【Rust自学】15.5. Rc＜T＞：引用计数智能指针与共享所有权

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 15.5.1. 什么是Rc<T> 所有权在大部分情况下都是清晰的。对于一个给定的值&#xff0c;程序员可以准确地推断出哪个变量拥有它。 …
阅读更多...
UE5制作视差图

UE5制作视差图

双目深度估计开源数据集很多都是用UE制作的&#xff0c;那么我们自己能否通过UE制作自己想要的场景的数据集呢。最近花了点时间研究了一下&#xff0c;分享给需要的小伙伴。 主要使用的是UnrealCV插件&#xff0c;UnrealCV是一个开源项目&#xff0c;旨在帮助计算机视觉研究人…
阅读更多...
基于遗传优化GRNN和Hog特征提取的交通标志识别算法matlab仿真

基于遗传优化GRNN和Hog特征提取的交通标志识别算法matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 4.1 HOG 4.2 GRNN&#xff08;General Regression Neural Network&#xff09;模型原理 4.3 遗传算法&#xff08;GA&#xff09;优化GRNN平滑因子 5.算法完整程序工程 1.算法运行效果图预…
阅读更多...
C语言【基础篇】之流程控制——掌握三大结构的奥秘

C语言【基础篇】之流程控制——掌握三大结构的奥秘

流程控制 &#x1f680;前言&#x1f99c;顺序结构&#x1f4af; 定义&#x1f4af;执行规则 &#x1f31f;选择结构&#x1f4af;if语句&#x1f4af;switch语句&#x1f4af;case穿透规则 &#x1f914;循环结构&#x1f4af;for循环&#x1f4af;while循环&#x1f4af;do -…
阅读更多...
C++实现状态模式

C++实现状态模式

首先上代码&#xff1a; #include <iostream> #include <memory>class Context;class State { public:virtual void Handle(Context * context) 0; //纯虚函数virtual ~State() default; //虚析构函数 };//创建状态A class ConcreateStateA : public State{…
阅读更多...
【React】PureComponent 和 Component 的区别

【React】PureComponent 和 Component 的区别

前言 在 React 中&#xff0c;PureComponent 和 Component 都是用于创建组件的基类&#xff0c;但它们有一个主要的区别&#xff1a;PureComponent 会给类组件默认加一个shouldComponentUpdate周期函数。在此周期函数中&#xff0c;它对props 和 state (新老的属性/状态)会做一…
阅读更多...
二级C语言：二维数组每行最大值与首元素交换、删除结构体的重复项、取出单词首字母

二级C语言：二维数组每行最大值与首元素交换、删除结构体的重复项、取出单词首字母

目录 一、程序填空 --- 二维数组每行最大值与首元素交换 题目 分析 知识点 --- 交换语句 二、程序修改 --- 删除结构体的重复项 题目 分析 三、程序设计 --- 取出单词首字母 题目 分析 前言 本章讲解&#xff1a;二维数组每行最大值与首元素交换、删除结构体的重复项…
阅读更多...
CUDA学习-内存访问

CUDA学习-内存访问

一 访存合并 1.1 说明 本部分内容主要参考： 搞懂 CUDA Shared Memory 上的 bank conflicts 和向量化指令（LDS.128 / float4）的访存特点 - 知乎 1.2 share memory结构 图1.1 share memory结构 放在 shared memory 中的数据是以 4 bytes（即 32 bits）作为 1 个 word，依…
阅读更多...
【python】python基于机器学习与数据分析的手机特性关联与分类预测（源码+数据集）【独一无二】

【python】python基于机器学习与数据分析的手机特性关联与分类预测（源码+数据集）【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;专__注&#x1f448;&#xff1a;专注主流机器人、人工智能等相关领域的开发、测试技术。 python基于机器学习与数据分析的手机特性关联与分类…
阅读更多...
【leetcode详解】T3175(一点反思)

【leetcode详解】T3175(一点反思)

解题心得 要写出一个好的程序&#xff0c;有效解决问题&#xff0c;思路上就不能“太乖” —— 不能被题目的叙述过程所束缚&#xff0c;而是力求细思问题&#xff0c;抽象化问题&#xff0c;并找到背后的逻辑&#xff1b;最后抓住核心对象&#xff0c;去除多余项&#xff0c;…
阅读更多...
图论——最小生成树

图论——最小生成树

最小生成树 给定一个无向图&#xff0c;在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中&#xff0c;叫做求最小生成树。 prim算法 prim 算法采用的是一种贪心的策略。 每次将离连通部分的最近的点和点对应的边加入的连通部分&#xff0c;连通部分逐渐扩大…
阅读更多...
jvisualvm工具使用

jvisualvm工具使用

jvisualvm 是JDK自带的具有图形界面操作功能的JVM性能监控和诊断工具&#xff0c;它不仅能分析和诊断堆转储文件&#xff0c;在线实时监控本地JVM进程&#xff0c;还能监控远程服务器上的JVM进程。 1 分析服务器下载dump文件 1&#xff09;在我们在安装JDK的bin目录双击jvisa…
阅读更多...
C++ list

C++ list

list需知&#xff1a; list不会出现insert迭代器失效问题 链表插入不会影响原有数据相对位置&#xff0c;且不用扩容 但是erase会导致相对数据位置移动&#xff0c;所有其erase会导致迭代器失效 list排序效率很低 不建议使用 小规模数据量可以使用&#xff0c;比较方便 此外…
阅读更多...
DeepSeek-R1 论文解读 —— 强化学习大语言模型新时代来临？

DeepSeek-R1 论文解读 —— 强化学习大语言模型新时代来临？

近年来&#xff0c;人工智能&#xff08;AI&#xff09;领域发展迅猛&#xff0c;大语言模型&#xff08;LLMs&#xff09;为通用人工智能&#xff08;AGI&#xff09;的发展开辟了道路。OpenAI 的 o1 模型表现非凡&#xff0c;它引入的创新性推理时缩放技术显著提升了推理能力…
阅读更多...
【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户注册

【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户注册

&#x1f9f8;安清h&#xff1a;个人主页 &#x1f3a5;个人专栏&#xff1a;【计算机网络】【Mybatis篇】 &#x1f6a6;作者简介&#xff1a;一个有趣爱睡觉的intp&#xff0c;期待和更多人分享自己所学知识的真诚大学生。 目录 &#x1f3af;项目基本介绍 &#x1f6a6;项…
阅读更多...
蓝桥杯思维训练营(一）

蓝桥杯思维训练营(一）

文章目录 题目总览题目详解翻之一起做很甜的梦 蓝桥杯的前几题用到的算法较少&#xff0c;大部分考察的都是思维能力&#xff0c;方法比较巧妙&#xff0c;所以我们要积累对应的题目&#xff0c;多训练 题目总览 翻之 一起做很甜的梦 题目详解 翻之 思维分析&#xff1a;一开…
阅读更多...
【AI】DeepSeek 概念/影响/使用/部署

【AI】DeepSeek 概念/影响/使用/部署

在大年三十那天&#xff0c;不知道你是否留意到&#xff0c;“deepseek”这个词出现在了各大热搜榜单上。这引起了我的关注&#xff0c;出于学习的兴趣&#xff0c;我深入研究了一番&#xff0c;才有了这篇文章的诞生。 概念 那么&#xff0c;什么是DeepSeek&#xff1f;首先百…
阅读更多...
minimind - 从零开始训练小型语言模型

minimind - 从零开始训练小型语言模型

大语言模型&#xff08;LLM&#xff09;领域&#xff0c;如 GPT、LLaMA、GLM 等&#xff0c;虽然它们效果惊艳&#xff0c; 但动辄10 Bilion庞大的模型参数个人设备显存远不够训练&#xff0c;甚至推理困难。 几乎所有人都不会只满足于用Lora等方案fine-tuing大模型学会一些新的…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023