Handling of bucket overflows

1. Open hashing occurs where records are stored in different buckets. Compute the hash function and search the corresponding bucket to find a record.
2. Closed hashing occurs where all records are stored in one bucket. Hash function computes addresses within that bucket. (Deletions are difficult.) Not used much in database applications.
3. Drawback to our approach: Hash function must be chosen at implementation time.
   • Number of buckets is fixed, but the database may grow.
   • If number is too large, we waste space.

   • If number is too small, we get too many ``collisions'', resulting in records of many search key values being in the same bucket.
   • Choosing the number to be twice the number of search key values in the file gives a good space/performance tradeoff.