[prev] 32 [next]

Deletion with Hashing

Similar performance to select:

// delete from R where k = val
// f = data file ... ovf = ovflow file
p = hash(val) % nPages(R)
buf = getPage(f,p)
ndel = delTuples(buf,k,val)
if (ndel > 0) putPage(f,buf,p)
p = ovFlow(buf)
while (p != NO_PAGE) {
    buf = getPage(ovf,p)
    ndel = delTuples(buf,k,val)
    if (ndel > 0) putPage(ovf,buf,p)
    p = ovFlow(buf)
}

Extra cost over select is cost of writing back modified blocks.

Method works for both unique and non-unique hash keys.