其它高阶数据结构⑤_B树（概念+实现OJ）-EW帮帮网

一棵m阶（m>2）的B树（B树中所有结点的孩子个数的最大值称为B树的阶），是一棵M路的平衡搜索树，可以是空树或者满足一下性质的树：

树中每个结点至多有m棵子树，即至多含有m-1个关键字。

若根结点不是终端结点，则至少有两棵子树。

除根结点外的所有非叶子结点都包含k-1个关键字和k个孩子（终端结点孩子都是NULL)，其中 ceil(m/2) ≤ k ≤ m （ceil是向上取整函数）

所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)

每个节点中的关键字从小到大（也可以从大到小）排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分

每个结点的结构为：（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，Ai+1所指子树所有结点中的关键字均大于Ki+1。（结点中关键字升序的情况下）n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。

可以对照上面的图先来自行理解一下B树的这些性质，等后面熟悉了B树的结构之后再来反复理解这几条性质为什么是这样。

3. B树的插入图解和代码

3.1 B树的插入图解

为了方便理解，这里选取B树的阶数m取小一点，给一个3：（实际应用中m一半会取比较大，比如1024）即三阶B-树（三叉平衡树），那每个结点最多存储两个关键字，两个关键字可以将区间分割成三个部分，因此节点应该有三个孩子（子树）。那每个结点的结构就应该是这样的：

但是为了后续实现起来简单，关键字和孩子都多给一个空间（后面大家就能体会到为什么要多给一个）节点的结构如下：

下面我们就来找一组数据分析一下插入的过程，用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下：

75插入之后是这样，但是因为我们多开了一个空间，3阶的话每个结点最多3-1=2个关键字。所以现在这个结点关键字个数超了。要进行一个操作：分裂。分裂结点：

找到关键字序列的中间数，将关键字序列分成两半。
新建一个兄弟结点出来，将右半边的m/2个关键字分给兄弟结点。
将中间值提给父亲结点，新建结点成为其右孩子（没有父亲就创建新的根）为什么中位数做父亲？：满足搜索树的大小关系（左<根<右）。
将结点指针链接起来。

        这里体会一下上面的规则中为什么要求除根结点外的所有非叶子结点都包含k-1个关键字（ceil(m/2) ≤ k ≤ m，即k的最小值是ceil(m/2)），即最少包含ceil(m/2)-1个关键字。
        如果m是奇数，比如9，那ceil(m/2)是5个，5-1是4，而9个的话分裂之后正好两边每个结点都是4个关键字，中间的一个提取给父亲。
        如果m是偶数，比如10的话，ceil(m/2)是5，5-1是4，而10个分裂的话，肯定不平均，一边4个（最少的），一边5个，还有一个中间值要提取给父亲。所以它们最少就是ceil(m/2)-1个关键字。

还是我们上面给的那组数据，再往后插入49，145，36：

现在体会，为什么要多开一个空间？这样的话我们就可以在插入之后关键字顺序已经调整好的情况下去分裂，就方便很多。

再往下插入101：

插入101之后这个结点的关键字数量大于m-1了，进行分裂，分裂的步骤还是和上面一样。

分裂之后我们发现父亲满了，所以需要继续向上分裂。

那这就是一个完整的插入过程。

并且会发现B树每一次插入之后他都是天然的完全平衡，不需要像AVL树和红黑树那样，插入之后不满足平衡条件了，再去调整。

并且B树的平衡是绝对平衡。每一棵树的左右子树高度之差都是0。

为什么他能保持天然的完全平衡呢？

通过上面的插入过程很容易发现B树是向右和向上生成的，只会产生新的兄弟和父亲。

插入过程总结：

如果树为空，直接插入新节点中，该节点为树的根节点。
树非空，找待插入关键字在树中的插入位置（找到的插入节点位置一定在终端节点中）。
检测是否找到插入位置（假设树中的key唯一，即该元素已经存在时则不插入）。
按照插入排序的思想将该关键字插入到找到的结点中。
检测该节点关键字数量是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足，插入结束。
如果插入后节点不满足B树的性质，需要对该节点进行分裂：

