数据结构：图解手撕B-树

本篇总结的内容是B-树

为什么需要引入B-树？

回忆一下前面的搜索结构，有哈希，红黑树，二分…等很多的搜索结构，而实际上这样的结构对于数据量不是很大的情况是比较适用的，但是假设有一组很大的数据，大到已经不能在内存中存储，此时应该如何处理呢？可以考虑将关键字及其映射的数据的地址放到一个内存中的搜索树的节点，优先考虑去这个地址处访问数据

从上面的文段中可以看出，问题出现在文件的IO是有损耗的，因此在使用哈希或是其他的数据结构，在搜索的过程中会不断地进行文件的IO，这样带来的降低效率是不建议出现的，因此解决方案之一就是可以降低树的高度，因此就引出了B-树：多叉平衡树

B树是什么？

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(后面有一个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

上面的规则很复杂，那么下面用图片来解释B树的插入原理，并进行一次模拟

B树的插入分析

假设此时的M = 3，也就是这是一个三叉树，那么从上面的规则来说，每个节点要存储两个数据，还有三个孩子节点，而实际上的过程中会分别多创建一个节点，也就是说会创建三个数据域和四个孩子节点，这样的好处后续在实现代码的过程中会体现出来

假设现在给定了这样的一组数据：53, 139, 75, 49, 145, 36, 101

图解如下：

那么超过了可以容纳的数据个数，该如何处理呢？看B树的规则是如何处理的：

B树的分裂规则：

当超过了最多能容纳的数据个数后，会进行分裂：

1. 找到节点数据域的中间位置
2. 创建一个兄弟节点，把后一半的数据挪动到兄弟节点中
3. 把中位数的数据移动到父节点中
4. 对这些节点建立链接

此时就完成了B树的一次分裂，从中就能看出B树的基本原理，既然是多叉搜索树，那么也要满足搜索树的规则，因此采取这样的分裂规则是可以满足搜索树的要求的

继续进行插入数据，按照上述的原理即可

当继续插入的时候，就会产生新的分裂问题：

由此得出了最终的生成图

从这个图中也能看出，确实是符合搜索树的预期的，那么下一步就是要把上面写的这一系列的过程转换成代码来进行实现

#include <iostream>
using namespace std;

// 定义B树节点的信息
template <class K, size_t M>
struct BTreeNode
{
	// 节点内部包含一个数组用来存储数据域信息，和一个指针数组用来保存孩子节点信息，以及双亲的信息
	// 还要包括节点中已经存储的数据的数量
	// 多开辟一个空间，方便于判断是否需要进行分裂
	K _keys[M];
	BTreeNode<K, M>* _subs[M + 1];
	BTreeNode<K, M>* _parent;
	size_t _n;

	BTreeNode()
		:_parent(nullptr)
		, _n(0)
	{
		for (int i = 0; i < M; i++)
		{
			_subs[i] = nullptr;
			_keys[i] = nullptr;
		}
		_subs[M] = nullptr;
	}
};

// 存储B树的信息
template <class K, size_t M>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:
	// 查找函数，找某个确定的Key值，如果找到了返回它所在的节点和所处节点的位置
	pair<Node*, int> Find(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		// 开始寻找
		while (cur)
		{
			size_t i = 0;
			// 指针到每一层的节点后进行比较
			while (i < cur->_n)
			{
				if (key < cur->_keys)
				{
					// 说明此时要查找的节点信息不在这一层，一定是要到下面一层去找，因此跳出这一层的循环
					break;
				}
				else if (key > cur->_keys)
				{
					// 说明此时要查找的信息可能在当前查找的节点的后面，还要去后面找找看
					i++;
				}
				else
				{
					// 说明此时找到节点的信息了，直接把节点的信息进行返回即可
					return make_pair(cur, i);
				}
			}
			// 说明此时这一层已经找完了，现在该去下一层进行寻找了
			parent = cur;
			// 由B树的性质得出，subs[i]中存储的信息是比当前信息要小的树，因此去这里寻找目标Key值
			cur = cur->_subs[i];
		}

		// 运行到这里就是这个值在B树中不存在，返回查找最后的层数的节点和错误值即可
		return make_pair(parent, -1);
	}

	// 把元素插入到表中，本质上是一种插入排序
	void InsertKey(Node* node, const K& key, Node* child)
	{
		int end = node->_n - 1;
		while (end >= 0)
		{
			if (key < node->_keys[end])
			{
				// 挪动key和他的右孩子
				node->_keys[end + 1] = node->_keys[end];
				node->_subs[end + 2] = node->_subs[end + 1];
				--end;
			}
			else
			{
				break;
			}
		}

		// 把值写入到节点中
		node->_keys[end + 1] = key;
		node->_subs[end + 2] = child;
		// 如果有孩子节点，那么要更新孩子节点的指向，插入元素后双亲所在的位置发生了变化
		if (child)
			child->_parent = node;
		node->_n++;
	}

	bool Insert(const K& key)
	{
		// 如果_root是一个空树，那么直接创建节点再把值放进去即可
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = key;
			_root->_n++;
			return true;
		}

		// 运行到这里，说明这个树不是一个空树，那么首先要寻找插入的节点在现有的B树中是否存在
		pair<Node*, int> ret = Find(key);
		if (ret.second != -1)
		{
			// 键值对的第二个信息不是-1，说明在B树中找到了要插入的信息，这是不被允许的，因此返回
			return false;
		}

		// 运行到这里，说明要开始向B树中插入新节点了
		// 并且前面的ret还找到了parent，也就是实际应该是插入的位置信息
		Node* parent = ret.first;
		K newKey = key;
		// 创建孩子指针的意义是，后续可能会重复的进行分裂情况，并且插入元素的节点中可能原先有值
		// 直接插入后，会把原来孩子节点的双亲节点发生替换，因此要改变孩子节点的指向
		Node* child = nullptr;
		while (1)
		{
			// 此时就找到了要插入的元素，要插入的位置，进行插入
			InsertKey(parent, newKey, child);

			// 如果双亲节点没有超出限制，那么就说明此时插入已经完成了
			if (parent->_n < M)
			{
				return true;
			}
			else
			{
				// 运行到这里时，就说明已经超过了节点能容纳的最大值，此时应该进行分裂处理
				// 找到中间的元素
				size_t mid = M / 2;
				// 把[mid + 1, M - 1]分配个兄弟节点
				Node* brother = new Node;
				size_t j = 0;
				size_t i = mid + 1;
				for (; i <= M - 1; ++i)
				{
					// 分裂拷贝key和key的左孩子，把这些信息拷贝给兄弟节点
					brother->_keys[j] = parent->_keys[i];
					brother->_subs[j] = parent->_subs[i];
					if (parent->_subs[i])
						parent->_subs[i]->_parent = brother;
					++j;

					// 被拷贝走的元素所在的位置进行重置，表明已经被拷贝走了
					parent->_keys[i] = K();
					parent->_subs[i] = nullptr;
				}
				// 还有最后一个右孩子拷给
				brother->_subs[j] = parent->_subs[i];
				if (parent->_subs[i])
					parent->_subs[i]->_parent = brother;
				parent->_subs[i] = nullptr;
				
				// 更新一下原先节点和兄弟节点中的元素的个数
				brother->_n = j;
				parent->_n -= (brother->_n + 1);

				K midKey = parent->_keys[mid];
				parent->_keys[mid] = K();


				// 说明刚刚分裂是根节点，要创建一个新的根节点用来存储分裂的中位数的信息
				if (parent->_parent == nullptr)
				{
					_root = new Node;
					_root->_keys[0] = midKey;
					_root->_subs[0] = parent;
					_root->_subs[1] = brother;
					_root->_n = 1;

					parent->_parent = _root;
					brother->_parent = _root;
					break;
				}
				else
				{
					// 向parent中插入一个中位数，同时更新一下孩子的信息即可
					// 转换成往parent->parent 去插入parent->[mid] 和 brother
					newKey = midKey;
					child = brother;
					parent = parent->_parent;
				}
			}
		}
		return true;
	}
private:
	Node* _root = nullptr;
};