Chapter 13

Discuss the techniques for allowing a hash file to expand and shrink dynamically. What are the advantages and disadvantages of each?

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

Consider a disk with the following characteristics (these are not parameters of any particular disk unit): block size $B=512$ bytes; interblock gap size $G=128$ bytes; number of blocks per track $=20;$ number of tracks per surface $=400.$ A disk pack consists of 15 double-sided disks. a. What is the total capacity of a track, and what is its useful capacity (excluding interblock gaps)? b. How many cylinders are there? c. What are the total capacity and the useful capacity of a cylinder? d. What are the total capacity and the useful capacity of a disk pack? e. Suppose that the disk drive rotates the disk pack at a speed of 2400 rpm (revolutions per minute $);$ what are the transfer rate $(tr)$ in bytes/msec and the block transfer time $(btt)$ in msec? What is the average rotational delay $(rd)$ in msec? What is the bulk transfer rate? (See Appendix B.) f. Suppose that the average seek time is 30 msec. How much time does it take (on the average) in msec to locate and transfer a single block, given its block address? g. Calculate the average time it would take to transfer 20 random blocks, and compare this with the time it would take to transfer 20 consecutive blocks using double buffering to save seek time and rotational delay.

Suppose that a disk unit has the following parameters: seek time $s=20$ msec; rota tional delay $rd=10\mathrm{msec};$ block transfer time $btt=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 $bfr,$ 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 $tr$ 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.

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)=Kmod8.$ Calculate the average number of block accesses for a random retrieval on Part#.

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=Kmod{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.

Suppose that we have an unordered file of fixed-length records that uses an unspanned record organization. Outline algorithms for insertion, deletion, and modification of a file record. State any assumptions you make.

Suppose that we have an ordered file of fixed-length records and an unordered overflow file to handle insertion. Both files use unspanned records. Outline algorithms for insertion, deletion, and modification of a file record and for reorganizing the file. State any assumptions you make.

Can you think of techniques other than an unordered overflow file that can be used to make insertions in an ordered file more efficient?

Suppose that we have a hash file of fixed-length records, and suppose that overflow is handled by chaining. Outline algorithms for insertion, deletion, and modification of a file record. State any assumptions you make.