B-树
B-树的概念
对于m阶B-树
1、树中每个结点至多有m棵子树
2、若根结点不是叶子结点,至少有2棵子树
3、除根结点外所有非终端结点至少有m/2向上取整棵子树
4、所有非终端结点的结构为n、A0、K1、A1、......、Kn、An
关键字数量 m/2向上取整 -1 ≤ n ≤ m-1 且关键字从小到大有序排列
5、所有叶结点在同一层次上,且不含有任何信息
B-树如图
B-树的查找
从根结点出发,沿指针搜索结点和在结点内进行顺序(或折半)查找两个过程交叉进行;
若查找成功,则返回指向被查关键字所在结点的指针和关键字在结点中的位置;
若查找不成功,则返回插入位置;
如在上图中查找47,在根结点中找到35右边的指针域,再从35右边指针域所指结点中找到43 和 78中间的指针域,在其所指向的结点中找到47
B-树的插入
B-树的插入是查找失败返回插入位置后插入的,因此是在底层某个非终端结点上添加一个关键字,若插入后关键字个数不超过m-1,则插入完成,若达到m个,则将第n/2向上取整 - 1 个关键字插入到父结点,然后调整。
如在该图上插入30,即在37左边插入,因为是3阶B-树,没有达到m,不用调整,得到下图、
在往图上插入26,在30左边插入,因为达到了m,因此分裂,将30插入到父结点,此时父结点未达到m,接着调整树,得到下图
B-树的删除(难点)
-
若删除的关键字是底层上的
-
若删除后关键字个数大于 m/2向上取整-1,直接删
-
若删除后关键字个数小于m/2向上取整-1,不能直接删,若兄弟结点关键字数目大于m/2向上取整-1,借兄弟的结点
-
若兄弟结点也小于m/2向上取整-1,双亲结点中关键字和兄弟结点关键字合并,再调整
将兄弟结点67插入到父结点,再将53调整下来,完成对50的删除
此时删除53,因为兄弟结点中不能借,所以将父结点中的关键字和兄弟结点关键字合并,如图
- 若删除的关键字不是底层上的
若删除非底层结点中的关键字Ki,则可以指针Ai所指子树中的最小关键字X替代Ki,这个X在最底层结点上,然后,再删除关键字X,即转为第一种情形
找到45右边子树的最小关键字(因为该关键子比左子树上的都大,同时比右子树上的都小),替换45,然后45到达了底层,用上面的三个方法删除即可