Algorithm

  1. Traverse as if doing a lookup to find the target leaf node 29:28 29:48.
  2. If the leaf has space → insert in sorted order. Done 29:48.
  3. If it is full → split: create a new node, move half the keys there, keep half 29:48 30:43.
  4. Promote the smallest key of the new right node into the parent as a new guide post 31:07.
  5. If the parent is now full → split it too, recursively up the tree 30:17 32:35.
  6. If the root splits → pick its middle key, push it into a brand-new root one level above. This is the only way the tree grows in height 33:10 34:01.
flowchart TD
    A[Insert key K] --> B[Traverse to leaf]
    B --> C{Leaf has space?}
    C -->|yes| D[Insert in sorted order — done]
    C -->|no| E[Split leaf: half keys to new node]
    E --> F[Promote smallest key of new node to parent]
    F --> G{Parent full?}
    G -->|no| D
    G -->|yes| H[Split parent recursively]
    H --> I{Was it the root?}
    I -->|no| G
    I -->|yes| J[Push middle key into a new root — height +1]

Worked examples from the lecture

  • Insert 6 into a full leaf holding 5, 9, 10 → split, keep 5 (and now 6) on the left, move 9 and 10 right, then promote 9 to the inner node as the new separator 30:43 31:07.
  • Insert 8 → 8 < 9, lands in the left leaf, plenty of room, done. No structural change 31:39.
  • Insert 17 into a larger tree → fits, no issue. Insert 16 → leaf full → split → parent full → split parent → root full → promote 13 into a new root, creating a new level 31:58 32:21 33:10 33:30.

Details worth remembering

  • Where do you split? In the middle. "There's no magic to it" 34:42.
  • Because leaves have no parent pointers, a split never has to touch the untouched side of the tree — those children don't know or care who their parent is 34:18.