【B-树、B+树、B* 树】多叉平衡搜索树,解决“IO次数”与“树高”问题~

news/2024/10/30 19:37:25/

目录

一、为什么会出现B-树?

面试题:

二、什么是B-树?

2.1、B+,B-树,B*树 导航

三、B-树的模拟实现

3.1、插入结点分析

3.1.1、根节点的分裂

3.1.2、继续插入数据,分裂子节点

3.2.3、再次插入数据,导致根节点继续向上分裂

3.2、性能分析

3.3、模拟实现B-树

四、总结

4.1、特性

小结


一、为什么会出现B-树?

        我们平时所知道的二叉搜索树,红黑树,AVL树,在访问一个大文件,或者是数据量比较大的时候,可能无法一次性把数据加载到内存中,而是只在树的结点中保留了指向该数据在磁盘中的位置,也就是说,真实的数据还在磁盘;我们也知道,在内存中访问数据是很快的,而在磁盘中访问数据相对就要慢很多了;

因此存在以下缺陷:

1. 树的高度比较高,查找的最坏情况是树的高度;

2. 数据量很大时,书中结点无法一次性加载到内存中,需要多次IO;(IO速度是很慢的);

解决方案:

1. 提高IO速度;

2. 降低树的高度——多叉平衡树;

面试题:

数据存储到hashmap和存储到文件中,有什么区别?

1. 存储到文件中读取速度慢;

2. hashmap相当于在内存中存储数据,一旦断电数据就丢失了;


二、什么是B-树?

注意:B-树 不是“B减树”,这个"-"只是一个分隔符,没有B-树这种数据结构;

2.1、B+,B-树,B*树 导航

什么是B树之前写过一篇文章,如下:(什么是B-树,B+树,以及特性)

http://t.csdn.cn/bnlJw

        简而言之,B树就是一颗N叉搜索树,每个结点(结点由关键字和孩子节点地址组成)中最多有N - 1,至少有N/2 - 1个关键字,这些关键字按照升序排序划分成了N个区间,孩子结点就在这些区间里,并且所有叶子结点都在同一层。

结点结构如下图:


三、B-树的模拟实现

3.1、插入结点分析

模拟实现B-树,我们通常会给每个节点多给一个空间,如下:

         为什么要多给一个空间呢?假设不多给一个空间,也就是N = 4,是一个四叉树,但是一个节点最多三个关键字,那么当你要放入第四个元素的时候,进行分裂的时候就不好分裂了,因为你要分情况,看把谁提走。如下图:(以下只是一个简略图,实际上右边树的分叉点不一定在最右边)

3.1.1、根节点的分裂

理解了上面的内容后,首先我们来看一下根节点该如何分裂~

例如一个三叉树,那么刚刚说到,需要多给一个结点一个空间,也就是一个结点有三个关键字,当这个三个关键字都被填满了,就需要分裂,如何分裂呢?步骤是以下三点:

1. 找到该结点的中间位置 m;

2. m 的右边数据,存储到一个新的结点中;

3. m 这个数据,存储到一个新的结点,变成了新的根节点,对于根节点而言,原来的一个结点,被分裂成了最终的三个结点;

如下图:

3.1.2、继续插入数据,分裂子节点

这里分裂的逻辑和分裂根节点相似,具体细节会在以下图中中讲到:

可以观察到:

B树的分裂是横向的,横向增长,也就意味着树的高度没有增加。

哪什么时候会增加树的高度呢?

只有分裂根节点的时候,树的高度才会增加。

3.2.3、再次插入数据,导致根节点继续向上分裂

        假设插入数据189,那么就会导致子节点分裂,子节点分裂又会向根节点提供一个数据,接着根节点就满了,就开始了根节点向上分裂,如下图:

3.2、性能分析

        实际的B树不会这么平凡的分裂,一般是1024叉树,那么想象一下,当M = 1024是,插入数据时,这个树的高度会如何变化?

第一层:1023个关键字;

第二层:1024个子结点 * 1023个关键字,大约是100W的级别;

