【C++从0到王者】第五十站：B树

文章目录

• 一、内查找与外查找
• • 1.内查找
  • 2.外查找
  • 二、B树概念
  • 三、B树的插入
  • • 1.B树的插入分析
    • 2.B树插入总结
    • 3.插入代码实现
    • 4.B树满树和最空时候的对比
    • 5.B树的删除
    • 6.遍历B树
    • 7.B���的性能分析

      一、内查找与外查找

      1.内查找

      像我们之前所用的在内存中的查找就是内查找

      种类	数据格式	时间复杂度
      顺序查找	无要求	O(N)
      二分查找	有序	O(log_2 N)
      二叉搜索树	无要求	O(N)
      二叉平衡树(AVL树和红黑树)	无要求	O(log_2 N)
      哈希	无要求	O(1)

      2.外查找

      如果数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘上，有需要搜索某些数据，那么如果处理呢？那么我们可以考虑将存放关键字及其映射的数据的地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。

      如下所示，是在一颗二叉树中，在内存中存储的只是在磁盘当中的地址。然后就可以去磁盘当中去寻找对应的值

      然而只是使用这种二叉树的结构，还是存在一些问题

      使用平衡二叉树搜索树的缺陷：

      • 平衡二叉树搜索树的高度是logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，logN次的磁盘访问，是一个难以接受的结果。

        使用哈希表的缺陷：

        • 哈希表的效率很高是O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的。

          下面是对磁盘IO访问速度的解释

          那如何加速对数据的访问呢？

          1. 提高IO的速度(SSD相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)

          2. 降低树的高度—多叉树平衡树

          对于红黑树和AVL树而言，他们需要经历高度次IO，哈希表极端场景下冲突很多，效率下降十分严重

          我们可以在平衡搜索树中去寻找优化空间

          1. 压缩高度，二叉变多叉
          2. 一个结点里面有多个关键字及其映射的值

          二、B树概念

          1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为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//K _keys[M - 1];//BTreeNodefor (int i = 0; i _keys[i]) //如果大于，那么说明可能在右侧可以找到{++i;}else //找到了，直接返回该节点指针和key下标{return make_pair(cur, i);}}//先记录一下我们的这个当前结点。以至于即便没有找到，那么我们也知道应该要去哪里插入了。即返回了要插入的那个叶子节点parent = cur;//往孩子去跳，一行代码两用，巧妙的控制了i，既在该该跳转到左孩子时候可以直接跳转到左孩子，也可以直接跳转到右孩子。比较巧妙cur = cur->_subs[i]; }//用第二个参数-1来区分是找到了还是没找到，因为下标不可能是-1，第一个参数用来指明既然没有找到，那么如果还想要插入这个key的话，那么去这里插入是对的return make_pair(parent, -1);}//该函数的应用场景有两种情形，一种是为叶子直接插入key值，此时child为nullptr，一种是下层的为叶子结点插入时候发生了分裂，导致为上层插入key，此时需要插入child兄弟指针//为node结点插入key和child。key是关键字。node就是父节点，child是兄弟结点，因为我们可能会插入新分裂出来的一个结点//因为我们的插入是需要移动key值和指针的。两个最后都会空余的。这两个就是用来插入这两个的void 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; //插入key值node->_subs[end + 2] = child; //插入可能的兄弟结点，child有可能为空，即并没有分裂。此时它一定为叶子结点，本身就是nullptr,所以赋值与否并不影响//因为我们只能对叶子结点进行直接插值，如果对非叶子结点插入值，只能是下层的进行了分裂，导致上层的才添加了数据。此时本身就需要将兄弟结点的指针挪动到该位置处//如果child为nullptr，那么是叶子结点，不用让兄弟结点去指向父亲节点。//如过不是nullptr，那么插入了这个结点以后让他指向父亲结点if (child){child->_parent = node; //兄弟结点的父亲结点设置为node}//无论如何，node结点的数据个数一定是加一的。node->_n++;}bool Insert(const K& key){//第一次插入，直接开辟一个结点出来，然后将这个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;}//如果没找到，那么ret的first也正好是要插入的那个叶子节点Node* parent = ret.first; //parent就是要插入的哪个结点K newkey = key;//这里我们把这个key值在保存一份，因为我们原来的这个key是不可以被修改的，但是我们后面是需要修改一下的，这里主要是为了照顾连续插入的场景，至少发生了一次分裂Node* child = nullptr; //兄弟指针，这里的名字可能不太好，它是为因为叶子节点产生分裂时，上层要插入数据的时候，一定会有一个key和一个指针的插入的。while (1){//无论parent是叶子结点还是非叶子结点，这个函数一语双关，都可以成功实现我们的目标InsertKey(parent, newkey, child);//满了就要分裂了，没有满就插入结束if (parent->_n _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]; //提前保存一下要插入给父亲结点的那个值。//清理被分裂的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; //这里其实已经可以直接return true了，不过因为编译器只是简单的认为不是所有的情况都有返回值。所以我们使用一下break,在外层返回一下也是可以的。毕竟里层的是个***循环，只有这里可以打破***循环}//如果分裂的不是根节点，就不需要额外创建那个结点else{newkey = midKey; //newkey是InsertKey的一个参数child = brother; //它也是上面函数的一个参数//转换成往parent->parent插入去插入parent->_keys[mid]和brotherparent = parent->_parent; //这个结点就是parent的父节点，也就是mid和brother都需要与他建立连接//由于该函数正好写在第一行，所以，我们直接循环回去去完成插入这件事情。//至此，这个循环就一直在运行，而且它最终一定会出去的，只要我们的B树是正确的！！！}}}return true;}private:Node* _root = nullptr;};void TestBTree(){int a[] = { 53, 139, 75, 49, 145, 36 ,101 };BTree t;for (auto e : a){if (e == 36)int a = 0;t.Insert(e);}}

             经过了上面的实现，我们也终于可以理解了，为什么它是平衡的，因为它是向右和向上增长的树

             4.B树满树和最空时候的对比

             5.B树的删除

             如下所示：是删除的大致思路：就是借

             6.遍历B树

             B树的遍历就是我们用类似于二叉树的中序遍历即可，不过我们的顺序是左子树，根，左子树，根…右子树

             代码如下

             #pragma once#include using namespace std;templatestruct BTreeNode{//K _keys[M - 1];//BTreeNode* _subs[M];//为了方便插入以后再分裂，多给一个空间K _keys[M]; //key值BTreeNode* _subs[M + 1]; //指针BTreeNode* _parent; //记录一下该节点的父节点size_t _n; //记录实际存储了多少个关键字BTreeNode(){for (int i = 0; i _n) //_n代表每个结点的数据个数，这里确保不要越界，如果超出了范围，那么这个i正好就是_n的值，也就是最右侧孩子处的结点，可以与下面的结合，直接跳转到最右孩子处{if (key _keys[i]) //一旦小于的话，那么我们一定可以确定的是，不在这个结点内，且当前的i正好指向这个_keys[i]的左孩子处{break; //直接使用break就是一种很巧妙的做法，可以利用外面的语句，直接跳转到对应的左孩子位置。}else if (key > cur->_keys[i]) //如果大于，那么说明可能在右侧可以找到{++i;}else //找到了，直接返回该节点指针和key下标{return make_pair(cur, i);}}//先记录一下我们的这个当前结点。以至于即便没有找到，那么我们也知道应该要去哪里插入了。即返回了要插入的那个叶子节点parent = cur;//往孩子去跳，一行代码两用，巧妙的控制了i，既在该该跳转到左孩子时候可以直接跳转到左孩子，也可以直接跳转到右孩子。比较巧妙cur = cur->_subs[i]; }//用第二个参数-1来区分是找到了还是没找到，因为下标不可能是-1，第一个参数用来指明既然没有找到，那么如果还想要插入这个key的话，那么去这里插入是对的return make_pair(parent, -1);}//该函数的应用场景有两种情形，一种是为叶子直接插入key值，此时child为nullptr，一种是下层的为叶子结点插入时候发生了分裂，导致为上层插入key，此时需要插入child兄弟指针//为node结点插入key和child。key是关键字。node就是父节点，child是兄弟结点，因为我们可能会插入新分裂出来的一个结点//因为我们的插入是需要移动key值和指针的。两个最后都会空余的。这两个就是用来插入这两个的void 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; //插入key值node->_subs[end + 2] = child; //插入可能的兄弟结点，child有可能为空，即并没有分裂。此时它一定为叶子结点，本身就是nullptr,所以赋值与否并不影响//因为我们只能对叶子结点进行直接插值，如果对非叶子结点插入值，只能是下层的进行了分裂，导致上层的才添加了数据。此时本身就需要将兄弟结点的指针挪动到该位置处//如果child为nullptr，那么是叶子结点，不用让兄弟结点去指向父亲节点。//如过不是nullptr，那么插入了这个结点以后让他指向父亲结点if (child){child->_parent = node; //兄弟结点的父亲结点设置为node}//无论如何，node结点的数据个数一定是加一的。node->_n++;}bool Insert(const K& key){//第一次插入，直接开辟一个结点出来，然后将这个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;}//如果没找到，那么ret的first也正好是要插入的那个叶子节点Node* parent = ret.first; //parent就是要插入的哪个结点K newkey = key;//这里我们把这个key值在保存一份，因为我们原来的这个key是不可以被修改的，但是我们后面是需要修改一下的，这里主要是为了照顾连续插入的场景，至少发生了一次分裂Node* child = nullptr; //兄弟指针，这里的名字可能不太好，它是为因为叶子节点产生分裂时，上层要插入数据的时候，一定会有一个key和一个指针的插入的。while (1){//无论parent是叶子结点还是非叶子结点，这个函数一语双关，都可以成功实现我们的目标InsertKey(parent, newkey, child);//满了就要分裂了，没有满就插入结束if (parent->_n _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]; //提前保存一下要插入给父亲结点的那个值。//清理被分裂的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; //这里其实已经可以直接return true了，不过因为编译器只是简单的认为不是所有的情况都有返回值。所以我们使用一下break,在外层返回一下也是可以的。毕竟里层的是个***循环，只有这里可以打破***循环}//如果分裂的不是根节点，就不需要额外创建那个结点else{newkey = midKey; //newkey是InsertKey的一个参数child = brother; //它也是上面函数的一个参数//转换成往parent->parent插入去插入parent->_keys[mid]和brotherparent = parent->_parent; //这个结点就是parent的父节点，也就是mid和brother都需要与他建立连接//由于该函数正好写在第一行，所以，我们直接循环回去去完成插入这件事情。//至此，这个循环就一直在运行，而且它最终一定会出去的，只要我们的B树是正确的！！！}}}return true;}void _InOrder(Node* root){if (root == nullptr){return;}//左子树，根，左子树，根.....右子树int i = 0;for (; i _n; i++){_InOrder(root->_subs[i]); //左子树cout _keys[i] _subs[i]); //最后的右子树}void InOrder(){_InOrder(_root);}private:Node* _root = nullptr;};void TestBTree(){int a[] = { 53, 139, 75, 49, 145, 36 ,101 };BTree t;for (auto e : a){if (e == 36)int a = 0;t.Insert(e);}t.InOrder();}

             运行结果为

             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，则 l o g M / 2 N log_{M/2}N logM/2​N