JavaDS —— B树

前言

本章节将带领大家进入B树的学习，主要介绍B树的概念和B树的插入代码的实现，删除代码不做讲解，最后简单介绍B+树和B*树。

B树的概念

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(有些地方写的是B-树，注意不要误读成"B减树")。

如果B树是一颗三叉平衡树的话，上面一层是关键字区域，下面一层存放的是孩子结点：
在这里插入图片描述

我们来直观感受一下插入的过程：

B树的插入过程

一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

  1. 根节点至少有两个孩子
  2. 每个非根节点至少有 【M/2(向上取整) - 1】 个关键字,至多有M-1个关键字，并且以升序排列
  3. 每个非根节点至少有【M/2(向上取整)】个孩子,至多有M个孩子
  4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
  5. 所有的叶子节点都在同一层

B树的实现

这里实现B树的插入代码。

结点定义

这里以三叉树为演示例子，定义 M 为 3，在结点初始化的时候，我们分别在keys 和 subs 域都增加一个空间，这样会方便我们后续的结点分裂。

    public static final int M = 3;public Node root;static class Node {public int[] keys;//关键字public Node[] subs;//孩子结点public Node parent;//双亲结点public int usedSize;//使用的空间个数public Node() {//多分配一个空间是为了后面便于我们分裂结点this.keys = new int[M];this.subs = new Node[M+1];}}

插入分析

首先如果根节点为空的话，直接插入即可：

//根节点为空，直接插入if(root == null) {root = new Node();root.keys[0] = key;root.usedSize = 1;return;}

然后这里我们实现的B树是不能插入相同的数据的，所以我们需要先查找是否已经存在过 key 值，先写一个查找代码：

当遇到和key 值是一样的情况下，我们直接返回即可，如果没有遇到，我们需要继续查找下去。

结点的 keys 是连续的数组，我们需要遍历这个数组：
如果发现 key 大于数组元素，需要继续向后遍历，如果发现 key 小于数组元素，我们则需要进入到对应的孩子结点继续寻找 key 。

最后我们要考虑返回值，我们应该返回什么样的数据？
如果至少单纯判断是否存在，也就是返回布尔值，如果存在某个数据就是返回true，这时候是不需要进行插入操作的，但是如果不存在，你返回的是 false ，那我们应该从哪个结点进行插入操作，所以我们需要获得具体的结点，这时候就需要在查找的循环过程中保存上一个 cur 结点，当cur 走到空的时候，cur 的上一个结点就是我们需要插入数据的结点了。

但是如果返回结点，那就意味着最后的返回值不可能为空，那就无法判断是否存在了 key，所以我们需要接收两个返回值，这时候我们可以定义一个泛型类，用来创建对象保存两个数据，一个是结点，一个是下标，当不存在的时候直接返回 -1。

public class Pair<K, V> {private K key;private V val;public Pair(K key, V val) {this.key = key;this.val = val;}public K getKey() {return key;}public void setKey(K key) {this.key = key;}public V getVal() {return val;}public void setVal(V val) {this.val = val;}
}
    //查找public Pair<Node,Integer> find(int key) {Node cur = root;Node prev = null;while(cur != null) {int i = 0;while(i < cur.usedSize) {if(cur.keys[i] == key) {//存在该节点return new Pair<>(cur,i);} else if(cur.keys[i] > key) {//需要进入孩子结点继续查找break;} else {//继续查找i++;}}prev = cur;cur = cur.subs[i];}//找不到，返回双亲结点return new Pair<>(prev,-1);}

如果不存在，我们就需要插入key ，在获取到的 prev 上进行直接插入，最后我们就要考虑是否超过了M，如果超过了M，就需要进行结点的分裂：

这里要注意的是，我们插入过程都是在叶子结点上进行的，所以不需要进行孩子域 subs 的调整。

        //不存在，需要进行插入Node cur = find.getKey();//插入是在叶子结点进行的，不需要调整孩子结点int i = cur.usedSize - 1;for (; i >= 0; i--) {if(cur.keys[i] > key) {cur.keys[i+1] = cur.keys[i];} else {break;}}cur.keys[i+1] = key;cur.usedSize++;//是否需要进行分裂if(cur.usedSize == M) {split(cur);}

分裂分析

我们来看一下非根结点的分裂过程：
在这里插入图片描述
我们需要获取中间的关键字，然后从中间的关键字的下一个开始拷贝到新结点上，然后中间的关键字需要提取到上面去，也就是需要调整 双亲结点将 中间值插入进去，最后调整三个结点即可。

由于你往双亲结点上插入了一个数据，所以可能导致双亲结点超过容量，所以最后还需要查看双亲结点是否需要进行分裂

		Node newNode = new Node();Node parent = cur.parent;//进行keys和孩子结点的拷贝int mid = M / 2;int i = 0;int j = mid + 1;for(; j < cur.usedSize; j++) {newNode.keys[i] = cur.keys[j];newNode.subs[i] = cur.subs[j];//如果拷贝过来的孩子结点不为空，需要修改孩子结点的双亲结点if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//usedSize 随之修改newNode.usedSize++;i++;}//还差一个孩子结点没有拷贝，再次拷贝孩子结点newNode.subs[i] = cur.subs[j];if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//新结点的双亲结点设置为 parentnewNode.parent = parent;//设置 cur 的 usedSize 数值cur.usedSize = mid;//需要提取的中间关键字int midVal = cur.keys[mid];//特殊情况：当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}//处理 parent 结点//将 cur 的中间关键值提到 parent;int end = parent.usedSize - 1;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 {break;}}parent.keys[end+1] = midVal;parent.subs[end+2] = newNode;parent.usedSize++;//是否需要继续分裂if(parent.usedSize == M) {split(parent);}

如果分裂的是根节点的话，就有一点不一样了：我们需要为中间值创建一个新结点作为新的 根节点
在这里插入图片描述
在这里插入图片描述

		//特殊情况：当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}

根节点的插入和非根结点的插入区别就在于中间值的处理，所以在前面拷贝的过程的代码可以保留，最后进行特殊情况的判断处理即可。

    private void split(Node cur) {Node newNode = new Node();Node parent = cur.parent;//进行keys和孩子结点的拷贝int mid = M / 2;int i = 0;int j = mid + 1;for(; j < cur.usedSize; j++) {newNode.keys[i] = cur.keys[j];newNode.subs[i] = cur.subs[j];//如果拷贝过来的孩子结点不为空，需要修改孩子结点的双亲结点if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//usedSize 随之修改newNode.usedSize++;i++;}//还差一个孩子结点没有拷贝，再次拷贝孩子结点newNode.subs[i] = cur.subs[j];if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//新结点的双亲结点设置为 parentnewNode.parent = parent;//设置 cur 的 usedSize 数值cur.usedSize = mid;//需要提取的中间关键字int midVal = cur.keys[mid];//特殊情况：当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}//处理 parent 结点//将 cur 的中间关键值提到 parent;int end = parent.usedSize - 1;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 {break;}}parent.keys[end+1] = midVal;parent.subs[end+2] = newNode;parent.usedSize++;//是否需要继续分裂if(parent.usedSize == M) {split(parent);}}

最终代码

package mybtree;public class Btree {public static final int M = 3;public Node root;static class Node {public int[] keys;//关键字public Node[] subs;//孩子结点public Node parent;//双亲结点public int usedSize;//使用的空间个数public Node() {//多分配一个空间是为了后面便于我们分裂结点this.keys = new int[M];this.subs = new Node[M+1];}}//插入public void insert(int key) {//根节点为空，直接插入if(root == null) {root = new Node();root.keys[0] = key;root.usedSize = 1;return;}//先查找是否存在keyPair<Node,Integer> find = find(key);//如果已经存在，直接返回if(find.getVal() != -1) {return;}//不存在，需要进行插入Node cur = find.getKey();//插入是在叶子结点进行的，不需要调整孩子结点int i = cur.usedSize - 1;for (; i >= 0; i--) {if(cur.keys[i] > key) {cur.keys[i+1] = cur.keys[i];} else {break;}}cur.keys[i+1] = key;cur.usedSize++;//是否需要进行分裂if(cur.usedSize == M) {split(cur);}}private void split(Node cur) {Node newNode = new Node();Node parent = cur.parent;//进行keys和孩子结点的拷贝int mid = M / 2;int i = 0;int j = mid + 1;for(; j < cur.usedSize; j++) {newNode.keys[i] = cur.keys[j];newNode.subs[i] = cur.subs[j];//如果拷贝过来的孩子结点不为空，需要修改孩子结点的双亲结点if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//usedSize 随之修改newNode.usedSize++;i++;}//还差一个孩子结点没有拷贝，再次拷贝孩子结点newNode.subs[i] = cur.subs[j];if(newNode.subs[i] != null) {newNode.subs[i].parent = newNode;}//新结点的双亲结点设置为 parentnewNode.parent = parent;//设置 cur 的 usedSize 数值cur.usedSize = mid;//需要提取的中间关键字int midVal = cur.keys[mid];//特殊情况：当分裂的结点正好是根结点if(cur == root) {root = new Node();root.keys[0] = midVal;root.subs[0] = cur;root.subs[1] = newNode;cur.parent = newNode.parent = root;root.usedSize = 1;return;}//处理 parent 结点//将 cur 的中间关键值提到 parent;int end = parent.usedSize - 1;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 {break;}}parent.keys[end+1] = midVal;parent.subs[end+2] = newNode;parent.usedSize++;//是否需要继续分裂if(parent.usedSize == M) {split(parent);}}//查找public Pair<Node,Integer> find(int key) {Node cur = root;Node prev = null;while(cur != null) {int i = 0;while(i < cur.usedSize) {if(cur.keys[i] == key) {//存在该节点return new Pair<>(cur,i);} else if(cur.keys[i] > key) {//需要进入孩子结点继续查找break;} else {//继续查找i++;}}prev = cur;cur = cur.subs[i];}//找不到，返回双亲结点return new Pair<>(prev,-1);}public void inorder(Node root){if(root == null)return;for(int i = 0; i < root.usedSize; ++i){inorder(root.subs[i]);System.out.println(root.keys[i]);}inorder(root.subs[root.usedSize]);}
}

B+树介绍

B+树是B-树的变形，也是一种多路搜索树：
其定义基本与B-树相同，除了：

  1. 非叶子节点的子树指针与关键字个数相同
  2. 非叶子节点的子树指针p[i]，指向关键字值属于【k[i]，k[i+1]】的子树【这句话的意思是B+树在B树的基础上只存在右子树，也就是说keys 数组第一个区域是不存在左孩子的，然后每一个孩子结点的范围是 k[i] 到 k[i+1] 之间的】
  3. 所有叶子节点通过双向链表进行连接
  4. 所有关键字都在叶子节点出现在这里插入图片描述

B+树的应用：
在MySQL中使用B+树来对数据进行管理，在下一篇MySQL的索引中我会进行详细的讲解。

B* 树介绍

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
在这里插入图片描述
这样做的好处是可以节约存储空间，结点在进行分裂的时候，会优先先看看兄弟结点是否已满，如果没有满，会将数值插入到兄弟结点上。

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

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

相关文章

【制作100个unity游戏之32】unity开发属于自己的一个2d/3d桌面宠物，可以实时计算已经获取的工资

【制作100个unity游戏之32】unity开发属于自己的一个2d/3d桌面宠物，可以实时计算已经获取的工资

最终效果 文章目录 最终效果一、实现Windows消息弹窗二、将窗口扩展到工作区三、穿透能点击到其他区域四、模型交互1、我们可以新增ObjectDrag 代码控制人物拖拖动2、实现模型交互五、最终代码六、其他七、游玩地址七、源码参考完结一、实现Windows消息弹窗 参考：https://lear…
阅读更多...
WEB打点

WEB打点

目录 web打点概述打点流程打点中的问题getshell手法汇总web打点批量检测端口扫描POC扫描指纹识别漏洞扫描 手工检测开源框架漏洞通用框架漏洞基础web漏洞商用系统漏洞 WAF绕过waf分类常见waf拦截界面WAF绕过思路侧面绕&#xff1a;适合云WAF直面WAF web打点概述 打点流程 资产…
阅读更多...
QT模型视图结构2

QT模型视图结构2

文章目录 Qt 模型视图结构——模型类(二)1.基本概念1.1.模型的基本结构1.2.模型索引1.3.行号和列号1.4.父项1.5.项的角色 Qt 模型视图结构——模型类(二) ​ 模型/视图结构是一种将数据存储和界面展示分离的编程方法。模型存储数据&#xff0c;视图组件显示模型中的数据&#…
阅读更多...
【AI赋能医学】基于深度学习和HRV特征的多类别心电图分类

【AI赋能医学】基于深度学习和HRV特征的多类别心电图分类

一、数据集简介 论文中使用了来自三类不同心电图记录的162条数据&#xff0c;这些数据来自三个公开的数据库&#xff1a; MIT-BIH 心律失常数据库 (ARR) 96条记录&#xff0c;主要包含不同类型的心律失常样本。 MIT-BIH 正常窦性心律数据库 (NSR) 36条记录&#xff0c;包含健…
阅读更多...
Gitlab实现多项目触发式自动CICD

Gitlab实现多项目触发式自动CICD

工作中可能会遇到这种场景&#xff0c;存在上游项目A和下游项目B&#xff0c;项目B的功能依赖项目A&#xff08;比如B负责日志解析&#xff0c;A是日志描述语言代码&#xff09;&#xff0c;这种相互依赖的项目更新流程一般如下&#xff1a; A项目更新&#xff0c;通知B项目开发…
阅读更多...
Unity中InputField一些属性的理解

Unity中InputField一些属性的理解

先看代码&#xff1a; using UnityEngine; using UnityEngine.UI;public class TestInput : MonoBehaviour {[SerializeField]InputField inputField;void Start(){Debug.Log(inputField.text);Debug.Log(inputField.text.Length);Debug.Log(inputField.preferredWidth);Debug…
阅读更多...
2024工业机器视觉产业现状

2024工业机器视觉产业现状

早在20世纪80年代美国国家标准局就预计&#xff0c;检测任务的80%乃至90%将由视觉测量系统来完成&#xff0c;该预测至今已基本变成现实。当前&#xff0c;以智能制造为核心的工业4.0时代背景下&#xff0c;新型工业化的战略部署逐步深入&#xff0c;伴随AI大模型技术应用的逐步…
阅读更多...
泰语快速学习方法！速成方法学习！

泰语快速学习方法！速成方法学习！

要快速学习泰语&#xff0c;可以采取多种策略&#xff0c;如掌握基础语法和词汇&#xff0c;专注于发音练习以掌握泰语特有的音调系统&#xff0c;利用语言学习软件进行互动学习&#xff0c;通过观看泰语媒体内容提高听力理解&#xff0c;与母语者进行语言交换来锻炼口语&#…
阅读更多...
I2C/IIC学习笔记

I2C/IIC学习笔记

I2C/IIC 有些同学I2C和IIC分不清&#xff0c;I2C和IIC实际上是指同一种通信协议。I2C是Inter-Integrated Circuit的缩写&#xff0c;而IIC是它的另一种表述方式&#xff0c;代表的是同一个意思&#xff0c;即“集成电路间总线”。I2C是一种由飞利浦公司&#xff08;现恩智浦半…
阅读更多...
python AssertionError: Torch not compiled with CUDA enabled

python AssertionError: Torch not compiled with CUDA enabled

查看&#xff1a;torch import torch# 输出带CPU&#xff0c;表示torch是CPU版本的 print(ftorch的版本是&#xff1a;{torch.__version__}) # print(ftorch是否能使用cuda&#xff1a;{torch.cuda.is_available()}) 修改一下代码&#xff0c;将cuda改成cpu 最后运行正常&…
阅读更多...
织物缺陷检测系统源码分享

织物缺陷检测系统源码分享

织物缺陷检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…
阅读更多...
跨界融合，GIS如何赋能游戏商业——以《黑神话：悟空》为例

跨界融合，GIS如何赋能游戏商业——以《黑神话：悟空》为例

在数字化时代&#xff0c;地理信息系统&#xff08;GIS&#xff09;技术正以其独特的空间分析和可视化能力&#xff0c;为游戏产业带来革命性的变革。《黑神话&#xff1a;悟空》作为中国首款3A级别的动作角色扮演游戏&#xff0c;不仅在游戏设计和技术上取得了突破&#xff0c…
阅读更多...
力扣刷题（6）

力扣刷题（6）

两数之和 II - 输入有序数组 两数之和 II - 输入有序数组-力扣 思路&#xff1a; 因为该数组是非递减顺序排列&#xff0c;因此可以设两个左右下标当左右下标的数相加大于target时&#xff0c;则表示右下标的数字过大&#xff0c;因此将右下标 - -当左右下标的数相加小于targ…
阅读更多...
51单片机-系列-单片机基础知识入门流水灯

51单片机-系列-单片机基础知识入门流水灯

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 单片机基础知识入门 常用的单片机封装 DIP直插 在DIP直插中&#xff0c;我们根据引脚数量的不同分为8P,14P,16P,18P,20P&#xff0c;这些是窄体&#xff0c;除了窄体之外&…
阅读更多...
【数字组合】

【数字组合】

题目 思路 状态表示&#xff1a; f [ i ] [ j ] f[i][j] f[i][j] 对应考虑1到 i 号数字&#xff0c;和为 j 的方法&#xff0c;表示方法数 目标表示&#xff1a; f [ n ] [ m ] f[n][m] f[n][m] 状态转移&#xff1a; f [ i ] [ j ] f [ i − 1 ] [ j ] f [ i − 1 ] [ j …
阅读更多...
2024.9.16 day 1 pytorch安装及环境配置

2024.9.16 day 1 pytorch安装及环境配置

一、配置pytorch环境&#xff0c;安装pytorch 1.查看python版本 python --version 2.在anaconda命令中创建pytorch环境 conda create -n pytorch python3.12(python版本&#xff09; 3.pytorch安装 pytorch首页 PyTorchhttps://pytorch.org/ os为windows推荐package选择…
阅读更多...
FPGA基本结构和简单原理

FPGA基本结构和简单原理

前言&#xff1a; FPGA全程为&#xff08;Field Programmable Gate Array&#xff09;现场可编程逻辑阵列&#xff0c;以基本的逻辑为主可以实现大多数芯片可以实现的功能&#xff0c;比如说&#xff1a;ASIC芯片等&#xff0c;在半导体领域有着重要的作用。 本文…
阅读更多...
基于SpringBoot的校园社团活动管理系统设计与实现

基于SpringBoot的校园社团活动管理系统设计与实现

文未可获取一份本项目的java源码和数据库参考。 一、设计&#xff08;论文&#xff09;研究背景与意义 在当今的社会&#xff0c;可以说是信息技术的发展时代&#xff0c;在社会的方方面面无不涉及到各种信息的处理。[1]信息是人们对客观世界的具体描述&#xff0c;是人们进行…
阅读更多...
【GO语言】Go语言详解与应用场景分析，与Java的对比及优缺点

【GO语言】Go语言详解与应用场景分析，与Java的对比及优缺点

Go is an open source programming language that makes it easy to build simple, reliable, and efficient software. Go是一种开源编程语言&#xff0c;可以轻松构建简单、可靠和高效的软件。 文章目录 一、引言二、Go语言详解1. 简史2. 特点3. 核心库 三、应用场景四、与Ja…
阅读更多...
苍穹外卖Day01

苍穹外卖Day01

文章目录 目录 文章目录 前端环境搭建 后端环境搭建 后端-数据库环境搭建 前后端联调 前端环境搭建 打开文件夹&#xff08;确保nginx在英文目录下&#xff09;双击ngnix.exe启动nginx服务&#xff0c;访问端口号80在地址栏输入localhost打开界面 后端环境搭建 熟悉项目…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发