当前位置： 首页 > article >正文

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

article 2025/2/22 2:22:44

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=0
	node->_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和child
	while (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和brother
			K 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.kler.cn/a/408244.html

相关文章：

  • 【Linux】线程的互斥和同步
  • AirScreen 安卓平板作为MacOS副屏
  • 【淘汰9成NLP面试者的高频面题】LSTM中的tanh和sigmoid分别用在什么地方？为什么？
  • postgresql按照年月日统计历史数据
  • VMware16安装macOS12【详细教程】
  • docker 相关命令
  • 力扣 最大数组和-53
  • SQL99版全外连接和交叉连接和总结
  • 4-使用您自己的输出 --github_com_fatih_color测试
  • 2024年Android面试总结
  • Android开发实战班 -网络编程 - Retrofit 网络请求 + OkHttp 使用详解
  • Spring 小案例体验创建对象的快感（Java EE 学习笔记05）
  • 【大数据测试ETL：从0-1实战详细教程】
  • Python爬虫：深入探索1688关键词接口获取之道
  • SpringMVC-Day1
  • 图像处理算法识别手势
  • OCR-free Document Understanding Transformer
  • 【django】扩展
  • TCP为什么需要三次握手？两次握手或四次握手可以吗？
  • LeetCode 904.水果成篮