申请新的兄弟节点。
找到该节点的中间位置。
将该节点中间位置右侧的元素以及其孩子搬移到新节点中。
将中间位置元素（新建结点成为其右孩子）提取至父亲结点中插入，从步骤4重复上述操作。

3.2 B树的代码分析

首先定义一下B树的结点：这里还是搞成模板，简单一点，就不实现成KV模型了，就搞个K，当然在搞个非类型模板参数M控制B树的阶。

template<class K, size_t M> // 数据是存在磁盘，K是磁盘地址

然后结点的话，上面分析过一棵3阶的B树，为了方便插入之后分裂，要多开一个空间：正常每个结点最多M-1个关键字，M个孩子。那增加一个就是M个关键字，M+1个孩子。

那我们如何定义这样一个结构呢？

这实际就是两个数组，然后还需要一个父亲指针，指向父结点；还需要再给一个成员变量记录当前结点实际存储关键字的个数。然后也可以写一个默认构造。

template<class K, size_t M>
class BTreeNode
{
public:
	K _keys[M]; // 为了方便插入以后再分裂，多给一个空间
	BTreeNode<K, M>* _subs[M + 1];
	BTreeNode<K, M>* _parent;
	size_t _n; // 记录实际存储多个关键字 

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

根据实现AVL树和红黑树以及上面B树的插入图解，先来实现一个find，因为后面插入也要先find。

这里实现一个不允许键值冗余的版本，如果存在就不再插入了，如果不存在，让find直接返回找到的那个要插入位置的结点，便于在Insert函数中直接将值插入到该结点中。

就比如上面的图，现在要查找53。那首先和根结点的关键字进行比较，当前根结点只有一个值75，53小于75，所以去其左子树查找。那来分析一下一个关键字和它的左右孩子之间的关系：

其实很容易看出来，在B树中，一个关键字的左孩子在_child数组中的下标和该关键字在_keys数组中的下标是一样的，而右孩子的话，比关键字的下标大1。

所以就走到它的左子树49这个结点，也只有一个关键字，53大于49，所以再去关键字49的右子树（如果49后面还有关键字的话，就继续跟后面的比）。

那此时就走到50，53这个结点。首先跟第一个关键字50比，比50大，那就继续往后比，后面是53，相等，找到了。那如果查找52呢（不存在）？前面是一样的，走到这个结点，比50大，往后比，比53小，所以去53的左子树，53的左子树为空，所以找不到了。

	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[i])
				{
					break;
				}
				else if (key > cur->_keys[i])
				{
					++i;
				}
				else
				{
					return make_pair(cur, i);
				}
			}
			parent = cur; // 往孩子去跳
			cur = cur->_subs[i];
		}
		return make_pair(parent, -1);
	}

接下来开始写B树的插入：

首先如果是第一次插入的话我们需要做一个单独处理：

		if (_root == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = key;
			_root->_n++;
			return true;
		}

那再往下就是已经有结点的情况下插入，首先查找一下如果key已经存在，就不再插入。如果不存在，那就去插入（find顺便带回了要插入的那个目标位置的结点），那接收一下find的返回值，在这个结点里面插入即可。

那插入的时候需要保证结点里面关键字的顺序，可以用插入排序的思想把新的关键字插进去（如果是分裂之后向父亲插入的话，它可能还有孩子），这里再单独封装一个InsertKey的函数。

