No.

Assuming you are talking about Extendable Hash Index, the maximum number of buckets (not "bucket directories") is 2^M, where M is a pre-determined value. In the exercise M is 4, so the max number of buckets is 16.

We always start with 1 bucket in the bucket directory and 1 index block when the index is empty, and the "depth" of the bucket directory (i.e. global depth) and the depth of each block (i.e. local depth) both start from 0. When an index entry is to be inserted into a block that is already full, the block splits and the local depth is incremented by 1. If the resulting local depth is greater than the current global depth, the global depth is also incremented by 1, which means the number of buckets will double.

jcalilu wrote:

cysun wrote:

No.

Assuming you are talking about Extendable Hash Index, the maximum number of buckets (not "bucket directories") is 2^M, where M is a pre-determined value. In the exercise M is 4, so the max number of buckets is 16.

We always start with 1 bucket in the bucket directory and 1 index block when the index is empty, and the "depth" of the bucket directory (i.e. global depth) and the depth of each block (i.e. local depth) both start from 0. When an index entry is to be inserted into a block that is already full, the block splits and the local depth is incremented by 1. If the resulting local depth is greater than the current global depth, the global depth is also incremented by 1, which means the number of buckets will double.

If we double the amount of blocks due to an overflow, does the hash function remain the same?

Also, I noticed that the max number of buckets is 16. So when we have 16 buckets and need to double the size again, what happens?

 

1. The hash function always remains the same.

2. Once the max number of buckets is reached (or in other words, the max depth is reached), there's no more splitting - if a block is full, just attach an overflow block to it.