What will this B-tree look like?

Question

The B-tree is of order 4, meaning that a node can hold 4 pointers, and 3 keys.

The following is inserted: A G I Y

Since they can't all fit in one node, I know that the node will split. So I know there's going to be a root node with 2 child nodes after these things are inserted, but I don't know exactly what they'll look like.

Answer 1

A

A is inserted

AG

G is inserted

AGI

I is inserted

  G
 / \
A   I

While inserting Y the node is full, split into 2 nodes and pass up the middle, G

  G
 / \
A   IY

Y is inserted