然后就可以调用InsertKey接口去插入关键字，但是插入的话：按理说是插入一次，但是如果插入之后存储关键字的数组满了（多开了一个空间，满的话就不满足B树的性质：至多含有m-1个关键字了），就需要进行分裂，分裂的话，就又需要往parent去插入（插入中间值），当然分裂的兄弟结点也要成为parent的孩子（孩子和关键字都增加1，依然符合规则）然后插入之后满了还需要再往上分裂，所以应该写成一个循环。完整的Insert函数：（建议复制到编译器跟着注释看）

	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 // 跳出和end为-1的情况一起处理
			{
				break;
			}
		}
		node->_keys[end + 1] = key;
		node->_subs[end + 2] = child;
		if (child)
		{
			child->_parent = node;
		}
		node->_n++;
	}

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = key;
			_root->_n++;
			return true;
		}

		pair<Node*, int> ret = Find(key);
		if (ret.second >= 0) // key已经存在，不允许插入
		{
			return false;
		}

		Node* parent = ret.first; // 如果没有找到，find顺便带回了要插入的那个叶子节点
		K newKey = key;
		Node* child = nullptr;
		while (true) // 循环每次往cur插入 newkey和child
		{
			InsertKey(parent, newKey, child);
			if (parent->_n < M) // 满了就要分裂，没有满，插入就结束
			{
				return true;
			}
			else
			{
				size_t mid = M / 2;
				Node* brother = new Node; // 分裂一半[mid+1, M-1]给兄弟
				size_t j = 0;
				size_t i = mid + 1;
				for (; i <= M - 1; ++i)
				{
					brother->_keys[j] = parent->_keys[i];
					brother->_subs[j] = parent->_subs[i]; // 分裂拷贝key和key的左孩子
					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; // 跳出return true;
				}
				else // 转换成往parent->parent 去插入parent->[mid] 和 brother
				{
					newKey = midKey;

					child = brother;
					parent = parent->_parent;
				}
			}
		}
		return true;
	}

3.3 B树的中序遍历

上面构建一棵上面画的图的树来测试一下，在这之前看看B树的中序遍历：

之前学的二叉树来说中序遍历的思想是：左子树、根、右子树。那B树的话它可能是一个多叉的，中序遍历应该怎么走呢？首先肯定还是先访问左子树，搜索树中最左的结点一定是最小的。

当然如果算上空结点的话最左的应该是空，左子树，然后依然是根，就是36，36就是最小的，没问题。左子树、根，那然后呢？是36的右子树吗？可以认为是36的右子树，但是我们要把它当作40的左孩子看。36这个关键字访问完，就走到后面的40，对于40，同样是先左子树再根。

那这个第二个访问到的元素就是40，此时当前结点所有的关键字访问完了，最后再去访问最后一个关键字的右子树：

此时整个结点才被访问完。那此时就相当于是49的左子树访问完了，然后访问根49，后面就是一样的处理…

所以B树的中序遍历是怎么样的呢？左子树、根；（下一个关键字的）左子树、根；（再下一个）左子树、根；…(一直往后直至走完最后一个关键字）；右子树（最后一个关键字的右子树）左根左根 … 右。B树的中序遍历代码：

	void _InOrder(Node* cur)
	{
		if (cur == nullptr)
			return;

		size_t i = 0; // 左 根  左 根  ...  右
		for (; i < cur->_n; ++i)
		{
			_InOrder(cur->_subs[i]); // 左子树
			cout << cur->_keys[i] << " "; // 根
		}
		_InOrder(cur->_subs[i]); // 最后的那个右子树
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

放出完整代码：

3.4 B树的完整代码（无删除）

#pragma once
#include <iostream>
using namespace std;

template<class K, size_t M>
class BTreeNode
{
public:
	K _keys[M]; // 为了方便插入以后再分裂，多给一个空间
	BTreeNode<K, M>* _subs[M + 1];
	BTreeNode<K, M>* _parent;
	size_t _n; // 记录实际存储多个关键字 

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

template<class K, size_t M> // 数据是存在磁盘，K是磁盘地址
class BTree
{
private:
	typedef BTreeNode<K, M> Node;
	Node* _root = nullptr;

public:
	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[i])
				{
					break;
				}
				else if (key > cur->_keys[i])
				{
					++i;
				}
				else
				{
					return make_pair(cur, i);
				}
			}
			parent = cur; // 往孩子去跳
			cur = cur->_subs[i];
		}
		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 // 跳出和end为-1的情况一起处理
			{
				break;
			}
		}
		node->_keys[end + 1] = key;
		node->_subs[end + 2] = child;
		if (child)
		{
			child->_parent = node;
		}
		node->_n++;
	}

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = key;
			_root->_n++;
			return true;
		}

		pair<Node*, int> ret = Find(key);
		if (ret.second >= 0) // key已经存在，不允许插入
		{
			return false;
		}

		Node* parent = ret.first; // 如果没有找到，find顺便带回了要插入的那个叶子节点
		K newKey = key;
		Node* child = nullptr;
		while (true) // 循环每次往cur插入 newkey和child
		{
			InsertKey(parent, newKey, child);
			if (parent->_n < M) // 满了就要分裂，没有满，插入就结束
			{
				return true;
			}
			else
			{
				size_t mid = M / 2;
				Node* brother = new Node; // 分裂一半[mid+1, M-1]给兄弟
				size_t j = 0;
				size_t i = mid + 1;
				for (; i <= M - 1; ++i)
				{
					brother->_keys[j] = parent->_keys[i];
					brother->_subs[j] = parent->_subs[i]; // 分裂拷贝key和key的左孩子
					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; // 跳出return true;
				}
				else // 转换成往parent->parent 去插入parent->[mid] 和 brother
				{
					newKey = midKey;

					child = brother;
					parent = parent->_parent;
				}
			}
		}
		return true;
	}

	void _InOrder(Node* cur)
	{
		if (cur == nullptr)
			return;

		size_t i = 0; // 左 根  左 根  ...  右
		for (; i < cur->_n; ++i)
		{
			_InOrder(cur->_subs[i]); // 左子树
			cout << cur->_keys[i] << " "; // 根
		}
		_InOrder(cur->_subs[i]); // 最后的那个右子树
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
};

