B-树底层原理
一、B-树介绍
定义：
B-树（B-Tree）是一种自平衡的树形数据结构，广泛应用于数据库和操作系统中。它的设计目标是减少搜索、顺序访问、插入和删除操作中比较次数和移动次数，特别适合于磁盘中数据的存储和检索。
性质：
1、每个节点至多拥有M棵子树。
2、根节点至少拥有两颗子树。
3、除了根节点，其余每个分支节点至少拥有M/2棵子树。
4、所有叶子节点都在同一层。
5、有K棵子树的分支节点至少有K-1个关键字，关键字按照递增的方式排序。
6、关键字数量满足ceil(M/2)-1 <= n <= M-1。
二、B-树的操作
首先看一下B-树的形状：
1、插入元素
情况一：根节点分裂
这种情况是由于根节点不满足B-树的性质时，需要分裂来维持性质，该操作会增加树的高度。
演示：通过不断插入26个英文字母来演示分裂过程。
我们定义一个6阶B-树，也就是M =6；每个节点中至多有M - 1 = 5 个键值。
以上就是根节点分裂。
情况二：非根节点分裂
发生分裂的原因依旧是插入元素时，对应的节点中的键值超过了上限，这时就需要分裂。
演示：接着操作26个英文字母。
以上就是节点分裂情况。插入后续剩余字母后：
2、删除元素
情况一：删除叶子节点
还是在我们26个字母组成的树中操作：
按顺序删除元素
如图，删除叶子节点可能涉及到两种操作，一是“借位”，二是合并，当父节点左右两边的节点中的元素个数都为M/2-1时，进行合并操作，若需要删除元素的一方节点中元素的个数为M/2-1，另一方元素个数大于M/2-1，则“借位”，反之直接向下进行删除动作。
情况二：删除内节点
我们还是用我们的老演员
在这个图的基础上删除 I 元素
如果我们删除O元素，那么判断O元素所在的节点是否等于M/2-1，显然该节点中的元素个数大于M/2-1，那么我们无需借位操作，仅需向下合并，直到O元素所在的节点为叶子节点，然后进行删除。删除根节点同理。