tid = insert tuple into page P at position p
find location for new entry in index file
insert new index entry (k,tid) into index file 

Problem: order of index entries must be maintained

• need to avoid overflow pages in index
• either reorganise index file or mark entries

Reogranisation requires, on average, read/write half of index file:

Cost_insert,prim  =  (log₂i)_r + i/2.(1_r+1_w) + (1+Ov)_r + (1+δ)_w