【高阶数据结构(六)】B-树详解

avatar
作者
筋斗云
阅读量:0

💓博主CSDN主页:杭电码农-NEO💓
 
⏩专栏分类:高阶数据结构专栏⏪
 
🚚代码仓库:NEO的学习日记🚚
 
🌹关注我🫵带你学习更多数据结构
  🔝🔝

在这里插入图片描述

高阶数据结构

1. 前言

相信大家之前或多或少都听说过B树或B+树,奔跑文章将从认识B树到手撕B树(注意不是B减树,是B树),一步一步带你吃透它!

本章重点:

本篇文章着重讲解B树的概念和它的性质,并且回一步一步分析它的插入规则,为后续手撕B树做铺垫. 手撕B树指挥实现插入版本,删除过于复杂这里不多做讨论, 期间回将B树和传统的搜索结构如哈希,红黑树等做对比.

B树学习难度较大, 请大家耐心学习

2. 初识B树

首先要明确一点, B树是一个搜索结构.那么它和传统的搜索结构,比如红黑树, 哈希等有什么区别呢?先请看下图:

在这里插入图片描述

以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了. 是的传统的搜索结构用于内查找,也就是在内存中查找,但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。

在这里插入图片描述

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

3. B树的插入分析

现在我们使用一个B树做插入的案例,来解释B树的这些性质. 设M=3,即三叉树,每个节点存两个数据,和三个孩子区域的划分

在这里插入图片描述
注意：孩子永远比数据多一个。

用后面的图可以更好的演示B树的分裂

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

第一步:
在这里插入图片描述

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

在这里插入图片描述

这样做恰好满足了B树的一个性质: A1,K1,A2,K2数组中, A1,这里代表75的左孩子,是小于K1的,K1也就是75. 而A2,对应是139所在的节点, 是大于K1的.

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

在这里插入图片描述
这两次插入都没违反规则

第三步:

在这里插入图片描述

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

在这里插入图片描述

并且也要满足上面所说的A1<K1<A2<K2<A3
注意, 节点中只存了两个数据, 数据下面的数据存储的是孩子节点的地址

第四步:

在这里插入图片描述

看见此图,聪明的你肯定已经想到了需要进行分裂, 将中间数据139提到父亲节点. 那么更聪明的人也发现了,此时父亲节点的数据也是三个,不符合规则, 所以父亲节点也需要进行分裂. 分裂的规则和之前是一样的,这里就不再画图了,大家可以自己尝试去画一下图.

4. B树的规则再分析

了解了B树是如何分裂了之后,我们在倒过来看看B树的规则,就好理解多了:

  1. 根节点至少有两个孩子: 为什么呢?因为B树进行一次分裂之后, 至少会分裂出两个孩子.
  2. 第二点解释: 孩子的数量永远比数据多一个,K一般就取值为M

剩下的我相信大家都能理解了

5. B树模拟实现

首先是基本的B树节点的结构:

