不可能在分支结点中命中

一、高度为h、如果数据量非常大，比如由100G数据，无法一次放进内存中，那就只能放在磁盘上了。

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

每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki(1≤i≤n)为关键字，且Ki<Ki+1(1≤i≤n-1)。
但是由于磁盘访问的速度很慢，对于上述树形查找结构来说就是需要logN次的IO，这是一个很难接受的结果。AVL树和红黑树三种树形查找结构，但上述结构适用于数据量相对不是很大，能够一次性放进内存中，进行数据查找的场景。阶数为m的B树：

1. 若让每个结点中的关键字个数达到最多，则容纳同样多关键字的B树的高度达到最小。一颗m阶(m>2)的B树，是一棵的m路平衡搜索树，它可以是空树或者满足以下性质：
   1. 根节点至少有两个孩子。

   二、

   pair<Node*,int>Find(constK&key){Node*parent =nullptr;Node*cur =_root;while(cur){size_t i =0;while(i <cur->_n)// 在当前结点进行查找{if(key <cur->_keys[i])// 如果小于则进入与当前下标相同的孩子{break;}elseif(key >cur->_keys[i])//如果大于则++i{++i;}else{returnmake_pair(cur,i);// 找到了就返回当前结点以及该关键字所在的位置}}parent =cur;cur =cur->_subs[i];}returnmake_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. 如果向上已经分裂到根节点的位置，插入结束

   // 插入操作中用到的函数voidInsertKey(Node*node,constK&key,Node*child)// 插入新关键字{intend =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树的插入boolInsert(constK&key){if(_root ==nullptr)//如果根结点为空{_root =newNode;_root->_keys[0]=key;++_root->_n;returntrue;}pair<Node*,int>ret =Find(key);// 借助查找操作来判定是否存在要插入的值if(ret.second >=0)// 如果不存在则可以找到要进行插入的位置{returnfalse;}Node*parent =ret.first;K newKey =key;Node*child =nullptr;while(1){InsertKey(parent,newKey,child);// 先利用插入排序的方法进行插入if(parent->_n <M)// 如果没有破坏B树的性质则返回true{returntrue;}else// 否则进行分裂操作{size_t mid =M /2;Node*brother =newNode;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 =newNode;_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;}}}returntrue;}

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

2. 兄弟够借：若再删除一个关键字就会破坏B树定义，并且左，右兄弟的关键字个数大于等于ceil(m/2)，则需要调整该结点、对于关键字个数为n的B树，叶结点即查找不成功的结点为n+1，由此有$n+1>=2(ceil(m/2){)}^{h-1}$，即$h<=lo{g}_{ceil(m/2)}((n+1)/2)+1$。第一层至少有1个结点；第二层至少有两个结点；除根结点外的每个非叶结点至少有ceil(m/2)棵子树，则第三层至少有2ceil(m/2)个结点……第h+1层至少有$2(ceil(m/2){)}^{h-1}$个结点，注意到第h+1层是不包含任何信息的叶结点。
   

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

1.B+树

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

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

B+树的特性：

1. 所有关键字都出现在叶子结点的链表中，且链表中的结点都是有序的。B树的基本概念
2. • 1.引入
   • 2.B树的概念
3. 二、
4. 每个分支节点都包含k-1个关键字和k个孩子，其中 ceil(m/2) ≤ k ≤ m （ceil是向上取整函数）。
   若n>=1，则对任意一颗包含n个关键字、B树的实现
5. • 1.B树的定义
   • 2.B树的查找
   • 3.B树的插入操作
   • 4.B树的删除
   • 5.B树的遍历
   • 6.B树的高度
   • 7.整体代码
6. 三、Ai(0≤i≤n)为指向子树根结点的指针。

   4.B树的删除

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

   1. 直接删除关键字：若删除当前关键字后仍然满足B树定义，则直接删除该关键字。
      所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

      3.总结

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

      1. B树：有序数组+平衡多叉树；
      2. B+树：有序数组链表+平衡多叉树；
      3. B*树：一棵更丰满的，空间利用率更高的B+树。
      4. 不可能在分支结点中命中。
      5. 每个节点中的关键字从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分。

         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]);// 最后的那个右子树}voidInOrder(){_InOrder(_root);}

         6.B树的高度

         B树的效率取决于B树的高度，因为磁盘存取次数与高度成正比。

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

      1.B树的定义

      为了方便学习，我们在这里先将m设为3，这时每个结点能存2个关键字和3个孩子。