数据结构：图解手撕B-树以及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] 和 brothernewKey = midKey;child = brother;parent = parent->_parent;}}}return true;}
private:Node* _root = nullptr;
};

B+树和B*树

B+树

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

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

B+树的特性：

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

B*树

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

分裂原理

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

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

所以，B*树分配新结点的概率比B+树要低，空间使用率更高

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

B树的应用

B树的最常见应用就是当做索引

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

mysql是目前非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥
有灵活的插件式存储引擎