[prev] 40 [next]

Selection with Lin.Hashing

If b=2d, the file behaves exactly like standard hashing.

Use d bits of hash to compute block address. 

// select * from R where k = val
h = hash(val);
P = bits(d,h);  // lower-order bits
for each tuple t in page P
         and its overflow pages {
    if (t.k == val) return t;
}

Average Costone  =  1+Ov