[高阶数据结构三] B-树详解

devtools/2024/11/25 10:18:40/

1.前言

相信大家或多或少的都听过B树,本篇文章将带领大家一步一步学习B树,从了解他的概念到模拟实现他的插入过程。

本章重点:

了解B树的相关概念后,由于后续学习B树的插入过程较难,所以会一步一步的对他的插入进行分析。


B树是非常难得,请大家耐心耐心再耐心的学习。

2.为什么要用B树

在正式学习B树之前,先需要明确的是,B树是一种搜索结构,那么它和传统的搜索结构相比,有什么区别呢?

以上的数据结构只能够适用于数据量不太大,能够一次性放入内存中,进行查找的场景。那么对于数据量很大,例如有100G的数据在磁盘里面,那么这么大的数据是无法一次性放入内存的,但是你又需要再这些数据中找到你想要的数据,那么应该怎么办呢?用什么数据结构呢?---这个时候B树就闪亮登场了,B树中存储的是数据在磁盘中的地址,通过B树,就能够在磁盘中找到对应的数据,只需要读取这一个数据进内存即可了。

PS:对于那些能够直接在内存中查找的数据结构,我们称之为内查找。而对于B树这种数据结构来说,我们称之为外查找。

当然也有同学会说,那么为什么不能用AVL树、红黑树和哈希表呢?他们的性能也是很优秀的呀。

下面举一个例子来说明为什么不用AVL树,红黑树等数据结构

例如:

如果使用的是平衡二叉搜索树的话,那么你查找到某一个数据的时间复杂度就是O(LogN),就是说你要查找这么多次,那么LogN次在内存中其实是相当快得了,但是如果是放在磁盘上的话,访问磁盘的速度是很慢的,那么LogN的次数就无法让人接受了。

在磁盘中,其实读数据是一个很快的过程,但是读的前提是找到数据,这个过程就非常的慢了。

如果使用的是哈希表的话,哈希表的访问效率是极高的,常数次就够了。但是在一些极端的情况下某些位置冲突较多,那么就容易导致访问次数增多,这也是无法让人接受的。

那么有没有一种数据结构能够加快对数据的访问呢?

1.提高IO的次数(SSD相对于传统的机械硬盘来说快了不少,但是本质上还是没有得到提升的)

2.把这棵平衡二叉搜索树进行压缩,只要把高度压缩下来,那么次数也就下来了,也能够达到要求。

3.B树的概念

在学习概念之前,先明确一点,有些地方把B树写成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-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki+1。n为结点中关键字的个数,满足ceil(m/2)-1≤n≤m-1。

解释:第六点的意思是:n表示当前块里面有效的关键字的个数,A0<K1指针里面的值<A1<K2指针里面的值.........;依次类推

光看B树的定义是非常抽象的, 甚至于是看不懂,但定义中的关键点是每个节点中的关键字是有序的, 并且节点的结构是: 关键字,孩子,关键字,孩子…实际上当M=2时,B树就是一颗二叉树, B树的节点中是一个数组,可存放多个数据。

4.B树的插入分析

现在使用一个案例,来解释B树的这些性质. 设M=3,即三叉树,每个节点存两个数据,和三个孩子区域的划分。采用如下结构来进行分析,也方便后续好写代码

PS:这里记住,孩子是永远都比数据要多一个的。

用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下:

第一步:

由于M=3,一个节点只能存储两个数据,所以当插入75时,需要对这棵树做分裂. 怎样分裂呢?方法如下: 1. 找到节点中的中间数据(图中为75). 2. 创建一个新节点, 将中间数据挪动到新节点. 3. 以中间数据(75)作为分割, 将中间数据左边的所有节点保持不动, 将中间数据右边的所有节点移动至另外一个新节点. 4. 将中间数据所在的新节点当父亲, 左右两个兄弟节点当儿子, 连接起来. 具体结果看下图:

第二步分裂如下:

此时分裂之后的结果是满足B树的性质6的,也满足B树的其他性质。

第三步:

插入49和145

PS:B树的插入都是在叶子节点进行的,当叶子节点不符合B树规则时才会向上形成新的节点,也就是所谓的分裂操作

发现这两次均没有违反B树的概念。

第四步:插入36

违反规则,进行调整

这一次插入36,会导致左下角的节点违反B树的规则,所以需要进行分裂. 本次分裂和上次分裂基本一致,唯一的区别就是, 中间数据,也就是49,不需要再重新形成一个新节点并将49放入,数据49可以直接被放在数据75所在的节点中. 具体的结果图如下:

第五步:插入101

这里分裂的变化和上述一样,直接给出最终结果。

经过分析上述插入过程,总结如下:

