Hashing

Question 1

what is a bucket?

Answer 1

A unit of storage that holds one or more records with the same hash value, typically a disk block

Question 2

what is static hashing? pros and cons

Answer 2

static hashing maps search values to a fixed set of buckets

pros:

cons:
can be wasteful if we have too many buckets
can be slow if we have to use overflow buckets to make up for small size

Question 3

how are static bucket numbers determined? what’s fudge?

Answer 3

number of buckets = (num records/num records can fit per bucket) x (1+d)

fudge is d
d = is a fudge factor that reduces risk of overflow by allowing for 20% waste

Question 4

what is chaining?

Answer 4

when we have overflow we can link buckets together to increase the size

Question 5

how does a static hashing scheme grow?

Answer 5

have to rehash everything with a new hash function.
if we chose a hash based on the current bucket sizes we’re going to have back performance as the buckets grow
if we anticipate we waste space

Question 6

what is dynamic hashing?

Answer 6

allows the database to grow and shrink by splitting and coalescing buckets, retaining space efficiency
a hash function generates values over a large range of typically 32 bit integer, and we only use a few bits of it at a time

the first i bits of the hash are used as an index n into the BAT (bucket address table)