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

embedded/2025/2/7 4:21:01/

🌸个人主页: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.ppmy.cn/embedded/160203.html

相关文章

（2025，LLM，下一 token 预测，扩散微调，L2D，推理增强，可扩展计算）从大语言模型到扩散微调

（2025，LLM，下一 token 预测，扩散微调，L2D，推理增强，可扩展计算）从大语言模型到扩散微调

Large Language Models to Diffusion Finetuning 目录 1. 概述 2. 研究背景 3. 方法 3.1 用于 LM 微调的高斯扩散 3.2 架构 4. 主要实验结果 5. 结论 1. 概述 本文提出了一种新的微调方法——LM to Diffusion (L2D)&#xff0c;旨在赋予预训练的大语言模型&#xff08;…
阅读更多...
Qt常用控件 多元素控件

Qt常用控件 多元素控件

文章目录 1. QListWidget1.1 常用属性和方法1.2 常用信号1.4 例子1&#xff0c;操作元素 2. QTableWidget2.1 常用属性和方法2.2 常用信号2.3 例子1&#xff0c;创建表格3.1 常用属性和方法3.2 常用信号3.3 例子1&#xff0c;创建树形结构 Qt中提供的多元素控件有: QListWidget…
阅读更多...
ICANN 关闭 WHOIS Port 43

ICANN 关闭 WHOIS Port 43

2025年1月28日&#xff0c;ICANN&#xff08;互联网名称与数字地址分配机构&#xff09;将正式终止WHOIS Port 43服务。这一决定标志着网络安全行业、域名注册机构以及依赖域名数据进行运营或调查的所有人迎来重要变革。那么&#xff0c;这一变化意味着什么&#xff1f;它将如何…
阅读更多...
Linux 常用命令与实战教程

Linux 常用命令与实战教程

Linux 常用命令与实战教程 引言 Linux 是一个强大的开源操作系统&#xff0c;广泛应用于服务器、嵌入式系统、个人计算机等多个领域。其灵活性、稳定性和安全性使其成为开发人员和运维工程师的首选操作系统之一。对于开发者而言&#xff0c;熟练掌握 Linux 命令行不仅能提高工…
阅读更多...
Sqoop支持ORC文件格式

Sqoop支持ORC文件格式

个人博客地址：Sqoop支持ORC文件格式 | 一张假钞的真实世界 ORC介绍 ORC文件格式是Hive 0.11.0版本引入的一种文件格式。ORC的引入是为了解决其他Hive文件格式的局限性。使用ORC文件格式提升Hive读取、写入及处理数据的性能。 与RCFile对比，ORC文件格式有很多优点： 每个Ta…
阅读更多...
Python-基于PyQt5,pdf2docx,pathlib的PDF转Word工具(专业版)

Python-基于PyQt5,pdf2docx,pathlib的PDF转Word工具(专业版)

前言：日常生活中，我们常常会跟WPS Office打交道。作表格，写报告，写PPT......可以说，我们的生活已经离不开WPS Office了。与此同时，我们在这个过程中也会遇到各种各样的技术阻碍，例如部分软件的PDF转Word需要收取额外费用等。那么，可不可以自己开发一个小工具来实现PDF转…
阅读更多...
vue中的v-cloak和v-pre有什么作用

vue中的v-cloak和v-pre有什么作用

v-cloak v-cloak用于防止vue模板在编译完成之前显示未编译的原始Mustache语法&#xff08;如 {{ message }}&#xff09;&#xff0c;用于防止页面闪烁。 使用场景&#xff1a; <div v-cloak>{{ message }} </div> <style>[v-cloak] {display: none;} <…
阅读更多...
ONE NET MQTT+HTTP多端控制

ONE NET MQTT+HTTP多端控制

使用移动的ONENET实现数据上传与远程控制&#xff0c;数据上传使用MQTT协议&#xff08;ESP8266&#xff09;&#xff0c;而数据查看和远程控制使用的HTTP&#xff08;安卓端/QT&#xff09;&#xff0c;效果&#xff1a; ONENET简单MQTT和HTTP使用 ESP8266通过MQTT上传和订阅数…
阅读更多...
最新文章

Copyright @ 2022~2023