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

Question

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

Answer 1

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

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

如果你的问题是遗留在被分割的节点中的存储，那么，这是另一个优化选择，无论是否释放和重新分配更小的空间。可能不会，因为可能会有更多的插入进入该节点的1/2的键空间。

Answer 2

我想你是指一棵B+树。

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