【数据库】B树和B+树的插入删除的实现过程

在总结B树和B&＃43;树插入和删除的过程之前&＃xff0c;首先要明确一下B树和B&＃43;树的几个性质&＃xff1a;

• 对于B树和B&＃43;树的根节点都至少有一个根节点&＃xff1b;
• 对于B树和B&＃43;树的非根节点元素&＃xff0c;每个节点中的关键字的个数的范围为&＃xff1a;&＃xff08;假设一个m阶的B/B&＃43;树&＃xff09;[m/2&＃xff0c;m-1]。&＃xff08;闭区间&＃xff09;
• 对于每个节点中的关键字都按照升序进行排列。
• 对于B树&＃xff0c;每个关键字的左子树中的所有关键字都小于它&＃xff0c;而右子树中的所有关键字都大于它。
• 对于B树&＃xff0c;所有叶子结点都位于同一层&＃xff0c;或者说根结点到每个叶子结点的长度都相同。

除此之外B&＃43;树还有如下性质&＃xff1a;

• B&＃43;树包含2种类型的结点&＃xff1a;内部结点&＃xff08;也称索引结点&＃xff09;和叶子结点。根结点本身即可以是内部结点&＃xff0c;也可以是叶子结点。根结点的关键字个数最少可以只有1个。

• B&＃43;树与B树最大的不同是内部结点不保存数据&＃xff0c;只用于索引&＃xff0c;所有数据&＃xff08;或者说记录&＃xff09;都保存在叶子结点中。

• m阶B&＃43;树表示了内部结点最多有m-1个关键字&＃xff08;或者说内部结点最多有m个子树&＃xff09;&＃xff0c;阶数m同时限制了叶子结点最多存储m-1个记录。

• 内部结点中的key都按照从小到大的顺序排列&＃xff0c;对于内部结点中的一个key&＃xff0c;左树中的所有key都小于它&＃xff0c;右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

• 每个叶子结点都存有相邻叶子结点的指针&＃xff0c;叶子结点本身依关键字的大小自小而大顺序链接。

在一下插入和删除的分析中&＃xff0c;以一颗5阶的B树为例来进行分析&＃xff1a;

插入

假设现在给定一组数据&＃xff1a;39&＃xff0c;22&＃xff0c;97&＃xff0c;41……等一系列数据&＃xff0c;要将他们插入这棵5
阶的B树中。
首先&＃xff0c;根据该B树为5阶&＃xff0c;可知每个非根节点的关键字个数的范围为&＃xff1a;[2,4]&＃xff0c;即每个非根节点的关键字数必须大于等于二且小于等于4。这一系列数据的插入过程分析如下&＃xff1a;

• 对于前4个数据&＃xff0c;可以直接插入到根节点作为关键字&＃xff0c;因为其数量不大于4。其中&＃xff0c;每插入一个数据之后的关键字都按照升序进行排列。
• 当插入第五个数据时&＃xff0c;因为直接插入到根节点关键字数量已经不符合范围要求&＃xff0c;这时还是将这5个树升序排列&＃xff0c;并从他们的“中位数”将这一串关键字分裂开&＃xff0c;即分为一个根节点和两个非根节点。&＃xff08;如果最大关键字数量为奇数&＃xff0c;当关键字数量超过变成偶数时&＃xff0c;则选择中位数中的其中之一作为根节点分开即可&＃xff09;
• 对于之后插入的数据&＃xff0c;根据数据的的大小判断应插入到哪一个叶节点中&＃xff0c;并判断当前插入到的节点中的关键字数量是否超过范围。
• 如果超过范围&＃xff0c;则按照第二步中“分裂”的方法&＃xff0c;并将当前分裂出的父节点归结到根节点中。
• 继续按照上述方法插入&＃xff0c;如果根节点的关键字个数也超过4时&＃xff0c;这时继续“分裂”&＃xff0c;也就产生了第一层非根节点。
• 之后的插入以此类推。

删除

仍然以一个5阶B树为例分析其删除节点的过程&＃xff0c;假设给定一个要删除的结点&＃xff1a;

