91Ó°ÊÓ

Discuss the techniques for allocating file blocks on disk.

What is the difference between a file organization and an access method?

What is the difference between static and dynamic files?

What are the typical record-at-a-time operations for accessing a file? Which of these depend on the current record of a file?

Discuss the advantages and disadvantages of using (a) an unordered file, (b) an ordered file, and (c) a static hash file with buckets and chaining. Which operations can be performed efficiently on each of these organizations, and which operations are expensive?

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

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 \((t r)\) in bytes/msec and the block transfer time \((b t t)\) in msec? What is the average rotational delay \((r d)\) 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 \(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.

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

Can you think of techniques other than chaining to handle bucket overflow in external hashing?