Insertion Cost
If no split required, cost same as for standard hashing:
Costinsert:
Best: 1r + 1w,
Avg: (1+Ov)r + 1w,
Worst: (1+max(Ov))r + 2w
If split occurs, incur Costinsert plus cost of splitting:
- read block sp (plus all of its overflow blocks)
- write block sp (and its new overflow blocks)
- write block sp+2d (and its new overflow blocks)
On average,
Costsplit = (1+Ov)r + (2+Ov)w
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}