What Are The Causes Of Bucket Overflow In A Hash File Organization? W

1.	What Are The Causes Of Bucket Overflow In A Hash File Organization? What Can Be Done To Reduce The Occurrence Of Bucket Overflows?
Answer» The causes of bucket overflow are :- Our estimate of the number of records that the relation will have was toolow, and hence the number of buckets allotted was not sufficient. Skew in the distribution of records to buckets. This may happen either becausethere are many records with the same search key value, or becausethe the hash function CHOSEN did not have the desirable properties of uniformityand randomness. To reduce the occurrence of OVERFLOWS, we can :- Choose the hash function more carefully, and make better ESTIMATES of therelation size. If the ESTIMATED size of the relation is nr and number of records per block isfr, allocate (nr/fr) ∗ (1 + d) buckets instead of (nr/fr) buckets. Here d is afudge factor, typically around 0.2. Some space iswasted: About 20 percentof the space in the buckets will be empty. But the benefit is that some of theskew is handled and the probability of overflow is reduced. The causes of bucket overflow are :- To reduce the occurrence of overflows, we can :-

What Are The Causes Of Bucket Overflow In A Hash File Organization? What Can Be Done To Reduce The Occurrence Of Bucket Overflows?

Answer»

The causes of bucket overflow are :-

Our estimate of the number of records that the relation will have was toolow, and hence the number of buckets allotted was not sufficient.
Skew in the distribution of records to buckets. This may happen either becausethere are many records with the same search key value, or becausethe the hash function CHOSEN did not have the desirable properties of uniformityand randomness.

To reduce the occurrence of OVERFLOWS, we can :-

Choose the hash function more carefully, and make better ESTIMATES of therelation size.
If the ESTIMATED size of the relation is nr and number of records per block isfr, allocate (nr/fr) ∗ (1 + d) buckets instead of (nr/fr) buckets. Here d is afudge factor, typically around 0.2. Some space iswasted: About 20 percentof the space in the buckets will be empty. But the benefit is that some of theskew is handled and the probability of overflow is reduced.