[C++数据结构](34)B树

B 树概念与性质

1970 年，R.Bayer 和 E.mccreight 提出了一种适用于外查找的树，它是一种平衡的多叉树，称为 B 树（或 B-树、B_树）。

一棵 $m$ 阶 $(m>2)$ 的 B 树，是一棵 $m$ 路平衡搜索树（ $m$ 表示这个树的每一个结点最多可以拥有的子结点个数），可以是空树或满足以下性质：

1. 根结点至少有两个孩子
2. 每个分支结点都包含 $k-1$ 个关键字和 $k$ 个孩子（孩子的个数永远比关键字多一个），其中 ⌈ m 2 ⌉ ≤ k ≤ m \lceil\frac{m}{2}\rceil\le k\le m ⌈2m⌉≤k≤m
3. 每个叶子结点都包含 $k-1$ 个关键字，其中 ⌈ m 2 ⌉ ≤ k ≤ m \lceil\frac{m}{2}\rceil\le k\le m ⌈2m⌉≤k≤m
4. 所有叶子结点都在同一层
5. 每个结点中的关键字从小到大排列，结点中 $k-1$ 个元素正好是 $k$ 个孩子包含的元素的值域划分
6. 每个结点的结构为： ( n , A 0 , K 1 , A 1 , K 2 , A 2 , … , K n , A n ) (n,A_0,K_1,A_1,K_2,A_2,\dots,K_n,A_n) (n,A0,K1,A1,K2,A2,…,Kn,An) 其中， K i ( 1 ≤ i ≤ n ) K_i(1\le i\le n) Ki(1≤i≤n) 为关键字，且 K i < K i 1 ( 1 ≤ i ≤ n − 1 ) K_i<K_{i 1}(1\le i\le n-1) Ki<Ki 1(1≤i≤n−1)。 A i ( 0 ≤ i ≤ n ) A_i(0\le i\le n) Ai(0≤i≤n) 为指向子树根结点的指针。且 A i A_i Ai 所指子树所有结点中的关键字均小于 K i 1 K_i 1 Ki 1。$n$ 为结点中关键字个数，满足 ⌈ m 2 ⌉ − 1 ≤ n ≤ m − 1 \lceil\frac{m}{2}\rceil-1\le n\le m-1 ⌈2m⌉−1≤n≤m−1

示例：一个 3 阶 B 树

B 树基本操作与实现

框架

结点的结构，包含key数组和subs孩子结点指针数组，这两个数组都要多开一个空间，方便后面先插入再分裂的实现。此外，还需要一个父指针，后面实现插入的时候也用得到。

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()
	{
		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>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:

private:
	Node* _root = nullptr;
};

查找

按照搜索树的查找规则进行查找即可，与我们之前写的搜索树不同的是，B 树的每个结点可能有多个 key，所以对每个结点内的 key 都要逐个比较。

	// 查找，返回关键字所在结点指针及下标
	// 未找到，则返回该关键字应该插入在哪个叶子结点，返回下标为-1
	pair<Node*, int> Find(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		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 { cur, i };
			}
			parent = cur;
			cur = cur->_subs[i];
		}
		return { parent, -1 };
	}

插入

针对一棵高度为 $h$ 的 $m$ 阶 B 树，插入一个元素时，首先要验证该元素在 B 树中是否已经存在，如果不存在，那么就要在叶子结点中插入该新元素。步骤如下：（注：一个结点最多允许拥有 $m-1$ 个关键字，但我们往往会多开一个空间，允许拥有 $m$ 个关键字，并将有 $m$ 个关键字称为”满了“）。

1. 按照搜索树规则将元素插入到叶子结点
2. 如果叶子结点空间满了，即该结点的关键字个数有 $m$ 个，则需要将该结点进行分裂，将一半数量的关键字分裂到新的与其相邻的右兄弟结点中，中间关键字上移到父结点。
   1. 从该结点中选出中位数
   2. 小于这一中位数的元素留在左结点，大于这一中位数的放入右结点，中位数作为分隔值
   3. 分隔值被插入到父结点中，这可能导致父结点满了，进行分裂，分裂步骤同上。父结点分裂又可能导致它的父结点分裂，以此类推，直到父结点无须分裂为止。如果没有父结点（即遇到根结点），就创建一个新的根结点（增加一层）。

示意图：

以 3 阶 B 树为例 $(m=3)$

向一个结点里插入 key 和 孩子：

