b-tree - 节点拆分时，B-tree 节点中的键是否重复？

Question

当 B 树中的一个节点被分裂时，来自原始节点的键是否在新节点中重复？这样做的目的是什么？这不是低效吗？

Answer 1

不，这一切都是用指针完成的。一半的指针被移动到新节点。

当然，没有“B-tree”这样的东西。有无数不同的实现。我可以想象其中键实际上存储在节点中的一种，例如键是整数的树。但它们仍然不会被“复制”，只是复制的数据。

如果你的牛肉是节点中留下的被拆分的存储，那么无论是否释放和重新分配更小，这都是另一个优化选择。可能不会，因为更多的插入可能会到达该节点的 1/2 键空间。

Answer 2

我认为您的意思是B +树。

在我编写的 B+ 树中，我确实在拆分期间复制了父节点中的键值。父节点中的 key[pos] 被设置为左节点的最小值并指向左节点。右节点的最小值成为父节点中的 key[pos+1]。