void TestBtree()
{
	int arr[] = { 53, 139, 75, 49, 145, 36, 101 };
	BTree<int, 3> t;
	for (auto& e : arr)
	{
		t.Insert(e);
	}
	t.InOrder();
}

预期之内，通过监视窗口来观察一下：

对比一下，是没什么问题的。

3.5 B树的删除图解

学习B树的插入足够帮助我们理解B树的特性了，至于删除这里讲一讲思路，代码的话就不实现了，删除的代码也要比插入更加复杂，有兴趣的话可以参考《算法导论》的伪代码和《数据结构-殷人昆》的C++实现代码。下面画图讲一下B树的删除思想。

同样也需要分情况讨论：

删除的关键字在非终端结点处理方法是：用其直接前驱或直接后继替代其位置，转化为对“终端结点”的删除。

直接前驱：当前关键字左边指针所指子树中“最右下”的元素。
直接后继：当前关键字右边指针所指子树中“最左下”的元素比如：

现在要删除75，首先第一种方法可以用直接前驱55替代其位置，或者用直接后继101替代。所以对非终端结点关键字的删除操作，必然可以转化为对终端结点的删除。

所以下面重点来讨论终端结点的删除。

删除的关键字在终端结点且删除后结点关键字个数未低于下限：若删除后结点关键字个数未低于下限ceil(m/2)-1，直接删除，无需做任何其它处理。比如：

现在要删除36，所在的结点是终端结点，且删除之后，关键字的个数不少于ceil(3/2)-1=1，所以直接删除即可。

那如果删除之后关键字的个数低于下限ceil(m/2)-1呢？

若删除的关键字在终端结点且删除后结点关键字个数低于下限ceil(m/2)-1。这时候的处理思路是这样的：

删除之后关键字数量低于下限，那就去“借”结点，跟父亲借，父亲再去跟兄弟借。
如果不能借（即借完之后父亲或兄弟关键字个数也不满足了），那就按情况进行合并（可能要合并多次）。最终使得树重新满足B树的性质。比如：

现在要删40，那40删掉的话这个结点关键字个数就不满足性质了，那就去跟父亲借，49借下来，那这样父亲不满足了，父亲再向兄弟借（要删除的那个关键字所在结点的兄弟结点），53搞上去，变成这样：

此时就又是一棵B树了。那如果不能借的情况呢？比如：

现在要删除160，160如果跟父亲借的话，150下来，那父亲不满足了，因为3个孩子，必须是2个关键字。而且此时兄弟145所在的这个结点也不能借了。因为此时它只有一个关键字，父亲借走一个的话，就不满足了。

