btree插入的一个特殊问题

Question

我一直在玩slady.net上非常酷的btree小程序.我无法理解特定的行为.看看这个起始状态:

通过插入以下序列得到该特定状态:10,15,30,16,70,1,9,27,45,50,55.

我的问题是当我在序列中插入下一个值时,[45,]节点会发生什么,65.

[55,70]节点将被65分割,并且作为中间值,65将返回,然后分割[30,50]节点.我的问题是:为什么[45,]节点最终成为[30,]节点的子节点？它的父母最初有3个孩子,最左边和最右边成为新的单独节点.45是在这些值之间,似乎它最终也可以在[65,]节点下结束......为什么？

Answer 1

一张图片胜过千言万语; 一部动画价值百万：

这里要注意的关键是，当中心节点 50 被拉起时，它必须丢弃它的右子节点，因为它太靠下了。然而，65 需要一个新的左子节点，因此 50 将 45 移交给 65。50 现在需要一个新的右子节点，并且包含 65 的节点需要创建子节点，因此它将新形成的 65 代替。

下面说明了 B 树插入规则（其中最大节点大小为 4 个项目，5 个子节点）：

xr如果您插入叶子（您首先要做的），则不会存在并且无关紧要。但是，如果您必须将一个节点分成两半，则 newx是您拉出的中心项目，而 newxr是的右子节点x。