Search code examples
b-tree

What will this B-tree look like?


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.


Solution

  • 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