【数据结构】B树的介绍及其实现C++

B树的介绍及其实现

一、B树的基本概念

为什么要引入B树

在学习过的数据结构中，如：AVL树、红黑树和哈希表等都具有很好的查找效率，但是只能适用于数据量不大的情况下。如果数据量很大时，这些数据不能够一次性的存入内存中，那么在进行查找的时候，就需要多次的访问IO，这样的速度是非常的慢的，此时就引入了BTree这个结构。我们只需要将关键字和其映射的数据的地址放到内存中的BTree中，就可以很快的定位到数据的地址，然后去磁盘中查找了。

1.1 B树的概念

B树是一种适合外查找的树，它是一种平衡的多叉树，称为B树 。B树的特点：

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

2.1 B树的定义

根据B树的特点，需要定义存放key值的数组、指向孩子节点的指针数组、父节点指针、key个数：

其中M使用的是非类型模板参数，只能为整数。

template<class T, size_t M>
struct BTreeNode {typedef BTreeNode<T, M> node; T _keys[M];				//存放数值node* _subs[M + 1];		//存放孩子节点node* _parent;			//父节点size_t _n;				//key的个数BTreeNode() {for (int i = 0; i < M; ++i) {_keys[i] = T();_subs[i] = nullptr;}_subs[M] = nullptr;_parent = nullptr;_n = 0;}
};

2.2 B树的查找

1. 如果key小于当前遍历到的节点的值，就访问它的左孩子节点
2. 如果key大于当前遍历到的节点的值，就在当前节点往后遍历_keys数组
3. 如果相等，那么返回该节点的地址和其所在_keys数组中的下标

pair<Node*, int> Find(const T& 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);}

2.3 B树的插入

使用{53, 139, 75, 49, 145，36}构建B树的过程如下所示：

1. 刚开始插入53和139：

2. 插入75：

3. 插入36：
   

通过上述的观察可得出：

1. 如果树为空，创建一个新节点作为根节点，然后直接插入
2. 如果树不为空，找到要插入的位置，然后插入
3. 插入后检查节点是否满足B树的性质，满足就不需要处理
4. 如果不满足，将需要对该节点进行分裂：
   • 申请新节点
   • 找到该节点的中间位置
   • 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
   • 判断父节点是否为空，如果为空就创建一个新节点作为父节点，然后将中间位置的元素插入到父节点中，如果父节点不为空，那么就直接插入到父节点中。最后将他们相连

//插入排序插入数据
void InsertKey(Node* cur, const T& key, Node* child) {//使用插入排序的方式，将元素向后移动int end = cur->_n - 1;while (end >= 0) {if (key < cur->_keys[end]) {cur->_keys[end + 1] = cur->_keys[end];cur->_subs[end + 2] = cur->_subs[end + 1];--end;}else {break;}}//当key >= cur->_keys[end]时，将key插入cur->_keys[end + 1] = key;cur->_subs[end + 2] = child;if (child) {child->_parent = cur;}++cur->_n;
}bool insert(const T& key) {//如果root为空，创建一个节点，直接插入if (!_root) {_root = new Node();_root->_keys[0] = key;++_root->_n;return true;}//判断树中是否存在该key，存在就不插入了pair<Node*, int> ff = Find(key);if (ff.second >= 0)return false;//不存在就进行插入操作Node* cur = ff.first;T newkey = key;Node* child = nullptr;while (true) {InsertKey(cur, newkey, child);//插入后对节点进行检查if (cur->_n < M) {return true;}else {//进行分裂操作size_t mid = cur->_n / 2;Node* brother = new Node();size_t i = mid + 1;size_t j = 0;//将cur中的1/2移动到他的兄弟节点while (i < cur->_n) {brother->_keys[j] = cur->_keys[i];brother->_subs[j] = cur->_subs[i];if (cur->_subs[i]) {cur->_subs[i]->_parent = brother;}cur->_keys[i] = T();cur->_subs[i] = nullptr;++i, ++j;}brother->_subs[j] = cur->_subs[i];if (cur->_subs[i]) {cur->_subs[i]->_parent = brother;}cur->_subs[i] = nullptr;brother->_n = j;//因为移走了n个到brother中，还有一个要移到父节点中，所以多-1cur->_n -= brother->_n + 1; T midkey = cur->_keys[mid];cur->_keys[mid] = T();//如果cur没有父节点，那么就创建if (!cur->_parent) {_root = new Node();cur->_parent = _root;brother->_parent = _root;_root->_keys[0] = midkey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_n = 1;break;}else {//有父节点，将插入排序插入的参数修改，使用上述的逻辑进行插入newkey = midkey;child = brother;cur = cur->_parent;}}}
}

2.4 B树的删除

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

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

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

