[prev] 28 [next]

B-Tree Insertion Cost (cont)

Worst case: 2D-1 node writes (propagate to root)
  • traverse from root to leaf, holding nodes in buffers
  • read/write data page
  • update/write leaf, parent and sibling
  • repeat previous step D-1 times
Costinsert  =  Dr + (2D-1)w + 1r + 1w