1.B树的介绍
1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(有些地方写
的是B-树，注意不要误读成"B减树")。一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：
- 根节点至少有两个孩子
- 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子
- 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字，并且以升序排列
- key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
- 所有的叶子节点都在同一层
我们之前学习了一些基础的搜索结构,如下表所示：
种类 数据格式时间复杂度 顺序查找无要求O（N） 二分查找有序O（log N) 二叉搜索树无要求O（N) 平衡搜索树无要求O(logN) 哈西无要求O(1) 位图无要求O(1)布隆过滤器无要求O(k)
既然有了这些搜索的数据结构为什么还有引入B树这种数据结构呢？我们之前学过的平衡搜索二叉树已经足够优秀了，时间复杂度O（log N）已经非常的优秀了，10亿数据只要查找30次左右。这是因为：如果数据量非常大，一次性无法加载到内存中，使用上述结构就
不是很方便。比如：使用平衡树搜索一个大文件：
而IO的速度是很慢的。
解决方案：
- 提高IO的速度
- 降低树的高度---多叉树平衡树
下面我们来看例子：
如果我们使用二叉搜索树作为索引结构，假设树的高度为4，查找10流程如下
二叉搜索树的结构：
** 第一次磁盘IO**：
第二次磁盘IO：
**第三次IO： **
第四次IO：
我们可以发现磁盘的IO次数是由二叉搜索树的高度决定。所以才引入了B树
下面我们以三阶的B树为例：
这棵树中，咱们重点来看(2,6)节点。该节点有两个元素2和6，又有三个孩子1,(3,5)，8。其中1小于元素2，(3，5）在元素2,6之间，8大于(3,5)，正好符合刚刚所列的几条特征。
下面来看一下B树的查询过程：假设我们要找的是5
**第一次IO： **
在内存中和9进行比较：
第2次磁盘IO：
** 在内存中和2，6比较：**
第3次磁盘IO：
在内存中和3，5进行比较：
通过整个流程我们可以看出，B-树在查询中的比较次数其实不比二叉查找树少，尤其当单一节点中的元素数量很多时。可是相比磁盘I0的速度，内存中的比较耗时几乎可以忽略。所以只要树的高度足够低，IO次数足够少，就可以提升查找性能。相比之下节点内部元素多一些也没有关系，仅仅是多了几次内存交互，只要不超过磁盘页的大小即可。这就是B-树的优势之一
2.B树节点的定义及其实现
2.1B树节点的定义：
template<class K,class V,size_t M> struct BTreeNode { BTreeNode() :_kvSize(0) , _parent(nullptr) { for (size_t i = 0; i < M+1; i++) {//初始化 _subs[i] = nullptr; } } pair<K, V>_kvs[M];//值 BTreeNode<K, V,M>* _subs[M+1];//孩子的数量注意我们在这里面多看了一个空间方便后面的分裂 BTreeNode<K, V,M>* _parent;//父亲指针 size_t _kvSize;//个数 };注意在这里我们多看了一个空间，方便后序插入节点时的分裂。
2.2B树的查找
在上面已经介绍过B树的查找在这里就只给出代码：
pair<Node*, int> Find(const K& key) { Node* parent = nullptr;//记录父亲节点 Node* cur = _root;//从根开始找 while (cur) { size_t i = 0; while (i < cur->_kvSize) // 如果M比较大，这里应该改一改换成二分查找会快一些 { if (cur->_kvs[i].first < key) // key大于当前位置key，往右找 ++i; else if (cur->_kvs[i].first > key) // key小于当前位置key，就往左孩子去找 break; else return make_pair(cur, i);//找到了并返回对应的位置 } parent = cur;//记录父亲节点 cur = cur->_subs[i]; } // 没有找到并将父亲节点返回 return make_pair(parent, -1); }
2.2B树的插入
比如我们要在这颗B树上插入4：
自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。
节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。
拆分时要将孩子节点也要带走：
对应代码：
bool Insert(const pair<K, V>& kv) { if (_root == nullptr)//空树直接创建新节点 { _root = new Node; _root->_kvs[0] = kv; _root->_kvSize = 1; return true; } pair<Node*, int> ret = Find(kv.first);//先进行查找 // 已经有了，不能插入 (当前如果允许插入就是mutil版本) if (ret.second >= 0) { return false; } // 往cur节点中插入一个newkv和sub // 1、如果cur没满就结束 // 2、如果满了就分裂，分裂出兄弟以后，往父亲插入一个关键字和孩子，再满还要继续分裂 // 3、最坏的情况就是分裂到根，原来根分裂，产生出一个新的根，就结束了 // 也就是说，我们最多分裂高度次 Node* cur = ret.first;//当前节点 pair<K, V> newkv = kv; Node* sub = nullptr;//实现后面的迭代逻辑 while (1) { InsertKV(cur, newkv, sub); //插入 // 1、如果cur没满就结束，判断是否要分裂 if (cur->_kvSize < M) { return true; } else // 2、满了，需要分裂 { // 分裂出一个兄弟节点 Node* newnode = new Node; // 1、拷贝右半区间给分裂的兄弟节点 // int mid = M / 2; int j = 0; int i = mid + 1; newkv = cur->_kvs[mid]; cur->_kvs[mid] = pair<K, V>();//清空原来的节点的值 for (; i < M; ++i)//拷贝值并拷贝孩子节点 { newnode->_kvs[j] = cur->_kvs[i]; cur->_kvs[i] = pair<K, V>(); newnode->_subs[j] = cur->_subs[i]; cur->_subs[i] = nullptr; if (newnode->_subs[j])//链接父亲指针 { newnode->_subs[j]->_parent = newnode; } j++; newnode->_kvSize++;//个数增加 } // 还剩最后一个右孩子 newnode->_subs[j] = cur->_subs[i]; cur->_subs[i] = nullptr; if (newnode->_subs[j])//是否为空 { newnode->_subs[j]->_parent = newnode; } cur->_kvSize = cur->_kvSize - newnode->_kvSize - 1;//重新计算大小 // 1、如果cur没有父亲，那么cur就是根，产生新的根 // 2、如果cur有父亲，那么就要转换成往cur的父亲中插入一个key和一个孩子newnode if (cur->_parent == nullptr)//说明当前节点没有父亲是根 { //创建新的根，并链接关系 _root = new Node; _root->_kvs[0] = newkv; _root->_subs[0] = cur; _root->_subs[1] = newnode; cur->_parent = _root; newnode->_parent = _root; _root->_kvSize = 1; return true; } else {//有父亲转化为迭代逻辑 // 往父亲去插入newkv和newnode，转换成迭代逻辑 sub = newnode; cur = cur->_parent; } } } return true; } void InsertKV(Node* cur, const pair<K, V>& kv, Node* sub) { // 将kv找到合适的位置插入进去 int i = cur->_kvSize - 1;//从最后一个位置开始 for (; i >= 0; ) { if (cur->_kvs[i].first < kv.first) { break; } else { //kv[i]往后挪动，kv[i]的右孩子也挪动 cur->_kvs[i + 1] = cur->_kvs[i]; cur->_subs[i + 2] = cur->_subs[i + 1]; --i; } } //插入并将孩子节点也链接上 cur->_kvs[i + 1] = kv; cur->_subs[i + 2] = sub; cur->_kvSize++; if (sub) { sub->_parent = cur;//链接父亲节点 } }
2.3B树的删除
删除比插入复杂的多在这里就只给出思路：
Ｂ树中关键字的删除比插入更复杂，在这里，只介绍其中的一种方法：
在B树上删除关键字k的过程分两步完成：
（1）找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。
（2）若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针_son[i]所指的子树中
找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。
在B-树叶结点上删除一个关键字的方法：
首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况：（1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)，说明删去该关键字后该结点仍满足B树的定义。
这种情况最为简单，只需从该结点中直接删去关键字即可。（2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B树的定义，需要调整。
调整过程为：
如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于
ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上
移关键字的关键字下移至被删关键字所在结点中。
如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于
ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者
的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起，
合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲
结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使
整个树减少一层。总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。
下面举个简单的例子删除11这个节点：
首先找到11这个节点：
删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）
3.B+树和B*树
B+树是B-树的变形，也是一种多路搜索树，其规则如下：
- 其定义基本与B-树相同，除了：
- 非叶子节点的子树指针与关键字个数相同
- 非叶子节点的子树指针p[i]，指向关键字值属于【k[i]，k[i+1])的子树
- 为所有叶子节点增加一个链指针
- 所有关键字都在叶子节点出现
既然有了B树那为什么还要有B+树了？下面我们从各自的优点出发：
B树：
B树好处：
B树的每一个结点都包含key(索引值) 和 value(对应数据)，因此方位离根结点近的元素会更快速。（相对于B+树）
B树的不足：
不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找。
B+树的优点：
1.B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2.B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3.B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4.B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
这就是为什么要有B+树的原因。
B*树：
B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
1.B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3(代替B+树的1/2） 。
2.B+树的分裂:当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针﹔B+树的分裂只影响原结点和父结点，而不会影响兄弟结点,所以它不需要指向兄弟的指针。
3.B树的分裂:当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了〉﹔如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针;
4.所以，B树分配新结点的概率比B+树要低，空间使用率更高﹔
4.总结
B-树:多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点;
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中﹔
B+树:在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中﹔
B*树:在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率
版权归原作者 一个山里的少年 所有， 如有侵权，请联系我们删除。