b树的删除操作,图解

TheDisguiser 2020-05-27 22:28:36 java常见问答 7133

之前给大家讲解了b树的原理及概念,这次就给大家说一说b树的删除操作该怎么进行吧。

b树删除操作

b树中,删除操作就是,依据key删除记录,如果b树中记录不存在对应key的记录,则删除失败。

删除操作:

1)、假如,现在要删除的key位于非叶子结点上,那么,使用后续记录来覆盖掉要删除的key,再在后继key所在的子支中删除这个后继key。

这个时候,后继key一定会位于叶子结点上。

删除这个记录之后,进行第2步的执行。

2)、假如,这个结点key个数大于等于Math.ceil(m/2)-1,结束删除操作,否则的话就执行第3步。

3)、假如,兄弟结点key个数大于Math.ceil(m/2)-1,那么,父结点中key下移到这个结点,兄弟结点中的一个key上移,删除操作结束。

不然的话,就将父结点中的key下移到和当前结点及它的兄弟结点中的key合并,来形成一个新的结点。

这个时候,原来父结点中的key的两个子节点指针就变成了一个子节点指针,会指向这个新结点。

然后当前结点的指针又指向父结点,重复上第2步。

在某些时候,一些结点它可能即有左兄弟,又有右兄弟,那么,在这样的情况下,就只要任意选择一个来进行操作就可以了。

图解:

b树的删除 图解

以上就是关于b树删除操作的所有内容了,更多相关java常见问答知识,请关注奇Q工具网了解吧。

推荐阅读:

b树索引是什么?有哪些概念?

b树与b+树的区别是什么?各自有什么优点?

b树是二叉树吗?b树是什么树?