insert tuple into page P
find location for new entry in index file
   // could check whether it already exists
insert new index entry (k,P+i) into index file 
   // P+i is tupleID = (PageID + offset within page)

Problem: order of index entries must be maintained

• need to avoid overflow pages in index
• so we need to reorganise index file

On average, this requires us to read/write half of index file.

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