【B树操作实例】实例讲解插入、删除元素的过程
基本概念
B树又称为平衡多路查找树。对于一棵m阶的B树（m代表子树的最大数量），有如下特性：
- 根节点的元素数量至少为1，至多为m-1
- 非根节点的元素数量至少为ceil(m/2)-1，至多为m-1（ceil是向上取整）
- 根节点若不是叶节点，则至少有2个子树
- 叶节点都在同一层
以上信息都可以在百度百科和其他博客查到，本文重点以实例讲解对B树进行插入、删除元素的操作。
实例讲解
插入和删除操作可以遵循以下口诀：
插入的操作应该都在叶节点进行，当插入元素后该叶节点没有过饱和，插入操作结束（实例1）；若达到过饱和，就将当前叶节点分裂成两个节点，把中间元素向上传递到父节点（实例2）。
删除的操作可能在叶节点或非叶节点发生，删除非叶节点的元素时，将其两个子树合并成为一个节点（实例3）；删除叶节点的元素时，如果没有剩余的数量仍大于等于ceil(m/2)-1,删除操作结束（实例4）；如小于，则将父节点对应的元素下移进该节点，此时相当于删除了父节点（非叶节点）的元素，需要将两个子树合并成为一个节点（实例5）；在删除元素时，合并子树得到的新节点如果过饱和，需要进行分裂上溢（实例6）。
接下来以5阶B树，举例说明。
实例1
向叶节点（7，8）插入元素9之后，叶节点（7，8，9）还没饱和，插入操作结束。
实例2
向叶节点（22，24，25，28）插入26后，叶节点（22，24，25，26，28）元素数量大于4（即m-1），分裂成（22，24）和（26，28）两个节点，并把25上溢到（6，10，21，33）得到（6，10，21，25，33），该节点也过饱和了，所以也将分裂成（6，10）和（25，33）两个节点，并把21上溢成为两个节点的父节点。
实例3
从非叶节点（25，33，44）中删除元素33，变为（25，44），且将33的左右子树（26，28）和（38，40）合并成为一个节点（26，28，38，40），该新节点没有过饱和，删除元素过程结束。其实这里也很好理解，因为删除33后该节点只剩2个元树最多只能分割3个子树。
实例4
从叶节点（47，50，53）中删除元素47，删除后该节点的元素数量仍大于2（即ceil(5/2)-1），删除结果结束。
实例5
从叶节点（22，24）删除元素24后该节点的元素数量少于2（即ceil(5/2)-1），需要向父节点借一个元素并与相邻子树（26，28），本例中向上借到了25，使父节点变成（33，44），并与右边的相邻子树合并成（22，25，26，28），此时自身和父节点都处于平衡状态。
实例6
实例6是实例5的拓展。节点（38，40）删除了元素40以后，该节点向上借到元素44并于右边的相邻子树合并成节点（38，44，47，50，53），此时该节点过饱和，所以把中间元素47交给父节点，自己分裂成两个节点。
总结
在对B树操作的过程中遵循前面提到的口诀：
如果你遇到的情况不在上面六种实例中，欢迎私信或留言让我补充~
本文地址：https://blog.csdn.net/Jay_Wooz/article/details/107072756