B树

B树

B树是一种自平衡树数据结构 它维护有序数据并允许以对数时间进行搜索 顺序访问、插入和删除
B树是二叉搜索树的一般化 因为节点可以有两个以上的子节点
与其他自平衡二进制搜索树不同 B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统
B树的
它通常用于数据库和文件系统

B树是一种平衡的多分树 一颗m阶的B树必须满足如下条件：
1）树中每个结点至多有m个孩子
2）除根结点和叶子结点外，其它每个结点至少有m/2个孩子（比如m=5 则必须有）
3）若根结点不是叶子结点，则至少有2个孩子
4）所有叶子结点都出现在同一层（即同一高度），叶子结点不包含任何关键字信息
5）有k个孩子的非终端结点恰好包含有k-1个关键字（如下图M关键字有两个孩子 D、G关键字有三个孩子）
在B树中 每个结点中关键字从小到大排列
B树查询流程

假设要找E
1）获取根节点的关键字进行比较 当前根节点关键字为M E所以往找到指向左边的子节点（二分法规则 左小右大 左边放小于当前节点值的子节点 右边放大于当前节点值的子节点）
2）拿到关键字D和G D3）拿到E和F 因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）
B树插入流程
定义一个5阶B树 将3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来
遵循规则：
1）节点拆分规则：当前是要组成一个5阶B树 那么此时m=5 关键字数必须为4（即关键字数>4就要进行节点拆分）
2）排序规则：满足节点本身比左边节点大 比右边节点小的排序规则
先插入 3、8、31、11

再插入23、29

再插入50、28

B树删除流程
节点合并规则：
1）当前是要组成一个5阶B树 那么此时m=5 关键字数必须大于等于（5/2）即2（所以这里关键字数<2就要进行节点合并）
2）满足节点本身比左边节点大 比右边节点小的排序规则
3）关键字数小于2时先从子节点取 子节点没有符合条件时就向向父节点取 取中间值往父节点放
如图依次删除依次删除【8】,【20】,【18】,【5】

a）删除【8】

b）删除【20】

c）删除【18】

d）删除【5】