What are the causes of bucket overflow in a hash file, Database Management System

Assignment Help:

What are the causes of bucket overflow in a hash file organization? What can be done to reduce the occurrence of bucket overflow?

When a record is inserted, the bucket to that it is mapped has space to store the record. If the bucket does not have sufficient space, a bucket overflow is said to occur.

Bucket overflow can occur for various reasons:

Insufficient buckets: The number of buckets, that we indicate nb, must be chosen such than nb>nc/ff, where n, denote the total number of records that will be stored, and fr denotes the number of records in which will fit in a bucket. This designation, of course, supposes that the total number of records is known while the hash function is chosen.

Skew : Some buckets are assigned more records than are others, so a bucket might overflow even while other buckets still have space. This situation is known as bucket skew.

Skew can occur for two reasons:
1. Multiple records might have the same search key.
2. The chosen hash function may result in non-uniform distribution of search keys.
So, that the probability of bucket overflow is reduced, the number of buckets is selected to be (n/f)*(1+d), where d is a fudge factor typically around 0.2. Some space is wasted:r r

About 20 percent o the space in the buckets will be empty. But the advantages are that the probability of overflow is decreased.
Despite allocation of a few more buckets than needed, bucket overflow can still occur. We handle bucket overflow through using overflow buckets. If a record must be inserted into a bucket b, and b is already full, the system gives an overflow bucket for b, and inserts the record within the overflow bucket, and so on.

All the overflow buckets of a given bucket are chained together in a linked list. Overflow handling using like linked list is known as overflow chaining.


Related Discussions:- What are the causes of bucket overflow in a hash file

What do you understand by raid, What do you understand by RAID? Explain RA...

What do you understand by RAID? Explain RAID Level 4 and Level5? RAID - It is stands for Redundant Array of Inexpensive Disks (as named by the inventor), or alternatively Re

Multi-list file organisation, Multi-list file Organisation Multi-list f...

Multi-list file Organisation Multi-list file organisation is a multi-index linked file organisation. A linked file organisation is a logical organisation where physical orderin

Unix System Administration, What Command You Use What Day of the week were ...

What Command You Use What Day of the week were you born

Obtain the house numbers street wise from database, For the relations answe...

For the relations answer the following queries in SQL Street (name, location, city) House (number, street_name) Lives (name, house_number) (i) Obtain the names of persons who liv

Distributed query and transaction processing, a.  Construct a query around ...

a.  Construct a query around any one of the functional divisions you made in 4a such that if executed in the distributed design of 4 would require reconstruction of at least two ho

Explain weak and strong entity sets, Explain weak and strong entity sets? ...

Explain weak and strong entity sets? Weak and Strong entity sets: A physically powerful entity set has a primary key. All tuples in the group are distinguishable through that k

Farm management system, draw er diagram using entities crop,employee,depart...

draw er diagram using entities crop,employee,department,plot,cultivation plan,machinery,seed,fertilizer

Er schema, Consider entity type Employee with attributes empNumber (this is...

Consider entity type Employee with attributes empNumber (this is unique), empName, and the year when he/she was hired. An employee can either be a technical employee, a marketing e

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd