Suppose the file is not ordered by the key field SSN and we want to construct a secondary index on SSN. Repeat the previous exercise (part c) for the secondary index and compare with the primary index.

Question

Consider a disk with block size B=512 bytes. A block pointer is P=6 bytes long,
and a record pointer is P R =7 bytes long. A file has r=30,000 EMPLOYEE records
of fixed-length. Each record has the following fields: NAME (30 bytes), SSN (9
bytes), DEPARTMENTCODE (9 bytes), ADDRESS (40 bytes), PHONE (9 bytes),
BIRTHDATE (8 bytes), SEX (1 byte), JOBCODE (4 bytes), SALARY (4 bytes, real
number). An additional byte is used as a deletion marker.

Answer 1

i. Index record size R i = (V SSN + P) = (9 + 6) = 15 bytes
Index blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(512/15)
= 34 index records per block
(This has not changed from part (c) above)
(Alternative solution: The previous solution assumes that leaf-level index blocks contain
block pointers; it is also possible to assume that they contain record pointers, in
which case the index record size would be V SSN + P R = 9 + 7 = 16 bytes. In this
case, the calculations for leaf nodes in (i) below would then have to use R i = 16
bytes rather than R i = 15 bytes, so we get:
Index record size R i = (V SSN + P R ) = (9 + 7) = 15 bytes
Leaf-level ndex blocking factor bfr i = floor(B/R i ) = floor(512/16)
= 32 index records per block
However, for internal nodes, block pointers are always used so the fan-out for
internal nodes fo would still be 34.)
ii. Number of first-level index entries r 1 = number of file records r = 30000
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(30000/34)
= 883 blocks
(Alternative solution:
Number of first-level index entries r 1 = number of file records r = 30000
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(30000/32)
= 938 blocks)
iii. We can calculate the number of levels as follows:
Number of second-level index entries r 2 = number of first-level index blocks b 1
= 883 entries
Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(883/34)
= 26 blocks
Number of third-level index entries r 3 = number of second-level index blocks b 2
= 26 entries
Number of third-level index blocks b 3 = ceiling(r 3 /bfr i ) = ceiling(26/34) = 1
Since the third level has only one block, it is the top index level.
Hence, the index has x = 3 levels
(Alternative solution:
Number of second-level index entries r 2 = number of first-level index blocks b 1
= 938 entries
Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(938/34)
= 28 blocks
Number of third-level index entries r 3 = number of second-level index blocks b 2
= 28 entries
Number of third-level index blocks b 3 = ceiling(r 3 /bfr i ) = ceiling(28/34) = 1
Since the third level has only one block, it is the top index level.
Hence, the index has x = 3 levels)
iv. Total number of blocks for the index b i = b 1 + b 2 + b 3 = 883 + 26 + 1 = 910
(Alternative solution:
Total number of blocks for the index b i = b 1 + b 2 + b 3 = 938 + 28 + 1 = 987)
v. Number of block accesses to search for a record = x + 1 = 3 + 1 = 4