database - 理解B+树插入

Question

我正在尝试按以下顺序创建一个 B+ 树，

10 20 30 40 50 60 70 80 90 100

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

问题是 root 的第二个 child 有一个节点，我无法修复它。它应该至少有 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)

P.S:我是手工做的，亲手做的，为了理解算法。没有密码!

Answer 1

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

如果你还一头雾水，看这个B+ Tree Simulator .试试吧。