快速了解B+树的插入、删除操作

B+树非常的复杂,这里不进行详细的讲解,只对基本的插入删除操作进行说明。

在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶节点中,各叶节点用指针连接。因此在进行插入删除操作时,要进行调整,维持其平衡性。

我们先来看一个B+树,其高度为2,每页可存放4条记录,扇出(fan out)为5,可以理解成5阶多叉树。

可以看出,所有记录都在叶节点中,并且是顺序存放的,如果我们从最左边的叶节点开始顺序遍历,可以得到所有键值的顺序排序:5、10、15、20、25、30、50、55、60、65、75、80、85、90。

1、插入

B+树的插入必须保证插入后叶节点中的记录依然排序,同时需要考虑插入B+树的三种情况,每种情况都可能会导致不同的插入算法,如表5-1所示。

我们用实例来分析B+树的插入,我们插入28这个键值,发现当前Leaf Page和Index Page都没有满,我们直接插入就可以了。

这次我们再插入一条70这个键值,这时原先的Leaf Page已经满了,但是Index Page还没有满,符合表5-1的第二种情况,这时插入Leaf Page后的情况为50、55、60、65、70。我们根据中间的值60拆分叶节点。

因为图片显示的关系,这次我没有能在各叶节点加上双向链表指针。最后我们来插入记录95,这时符合表5-1讨论的第三种情况,即Leaf Page和Index Page都满了,这时需要做两次拆分。

可以看到,不管怎么变化,B+树总是会保持平衡。但是为了保持平衡,对于新插入的键值可能需要做大量的拆分页(split)操作,而B+树主要用于磁盘,因此页的拆分意味着磁盘的操作,应该在可能的情况下尽量减少页的拆分。因此,B+树提供了旋转(rotation)的功能。

旋转发生在Leaf Page已经满了、但是其左右兄弟节点没有满的情况下


可以看到,采用旋转操作使B+树减少了一次页的拆分操作,而这时B+树的高度依然还是2。

2、删除


a)初始状态

b)删除22

c)删除15

删除后当前结点只有一个key,不满足条件,而兄弟结点有三个key,可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9,删除结束。

d)删除7

当前结点关键字个数小于2,(左)兄弟结点中的也没有富余的关键字(当前结点还有个右兄弟,不过选择任意一个进行分析就可以了,这里我们选择了左边的),所以当前结点和兄弟结点合并,并删除父结点中的key,当前结点指向父结点。

此时当前结点的关键字个数小于2,兄弟结点的关键字也没有富余,所以父结点中的关键字下移,和两个孩子结点合并,结果如下图所示。

参考资料:
[1].B+树介绍 
https://www.cnblogs.com/wade-luffy/p/6292784.html#_label0_1
[2].B树和B+树的插入、删除图文详解 https://www.cnblogs.com/nullzx/p/8729425.html

发表评论

电子邮件地址不会被公开。