Kotidis I., First Exercise Pack 2021-2022.

Question

Consider an extendible hash index, each bucket of which holds N entries. 
What is the probability that an overflowed bucket needs to be dealt with recursively? 
“Dealt with recursively” means that all of this bucket’s records are moved to one of the two new buckets 
that will be created.

Answer 1

In extensible hashing ,given that there are two new buckets are created. so totally there will be 4 buckets.

The probability of all records in one bucket out of four is ¼  or 0.25