B+树是一种应用广泛的树型数据结构,通常用于数据库(例如Mysql 但是k-v模型非关系库数据库是基于哈希表 比如redis memcached)和操作系统的文件系统中。 非常简单来的谈一下,或许听着很强,但是并不难。
查找以典型的方式进行,类似于二叉查找树。 在节点内部典型的使用是二分查找来确定这个位置。
二叉查找又名折半查找,顾名思义,就是分成两半比较。 也许这样你不能理解,这时候举个栗子就很有必要了。 我们来玩这个游戏 比如说有一个1-100的数字,我随机的选择其中一个数字(假设为60),你需要以最少的次数猜到我所选择的数字,每次猜测后,我会告诉你大了,小了,对了。
假设你第一次从1开始猜,小了
第二次:2 小了
第三次:3 小了
…
第五十九次:59 小了
第六十次:60 对了
这是参考思路之一,顺序遍历出答案。 这是简单的查找,每次猜测只能排除一个数字,如果我想的数字是100,那么你可能需要从1猜到100了! 那么有没有更好的查找方式呢? 答案很明显使用下面的操作
第一次:50 小了
你把100折成50
就可以判断这个数字在0-50 还是 50-100
第二次:75 大了
将剩下的继续折半
你可以
依次1/2分割结果可以得出答案,效率也是非常可观的,第一种需要猜测60次才能猜出正确答案,而使用第二种方式,只需要七次就能猜出正确答案,ohhhh,很强对不对。
果然程序员都是懒人 所以发明都这么懒
一颗 m 阶的 B+树 有 n 棵子树的结点中含有 n 个关键字; 在 B+树中每个结点中关键字个数 n 的取值范围为:⌈m/2⌉≤n≤m。
例如这个就是三阶b+树 1、 若被插入关键字所在的结点,其含有关键字数目小于阶数 M,则直接插入结束; 例如,在上图 中插入关键字13,其结果下图 所示:
2、 若被插入关键字所在的结点,其含有关键字数目等于阶数 M,则需要将该结点分裂为两个结点,一个结点包含⌊M/2⌋,另一个结点包含⌈M/2⌉。同时,将⌈M/2⌉的关键字上移至其双亲结点。假设其双亲结点中包含的关键字个数小于 M,则插入操作完成。
例如,在刚刚三阶的基础上插入关键字 95,其插入后的 B+树下图所示:
3、在第 2 情况中,如果上移操作导致其双亲结点中关键字个数大于 M,则应继续分裂其双亲结点。 例如,在刚刚的三列树B+树中插入关键字 40,则插入后的 B+树下图所示:
注意:如果插入的关键字比当前结点中的最大值还大,破坏了B+树中从根结点到当前结点的所有索引值,此时需要及时修正后,再做其他操作。例如,在图 1 的 B+树种插入关键字 100,由于其值比 97 还大,插入之后,从根结点到该结点经过的所有结点中的所有值都要由 97 改为 100。改完之后再做分裂操作。 //脑子不太够用搬运大佬的
//待补充
有兴趣推荐一个网站,可视化学习算法,以前推荐过啦,今天翻出啦,热热还能吃