java - 当你从 B-Tree 中拆分一个节点并且它的顺序是奇数时，你如何平均分配键？

Question

当您拆分一个 5 阶的节点时，您将拥有 4 个密钥，因此您可以均匀分布，但是当节点具有奇数个密钥时，事情就不会如此均匀地分布。有什么帮助吗？

Answer 1

Go read Wikipedia article. It describes this exactly:

If this number is odd, then U=2L and one of the new nodes contains (U−2)/2 = L−1 elements, and hence is a legal node, and the other contains one more element, and hence it is legal too. If U−1 is even, then U=2L−1, so there are 2L−2 elements in the node. Half of this number is L−1, which is the minimum number of elements allowed per node.

http://en.wikipedia.org/wiki/B-tree