Suppose the file is not ordered by the non-key field DEPARTMENTCODE and we want to construct a secondary index on SSN using Option 3 of Section 18.1.3, with an extra level of indirection that stores record pointers. Assume there are 1000 distinct values of DEPARTMENTCODE, and that the EMPLOYEE records are evenly distributed among these values. Calculate (i) the index blocking factor bfr i (which is also the index fan-out fo); (ii) the number of blocks needed by the level of indirection that stores record pointers; (iii) the number of first-level index entries and the number of first-level index blocks; (iv) the number of levels needed if we make it a multi-level index; (v) the total number of blocks required by the multi-level index and the blocks used in the extra level of indirection; an

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.

i. Index record size R i = (V DEPARTMENTCODE + 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
ii. There are 1000 distinct values of DEPARTMENTCODE, so the average number of
records for each value is (r/1000) = (30000/1000) = 30
Since a record pointer size P R = 7 bytes, the number of bytes needed at the level
of indirection for each value of DEPARTMENTCODE is 7 * 30 =210 bytes, which
fits in one block. Hence, 1000 blocks are needed for the level of indirection.
iii. Number of first-level index entries r 1
= number of distinct values of DEPARTMENTCODE = 1000 entries
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(1000/34)
= 30 blocks
iv. 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
= 30 entries
Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(30/34) = 1
Hence, the index has x = 2 levels
v. total number of blocks for the index b i = b 1 + b 2 + b indirection
= 30 + 1 + 1000 = 1031 blocks
vi. Number of block accesses to search for and retrieve the block containing the
record pointers at the level of indirection = x + 1 = 2 + 1 = 3 block accesses
If we assume that the 30 records are distributed over 30 distinct blocks, we need
an additional 30 block accesses to retrieve all 30 records. Hence, total block
accesses needed on average to retrieve all the records with a given value for
DEPARTMENTCODE = x + 1 + 30 = 33