2.5 B树的前序遍历

使用循环遍历节点孩子数组，先访问左孩子，再访问右孩子。

//前序遍历子函数
void _InOrder(Node* cur) {if (!cur)return;size_t i = 0;while (i < cur->_n) {_InOrder(cur->_subs[i]);cout << cur->_keys[i] << " ";++i;}_InOrder(cur->_subs[i]);//遍历每个节点中的最后一个孩子
}//前序遍历
void InOrder() {_InOrder(_root);
}

三、测试创建的B树是否正确

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树的性能分析

1. 对于一棵节点为N度为M的B-树，查找和插入需要log{M-1}N~log{M/2}N次比较，这个很好证明：对于度为M的B-树，每一个节点的子节点个数为M/2 ~(M-1)之间，因此树的高度应该在要 log{M-1}N 和 log{M/2}N之间，在定位到该节点后，再采用二分查找的方式可以很快的定位 到该元素。
2. B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则log_{M/2}N <= 4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用 二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。

五、全部代码

#include<iostream>
using namespace std;template<class T, size_t M>
struct BTreeNode {typedef BTreeNode<T, M> node; T _keys[M];				//存放数值node* _subs[M + 1];		//存放孩子节点node* _parent;			//父节点size_t _n;				//key的个数BTreeNode() {for (int i = 0; i < M; ++i) {_keys[i] = T();_subs[i] = nullptr;}_subs[M] = nullptr;_parent = nullptr;_n = 0;}
};template<class T, size_t M>
class BTree {typedef BTreeNode<T, M> Node;
public:BTree():_root(nullptr){}pair<Node*, int> Find(const T& 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);}bool insert(const T& key) {//如果root为空，创建一个节点，直接插入if (!_root) {_root = new Node();_root->_keys[0] = key;++_root->_n;return true;}//判断树中是否存在该key，存在就不插入了pair<Node*, int> ff = Find(key);if (ff.second >= 0)return false;//不存在就进行插入操作Node* cur = ff.first;T newkey = key;Node* child = nullptr;while (true) {InsertKey(cur, newkey, child);if (cur->_n < M) {return true;}else {//进行分裂操作size_t mid = cur->_n / 2;Node* brother = new Node();size_t i = mid + 1;size_t j = 0;//将cur中的1/2移动到他的兄弟节点while (i < cur->_n) {brother->_keys[j] = cur->_keys[i];brother->_subs[j] = cur->_subs[i];if (cur->_subs[i]) {cur->_subs[i]->_parent = brother;}cur->_keys[i] = T();cur->_subs[i] = nullptr;++i, ++j;}brother->_subs[j] = cur->_subs[i];if (cur->_subs[i]) {cur->_subs[i]->_parent = brother;}cur->_subs[i] = nullptr;brother->_n = j;//因为移走了n个到brother中，还有一个要移到父节点中，所以多-1cur->_n -= brother->_n + 1; T midkey = cur->_keys[mid];cur->_keys[mid] = T();//如果cur没有父节点，那么就创建if (!cur->_parent) {_root = new Node();cur->_parent = _root;brother->_parent = _root;_root->_keys[0] = midkey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_n = 1;break;}else {//有父节点，将插入排序插入的参数修改，使用上述的逻辑进行插入newkey = midkey;child = brother;cur = cur->_parent;}}}}//前序遍历void InOrder() {_InOrder(_root);}
private://插入排序插入数据void InsertKey(Node* cur, const T& key, Node* child) {//使用插入排序的方式，将元素向后移动int end = cur->_n - 1;while (end >= 0) {if (key < cur->_keys[end]) {cur->_keys[end + 1] = cur->_keys[end];cur->_subs[end + 2] = cur->_subs[end + 1];--end;}else {break;}}//当key >= cur->_keys[end]时，将key插入cur->_keys[end + 1] = key;cur->_subs[end + 2] = child;if (child) {child->_parent = cur;}++cur->_n;}//前序遍历void _InOrder(Node* cur) {if (!cur)return;size_t i = 0;while (i < cur->_n) {_InOrder(cur->_subs[i]);cout << cur->_keys[i] << " ";++i;}_InOrder(cur->_subs[i]);//遍历每个节点中的最后一个孩子}Node* _root;
};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*树

6.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+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向 兄弟的指针。

6.2 B*树

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

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

总结

• B树：有序数组+平衡多叉树；

• B+树：有序数组链表+平衡多叉树；

• B*树：一棵更丰满的，空间利用率更高的B+树。

七、B树的应用

B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，比如： 书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价 值的分类网站，本质上就是互联网页面中的索引结构。

MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说： 索引就是数据结构。

当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数 据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数 据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法， 该数据结构就是索引。