分裂B+树根

Question

在拆分b+树的根节点时，我知道您采用n/2 +1，并将新根设置为新根，并相应地拆分所有内容。

我的问题是当n等于一个奇数时。就像在这种情况下，n = 5。

因此，让我们使用一个简单的例子：

   10  20  30  40 
 /   |   |   |   \

所有的孩子都是空的。让我说，我想再加50。

它看起来像

       30
      /  \
(10,20)   (40,50) 

或

           40
          /  \
 (10,20,30)  (50)

或者别的什么？

Answer 1

如果拆分一个包含n键的节点--包括导致拆分的传入键--那么(n - 1) / 2键将转到一个新的子节点，n - 1 - (n - 1) / 2转到另一个子节点，其中一个键上升到父级(作为分隔键)。向上上升的键不一定与导致分裂的键相同。如果分隔符没有位置，那么您将有一个新的根，分隔键将是它的唯一占用率(最低占用率要求不适用于根节点)。

当然，如果您查看取出新分隔符后剩下的部分，则公式看起来更友好：r = n - 1给出了另一边的r / 2，另一边给出了r - r / 2。

换句话说，在正常情况下，两个‘一半’最多是一个不同的，如果总键计数为偶数，则会出现这种情况，因此在取出分隔键时会留下一个奇怪的休息。额外的键是左键还是右键并不重要。

然而，这并不是一成不变的。还有其他有效的重新分配策略，最显著的是*，其中两个完整节点使三个节点已经满了2/3 3rds，依此类推。这还表明，拆分/合并逻辑与不改变结构的重新分配措施密切相关，即兄弟姐妹之间的捐赠和钥匙借用。