了解B +树插入

Question

我正在尝试使用以下顺序创建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:我手动手动操作,以了解算法.没有代码!

Answer 1

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

如果你仍然感到困惑,请看看这个B+ Tree Simulator.试试吧.