1. Consider a disk with block size B=512 bytes. A block pointer is P=6 bytes long, and a record pointeris P R =7 bytes long. A file has r=3000 EMPLOYEE records of fixed-length. Each record has thefollowing fields: NAME (30 bytes), SSN (10 bytes), DEPARTMENTCODE (10 bytes), ADDRESS (30bytes), PHONE (10 bytes), BIRTHDATE (10 bytes), GENDER (1 byte), JOBCODE (4 bytes), SALARY (4bytes, real number). An additional byte is used as a deletion marker. Answers:a. Record length R = (30 + 10 + 10 + 30 + 10 + 10 + 1 + 4 + 4) + 1 = 110 bytesb. Blocking factor bfr = floor(B/R) = floor(512/110) = 4 records per blockNumber of blocks needed for file = ceiling(r/bfr) = ceiling (3000/4) = 750c. i. Index record size R i = (V SSN + P) = (10 + 6) = 16 bytesIndex blocking factor bfr i = fo = floor (B/R i ) = floor(512/16) = 32ii. Number of first-level index entries r 1 = number of file blocks b = 750 entriesNumber of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(750/32)= 23 blocksiii. We can calculate the number of levels as follows:Number of second-level index entries r 2 = number of first-level blocks b 1= 23 entriesNumber of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(23/32)= 1 blocksSince the second level has only one block, it is the top index level.Hence, the index has x = 2 levelsiv. Total number of blocks for the index b i = b 1 + b 2 = 23 + 1= 24 blocksv. Number of block accesses to search for a record = x + 1 = 2 + 1 = 3d. i. Index record size R i = (V SSN + P) = (10 + 6) = 16 bytesIndex blocking factor bfr i = floor (B/R i ) = floor(512/16)= 32 index records per blockii. Number of first-level index entries r 1 = number of file records r = 3000Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(3000/32)= 94 blocksiii. Number of second-level index entries r 2 = number of first-level index blocks b 1= 94 entriesNumber of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(94/32)= 3 blocksNumber of third-level index entries r 3 = number of second-level index blocks b 2= 3 entriesNumber of third-level index blocks b 3 = ceiling(r 3 /bfr i ) = ceiling(3/32) = 1Since the third level has only one block, it is the top index level.Hence, the index has x = 3 levelsv. Number of block accesses to search for a record = x + 1 = 3 + 1 = 4e. i. Index record size R i = (V DEPARTMENTCODE + P) = (10 + 6) = 16 bytesIndex blocking factor bfr i = floor (B/R i ) = floor(512/16)= 32 index records per blockii. There are 100 distinct values of DEPARTMENTCODE, so the average number of records for each value is (r/100) = (3000/100) = 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, 100 blocks are needed for the level of indirection.iii. Number of first-level index entries r 1= number of distinct values of DEPARTMENTCODE = 100 entriesNumber of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(100/32)= 4 blocksiv. Number of second-level index entries r 2 = number of first-level index blocks b 1 = 4 entriesNumber of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(4/32) = 1Hence, the index has x = 2 levelsv. total number of blocks for the index b i = b 1 + b 2 + b indirection = 4 + 1 + 100 = 105 blocksvi. 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 = 33f. i. Index record size R i = (V DEPARTMENTCODE + P) = (10 + 6) = 16 bytesIndex blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(512/16)= 32 index records per blockii. Number of first-level index entries r 1= number of distinct DEPARTMENTCODE values= 100 entriesNumber of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(100/32) = 4 blocksiii. Number of second-level index entries r 2 = number of first-level index blocks b 1= 4 entriesNumber of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(4/32) = 1Since the second level has one block, it is the top index level.Hence, the index has x = 2 levelsiv. Total number of blocks for the index b i = b 1 + b 2 = 4 + 1 = 5 blocksv. Number of block accesses to search for the first block in the cluster of blocks= x + 1 = 2 + 1 = 3The 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 givenDEPARTMENTCODE = x + 8 = 2 + 8 = 10 block accesses.g. i. For a B + -tree of order p, the following inequality must be satisfied for each internal tree node:(p * P) + ((p - 1) * V SSN ) < B, or(p * 6) + ((p - 1) * 10) < 512, which gives 16p < 522, so p=32For leaf nodes, assuming that record pointers are included in the leaf nodes, the following inequality must be satisfied: (p leaf * (V SSN +P R )) + P < B, or (p leaf * (10+7)) + 6 < 512, which gives 16p leaf < 506, so p leaf =30ii. Assuming that nodes are 69% full on the average, the average number of key values in a leaf nodeis 0.69*p leaf = 0.69*30 = 21.7 . If we round this up for convenience, we get 21 key values (and 22 record pointers) per leaf node. Since the file has 3000 records and hence 3000 values of SSN, the number of leaf-level nodes (blocks) needed is b 1 = ceiling (3000/21) = 143 blocks iii. We can calculate the number of levels as follows:The average fan-out for the internal nodes (rounded up for convenience) is fo = ceiling (0.69*p) = ceiling (0.69*32) = ceiling (22.08) = 23Number of second-level tree blocks b 2 = ceiling (b 1 /fo) = ceiling (143/23) = 7 blocksNumber of third-level tree blocks b 3 = ceiling (b 2 /fo) = ceiling (7/24) = 1Since the third level has only one block, the tree has x = 3 levels (counting …
View Full Document
Unlocking...