template<class K, size_t M> struct BTreeNode { 	K _keys[M];//m个孩子,m-1个关键字.但为了方便插入再分裂,定义为M个关键字,M+1个child 	BTreeNode<K, M>* _childs[M + 1]; 	BTreeNode<K, M>* _parent; //存父亲节点,分裂时需要用 	size_t _num;//记录实际存储了多少个key(记录key或child都行)  	BTreeNode() { 		for (int i = 0; i < M; i++) { 			_keys[i] = K(); 			_childs[i] = nullptr; 		} 		_num = 0; 		_childs[M] = nullptr; 		_parent = nullptr; 	} }; //数据是存在磁盘, K就是磁盘地址 template<class K,size_t M> class BTree { 	typedef BTreeNode<K, M> Node; private: 	Node* _root = nullptr; };

当然在实现B树的插入之前, 我们需要先实现Find函数, 如果插入的值已存在,那么就什么都不用做了. 当前我们也可以提前封装好插入节点的逻辑

pair<Node*, int> Find(const K& key)//返回这个值以及它的下标 { 	Node* cur = _root; 	//记录路径,最后会获得叶子节点 	Node* prev = nullptr; 	while (cur) 	{ 		size_t i = 0; 		//下面的逻辑表示在一个节点中查找 		while (cur && i < cur->_num) 		{ 			//在左孩子中去找,左孩子的数组的下标等于当前下标 			if (key < cur->_keys[i]) 				break; 			//比当前值大就往后++,直到值比key大 			else if (key > cur->_keys[i]) 				i++; 			else return make_pair(cur, i); 		} 		//往孩子去跳 		prev = cur; 		cur = cur->_childs[i]; 	} 	return make_pair(prev, -1); }  //给一个节点的指针,插入key和children 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->_childs[end + 2] = node->_childs[end + 1]; 			end--; 		} 		else break; 	} 	//插入在end位置的后面,可能比所有值都小,end+1=0 	node->_keys[end + 1] = key; 	node->_childs[end + 2] = children; 	if (children) 		children->_parent = node; 	node->_num++; }

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

bool Insert(const K& key) { 	//第一次插入的逻辑 	if (_root == nullptr) { 		_root = new Node; 		_root->_keys[0] = key; 		_root->_num++; 		return true; 	} 	pair<Node*, int> ret = Find(key); 	//key已经存在,插入失败 	if (ret.second  >= 0) 		return false; 	//若key不存在,find顺便带回来了要插入的叶子节点 	Node* cur = ret.first; 	K newKey = key; 	Node* children = nullptr; 	//循环每次往cur插入newkey和child 	while (1) { 		InsertKey(cur, newKey,children); 		//判断此节点满没有 		if (cur->_num < M) 			return true; 		//需要分裂,创建一个兄弟节点 		else { 			size_t mid = M / 2; 			//[mid+1,M-1]给兄弟 			Node* brother = new Node; 			int j = 0; 			for (int i = mid + 1; i <= M - 1; i++) 			{ 				brother->_keys[j] = cur->_keys[i]; 				//不仅仅要拷贝走一半的数据,并且还需要将这一半数据的孩子一起拷贝给brother 				//拷走一个key就要拷走这个key的左孩子.孩子的父亲变了,需要修改 				brother->_childs[j] = cur->_childs[i]; 				if (cur->_childs[i]) 					cur->_childs[i]->_parent = brother; 				//将拷贝走的数据重置 				cur->_keys[i] = K(); 				cur->_childs[i] = nullptr; 				j++; 			} 			//拷贝完后还有最后一个右孩子,最右的孩子需要拷贝走 			brother->_childs[j] = cur->_childs[M]; 			if (cur->_childs[M]) 				cur->_childs[M]->_parent = brother; 			cur->_childs[M] = nullptr; 			brother->_num = j; 			cur->_num -= (j + 1);//拷走了j个,mid也被提取了 			//分裂后转换成往cur->parent插入mid和brother 			K midKey = cur->_keys[mid]; 			//cur等于空证明分裂的是根节点 			cur->_keys[mid] = K(); 			if (cur->_parent == nullptr) 			{ 				_root = new Node; 				_root->_keys[0] = midKey; 				_root->_childs[0] = cur; 				_root->_childs[1] = brother; 				_root->_num = 1; 				cur->_parent = _root; 				brother->_parent = _root; 				break; 			} 			else { 				newKey = midKey; 				//中位数给父亲了,也重置一下 				children = brother; 				cur = cur->_parent; 			} 		} 	} 	return true; }

6. 总结以及拓展

B树模块的重点是它的分裂逻辑和使用场景, 并且B树在实际生产中运行并不多, 因为有更好的数据结构: B+树或是B*树来代替它. 但是学习后两者的前提是需要你知晓B树的性质, 所以学习不是一蹴而就的,是需要持之以恒的

🔎 下期预告:B+树,B*树,MySQL索引讲解 🔍
相关阅读
  1. 如何查看和设置我的Android N设备的权限？
  2. 如何在安卓手机上自定义应用图标？
  3. 如何在安卓微信中同时听语音和查看图片？
  4. 华为哪些设备将支持升级至安卓7.0？
  5. 微信安卓软件中Q10功能有哪些独特之处？
  6. 安卓用户如何挑选最佳视频播放器应用？
  7. 安卓系统中用户文件目录的确切位置是什么？
  8. 小米4用户如何安全升级到安卓8.0系统？
  9. 如何成功将魅蓝5升级至安卓原生7.0版本？
  10. 16GB存储的安卓手机是否能满足日常需求？

广告一刻

为您即时展示最新活动产品广告消息，让您随时掌握产品活动新动态！