• Static hashing
• Extendable hashing

Extendable Hashing

1. Use i of b bits from hash output, increasing i as needed

   

2. Add a level of indirection: directory of pointers to hash buckets

   

Extendable Hash : Insertion

i number for the bucket: how many times the bucket has been split and how many same bits does each entry in the buckets have

• if no hash bucket overflow:
  • Insert the tuple into the hash bucket
• If a hash bucket overflows:
  • If the hash bucket i == directory i, then
    • Double directory size by copying existing pointers
    • Increase directory i value by 1
  • Else, split the overflowing hash bucket
    • Move tuples in the bucket to the new bucket based on their hash values
    • Update directory pointer
    • Increase the hash bucket i value by 1

Extendable Hash : Deletion

We can simply delete it, but we can also find a more compact way that after the deletion, we can merge the buckets

and if the i number on the buckets are smaller than the directory, we can shrink the directory size by half

Merge Condition

• Hash bucket merge condition
  • Bucket i's are the same
  • First (i-1) bits of the hash key values are the same
• Directory shrink condition
  • All bucket i's are smaller than the directory i

Extendable Hash can't provide minimum space guarantee in case like this. We only has 3 tuples but we have to split 4 times

This can only be solved by choosing a better hash function to make the tuples be more spread out