【C++】B树及其实现

一、B树的基本概念

1.引入

我们已经学习过二叉排序树、AVL树和红黑树三种树形查找结构，但上述结构适用于数据量相对不是很大，能够一次性放进内存中，进行数据查找的场景。如果数据量非常大，比如由100G数据，无法一次放进内存中，那就只能放在磁盘上了。此时想要搜索数据就需要将存放关键字及其映射的数据的地址放到内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。
但是由于磁盘访问的速度很慢，对于上述树形查找结构来说就是需要logN次的IO，这是一个很难接受的结果。
那么如何加速对数据的访问呢？

1. 提高IO的速度（SSD相比传统机械硬盘是快了不少，但还是没有得到本质性的提升）
2. 降低树的高度——多路平衡查找树

2.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树的实现

1.B树的定义

为了方便学习，我们在这里先将m设为3，这时每个结点能存2个关键字和3个孩子。不过为了方便后续插入，分别额外多开了一个空间。

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;}
};

2.B树的查找

查找的具体步骤应该是先进入根结点，如果等于data1，则返回，如果小于data1，则进入child1，如果大于data1则++i，此时i指向data2，若小于data2，则进入child2，若大于data2，则进入child3。

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{++i;}else{return make_pair(cur, i);	// 找到了就返回当前结点以及该关键字所在的位置}}parent = cur;cur = cur->_subs[i];}return make_pair(parent, -1);	//找不到返回父结点
}

3.B树的插入操作

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

插入过程总结：

1. 如果树为空，直接插入新节点中，该节点为树的根节点
2. 树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
3. 检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)
4. 按照插入排序的思想将该元素插入到找到的节点中
5. 检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足
6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：
   • 申请新节点
   • 找到该节点的中间位置
   • 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
   • 将中间位置元素以及新节点往该节点的双亲节点中插入，即继续4
7. 如果向上已经分裂到根节点的位置，插入结束

// 插入操作中用到的函数
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;
}
// B树的插入
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)					// 如果没有破坏B树的性质则返回true{return true;}else								// 否则进行分裂操作{size_t mid = M / 2;Node* brother = new Node;size_t i = mid + 1;size_t j = 0;for (; i < M; ++i)				// 把一半的数据分给新建的兄弟结点{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	// 有父结点则将插入排序的参数修改，然后回到循环开始插入{newKey = midKey;child = brother;parent = parent->_parent;}}}return true;
}

B树插入的代码实现非常复杂，需要十分细心，要注意对结点的维护。

4.B树的删除

B树的删除分为3种情况：

1. 直接删除关键字：若删除当前关键字后仍然满足B树定义，则直接删除该关键字。
2. 兄弟够借：若再删除一个关键字就会破坏B树定义，并且左，右兄弟的关键字个数大于等于ceil(m/2)，则需要调整该结点、右（或左）兄弟结点及其父结点（父子换位法），以达到新的平衡。
3. 兄弟不够借：若左、右兄弟结点的关键字个数都不足以被借，则将关键字删除后与左（或右）兄弟结点及父结点的关键字进行合并。

由于B树的删除用代码实现非常复杂，就不多讲了。

5.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);
}

6.B树的高度

B树的效率取决于B树的高度，因为磁盘存取次数与高度成正比。
若n>=1，则对任意一颗包含n个关键字、高度为h、阶数为m的B树：

1. 若让每个结点中的关键字个数达到最多，则容纳同样多关键字的B树的高度达到最小。因为B树种每个结点最多有m棵子树，m-1个关键字，所以在一颗高度为h的m阶B树中关键字的个数应满足$n<=(m-1)(1+m+m^2+...+m^{h-1})=m^h-1$，因此有$$h>=lo{g}_m(n+1)$$
2. 若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树高度达到最大。第一层至少有1个结点；第二层至少有两个结点；除根结点外的每个非叶结点至少有ceil(m/2)棵子树，则第三层至少有2ceil(m/2)个结点……第h+1层至少有$2(ceil(m/2){)}^{h-1}$个结点，注意到第h+1层是不包含任何信息的叶结点。对于关键字个数为n的B树，叶结点即查找不成功的结点为n+1，由此有$n+1>=2(ceil(m/2){)}^{h-1}$，即$h<=lo{g}_{ceil(m/2)}((n+1)/2)+1$。

7.整体代码

#include <iostream>
using namespace std;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: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{++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]){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)					// 如果没有破坏B树的性质则返回true{return true;}else								// 否则进行分裂操作{size_t mid = M / 2;Node* brother = new Node;size_t i = mid + 1;size_t j = 0;for (; i < M; ++i)				// 把一半的数据分给新建的兄弟结点{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	// 有父结点则将插入排序的参数修改，然后回到循环开始插入{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);}
private:Node* _root = nullptr;
};void TestBtree()
{int a[] = { 53, 139, 75, 49, 145, 36, 101 };BTree<int, 3> t;for (auto e : a){t.Insert(e);}t.InOrder();
}

三、B+树和B*树

1.B+树

B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

1. 分支节点的子树指针与关键字个数相同
2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
3. 所有叶子节点增加一个链接指针链接在一起
4. 所有关键字及其映射数据都在叶子节点出现

B+树的特性：

1. 所有关键字都出现在叶子结点的链表中，且链表中的结点都是有序的。
2. 不可能在分支结点中命中。
3. 分支结点相当于是叶子结点的索引，叶子结点才是存储数据的数据层。

B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增
加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向
兄弟的指针。

2.B*树

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结
点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如
果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父
结点增加新结点的指针。
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

3.总结

通过以上介绍，大致将B树，B+树，B*树总结如下：

1. B树：有序数组+平衡多叉树；
2. B+树：有序数组链表+平衡多叉树；
3. B*树：一棵更丰满的，空间利用率更高的B+树。