Properties

  • All leaves at same depth
  • Node has between ⌈M/2⌉ and M-1 keys (root exception)
  • Keys in each node are sorted
Advertisement

Insert with split

Insert into leaf. If node overflows (M keys), split: middle key promotes to parent, node splits in two. Recurse up.

Advertisement

Delete with merge/redistribute

Remove key. If node underflows, redistribute with sibling or merge two nodes into one. Recurse up.

Why disk-friendly

Each node = one page (4KB, 8KB). M can be hundreds. Height ≈ 3-4 for millions of records. Random reads dominate cost.