[prev] 21 [next]

Hashing

Basic idea: use key value to compute page address of tuple.

[Diagram:Pics/file-struct/hash.png]

e.g. tuple with key = v is stored in page i

Requires: hash function h(v) that maps KeyDomain → [0..b-1].

  • hashing converts key value (any type) into integer value
  • integer value is then mapped to page index
  • note: can view integer value as a bit-string