Updates to Sorted Files
Insertion approach:
- find appropriate page for tuple (via binary search)
- if page not full, insert into page
- otherwise, insert into next overflow block with space
Thus, Costinsert = Costone + δw
(where δw = 1 or 2)
Deletion strategy:
- find matching tuple(s)
- mark them as deleted
Cost depends on selectivity of selection condition
Thus, Costdelete = Costselect + bqw
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}