第三层:1024 * 1024 * 1023,大约是10亿的级别;

第四层:1024 * 1024 * 1024 * 1023,大约是万亿级别;

......

多么恐怖的数量,指数爆炸!!!

        那么它的时间复杂度在logM N ~ logM/2 N 之间,也就是说M越大,效率越高,但是M也不是越大越好,因为 会有空间的浪费,有因为结点满了要拷走一半,浪费一个结点一半的空间;

        并且一旦找到结点,可以利用二分查找可以快速定位到该元素,大大减少了读取磁盘的次数!!!

3.3、模拟实现B-树

具体的思路如上,详细代码和注释如下:

public class MyBtree {static class BTRNode {public int[] keys;//关键字public BTRNode[] subs;//孩子public BTRNode parent;//当前孩子节点的父亲结点public int usedSize;//当前结点关键字的数量public BTRNode() {//这里多给一个空间,是为了更好的分裂this.keys =  new int[M];this.subs = new BTRNode[M + 1];}}public static final int M = 3;public BTRNode root;//当前B树的根节点/*** 插入元素* @param key*/public boolean insert(int key) {if(root == null) {root = new BTRNode();root.keys[0] = key;root.usedSize++;return true;}//2. 当树不为空,就看Key是否存在B树中Pair<BTRNode, Integer> pair = find(key);//根据判断这里的val值是否为-1, 确定是否存在keyif(pair.getVal() != -1) {//结点存在return false;}//不存在key,就要进行插入(插入排序)BTRNode parent = pair.getKey();int index = parent.usedSize - 1;for(; index >= 0; index--) {if(parent.keys[index] >= key) {parent.keys[index + 1] = parent.keys[index];} else {break;}}parent.keys[index + 1] = key;parent.usedSize++;//为什么不处理孩子?//因为每次插入都是在叶子结点,所以叶子结点都是nullif(parent.usedSize < M) {//没有满return true;} else {//满了,需要分裂split(parent);return true;}}/*** 分裂逻辑* @param cur 代表当前需要分裂的结点*/private void split(BTRNode cur) {BTRNode newNode = new BTRNode();//1.先存储当前需要分裂结点的父节点BTRNode parent = cur.parent;//2.开始挪动数据int mid = cur.usedSize >> 1;int i = mid + 1;int j = 0;for(; i < cur.usedSize; i++) {//这里既要拷贝数值也需要拷贝孩子的地址newNode.keys[j] = cur.keys[i];newNode.subs[j] = cur.subs[i];//处理刚刚拷贝过来的孩子节点的父亲结点,为新分裂的结点if(newNode.subs[j] != null){newNode.subs[j].parent = newNode;}j++;}//多拷贝一次孩子newNode.subs[j] = cur.subs[i];if(newNode.subs[j] != null){newNode.subs[j].parent = newNode;}//更新当前新节点的有效数据newNode.usedSize = j;//这里-1是因为将来要提到父亲结点的keycur.usedSize = cur.usedSize - j - 1;//处理根节点的情况if(cur == root) {root = new BTRNode();root.keys[0] = cur.keys[mid];root.subs[0] = cur;root.subs[1] = newNode;root.usedSize = 1;cur.parent = root;newNode.parent = root;return;}//让新的结点的父亲指向刚刚分裂结点的父亲newNode.parent = parent;//开始移动父亲结点int endT = parent.usedSize - 1;int midVal = cur.keys[mid];for(; endT >= 0; endT--) {if(parent.keys[endT] >= midVal) {parent.keys[endT + 1] = parent.keys[endT];parent.subs[endT + 2] = parent.subs[endT + 1];} else {break;}}parent.keys[endT + 1] = midVal;//将当前父亲结点的孩子结点新增为newNode;parent.subs[endT + 2] = newNode;parent.usedSize++;if(parent.usedSize >= M) {split(parent);}}/*** 返回一个值是否可行?* 地址-》无法记录你存储在哪* 所以需要返回一对* @param key* @return*/private Pair<BTRNode, Integer> find(int key) {BTRNode cur = root;BTRNode parent = 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) {i++;} else {break;}}parent = cur;cur = cur.subs[i];}return new Pair<>(parent, -1);}//测试public static void main(String[] args) {MyBtree myBtree = new MyBtree();int[] arr = {53, 139, 75, 49, 145, 36, 101};for(int i = 0; i < arr.length; i++) {myBtree.insert(arr[i]);}System.out.println("123121");}
}

四、总结

4.1、特性

1. 根节点至少有两个孩子。

2. 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字,并且以升序排列。

3. 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子。

4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间。

5. 所有的叶子节点都在同一层。


小结

面试不会考这样的,但是建议多敲~

思想要懂!



http://www.ppmy.cn/news/12202.html

相关文章

【docker16】Docker-Compose容器编排

1.是什么 Docker-Compose是Docker官方的开源项目&#xff0c;负责实现对Docker容器集群的快速编排。 Compose是Docker公司推出的一个工具软件&#xff0c;可以管理多个Docker容器组成一个应用&#xff0c;你需要定义一个YAML格式的配置文件docker-compose.yml&#xff0c;写好…

机器学习公式推导与代码实现-无监督学习模型

聚类分析与k均值聚类算法 督学习算法。在给定样本的情况下,聚类分析通过度量特征相似度或者距离,将样本自动划分为若干类别。 距离度量和相似度度量方式 距离度量和相似度度量是聚类分析的核心概念,大多数聚类算法建立在距离度量之上。常用的距离度量方式包括闵氏距离和马…

Map和Set的介绍

目录 1、Map 和 Set 的概念 2、模型 3、Map 的学习 3.1 关于 Map.Entry 3.2 Map 的常用方法 4、Set 的常用方法 5、 Map 和 Set 的注意点 1、Map 和 Set 的概念 Java 提供了 Map 和 Set 的接口&#xff0c;是一种专门用来进行搜索的容器或数据结构&#xff0c;而他搜索…

Anfis-基于模糊推理的自适应神经网络程序(免费分享)

输出结果展示&#xff1a;完整代码&#xff1a;clear;close all;gamma0.75;%设定惯性因子eps10.005;%设定停止训练的条件参数m18;%设定隶属函数个数m28;a-1;b1;w0a(b-a)*rand(1,m1*m2);%初始化权值阵for i1:2switch icase 1,beta0.75;%设定学习率otherwise,beta0.25;endc[2/7*(…

RocketMq文件存储-MappedFile

broker端存储消息数据&#xff0c;如CommitLog&#xff0c;ConsumeQueue&#xff0c;IndexFile等均是通过MappedFile实现&#xff0c;其是对文件操作的封装。MappedFile对应着磁盘上的存储文件&#xff0c;同时也是MappedByteBuffer的封装&#xff0c;消息存储跟磁盘、内存的交…

[激光原理与应用-63]:激光器-光学-探测光、泵浦光和种子光三种光的区别

目录 种子光 泵浦光&#xff1a; 探测光&#xff1a; 种子光 种子光是用来放大出光的&#xff0c;它的作用好比在激光中增加了受激辐射的光子数&#xff0c;因此加快放大出光。 为放大器或者其它激光器产生种子光的激光器。 种子激光器是其输出光被注入到一些放大器或者其…

动态规划系列 —— 背包问题

什么是背包问题 背包问题是有N件物品&#xff0c;容量为V的背包 每个物品有两个属性&#xff1a;体积&#xff0c;价值&#xff0c;分别用数组v&#xff0c;w表示 第i件物品的体积为v[i]&#xff0c;价值为w[i] 计算在背包装得下的情况下&#xff0c;能装的最大价值是多少&…

试题 基础练习 数的读法

问题描述 Tom教授正在给研究生讲授一门关于基因的课程&#xff0c;有一件事情让他颇为头疼&#xff1a;一条染色体上有成千上万个碱基对&#xff0c;它们从0开始编号&#xff0c;到几百万&#xff0c;几千万&#xff0c;甚至上亿。   比如说&#xff0c;在对学生讲解第123456…