Insertion into a B-Tree

To insert X:

1. Use search procedure to find leaf node where X should be added.

2. add X to this node at the appropriate place among the values.

3. if there are <= M-1 values, we are done! Otherwise, the node has overflowed. To repair, split the node into 3 parts:
   • Left: first (M-1)/2 values
   • Middle: value at position 1+(M-1)/2
   • Right: last (M-1)/2 values

   Left and Right have just enough values: make them into nodes. They become the left and right children of Middle, which we add in the appropriate place in this node's parent.

   If the parent overflows, we repeat the procedure.

   If the root overflows: we create a new root with Middle as its only value and Left and Right as its children.