7

我正在尝试使用以下序列创建 B+ 树，

10 20 30 40 50 60 70 80 90 100

所有索引节点应该有最少 2 个和最多 3 个键。我能够插入到 90，但是一旦插入 100，它就会将高度从 2 增加到 3。

问题是 root 的第二个孩子有一个节点，我无法修复它。它应该至少有2个，对吧？有人可以指导我吗？

更新：我正在遵循这个算法

If the bucket is not full (at most b - 1 entries after the insertion), add the record.
Otherwise, split the bucket.
Allocate new leaf and move half the bucket's elements to the new bucket.
Insert the new leaf's smallest key and address into the parent.
If the parent is full, split it too.
Add the middle key to the parent node.
Repeat until a parent is found that need not split.
If the root splits, create a new root which has one key and two pointers. (That is, the value that gets pushed to the new root gets removed from the original node)

PS：我正在手动进行，以了解算法。没有代码！

4

2 回答 2

5

我相信你的 B+ 树没问题，假设你的 B+ 树的顺序是 3。如果顺序是m，每个内部节点可以有⌈m/2⌉到m个子节点。在您的情况下，每个内部节点可以有 2 到 3 个子节点。在 B+ 树中，如果一个节点只有 2 个子节点，那么它只需要 1 个键，因此 B+ 树不会违反任何约束。

如果你仍然困惑，看看这个B+ Tree Simulator。试试看。

于 2013-04-17T18:31:57.273 回答
0

要在插入值 10 到 100 后获得您绘制的树，树的顺序必须是 4 而不是 3。否则给出的答案是正确的：顺序 m 允许在每个叶子和每个节点中有 m-1 个键。在那之后，维基百科的描述变得有点混乱，因为它专注于孩子而不是键，并且没有提到如何处理四舍五入。只处理键，规则是：

Max keys for all nodes = Order-1
Min keys for leaf nodes = floor(Order/2)
Min keys for internal nodes = floor(maxkeys/2)

所以你在节点中有一个键是正确的（order=4，max=3，minleaf=2，minnode=1）。您可能会发现此页面很有用，因为它具有在线 JavaScript 版本的流程以及插入和删除的文档：

http://goneill.co.nz/btree.php

于 2013-04-24T02:19:47.670 回答