Extendible Hashing
Situation: Bucket (primary page) becomes full. Why not re-organize file by doubling # of buckets?
- Reading and writing all pages is expensive!
- Idea: Use directory of pointers to buckets, double # of buckets by doubling the directory, splitting just the bucket that overflowed!
- Directory much smaller than file, so doubling it is much cheaper. Only one page of data entries is split. No overflow page!
- Trick lies in how hash function is adjusted!
Notes: