B+ Tree

Insertion

• STEP 1 Find correct leaf L
• STEP 2 Try to put (key, pointer) pair into L
  STEP 2a If L has enough space, then put it here Else, split L (into L and a new node L2)
  STEP 2b Redistribute L's entries evenly between L and L2
  STEP 2c Copy up the middle key, i.e., recursively insert middle key into parent of L and add a pointer from L's parent to L2
• STEP 3 When inserting into an internal node V:
  STEP 3a If V has enough space, then put it here Else, split V (into V and a new node V2)
  STEP 3b Redistribute V's entries evenly between V and V2
  STEP 3c Move up the middle key. (Contrast this with leaf splits.)
• STEP 4 Splits "grow" the tree by making it wider. If the root splits, the tree increases in height by one.

Program

Output