插入过程总结:
1. 如果树为空,直接插入新节点中,该节点为树的根节点
2. 树非空,找待插入元素在树中的插入位置 ( 注意:找到的插入节点位置一定在叶子节点中 )
3. 检测是否找到插入位置 ( 假设树中的 key 唯一,即该元素已经存在时则不插入 )
4. 按照插入排序的思想将该元素插入到找到的节点中
5. 检测该节点是否满足 B- 树的性质:即该节点中的元素个数是否等于 M ,如果小于则满足
6. 如果插入后节点不满足 B 树的性质,需要对该节点进行分裂:
申请新节点
找到该节点的中间位置
将该节点中间位置右侧的元素以及其孩子搬移到新节点中
将中间位置元素以及新节点往该节点的双亲节点中插入,即继续 4
7. 如果向上已经分裂到根节点的位置,插入结束

5.B树的插入模拟实现

先搭建B树的基本框架:

template <class K,size_t M>
struct BTreeNode
{K _keys[M];//本来是M-1个关键字,但是开辟了M个,可以方便后续分裂BTreeNode<K, M>* _subs[M + 1];BTreeNode<K, M>* _parent;int _num;//记录有多少个关键字BTreeNode(){for (size_t i = 0; i < M; i++){_keys[i] = K();_subs[i] = nullptr;}_subs[M] = nullptr;_parent = nullptr;_num = 0;}
};//数据是存在磁盘,K是磁盘地址
template<class K,size_t M>
class BTree
{typedef BTreeNode<K, M> Node;
public:
private:Node* _root = nullptr;
};

在插入之前要先找到,于是先实现找到的代码

pair<Node*, int> Find(const K& key)
{//找到了返回该值所在位置的节点和在节点中的下标//没找到就返回要插入的叶子节点Node* cur = _root;Node* parent = nullptr;while (cur){int i = 0;//下面的逻辑表示在一个节点中查找while (i < cur->_num){if (key < cur->_keys[i])break;//去左边的话,那么subs中下标与key中相同else if (key > cur->_keys[i])i++;//去右边的话,那么就一样else return make_pair(cur, i);}parent = cur;cur = cur->_subs[i];}return make_pair(parent, -1);
}

由于是在一个节点里面插入,所以找到之后那么返回的是一个节点,但是一个节点有存储数据的数组还有储存节点的孩子,所以还需要知道的是需要插入在数组的哪一个位置的前面 ,所以设计成了pair类型。

在插入的过程中,要先插入然后再判断是否需要分裂,所以插入的代码单独实现

//在一个节点里面插入值key和孩子
//void InsertKey(Node* node, const K& key)
//{
//	//下面插入代码有问题,在插入36时,53这个兄弟节点直接没有了。
//	int end = node->_num - 1;
//	//插入排序,若插入的数据较小,原先的数据会往后移动
//	while (end >= 0)
//	{
//		if (node->_keys[end] > key)
//		{
//			//挪动key
//			node->_keys[end + 1] = node->_keys[end];
//			end--;
//		}
//		else break;
//	}
//	//插入在end位置的后面,可能比所有值都小,end+1=0
//	node->_keys[end + 1] = key;
//	node->_num++;
//}//在一个节点里面插入值key和孩子---修改版
void InsertKey(Node* node, const K& key, Node* children)
{//修改版int end = node->_num - 1;//插入排序,若插入的数据较小,原先的数据会往后移动while (end >= 0){if (node->_keys[end] > key){//不仅要挪动key,还要挪动它的右孩子node->_keys[end + 1] = node->_keys[end];node->_subs[end + 2] = node->_subs[end + 1];end--;}else break;}//插入在end位置的后面,可能比所有值都小,end+1=0node->_keys[end + 1] = key;node->_subs[end + 2] = children;if (children)children->_parent = node;node->_num++;
}

下面主要实现分裂的过程,要插入时直接调用函数即可

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node;_root->_keys[0] = key;_root->_num++;return true;}K key1 = key;pair<Node*, int> ret = Find(key1);if (ret.second >= 0){//B树里面已经有了,不能重新插入cout << "B树里面已经有这个值了,请勿重新插入" << endl;return false;}//到这里就找到了要插入的所在节点了Node* cur = ret.first;//要插入的节点K newkey = key;Node* children = nullptr;//循环每次往cur插入newkey和childwhile (1){InsertKey(cur, newkey, children);if (cur->_num < M){return true;}else{//走到这里就要进行分裂了int mid = (int)M / 2;Node* brother = new Node;int j = 0;for (int i = mid + 1;  i<= M - 1; i++){//带走一个值那么就等同于要带走一个孩子--始终记得孩子是要比值多一个的brother->_keys[j] = cur->_keys[i];brother->_subs[j] = cur->_subs[i];if (cur->_subs[i])cur->_subs[i]->_parent = brother;//既然你已经赋值给别人了,那么就清空一下cur->_keys[i] = K();cur->_subs[i] = nullptr;j++;}brother->_num += j;cur->_num -= (j + 1);//+1表示还要把mid分走//拷贝完后还有最后一个右孩子,最右的孩子需要拷贝走brother->_subs[j] = cur->_subs[M];if (cur->_subs[M])cur->_subs[M]->_parent = brother;cur->_subs[M] = nullptr;//分裂后转换成往cur->parent插入mid和brotherK midKey = cur->_keys[mid];//cur等于空证明分裂的是根节点cur->_keys[mid] = K();if (cur->_parent == nullptr){_root = new Node;_root->_keys[0] = midKey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_num = 1;cur->_parent = _root;brother->_parent = _root;break;}else {newkey = midKey;//中位数给父亲了,也重置一下children = brother;cur = cur->_parent;}}}return true;
}