• 若当前节点不存在&＃xff0c;则找不到该节点&＃xff0c;删除失败。
• 如果当前节点为叶节点&＃xff0c;并且当前节点的关键字个数大于2&＃xff08;m/2&＃xff09;&＃xff0c;说明删除节点后的关键字个数仍符合范围要求&＃xff0c;所以直接删除&＃xff0c;删除节点结束。
• 如果删除后的关键字个数不符合范围要求&＃xff0c;此时需要向兄弟节点“借”一个结点&＃xff0c;如果兄弟节点删除后的个数符合要求&＃xff0c;则将相邻的关键字“上移”为当前节点的父节点&＃xff0c;对应的父节点下移与删除的结点中的关键字合并&＃xff1b;
• 如果此时兄弟节点的关键字个数“不够借”&＃xff0c;此时需要先删除这个关键字&＃xff0c;然后将该节点中的剩下的关键字与兄弟节点中的关键字&＃xff0c;以及将他们对应的父节点中的关键字“下移”&＃xff0c;将这三者合并为一个结点即可。
• 如果删除的结点是非叶节点&＃xff0c;则用后继key&＃xff08;这里的后继key均指后继记录的意思&＃xff0c;即子节点中第一个大于该节点中key值的关键字&＃xff09;覆盖要删除的key&＃xff0c;然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上&＃xff0c;这个过程和二叉搜索树删除结点的方式类似。

插入

对于B&＃43;树的插入&＃xff0c;和B树的插入过程基本相同&＃xff0c;不同的就是&＃xff0c;当遇到中间key要进行分裂时&＃xff0c;中间的key同时要成为父节点的key和右子树的第一个key。
注意&＃xff1a;
若当前key已经在父节点的key和子节点的key中重复出现过&＃xff0c;则不再作为右节点的第一个key出现&＃xff0c;如下图所示&＃xff1a;

在上图中&＃xff0c;关键字16就是这种情况。

删除

• 若待删除的key不存在&＃xff0c;则删除失败&＃xff0c;删除过程结束。
• 若key对应的结点删除之后key的数量仍满足范围&＃xff0c;则删除结束。
• 若不满足&＃xff0c;则采取向兄弟节点借的方式。若兄弟结点key有富余&＃xff08;大于Math.ceil(m-1)/2 – 1&＃xff09;&＃xff0c;向兄弟结点借一个记录&＃xff0c;同时用借到的key替换父结&＃xff08;指当前结点和兄弟结点共同的父结点&＃xff09;点中的key&＃xff0c;删除结束。否则执行下一步。
• 若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点&＃xff0c;并删除父结点中的key&＃xff08;父结点中的这个key两边的孩子指针就变成了一个指针&＃xff0c;正好指向这个新的叶子结点&＃xff09;&＃xff0c;将当前结点指向父结点&＃xff08;必为索引结点&＃xff09;&＃xff0c;执行第5步&＃xff08;第5步以后的操作和B树就完全一样了&＃xff0c;主要是为了更新索引结点&＃xff09;。
• 之后的操作和B树完全相同。

&＃xff08;在理解两树的插入和删除时最好结合例子来亲身体会&＃xff0c;不然会很难理解&＃xff09;

总结

对于B&＃43;树的删除&＃xff0c;在删除的过程中其实会遇到很多种情况&＃xff0c;但其实需要抓住字关键的一点&＃xff0c;即每删除一个key都要观察当前节点剩下的关键字个数够不够key的数量的最小值&＃xff0c;如果不够&＃xff0c;就需要通过“借”来进行修改&＃xff0c;并需要根据情况修改/替换/删除父节点的key值&＃xff0c;置于进行哪种具体操作&＃xff0c;需要视情况而定&＃xff1b;如果不够兄弟节点的关键字不够借&＃xff0c;则需要选择兄弟节点进行合并&＃xff0c;并修改父节点的关键字。

ps&＃xff1a;总结来自于博文&＃xff1a;
B树和B&＃43;树的插入、删除图文详解