DS高阶：B树系列

一、常见的搜索结构

1、顺序查找     时间复杂度：O(N)

2、二分查找     时间复杂度：O(logN)

        要求：（1）有序 （2）支持下标的随机访问

3、二叉搜索树（BS树）       时间复杂度：O(logN)——>O(N)

        若接近有序的数据插入到BS中，会导致退化成单支树，时间复杂度退化为O(N)

4、平衡搜索树 （AVL树和RB树）   时间复杂度：O(logN)

       在BS的基础上，通过一些规则加以限制，通过旋转来限制高度,维持logN的时间复杂度

5、哈希    时间复杂度：O(1)

        底层是散列表，要注意解决哈希冲突。综合效率优于平衡搜索树

        以上结构适合用于数据量相对不是很大，能够一次性存放在内存中（内查找），进行数据查找的场景。如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。（B树系列   解决外查找的问题）

         根据上面的分析，我们知道B树系列是为了解决外查找的问题而生的，但是你可能会有这样的疑惑：虽然高度下降了，但是由于我的一个节点存储这多个关键字信息，那么我即使找到这个节点，不也是要遍历关键字信息，效率真的能提高么？？

        答：在磁盘中的搜索来说，定位的效率低，但是如果准确定位到了（节点），后面效率就会很高（顺序遍历节点中的关键字），这个跟磁盘的底层结构有关，具体可以参照下面的文献去理解。

