[prev] 26 [next]

Selection with Hashing

Best performance occurs for one queries on hash key field.

Basic strategy:

  • compute page address via hash function hash(val)
  • fetch that page and look for matching tuple
  • possibly fetch additional pages from overflow chain
Best Costone  =  1    (find in data page)

Average Costone  =  1+Ov/2    (scan half of ovflow chain)

Worst Costone  =  1+max(OvLen)    (find in last page of ovflow chain)