理解B+树插入

Question

我试图创建一个具有以下顺序的B+树，

10 20 30 40 50 60 70 80 90 100

所有索引节点的最小值为2，最大为3键。我可以插入到90，但一旦插入100，它的高度从2增加到3。

问题是根的第二个子节点只有一个节点，我无法修复它。应该至少有两个，对吧？有人能指引我吗？

更新：--我遵循这个算法

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)

P.S:为了理解算法，我用手动的方法。没有密码！

Answer 1

我相信您的B+树是可以的，假设B+树的顺序是3。如果顺序是m，则每个内部节点都可以有⌈m/2⌉到m子节点。在这种情况下，每个内部节点可以有2到3个子节点。在一个B+树中，如果一个节点只有两个子节点，那么它只需要一个键，所以B+树不会违反约束。

如果您仍然感到困惑，请看这个B+ Tree Simulator。试试看。

Answer 2

要获得在插入10到100值后绘制的树，树的顺序必须是4而不是3。否则，给出的答案是正确的: Order 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