浅析B-树分裂

一、B-树的定义（适合查找的平衡的多叉树。）
一颗M阶（M>2）的B-树，是一颗平衡的M路平衡搜索树，可以是空树或者满足B-树的性质

二、B-树的性质？
(1) 根节点至少有两个孩子
(2) 每个非根节点至少有M/2（上取整）个孩子，至多有M个孩子
(3) 每个非根节点至少有M/2-i个关键字，至多有M-1个关键字，并且以升序排列
(4) key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
(5) 所有叶子节点都在同一层

三、B-树分裂图示
给定一组数：{12 45 9 78 60 55 58}
(1) 先插入12

(2) 再插入45

(3) 插入9

(4) 插入78

(5) 插入60

(6) 插入55

(7) 插入58

四、B-树的基本操作
1、 创建
2、 插入
（1） 若B树的根为空，则直接插入（new上一个新的节点，插入，更新size ）
（2）0当B树不为空时
a、在B树中查找插入位置的key，若找到则不插入返回；若没找到，则插入到叶子结点。
b、检测当前插入节点是否满足B树的性质,若满足则返回，不满足时则需要分裂。（分裂如上所示）

3、查找（主要查找两个方向：一是找key在不在；二是若key不在则找位置）
（1）从B树的根节点开始查找（中序遍历查找或者折半查找），若找到则返回；若无则进行下一步
（2）找不到key值时，则需要将key与节点中的key值作比较，小于节点的key值时，则往左子树里面查找；若大于时，往右子树里 面找。一直重复下去，最后返回需要插入的位置。

注意点：搬移元素的时候，孩子节点会比关键字多搬移一个元素
1

代码没有附上，读者可自行编写！！！