对于B树的插入来说, 步骤就是上面分析过的步骤,但是代码实现是比较抽象,比较难懂的, B树的模拟实现本身就属于拓展内容, 如果你理解不了也是没关系的, 知道B树的性质和用途就好了。

6.总结

上述代码的重点是它的分裂逻辑和使用场景, 并且B树在实际生产中运行并不会很多多, 因为有更好的数据结构: B+树或是B*树来代替它. 但是学习后两者的前提是需要你知晓B树的性质, 所以学习要一步一步来,不能一步登天。


http://www.ppmy.cn/devtools/136813.html

相关文章

C++:用红黑树封装map与set-1

文章目录 前言一、STL源码分析二、红黑树的构建三、map与set整体框架的搭建与解析四、如何取出进行比较&#xff1f;1. met与set的数据是不同的2. 取出数据进行比较1&#xff09;问题发现2&#xff09;仿函数解决 五、封装插入六、迭代器的实现1. operator* 与operator->2. …

Dubbo Golang快速开发Rpc服务

开发 RPC Server & RPC Client 基于 Dubbo 定义的 Triple 协议&#xff0c;你可以轻松编写浏览器、gRPC 兼容的 RPC 服务&#xff0c;并让这些服务同时运行在 HTTP/1 和 HTTP/2 上。Dubbo Go SDK 支持使用 IDL 或编程语言特有的方式定义服务&#xff0c;并提供一套轻量的 …

【计算机网络】IP协议

一、IP协议的功能 提供将数据从A主机跨网络送到主机B的能力 (在复杂的网络环境中确定一个合适的路径) 二、IP协议格式 ​​​​​​​1.报头的含义 &#xff08;1&#xff09;一般字段 ① 4位版本&#xff1a;指定IP协议的版本&#xff0c;对于IPv4来说就是4 ② 4位首部长度…

定时/延时任务-Timer用法

文章目录 1. 概要2. 简述2.1 固定速率2.2 固定延时2.3 区别 3. Timer 的用法3.1 固定延时 - public void schedule(TimerTask task, long delay, long period)3.1.1 解释 3.2 固定延时 - public void schedule(TimerTask task, Date firstTime, long period)3.3 固定速率 - pub…

mfc100u.dll是什么?分享几种mfc100u.dll丢失的解决方法

mfc100u.dll 是一个动态链接库&#xff08;DLL&#xff09;文件&#xff0c;属于 Microsoft Foundation Classes (MFC) 库的一部分。MFC 是微软公司开发的一套用于快速开发 Windows 应用程序的 C 类库。mfc100u.dll 文件包含了 MFC 库中一些常用的函数和类的定义&#xff0c;这…

C++设计模式:建造者模式(Builder) 房屋建造案例

什么是建造者模式&#xff1f; 建造者模式是一种创建型设计模式&#xff0c;它用于一步步地构建一个复杂对象&#xff0c;同时将对象的构建过程与它的表示分离开。简单来说&#xff1a; 它将复杂对象的“建造步骤”分成多部分&#xff0c;让我们可以灵活地控制这些步骤。通过…

设计模式-创建型-建造者模式

1.概念 建造者设计模式&#xff08;Builder Design Pattern&#xff09;是一种创建型设计模式&#xff0c;它通过将一个复杂对象的构建过程与它的表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。 2.作用 用于简化对复杂对象的创建 3.应用场景 当我们有一个非…

P1 练习卷(C++4道题)

1.纷繁世界 内存限制&#xff1a;256MB 时间限制&#xff1a;1s 问题描述 这是一个纷繁复杂的世界。 某一天清晨你起床很迟&#xff0c;没有吃上早饭。于是你骑着自行车去超市&#xff0c;但是你又发现商店的工作人员已经重新贴上了价格标签&#xff0c;零食价格都涨了50%。你…