Chapter 16: Disk Storage, Basic File Structures, and Hashing
1
CHAPTER 16: DISK STORAGE, BASIC FILE STRUCTURES, AND HASHING
Answers to Selected Exercises
16.27 – 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 is the total capacity and the useful capacity of a cylinder?
(d) What is the total capacity and the useful capacity of a disk pack?
(e) Suppose the disk drive rotates the disk pack at a speed of 2400 rpm
(revolutions per minute); what is the transfer rate 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 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 it with the time it would take to transfer 20 consecutive blocks using
double buffering to save seek time and rotational delay.
Answer:
(a) Total track size = 20 * (512+128) = 12800 bytes = 12.8 Kbytes
(b) Number of cylinders = number of tracks = 400
(f) average time to locate and transfer a block = s+rd+btt = 30+12.5+1 = 43.5 msec
Copyright © 2016 Pearson Education, Inc., Hoboken NJ
16.28 – A file has r=20,000 STUDENT records of fixed-length. Each record has the following
fields: NAME (30 bytes), SSN (9 bytes), ADDRESS (40 bytes), PHONE (9 bytes),
BIRTHDATE (8 bytes), SEX (1 byte), MAJORDEPTCODE (4 bytes), MINORDEPTCODE (4
bytes), CLASSCODE (4 bytes, integer), and DEGREEPROGRAM (3 bytes). An additional
byte is used as a deletion marker. The file is stored on the disk whose parameters are given
in Exercise 17.27.
(a) Calculate the record size R in bytes.
(b) Calculate the blocking factor bfr and the number of file blocks b assuming an
unspanned organization.
(c) Calculate the average time it takes to find a record by doing a linear search on
the file if (i) the file blocks are stored contiguously and double buffering is used,
and (ii) the file blocks are not stored contiguously.
(d) Assume the file is ordered by SSN; calculate the time it takes to search for a
record given its SSN value by doing a binary search.
Answer:
(a) R = (30 + 9 + 40 + 9 + 8 + 1 + 4 + 4 + 4 + 3) + 1 = 113 bytes
(b) bfr = floor(B / R) = floor(512 / 113) = 4 records per block
b = ceiling(r / bfr) = ceiling(20000 / 4) = 5000 blocks
16.25 Suppose that only 80% of the STUDENT records from Exercise 17.28 have a value for
PHONE, 85% for MAJORDEPTCODE, 15% for MINORDEPTCODE, and 90% for
DEGREEPROGRAM, and we use a variable-length record file. Each record has a 1-byte
field type for each field occurring in the record, plus the 1-byte deletion marker and a 1-byte
Chapter 16: Disk Storage, Basic File Structures, and Hashing
3
end–of-record marker. Suppose we use a spanned record organization, where each block
has a 5-byte pointer to the next block (this space is not used for record storage).
(a) Calculate the average record length R in bytes.
(b) Calculate the number of blocks needed for the file.
Answer:
(a) Assuming that every field has a 1-byte field type, and that the fields not mentioned
above (NAME, SSN, ADDRESS, BIRTHDATE, SEX, CLASSCODE) have values in every
record, we need the following number of bytes for these fields in each record, plus 1
(b) Using a spanned record organization with a 5-byte pointer at the end of each block,
the bytes available in each block are (B-5) = (512 – 5) = 507 bytes.
16.30 – Suppose that a disk unit has the following parameters: seek time s=20 msec;
rotational delay rd=10 msec; block transfer time btt=1 msec; block size B=2400 bytes;
interblock gap size G=600 bytes. An EMPLOYEE file has the following fields: SSN, 9 bytes;
LASTNAME, 20 bytes; FIRSTNAME, 20 bytes; MIDDLE INIT, 1 byte; BIRTHDATE, 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=30000
STUDENT records, fixed-length format, and unspanned blocking. Write down appropriate
formulas and calculate 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 organization.
(c) Calculate the transfer rate tr and the bulk transfer rate btr for this disk (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 the average time needed in msec 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 the average time needed in msec to search for an arbitrary record in
Chapter 16: Disk Storage, Basic File Structures, and Hashing
4
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.
Answer:
(a) R = (9 + 20 + 20 + 1 + 10 + 35 + 12 + 9 + 4 + 4) + 1 = 125 bytes
(c) Transfer rate tr= B/btt = 2400 / 1 = 2400 bytes/msec
(d) For linear search we have the following cases:
i. search on key field:
if record is found, half the file blocks are searched on average: b/2= 1579/2 blocks
(e) If the blocks are stored consecutively, and double buffering is used, the time to read
n consecutive blocks= s+rd+(n*(B/btr))
i. if n=b/2: time = 20+10+((1579/2)*(2400/1920))= 1016.9 msec = 1.017 sec
(f) If the blocks are scattered over the disk, a seek is needed for each block, so the time
to search n blocks is: n * (s + rd + btt)
(g) For binary search, the time to search for a record is estimated as:
16.31 – A PARTS file with Part# as hash key includes records with the following Part#
values: 2369, 3760, 4692, 4871, 5659, 1821, 1074, 7115, 1620, 2428,
3943, 4750, 6975, 4981, 9208. The file uses 8 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 mod 8. Calculate the average
number of block accesses for a random retrieval on Part#.
Answer:
The records will hash to the following buckets:
K h(K) (bucket number)
Chapter 16: Disk Storage, Basic File Structures, and Hashing
5
2369 1
3760 0
1620 4
2428 4 overflow
3943 7
4750 6
16.32 – Load the records of Exercise 17.31 into expandable hash files based on extendible
hashing. Show the structure of the directory at each step. Show the directory at each step,
and the global and local depths. Use the hash function h(k) = K mod 128.
Answer:
Hashing the records gives the following result:
Chapter 16: Disk Storage, Basic File Structures, and Hashing
6
Chapter 16: Disk Storage, Basic File Structures, and Hashing
7
Chapter 16: Disk Storage, Basic File Structures, and Hashing
9
Note: It is more common to specify a certain load factor for the file for triggering the splitting
Copyright © 2016 Pearson Education, Inc., Hoboken NJ
16.37 – Can you think of techniques other than an unordered overflow file that can be used to
make insertion in an ordered file more efficient?
16.38 – No solution provided.
16.39 – Can you think of techniques other than chaining to handle bucket overflow in external
hashing?
16.42 – Suppose that a file initially contains r=120,000 records of R=200 bytes each in an
unsorted (heap) file. The block size B=2400 bytes, the average seek time s=16 ms, the
average rotational latency rd=8.3 ms and the block transfer time btt=0.8 ms. Assume that 1
record is deleted for every 2 records added until the total number of active records is
240,000.
(a) How many block transfers are needed to reorganize the file?
(b) How long does it take to find a record right before reorganization?
(c) How long does it take to find a record right after reorganization?
Chapter 16: Disk Storage, Basic File Structures, and Hashing
11
Answer:
Let X = # of records deleted
Hence 2X= # of records added.
(a) No. of blocks for Reorganization
= Blocks Read + Blocks Written.
-200 bytes/record and 2400 bytes/block gives us 12 records per block
-Reading involves 360,000 records; i.e. 360,000/12 = 30K blocks
-Writing involves 240,000 records; i.e., 240000/12 = 20K blocks.
16.43 – Suppose we have a sequential (ordered) file of 100000 records where each record is
240 bytes. Assume that B=2400 bytes, s=16 ms, rd=8.3 ms, and btt=0.8 ms. Suppose we
want to make X independent random records from the file. We could make X random block
reads or we could perform one exhaustive read of the entire file looking for those X records.
The question is to decide when it would be more efficient to perform one exhaustive read of
the entire file than to perform X individual random reads. That is, what is the value for X
when an exhaustive read of the file is more efficient than random X reads? Develop this
function of X.
Answer:
Total blocks in file = 100000 records * 240 bytes/record divided by 2400
bytes/block = 10000 blocks.
Time for exhaustive read
= s + r + b.btt