二、B树的概念

      1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树(后面有一个B的改进版本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_n){if (key _keys[i]) break; //keys[i]的左孩子根他的下标是相等的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);}

1、返回值pair 前一个返回对应的节点，后一个表示对应节点中的下标。

2、parent指针的意义：因为我们在插入之前必须要调用这个查找函数，并且必须插入到相应的叶子节点中去。那么我们可以顺便通过这个返回值返回我们要插入的叶子节点。这样在insert函数中接受find函数的返回值的时就可以直接拿到待插入的叶子节点。

3、因为拓展都是往右拓展的，所以我们必须要确保比key当前元素小，我们才能跳到下一层去找他的左孩子，并且每次都要从第一个位置开始找，如果比当前元素大的话，那么先往后找，而不是直接往该节点的右孩子找！！

4.3 插入key的过程

         我们多开一块空间的目的先进行无脑插入，然后再去检查该节点是否满了，如果满了再进行分裂调整，但是我们有些时候可能不光要插入key，还要插入新增的节点。

//每次循环往cur插入newkey和childvoid InsertKey(Node* node, const K& key, Node* child){int end = node->_n - 1;while (end >= 0)  //如果我比你小，你就往后挪   类似插入排序逻辑{if (key _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; // 一定要记得反向链接维护parent指针++node->_n;}

1、只有多次分裂的时候才会出现需要链接新增的节点，如果只有一次分裂的话，child就是nullptr，所以在反向链接的时候要注意！！！

2、在插入关键字的时候，我们按照插入排序的逻辑从后开始往前找，不断将比自己大的元素往后挪，挪动的时候要别忘了把他的右子树也跟着往后挪动。

3、end必须设置成int而不能是size_t，因为是从后往前找的，所以end是有可能会出现负数的。

4.4 B树的插入整体实现

bool Insert(const K& key){if (_root == nullptr) //如果我为空 那我就让自己成为新的根{_root = new Node;_root->_keys[0] = key;++_root->_n;  return true;}//如果不为空  开始执行插入逻辑pair ret = Find(key);if (ret.second>=0) return false;//如果没有找到，find顺便带回了要插入的叶子节点Node* cur = ret.first;//每次循环往cur插入newkey和childK newKey = key;Node* child = nullptr;while (1){InsertKey(cur, newKey, child);//情况1 没满， 直接结束if (cur->_n _keys[j] = cur->_keys[i]; brother->_subs[j] = cur->_subs[i]; //节点也拷过去//与父亲建立连接if (cur->_subs[i])  cur->_subs[i]->_parent = brother;//清理一下方便观察cur->_keys[i] = K();cur->_subs[i] = nullptr;}// 还有最后一个右孩子拷过去brother->_subs[j] = cur->_subs[i];if (cur->_subs[i])  cur->_subs[i]->_parent = brother; //孩子如果不是空  那么父亲就得更新一下cur->_subs[i] = nullptr;brother->_n = j;cur->_n -= (brother->_n + 1);//因为还要把中位数往上放K midKey = cur->_keys[mid];cur->_keys[mid] = K();//方便观察//转化成往cur的parent去插入 cur->[mid]和 brother// 说明刚刚分裂是根节点if (cur->_parent == nullptr){_root = new Node; //最坏情况 我的父亲是空，那就造一个新的根出来_root->_keys[0] = midKey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_n = 1;//链接起来cur->_parent = _root;brother->_parent = _root;break;}else //如果父亲不是空，还可以向上调整{// 转换成往parent->parent 去插入parent->[mid] 和 brothernewKey = midKey;child = brother;cur = cur->_parent;}}return true;}

1、如果什么也没有，那么自己就成为新的树。

2、通过find函数去找B树中是否存在这个关键字，如果存在就结束，不存在，那就把返回的pair中的first（待插入的叶子节点）提取出来。

3、因为有可能会涉及到多次分裂，所以我们要将插入的函数写在循环里面（通过cur、newkey、child来帮助我们迭代 ），然后每次插入之后就去判断是否还要进行分裂。如果没满就结束，如果满了就分裂。

4、分裂一半的key和节点（要注意节点的反向链接）给自己的兄弟，然后清理一下数据方便我们调试观察，最后有一个右孩子还得再拷贝一次。

5、传中位数的时候，如果cur没有父亲，那么就直接造一个父亲出来。如果cur有父亲，就更新一下cur、newkey、child，继续往上迭代去走。将问题转化成往父亲节点插入中位数和一个brother节点。

4.5 B树的中序遍历验证

       他的整体逻辑是左、根、左、根、左、根……右  所以我们可以将前两个过程抽出来，然后最后再单独处理右。走一个中序遍历的逻辑实现有序。

void _InOrder(Node* cur){if (cur == nullptr)  return;// 左 根  左 根  ...  右size_t i = 0;for (; i _n; ++i){_InOrder(cur->_subs[i]); // 左子树cout _keys[i] _subs[i]); // 最后的那个右子树}void InOrder(){_InOrder(_root);}

 附上测试用例：

void testBtree(){BTree t;int a[] = { 53, 139, 75, 49, 145, 36, 101 };for (auto e : a)  t.Insert(e);t.InOrder();}

 4.6 整体的代码

#pragma once#includeusing namespace std;//K表示存的地址  M表示最多有几个分支template struct BTreeNode{BTreeNode(){for (size_t i = 0; i _n){if (key _keys[i]) break; //keys[i]的左孩子根他的下标是相等的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);}//每次循环往cur插入newkey和childvoid InsertKey(Node* node, const K& key, Node* child){int end = node->_n - 1;while (end >= 0)  //如果我比你小，你就往后挪   类似插入排序{if (key _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){if (_root == nullptr) //如果我为空 那我就让自己成为新的根{_root = new Node;_root->_keys[0] = key;++_root->_n;  return true;}//如果不为空  开始执行插入逻辑pair ret = Find(key);if (ret.second>=0) return false;//如果没有找到，find顺便带回了要插入的叶子节点Node* cur = ret.first;//每次循环往cur插入newkey和childK newKey = key;Node* child = nullptr;while (1){InsertKey(cur, newKey, child);//情况1 没满， 直接结束if (cur->_n _keys[j] = cur->_keys[i]; brother->_subs[j] = cur->_subs[i]; //节点也拷过去//与父亲建立连接if (cur->_subs[i])  cur->_subs[i]->_parent = brother;//清理一下方便观察cur->_keys[i] = K();cur->_subs[i] = nullptr;}// 还有最后一个右孩子拷过去brother->_subs[j] = cur->_subs[i];if (cur->_subs[i])  cur->_subs[i]->_parent = brother; //孩子如果不是空  那么父亲就得更新一下cur->_subs[i] = nullptr;brother->_n = j;cur->_n -= (brother->_n + 1);//因为还要把中位数往上放K midKey = cur->_keys[mid];cur->_keys[mid] = K();//方便观察//转化成往cur的parent去插入 cur->[mid]和 brother// 说明刚刚分裂是根节点if (cur->_parent == nullptr){_root = new Node; //最坏情况 我的父亲是空，那就造一个新的根出来_root->_keys[0] = midKey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_n = 1;//链接起来cur->_parent = _root;brother->_parent = _root;break;}else //如果父亲不是空，还可以向上调整{// 转换成往parent->parent 去插入parent->[mid] 和 brothernewKey = midKey;child = brother;cur = cur->_parent;}}return true;}void _InOrder(Node* cur){if (cur == nullptr)  return;// 左 根  左 根  ...  右size_t i = 0;for (; i _n; ++i){_InOrder(cur->_subs[i]); // 左子树cout _keys[i] _subs[i]); // 最后的那个右子树}void InOrder(){_InOrder(_root);}private:Node* _root=nullptr;};void testBtree(){BTree t;int a[] = { 53, 139, 75, 49, 145, 36, 101 };for (auto e : a)  t.Insert(e);t.InOrder();}

 4.7 B树的性能分析

       对于一棵节点为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$之间，在定位到该节点后，再采用二分查找的方式可以很快的定位

到该元素。

         B-树的效率是很高的，对于N = 62*1000000000个节点，如果度M为1024，则$log_{M/2}N$ key.2、父亲中存的是孩子节点中的最小值做索引）

和B树规则区别总结：

1、简化B树孩子比关键字多一个的规则，变成了相等（一一对应）。

2、而key value都存在叶子节点上，一方面是节省空间，一方面是方便遍历查找所有值

B+树的特性：
1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。

2. 不可能在分支节点中命中（因为只存k而没有存kv）。

3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层

5.2 B+树的插入过程分析

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

1、插入53

2、插入139

 3、插入75

4、插入49

 5、分裂

6、插入145

 7、插入36

8、插入50 

9、分裂

 10、插入47

11、插入101

 12、分裂

13、二次分裂

和B树插入的区别：

1、一开始创建的是两层，一层做根，一层做分支

2、父亲节点存的是孩子节点中的最小值做索引，如果最小值更新了，那么往上的索引值都要全部更新

3、孩子不再是比key多一个（包含关系），而是和key相等（一一对应关系）

4、分裂的时候，不再是把中位数往上拿，而是把分裂出来的兄弟节点的最小值往上拿 

5.3 B*树

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
为什么B*树的非叶子节点需要指向兄弟节点的指针呢？而B+树不需要呢？ 究竟想达到什么目的？

B+树的分裂：

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

B*树的分裂：

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

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

5.3 B树系列总结

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

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

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