Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 13: Problem 36

Write pseudocode for the insertion algorithms for linear hashing and for extendible hashing.

Short Answer

Expert verified
The pseudocode for linear hashing involves calculating the hash index, checking if it falls within the table's range, and handling situations where splitting is required. Extendible hashing involves initializing a directory with one bucket, checking if inserted keys can fit or if the bucket can be split, handling instances where the directory cannot contain additional pointers, and adjusting if the hash function distributes keys unevenly.

Step by step solution

01

Linear Hashing Pseudocode

1. Start with an initial array of fixed size, usually of size M.\n2. For a new entry, calculate the hash index using a predetermined hash function.\n3. If the hash index is within the current range of the table and the bucket at the hash index is not full, insert the item there.\n4. If the bucket at the hash index is full, split the next bucket that hasn't been split yet and redistribute the items between the old and new buckets.\n5. If all buckets up to the current boundary have been split, double the size of the hash table and start splitting the buckets again from the beginning.
02

Extendible Hashing Pseudocode

1. Initialize directory with one bucket, holding all the keys.\n2. When a key is to be inserted and the bucket is full, see if the bucket can split.\n3. If bucket can split, create a new bucket and redistribute keys.\n4. If bucket cannot split because the directory referencing it cannot contain additional pointers, double the directory size. Hence, all buckets can now split using the additional least-significant bit.\n5. If any bucket, even after splitting, cannot fit the key, it means the hash function is distributing keys unevenly. A different hash function or mechanism may be needed.

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!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

What are mixed files used for? What are other types of primary file organizations?

Suppose that a disk unit has the following parameters: seek time \(s=20\) msec; rota tional delay \(r d=10 \mathrm{msec} ;\) block transfer time \(b t t=1 \mathrm{msec} ;\) block size \(B=2400\) bytes; interblock gap size \(G=600\) bytes. An EMPLOYEE file has the following fields: \(\mathrm{SSN}, 9\) bytes; LASTNAME, 20 bytes; fIRSTNAYE, 20 bytes; MIDOLE INIT\(, 1\) byte; BIRTHOATE, 10 bytes; ADDRESS, 35 bytes; PHONE, 12 bytes; SUPERVISORSSN, 9 bytes; DEPARTMENT, 4 bytes; JOBCODE, 4 bytes; deletion marker, 1 byte. The EMPLOYEE file has \(r=30,000\) records, fixed-length format, and unspanned blocking. Write appropriate formulas and cal. culate the following values for the above eMPLoyee file: a. The record size \(R\) (including the deletion marker), the blocking factor \(b f r,\) and the number of disk blocks \(b\) b. Calculate the wasted space in each disk block because of the unspanned orga nization. c. Calculate the transfer rate \(t r\) and the bulk transfer rate brr for this disk unit (see Appendix B for definitions of tr and btr). d. Calculate the average number of block accesses needed to search for an arbitrary record in the file, using linear search. e. Calculate in msec the average time needed to search for an arbitrary record in the file, using linear search, if the file blocks are stored on consecutive disk blocks and double buffering is used. f. Calculate in msec the average time needed to search for an arbitrary record in the file, using linear search, if the file blocks are not stored on consecutive disk blocks. g. Assume that the records are ordered via some key field. Calculate the average number of block accesses and the average time needed to search for an arbitrary record in the file, using binary search.

Why are disks, not tapes, used to store online database files?

Suppose we want to create a linear hash file with a file load factor of 0.7 and a block. ing factor of 20 records per bucket, which is to contain 112,000 records initially. a. How many buckets should we allocate in the primary area? b. What should be the number of bits used for bucket addresses?

A PARTS file with Part* as hash key includes records with the following Part* val. ues: 2369,3760,4692,4871,5659,1821,1074,7115,1620,2428,3943,4750 \(6975,4981,9208 .\) The file uses eight buckets, numbered 0 to 7. Each bucket is one disk block and holds two records. Load these records into the file in the given order, using the hash function \(h(K)=K \bmod 8 .\) Calculate the average number of block accesses for a random retrieval on Part#.
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Systems

Read Explanation

Computer Network

Read Explanation

Big Data

Read Explanation

Theory of Computation

Read Explanation

Algorithms in Computer Science

Read Explanation

Issues in Computer Science

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free