Chapter 13: Problem 29

Load the records of Exercise 13.27 into an expandable hash file, using linear hash. ing. Start with a single disk block, using the hash function \(h_{0}=K \bmod 2^{0},\) and show how the file grows and how the hash functions change as the records are inserted. Assume that blocks are split whenever an overflow occurs, and show the value of \(n\) at each stage.

Short Answer

Expert verified

The hash file starts with a single disk block and the hash function \(h_{0}=K \mod 2^{0}\). With each record's insertion, the hash function is applied, the file grows, the value of \(n\) increases by one, and if overflows occur, the block is split and hash function is adjusted. Repeat these steps until all records are inserted.

Step by step solution

Initialization

Begin with an empty hash table and a single disk block, and define the hash function \(h_{0} = K \mod 2^{0}\). The parameter \(n\) has the initial value 0, which is equivalent to the number of disk blocks.

Insert the First Record

Insert the first record in the table. Apply the hash function \(h_{0}\) on the key of the record. Since \(h_{0}\) function is \(K \mod 2^{0}\), any number modulo 1 is always 0. Therefore, the first record will go into the initial block. After insertion, \(n\) becomes 1, indicating that one block is in use.

Process of Inserting Subsequent Records and Handling Overflows

For every subsequent record insertion, apply the current hash function. If no overflow happens, simply increase the value of \(n\). If an overflow occurs, proceed to Step 4.

Handle Overflow by Splitting Blocks

Whenever an overflow happens, split the block where the overflow occurred. Create a new disk block, and for the split block and the new block, adjust the hash function. The number \(n\) increases by one each time a block is split.

Repeat the Process

Continue the process of inserting records, adjusting the hash function, managing overflows, and increasing the value of \(n\) each time a record is inserted or a block is split until all records have been inserted.

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Short Answer

Step by step solution

Initialization

Insert the First Record

Process of Inserting Subsequent Records and Handling Overflows

Handle Overflow by Splitting Blocks

Repeat the Process

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Problem Solving Techniques

Theory of Computation

Functional Programming

Big Data

Computer Organisation and Architecture

Computer Network

Study anywhere. Anytime. Across all devices.