运用插入排序的思想，把 key 和其对应的右孩子同时往后挪，找到合适的位置把 新key 和 新孩子 插入。不要忘记把新孩子的父指针指向 node 父亲。

	void InsertKey(Node* node, const K& key, Node* child)
	{
		int end = node->_n - 1;
		while (end >= 0)
		{
			if (key < node->_keys[end])
			{
				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)
	{
        // 插入第一个结点
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = key;
			  _root->_n;
			return true;
		}

		// 查找
		pair<Node*, int> ret = Find(key);
		// 已存在
		if (ret.second >= 0)
			return false;

		// 不存在，插入新元素
		Node* parent = ret.first;
		K newKey = key;
		Node* child = nullptr;

		while (1)
		{
			InsertKey(parent, newKey, child);
			if (parent->_n < M) // 无须分裂
				return true;
			// 分裂
			size_t mid = M / 2;
			// 分出兄弟
			Node* brother = new Node;
			size_t j = 0;
			for (size_t i = mid   1; i < M;   i)
			{
				brother->_keys[j] = parent->_keys[i];
				brother->_subs[j  ] = parent->_subs[i];
				if (parent->_subs[i])
					parent->_subs[i]->_parent = brother;
			}
			brother->_subs[j] = parent->_subs[M];
			if (parent->_subs[M])
				parent->_subs[M]->_parent = brother;
			brother->_n = j;
			parent->_n -= j   1;
			brother->_parent = parent->_parent;

			// 把中位数分给根
			if (parent->_parent == nullptr) // 没有根，则创建一个新的根，结束
			{
				_root = new Node;
				_root->_keys[0] = parent->_keys[mid];
				_root->_subs[0] = parent;
				_root->_subs[1] = brother;
				_root->_n = 1;
				parent->_parent = _root;
				brother->_parent = _root;
				break;
			}
			// 有根，转换，准备循环
			newKey = parent->_keys[mid];
			child = brother;
			parent = parent->_parent;
		}
		return true;
	}

尤其要注意分裂分给兄弟的部分，不仅要将 key 和 孩子指针 分出去，还有注意分出去的孩子的父指针也应该改变。最后也不要忘了将兄弟结点的父指针指向对应的父结点。

遍历

	void _InOrder(Node* cur)
	{
		if (cur == nullptr)
			return;
		for (size_t i = 0; i < cur->_n;   i)
		{
			_InOrder(cur->_subs[i]);
			cout << cur->_keys[i] << " ";
		}
		_InOrder(cur->_subs[cur->_n]);
	}

	void InOrder()
	{
		_InOrder(_root);
	}

B 树性能分析及其优势

B 树的优势就在于一个结点可以存储多个数据，相比二叉搜索树而言，B 树可以将树的高度进一步压缩。并且能够将逻辑上相连的数据存储在一起。

考虑在磁盘中存储数据的情况，与内存相比，读写磁盘有以下不同点：

1. 读写磁盘的速度相比内存读写慢很多。
2. 每次读写磁盘的单位要比读写内存的最小单位大很多。

由于读写磁盘的这个特点，因此对应的数据结构应该尽量的满足 “局部性原理”：“当一个数据被用到时，其附近的数据也通常会马上被使用”，为了满足局部性原理， 所以应该将逻辑上相邻的数据在物理上也尽量存储在一起。这样才能减少读写磁盘的数量。

所以，对比起一个节点只能存储一个数据的 BST 类数据结构来，要求这种数据结构在形状上更 “胖”、更加 “扁平”，即：每个节点能容纳更多的数据， 这样就能降低树的高度，同时让逻辑上相邻的数据都能尽量存储在物理上也相邻的硬盘空间上，减少磁盘读写。

---

B 树上大部分基本操作所需访问盘的次数均取决于树高 $h$.

下面就最坏情况进行分析，

对任意一棵具有 $n$ 个关键字的 $m$ 阶 B 树 $(n\ge 1,m\ge 3)$，设最小度数 $t\ge 2$，其根结点包含至少一个关键字，其他结点包含至少 $t-1$ 个关键字。

这样，在深度为 1 有 $1$ 个根结点，在深度为 2 至少有 $2$ 个结点，在深度 3 至少有 $2t$ 个结点，在深度 4 至少有 2 t 2 2t^2 2t2 个结点，在深度 h 至少有 2 t h − 2 2t^{h-2} 2th−2 个结点。

由此，关键字的个数 $n$ 满足在不等式：
n ≥ 1 ( t − 1 ) ∑ i = 0 h − 2 2 t i = 1 2 ( t − 1 ) 1 − t h − 1 1 − t = 2 t h − 1 − 1 n\ge1 (t-1)\sum_{i=0}^{h-2}2t^{i}=1 2(t-1)\frac{1-t^{h-1}}{1-t}=2t^{h-1}-1 n≥1 (t−1)i=0∑h−22ti=1 2(t−1)1−t1−th−1=2th−1−1
则
h ≤ log ⁡ t n 1 2 1 h\le\log_t\frac{n 1}{2} 1 h≤logt2n 1 1
⌈ m 2 ⌉ ≤ t ≤ m \lceil\frac m2\rceil\le t\le m ⌈2m⌉≤t≤m，所以 B 树的高度可以记为 O ( log ⁡ m n ) O(\log_mn) O(logmn)，于是在 B 树上查找、插入和删除的读写盘的时间复杂度为 O ( log ⁡ m n ) O(\log_mn) O(logmn)

所以 B 树的阶数 m 我们往往设计得很大，以降低基本操作的时间复杂度。

这篇好文章是转载于：学新通技术网