algorithm - B-树插入 : during the descend in the tree, 为什么我们用 2t-1 个元素拆分每个节点？

Question

在B-tree插入算法中，我看到为了解决我们需要向具有2t-1个元素的叶子插入一个元素的情况，我们需要对树进行 split 算法。我不明白的是为什么在树下降(到愿意点)期间的插入算法中我们用 2t-1 个元素拆分每个节点，即使我看起来没用。例如 example

我知道有一种情况，叶子上方的几个节点有 2t-1 个元素，如果我们想将中值移动到它们，我们会遇到问题，但为什么不为此提供精确的解决方案，而不是每次都做拆分。

如果我说错了请指正。

Answer 1

我们在下降到目标位置的过程中拆分了完整节点，因为我们不知道是否需要“返回”。您可以按照您的想法进行操作，我们向下找到目标节点，将其拆分，然后将拆分的中值插入父节点，根据需要递归拆分节点。但这需要我们从根开始，向下到目标，然后返回，可能一直到根。这可能是不可取的，例如如果访问节点两次会太昂贵。在这种情况下，最好直接向下传递一次，将所有完整节点拆分以预期需要更多空间。

为了演示，您可以尝试将 10 插入绘图中间和底部的树中。底部的树，未 split ，需要像中间树一样一直 split 到根，因为两次通过算法没有留下任何空间。在中间的树中，插入 10 仍然会导致 split ，但不会一直向上延伸，因为树的顶部两层非常宽敞。

不过，有一个重要的警告。设 t 为每个节点的最小子节点数。对于二次通过算法，一个节点可以拥有的最大子节点数至少需要 u = 2t - 1。如果小于，比如2t - 2，那么拆分一个全节点(2t - 3元素)，即使插入额外的元素，也无法使两个非缺陷节点。一次通过算法需要更高的最大值，u = 2t。这是因为两次通过算法总是有一个元素可以恰好抵消一个缺陷。一次通过算法没有这种能力，因为它有时会不必要地 split 节点，所以它不能将它持有的元素粘在其中一个缺陷中。它可能不属于那里。