数据库底层实现-B+树
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+树 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+树删除
//待补充
后盐
有兴趣推荐一个网站，可视化学习算法，以前推荐过啦，今天翻出啦，热热还能吃