Suppose the file is ordered by the non-key field DEPARTMENTCODE and we want to construct a clustering index on DEPARTMENTCODE that uses block anchors (every new value of DEPARTMENTCODE starts at the beginning of a new block). 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 first-level index entries and the number of first-level index blocks; (iii) the number of levels needed if we make it a multi-level index; (iv) the total number of blocks required by the multi-level index; and (v) the number of block accesses needed to search for and retrieve all records in the file having a specific DEPARTMENTCODE value u

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 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. Number of first-level index entries r 1
= number of distinct DEPARTMENTCODE values= 1000 entries
Number of first-level index blocks b 1 = ceiling(r 1 /bfr i )
= ceiling(1000/34) = 30 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
= 30 entries
Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(30/34) = 1
Since the second level has one block, it is the top index level.
Hence, the index has x = 2 levels
iv. Total number of blocks for the index b i = b 1 + b 2 = 30 + 1 = 31 blocks
v. Number of block accesses to search for the first block in the cluster of blocks
= x + 1 = 2 + 1 = 3
The 30 records are clustered in ceiling(30/bfr) = ceiling(30/4) = 8 blocks.
Hence, total block accesses needed on average to retrieve all the records with a given
DEPARTMENTCODE = x + 8 = 2 + 8 = 10 block accesses