闲言杂记

B+树是一种应用广泛的树型数据结构,通常用于数据库(例如Mysql 但是k-v模型非关系库数据库是基于哈希表 比如redis memcached)和操作系统的文件系统中。
非常简单来的谈一下,或许听着很强,但是并不难。

核心算法

B+树查找

查找以典型的方式进行,类似于二叉查找树。
在节点内部典型的使用是二分查找来确定这个位置。

补充:二叉查找

二叉查找又名折半查找,顾名思义,就是分成两半比较。
也许这样你不能理解,这时候举个栗子就很有必要了。
我们来玩这个游戏
比如说有一个1-100的数字,我随机的选择其中一个数字(假设为60),你需要以最少的次数猜到我所选择的数字,每次猜测后,我会告诉你大了,小了,对了。

假设你第一次从1开始猜,小了

第二次:2 小了

第三次:3 小了

第五十九次:59 小了

第六十次:60 对了

这是参考思路之一,顺序遍历出答案。
这是简单的查找,每次猜测只能排除一个数字,如果我想的数字是100,那么你可能需要从1猜到100了!
那么有没有更好的查找方式呢?
答案很明显使用下面的操作

第一次:50 小了

你把100折成50

就可以判断这个数字在0-50 还是 50-100

第二次:75 大了

将剩下的继续折半

你可以

依次1/2分割结果可以得出答案,效率也是非常可观的,第一种需要猜测60次才能猜出正确答案,而使用第二种方式,只需要七次就能猜出正确答案,ohhhh,很强对不对。

果然程序员都是懒人 所以发明都这么懒

B+树插入

一颗 m 阶的 B+树
有 n 棵子树的结点中含有 n 个关键字;
在 B+树中每个结点中关键字个数 n 的取值范围为:⌈m/2⌉≤n≤m。

三阶B+树

例如这个就是三阶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。改完之后再做分裂操作。
//脑子不太够用搬运大佬的

B+树删除

//待补充

后盐

有兴趣推荐一个网站,可视化学习算法,以前推荐过啦,今天翻出啦,热热还能吃

算法可视化

评论

  1. windsky windsky
    Chrome 64

    啊哈哈哈,南博见你了?

    1. 乔千 乔千
      Chrome 79

      是啊 我想试试那个

This is just a placeholder img.