[prev] 27 [next]

B-Tree Insertion Cost

Insertion cost = CosttreeSearch + CosttreeInsert + CostdataInsert

Best case: write one page (most of time)

  • traverse from root to leaf
  • read/write data page, write updated leaf
Costinsert  =  Dr + 1w + 1r + 1w

Common case: 3 node writes (rearrange 2 leaves + parent)

  • traverse from root to leaf, holding nodes in buffer
  • read/write data page
  • update/write leaf, parent and sibling
Costinsert  =  Dr + 3w + 1r + 1w