B+Tree Indexing

  • Ordered keys, shallow height
  • Data stored in leaves
  • Splits maintain balance
1 / 4

Invariants

  • Sorted keys in each node
  • Leaves linked for range scans
2 / 4

Splits

  • Leaf split promotes first key of right
  • Internal split promotes middle key
3 / 4

What you will build

  • Search
  • Insert with splits
4 / 4
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.