[prev] 45 [next]

Insertion in Heaps

Insertion: new tuple is appended to file (in last page). 

f = openFile(fileName("R"),READ|WRITE);
b = nPages(f)-1;
buf = readPage(f, b);  // request page
if (isFull(buf)) // all slots used
    { b++; clear(buf); }
if (tooLarge(newTup,buf)) // not enough space for tuple
    { deal with oversize tuple }
insertTuple(newTup, buf);
writePage(f, b, buf);  // mark page as dirty & release

Costinsert  =  1r + 1w

Plus possible extra writes for oversize tuples, e.g. PostgreSQL's TOAST files