实搜网站建设,百度的链接,上海微信网站建设公司,90设计网站官网首页文章目录 1. 常见的搜索结构2. 问题提出使用平衡二叉树搜索树的缺陷使用哈希表的缺陷 3. B-树的概念4. B-树的插入分析插入过程分析插入过程总结 5. B-树的代码实现5.1 B-树的结点设计5.2 B-树的查找5.3 B-树的插入实现InsertKey插入和分裂测试 6. B-树的删除#xff08;思想思想7. B-树的高度最小高度最大高度 8. B-树的性能9. B-树的简单验证中序遍历 1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树称为B树。 那么在此之前我们也已经学过很多的搜索结构了我们来一起回顾一下
1. 常见的搜索结构 以上结构适合用于数据量相对不是很大能够一次性存放在内存中进行数据查找的场景内查找。 2. 问题提出
如果数据量很大比如有100G数据无法一次放进内存中那就只能放在磁盘上了如果放在磁盘上有时需要搜索某些数据那么该如何处理呢 我们可以考虑将关键字及其映射的数据的地址放到一个内存中的搜索树的节点中当通过搜索树找到要访问数据的关键字时取这个关键字对应的地址去磁盘访问数据。 但是呢实际中我们去查找的这个key可能不都是整型 可能是字符串比如身份证号码那这时我们还把所有的key和对应数据的地址都存到内存也可能是存不下的。 那这时候可以做一个改动 我不再存储key了只存储地址 那这样的话我如何判断找到了呢 那就需要拿着当前的地址去访问磁盘进行判断。 比如现在要找key为77的这个数据那从根结点开始首先访问根结点中的地址对应磁盘的数据是34那77大于34所以往右子树找右子树0x77对应的是89有一次访问磁盘77比89小再去左子树找左子树地址0x56访问磁盘对应的是77找到了。 那这样做的问题是什么呢 最坏的情况下我们要进行高度次的查找那就意味着要进行高度次的磁盘IO。 如果我们使用红黑树或者AVL树的话就是O( l o g 2 N log_2 N log2N)次。 那如果是在内存中的话这个查找次数还是很快的但是现在数据量比较大是在磁盘上存的而磁盘的速度是很慢的。 所以
使用平衡二叉树搜索树的缺陷 平衡二叉树搜索树的高度是logN这个查找次数在内存中是很快的。但是当数据都在磁盘中时访问磁盘速度很慢在数据量很大时logN次的磁盘访问是一个难以接受的结果。 那如果用哈希表呢
使用哈希表的缺陷 哈希表的效率很高是O(1)但是一些极端场景下某个位置哈希冲突很严重导致访问次数剧增也是难以接受的。 那如何加速对数据的访问呢 1. 提高IO的速度(SSD相比传统机械硬盘快了不少但是还是没有得到本质性的提升) 2. 降低树的高度——多叉树平衡树 那我们今天要学的B-树其实就是多叉平衡搜索树
3. B-树的概念 1970年R.Bayer和E.mccreight提出了一种适合外查找的树它是一种平衡的多叉树并且是绝对平衡称为B树(后面有一个B树的改进版本B树然后有些地方的B树写的的是B-树注意不要误读成B减树)。 一棵m阶(m2)的B树B树中所有结点的孩子个数的最大值称为B树的阶是一棵M路的平衡搜索树可以是空树或者满足一下性质的树 1. 树中每个结点至多有m棵子树即至多含有m-1个关键字。 2. 若根结点不是终端结点则至少有两棵子树。 3. 除根结点外的所有非叶子结点都包含k-1个关键字和k个孩子终端结点孩子都是NULL)其中 ceil(m/2) ≤ k ≤ m ceil是向上取整函数 4. 所有的叶结点都出现在同一层次上并且不带信息可以视为外部结点或类似于折半查找判定树的查找失败结点实际上这些结点不存在指向这些结点的指针为空) 5. 每个节点中的关键字从小到大也可以从大到小排列节点当中k-1个元素正好是k个孩子包含的元素的值域划分 6. 每个结点的结构为nA0K1A1K2A2… KnAn其中Ki(1≤i≤n)为关键字且KiKi1(1≤i≤n-1)。Ai(0≤i≤n)为指向子树根结点的指针。且Ai所指子树所有结点中的关键字均小于Ki1Ai1所指子树所有结点中的关键字均大于Ki1。结点中关键字升序的情况下 n为结点中关键字的个数满足ceil(m/2)-1≤n≤m-1。 大家可以对照上面的图先来自行理解一下B树的这些性质等后面我们熟悉了B树的结构之后大家可以再来反复理解这几条性质为什么是这样。
4. B-树的插入分析
那下面我们就来学习一下B-树的插入是怎样的。
那为了方便讲解也方便大家理解我们这里选取B-树的阶数取小一点给一个3 即三阶B-树三叉平衡树那每个结点最多存储两个关键字两个关键字可以将区间分割成三个部分因此节点应该有三个孩子子树 那每个结点的结构就应该是这样的 但是呢为了后续实现起来简单节点的结构如下 关键字和孩子我们都多给一个空间后面大家就能体会到为什么要多给一个 插入过程分析
那下面我们就来找一组数据分析一下插入的过程用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下 1. 插入53 满足B-树的性质不用动 2. 插入139关键字我们升序排列 也不用做任何处理 3. 插入75 75插入之后是这样但是因为我们多开了一个空间3阶的话每个结点最多3-12个关键字。 所以现在这个结点关键字个数超了。 那此时怎么办呢 要进行一个操作——分裂 怎么分裂呢 1. 找到关键字序列的中间数将关键字序列分成两半 2. 新建一个兄弟结点出来将右半边的m/2个关键字分给兄弟结点 3. 将中间值提给父亲结点新建结点成为其右孩子没有父亲就创建新的根 为什么中位数做父亲——满足搜索树的大小关系左根右 4. 结点指针链接起来 那通过这里大家来体会一下上面的规则中为什么要求除根结点外的所有非叶子结点都包含k-1个关键字ceil(m/2) ≤ k ≤ m即k的最小值是ceil(m/2)即最少包含ceil(m/2)-1个关键字。 如果m是奇数比如9那ceil(m/2)是5个5-1是4而9个的话分裂之后正好两边每个结点都是4个关键字中间的一个提取给父亲。 如果是偶数比如10的话ceil(m/2)是55-1是4而10个分裂的话肯定不平均一边4个最少的一边5个还有一个中间值要提取给父亲。 所以它们最少就是ceil(m/2)-1个关键字。 那我们再来插入几个看看 还是我们上面给的那组数据再往后插入49145 接着再往后36 那此时36插入的这个结点又满了然后就要进行分裂。 大家现在体会为什么我们要多开一个空间这样的话我们就可以在插入之后关键字顺序已经调整好的情况下去分裂就方便很多。 那然后我们来看这里的分裂怎么做 新增一个兄弟结点之后相当于它们的父亲结点就多了一个孩子所以也需要增加一个关键字关键值始终比孩子少一个就把中间值提给父亲结点。 49上提插入到父亲它比75小所以45往后移它的孩子也跟着往后移然后49插入到前面。 再往下插入101 那插入之后这个结点的关键字数量大于m-1了进行分裂 分裂的步骤还是和上面一样 但是此时分裂之后我们发现父亲满了所以需要继续向上分裂 那这就是一个完整的插入过程。 并且我们会发现B-树每一次插入之后他都是天然的完全平衡不需要想红黑树AVL树那样插入之后不满足平衡条件了再去调整。 并且B-树的平衡是绝对平衡。每一棵树的左右子树高度之差都是0。 为什么他能保持天然的完全平衡呢 通过上面的插入过程我们很容易发现B-树是向右和向上生成的只会产生新的兄弟和父亲。 插入过程总结
如果树为空直接插入新节点中该节点为树的根节点树非空找待插入关键字在树中的插入位置(注意找到的插入节点位置一定在终端节点中)检测是否找到插入位置(假设树中的key唯一即该元素已经存在时则不插入)按照插入排序的思想将该关键字插入到找到的结点中检测该节点关键字数量是否满足B-树的性质即该节点中的元素个数是否等于M如果小于则满足插入结束如果插入后节点不满足B树的性质需要对该节点进行分裂 申请新的兄弟节点 找到该节点的中间位置 将该节点中间位置右侧的元素以及其孩子搬移到新节点中 将中间位置元素新建结点成为其右孩子提取至父亲结点中插入从步骤4重复上述操作
5. B-树的代码实现
那下面我们就来写写代码
5.1 B-树的结点设计
那首先我们来定义一下B-树的结点 我们这里还是搞成模板简单一点我们就不实现成KV模型了就搞个K当然在搞个非类型模板参数M控制B树的阶 templateclass K, size_t M 然后结点的话我们上面分析过一棵3阶的B-树 为了方便插入之后分裂我们要多开一个空间正常每个结点最多M-1个关键字M个孩子那增加一个就是M个关键字M1个孩子。 那我们如何定义这样一个结构呢 那这就是两个数组嘛。 然后还需要一个父亲指针指向父结点还需要再给一个成员变量记录当前结点实际存储关键字的个数 然后我们也可以写一个默认构造 那结点我们就定义好了 5.2 B-树的查找
那我们先来实现一个find因为后面插入也要先find嘛 这里我们实现一个不允许键值冗余的版本如果存在就不再插入了如果不存在我们让find直接给我们返回找到的那个要插入位置的结点便于我们在Insert函数中直接将值插入到该结点中。 画个图我们来分析一下 就比如这个图我们现在要查找53。 那首先和根结点的关键字进行比较当前根结点只有一个值7553小于75所以去他的左子树查找。 那我们来分析一下一个关键字和它的左右孩子之间的关系 其实很容易看出来在b-树中 一个关键字的左孩子在_child数组中的下标和该关键字在_keys数组中的下标是一样的而右孩子的话比关键字的下标大1 所以就走到它的左子树49这个结点也只有一个关键字53大于49所以再去关键字49的右子树如果49后面还有关键字的话就继续跟后面的比 那此时就走到5053这个结点。 首先跟第一个关键字50比比50大那就继续往后比后面是53相等找到了。 那如果查找52呢不存在 前面是一样的走到这个结点比50大往后比比53小所以去53的左子树53的左子树为空所以找不到了。 find就写好了
pairNode*, 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[i]){break;}else if (key cur-_keys[i]){i;}else{return make_pair(cur, i);}}// 往孩子结点去跳parent cur;cur cur-_subs[i];}//没找到返回parentreturn make_pair(parent, -1);
}5.3 B-树的插入实现
接下来我们来写一下插入
首先如果是第一次插入的话我们需要做一个单独处理 判断rootnullptr为空的话就是第一次插入 if (_root nullptr)
{_root new Node;_root-_keys[0] key;_root-_n;return true;
}那再往下呢就是已经有结点的情况下插入 那首先判断一下如果key已经存在就不再插入 如果不存在那就去插入find顺便带回了要插入的那个目标位置的结点 那我们接收一下find的返回值在这个结点里面插入即可
InsertKey
那插入的时候需要保证结点里面关键字的顺序可以用插入排序的思想把新的关键字插进去如果是分裂之后向父亲插入的话它可能还有孩子那我们这里再单独封装一个InsertKey的函数 代码就是这样的插入排序如果大家遗忘了可以看之前的文章还有不理解的地方建议大家看着我们上面分析插入的图走一遍代码 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;
}插入和分裂
然后我们就可以调用InsertKey接口去插入关键字但是插入的话 按理说是插入一次但是如果插入之后存储关键字的数组满了我们多开了一个空间满的话就不满足B-树的性质——至多含有m-1个关键字了就需要进行分裂 分裂的话就又需要往parent去插入插入中间值当然分裂的兄弟结点也要成为parent的孩子孩子和关键字都增加1依然符合规则 然后插入之后满了还需要再往上分裂所以应该写成一个循环 最终完整的Insert函数 这里还是比较麻烦的不过注释写的比较清晰了我就不过多解释了。 建议大家对照着我们上面画的图去理解。 bool Insert(const K key)
{if (_root nullptr){_root new Node;_root-_keys[0] key;_root-_n;return true;}// key已经存在不再插入pairNode*, int ret Find(key);if (ret.second ! -1){return false;}// 如果不存在find顺便带回了要插入的那个目标位置的结点//因为后面可能需要分裂继续往父结点插入//所以这里我们接收find的返回值直接命名为parentNode* parent ret.first;//参数中的keyconst修饰不能修改定义一个newkeyK newKey key;//分裂的兄弟也要作为孩子插入到父结点所以再定义一个child//当然第一次插入关键字的时候孩子是空Node* child nullptr;//有可能多次分裂往上一直插入所以需要写成循环while (1){InsertKey(parent, newKey, child);// 没有满插入就结束if (parent-_n M){return true;}else// 满了就要分裂{size_t mid M / 2;// 分裂一半[mid1, 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;// 拷走的key清除重置一下方便调式观察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);//这个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;}else// 分裂的不是根转换成往parent-parent 去插入parent-[mid] 和 brother{newKey midKey;child brother;parent parent-_parent;}}}return true;
}测试
那下面我们就来构建一棵树来测试一下 就拿我们上面画图分析对应的那棵树 我们通过监视窗口来观察一下 对比一下是没什么问题的。 6. B-树的删除思想 学习B树的插入足够帮助我们理解B树的特性了那至于删除呢我们这里可以给大家讲一讲思路代码的话我们就不实现了删除的代码也要比插入更加复杂大家有兴趣的话呢可以参考《算法导论》-- 伪代码和《数据结构-殷人昆》–C实现代码。 那下面我们来讲一下删除的思想 同样也需要分情况讨论 删除的关键字在非终端结点 处理方法是 用其直接前驱或直接后继替代其位置转化为对“终端结点”的删除 直接前驱当前关键字左边指针所指子树中“最右下”的元素 直接后继当前关键字右边指针所指子树中“最左下”的元素 比如 现在要删除75 首先第一种方法可以用直接前驱55替代其位置 或者用直接后继101替代 所以对非终端结点关键字的删除操作必然可以转化为对终端结点的删除 所以下面我们重点来讨论终端结点的删除 删除的关键字在终端结点且删除后结点关键字个数未低于下限 若删除后结点关键字个数未低于下限ceil(m/2)-1直接删除无需做任何其它处理 比如 现在要删除36所在的结点是终端结点且删除之后关键字的个数不少于ceil(3/2)-11所以直接删除即可 那如果删除之后关键字的个数低于下限ceil(m/2)-1呢 若删除的关键字在终端结点且删除后结点关键字个数低于下限ceil(m/2)-1 这时候的处理思路是这样的 删除之后关键字数量低于下限那就去“借”结点跟父亲借父亲再去跟兄弟借 如果不能借即借完之后父亲或兄弟关键字个数也不满足了那就按情况进行合并可能要合并多次。 最终使得树重新满足B-树的性质。 比如 现在要删40那40删掉的话这个结点关键字个数就不满足性质了那就去跟父亲借49借下来那这样父亲不满足了父亲再向兄弟借要删除的那个关键字所在结点的兄弟结点53搞上去 变成这样 此时就又符合是一棵B-树了 那如果不能借的情况呢 比如 现在要删除160 160如果跟父亲借的话150下来那父亲不满足了因为3个孩子必须是2个关键字。而且此时兄弟145所在的这个结点也不能借了。因为此时它只有一个关键字父亲借走一个的话就不满足了。 所以此时借结点就不行了就需要合并了。 如何合并呢 如果结点不够借则需要将父结点内的关键字与兄弟进行合并。合并后导致父节点关键字数量-1可能需要继续合并。 那我们先来看这个 这个情况我们分析了不够借所以要合并。大家看160删掉的话父亲就少了一个孩子那关键字也应该减少一个所以可以把父结点的150与145这个孩子合并 这样就可以了。 当然还有些情况可能需要多次合并 比如 现在要删145怎么办呢 肯定是不够借的所以要合并确保合并之后依然满足B-树的规则就行了。 大家看这个可以怎么合并 145干掉之后左子树这里就不满足了可以先将139跟102合并。 但是此时不平衡了B-树是绝对平衡的。 那就要继续合并缩减高度 很容易看出来我们可以将101和53合并作为根这个正好两个关键字3个孩子 就可以了 7. B-树的高度
问含n个关键字的m阶B树最小高度、最大高度是 多少注大部分地方算B树的高度不包括叶子结点即查找失败结点
最小高度
首先我们来分析一下最小高度 n个关键字的m阶B树关键字个数和B-树的阶数已经确定的话那要让高度最小我们是不是要让每个结点存的关键字是最满的啊。 那对于m阶的B树来说每个结点最多m-1个关键字m个孩子 第一层肯定只有一个根结点最满的话是m-1个关键字m个孩子那第二层最多就有m个结点每个结点最多m-1关键字那第三层就是m*m个孩子嘛以此类推… 那我们假设这个高度是h的话关键字的总个数n就等于关键字个数*结点个数 (m-1)*(1mm^2m^3…m^h-1) 即有 n(m-1)*(1mm^2m^3…m^h-1) 解得最小高度h l o g m ( n 1 ) log_m(n1) logm(n1) 最大高度
那最大高度呢 那要让树变得尽可能高的话那就要让每个结点得关键字数量尽可能少分支尽可能少。 第一层只有一个根结点关键字最少是1孩子是2根结点最少两个孩子/分支所以第二层2个结点。 又因为除了根结点之外的结点最少有ceil(m/2)个孩子所以第三层就最少有2*ceil(m/2)个结点第四层就是2*ceil(m/2)^2以此类推… 第h就是2*ceil(m/2)^h-2个结点。 那么叶子结点查找失败结点的个数就是2*ceil(m/2)^h-1 那这里我们不再像上面那样求出总的关键字个数去算怎么算呢 这里补充一个结论n个关键字的B-树必然有n1个叶子节点 所以我们得出 n12*ceil(m/2)^h-1 那么解得最大高度h[ l o g c e i l ( m / 2 ) ( n 1 ) / 2 log_{ceil(m/2)}(n1)/2 logceil(m/2)(n1)/2] 1 当然也可以算出关键字的总个数来求解 上面我们已经知道每层的结点个数然后我们知道根结点最少一个关键字其它结点最少k-1个关键字k最小是ceil(m/2) 那么第一层就是1个关键字第二层往后就是该层的节点个数*每个结点的最小关键字个数(k-1) 那么因此就有n12(kh-1-1 同样解得最大高度 h[ l o g c e i l ( m / 2 ) ( n 1 ) / 2 log_{ceil(m/2)}(n1)/2 logceil(m/2)(n1)/2] 1 8. B-树的性能 B-树的效率是很高的对于N 62*1000000000个节点如果度M为1024。 查找的坏最坏就是高度次嘛h[ l o g c e i l ( M / 2 ) ( N 1 ) / 2 log_{ceil(M/2)}(N1)/2 logceil(M/2)(N1)/2] 1≈ l o g m / 2 N log_{m/2}N logm/2N 则 l o g m / 2 N log_{m/2}N logm/2N 4即在620亿个元素中如果这棵树的度为1024则需要小于4次即可定位到该节点然后利用二分查找可以快速定位到该元素大大减少了读取磁盘的次数。 9. B-树的简单验证中序遍历
那B-树呢也是搜索树同样满足左子树根右子树那我们可以对它进行一个验证看中序遍历是否能得到一个有序序列。
那下面我们就来实现一下B-树的中序遍历 我们还是来搞一个图对照着分析一下思路 就拿这个来分析 对于我们之前学的二叉树来说中序遍历的思想是左子树、根、右子树 那B-树的话它可能是一个多叉的那它的中序遍历应该怎么走呢 首先肯定还是先访问左子树搜索树中最左的结点一定是最小的 当然如果算上空结点的话最左的应该是空左子树然后依然是根就是3636就是最小的没问题。 左子树、根那然后呢 是36的右子树吗可以认为是36的右子树但是我们要把它当作40的左孩子看。 36这个关键字访问完就走到后面的40对于40同样是先左子树再根 那这个第二个访问到的元素就是40此时当前结点所有的关键字访问完了最后再去访问最后一个关键字的右子树 此时整个结点才被访问完。 那此时就相当于是49的左子树访问完了然后访问根49后面就是一样的处理… 大家看这样就可以了 所以B-树的中序遍历是怎么样的呢 左子树、根下一个关键字的左子树、根再下一个左子树、根…(一直往后直至走完最后一个关键字右子树最后一个关键字的右子树 左 根 左 根 … 右 那理清了思路我来实现一下代码 注释写的比较清晰就不多解释了 // 左 根 左 根 ... 右
void _InOrder(Node* root)
{if (root nullptr)return;size_t i 0;//依次访问当前结点中每个关键字的左子树和根for (; i root-_n; i){_InOrder(root-_subs[i]);//先访问左子树cout root-_keys[i] ;//再访问根}_InOrder(root-_subs[i]);//再访问最后一个关键字的右子树
}void InOrder()
{_InOrder(_root);
}那我们来验证一下呗中序遍历一下我们上面插入之后的那个B-树 没有问题 那对于B-树的讲解我们就先到这里…
