1procedure insert(tree, key)
2 find leaf node for key
3 insert key into leaf
4 if leaf has overflow (> max keys)
5 split node
6 median key moves to parent
7 left keys ← left child
8 right keys ← right child
9 if parent overflows, split recursively
10 if root splits, create new root