所以此时借结点就不行了，就需要合并了。如何合并呢？

如果结点不够借，则需要将父结点内的关键字与兄弟进行合并。合并后导致父节点关键字数量-1，可能需要继续合并。160删掉的话，父亲就少了一个孩子，那关键字也应该减少一个，所以可以把父结点的150与145这个孩子合并。

这样就可以了。当然还有些情况可能需要多次合并。比如下面删145的情况：

现在要删145，怎么办呢？肯定是不够借的，所以要合并，确保合并之后依然满足B树的规则就行了。 145删掉之后，左子树这里就不满足了，可以先将139跟102合并。

但是此时不平衡了（B-树是绝对平衡的）。那就要继续合并缩减高度：很容易看出来可以将101和53合并作为根，这个正好两个关键字，3个孩子

此时就完成了多次合并，B树的删除就暂时讲解到这里了。

4. B树的高度和性能

面试题：含n个关键字的m阶B树，最小高度、最大高度是多少？（注：大部分地方算B树的高度不包括叶子结点即查找失败结点）

4.1 B树的高度（大概）

首先来分析一下B树的最小高度：

n个关键字的m阶B树，关键字个数和B树的阶数已经确定的话，那要让高度最小，就要让每个结点存的关键字是最满的。

对于m阶的B树来说，每个结点最多m-1个关键字，m个孩子，第一层肯定只有一个根结点（最满的话是m-1个关键字，m个孩子），那第二层最多就有m个结点，每个结点最多m-1关键字，那第三层就是m*m个孩子，以此类推…

假设这个高度是h的话，关键字的总个数n就等于（关键字个数*结点个数）：

n=(m-1)*(1+m+m^2+m^3+…+m^h-1)

用错位相减法，解得最小高度h为以m为底n的对数。

类似地分析最高高度：那要让树变得尽可能高的话，那就要让每个结点得关键字数量尽可能少（分支尽可能少）。第一层只有一个根结点（关键字最少是1，孩子是2），根结点最少两个孩子/分支，所以第二层2个结点。又因为除了根结点之外的结点最少有ceil(m/2)个孩子，所以第三层就最少有 2 * ceil(m/2) ，，第四层就是 2 * ceil(m/2)^2，以此类推…第h就是2 * ceil(m/2)^h - 2个结点。那么解得最大高度h大概为log以ceil(m/2)为底n的对数

4.2 B树的性能和作用

设有效值个数 = N；度 = M ；

则：一个节点的有效值个数 = M/2 ~ M-1 ；

故：树的高度为 = log{M/2} N ~ log{M-1}N 。一个节点内查找的复杂度 = O(log{2}M/2 ) ~ O(log{2}M-1 ) ;

故：最终时间复杂度 = [ O(log{2}M/2 ) ~ O(log{2}M-1 ) ] * [ log{M/2} N ~ log{M-1}N ]

但实际应用情况不是这样，实际时间主要消耗在，从上级节点访问下级节点的过程中，因为访问节点其实是访问外存；

（关键理解点）B树查找过程中，IO操作即为进入节点的操作，当查找过程中需要访问到磁盘上的节点时，就需要进行IO操作将节点从磁盘读取到内存中。

所以主要的时间消耗为：[ log{M/2} N ~ log{M-1}N ] 次访问外存的次数。

对于N = 62*1000000000个节点，如果度M为1024，则log二分之M为底N的对数 <=4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。

贴个B树的作用：（下一篇会讲解B树系列在MySQL数据库的应用）

数据库索引：B树常被用作数据库的索引结构，能够高效地支持数据的查找和范围查询。
文件系统：B树被用于文件系统中的目录结构，可以高效地支持文件的查找和管理。
缓存系统：B树可以用于缓存系统中的索引结构，加速数据的访问和查询。
路由表：B树可以用于路由表的存储和查找，快速定位目标地址。

本篇完。

下一篇讲解在B树的基础上进行优化的B+树，和在B+树的基础上优化的B*树和B树系列在MySQL数据库的应用。

其它高阶数据结构⑤_B树（概念+实现OJ）

1. B树的提出

2. B树的概念