1 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 3000 EMPLOYEE records of fixed length Each record has the following fields NAME 30 bytes SSN 10 bytes DEPARTMENTCODE 10 bytes ADDRESS 30 bytes PHONE 10 bytes BIRTHDATE 10 bytes GENDER 1 byte JOBCODE 4 bytes SALARY 4 bytes 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 bytes b Blocking factor bfr floor B R floor 512 110 4 records per block Number of blocks needed for file ceiling r bfr ceiling 3000 4 750 c i Index record size R i V SSN P 10 6 16 bytes Index blocking factor bfr i fo floor B R i floor 512 16 32 ii Number of first level index entries r 1 number of file blocks b 750 entries Number of first level index blocks b 1 ceiling r 1 bfr i ceiling 750 32 23 blocks iii 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 entries Number of second level index blocks b 2 ceiling r 2 bfr i ceiling 23 32 1 blocks Since the second level has only 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 23 1 24 blocks v Number of block accesses to search for a record x 1 2 1 3 d i Index record size R i V SSN P 10 6 16 bytes Index blocking factor bfr i floor B R i floor 512 16 32 index records per block ii Number of first level index entries r 1 number of file records r 3000 Number of first level index blocks b 1 ceiling r 1 bfr i ceiling 3000 32 94 blocks iii Number of second level index entries r 2 number of first level index blocks b 1 94 entries Number of second level index blocks b 2 ceiling r 2 bfr i ceiling 94 32 3 blocks Number of third level index entries r 3 number of second level index blocks b 2 3 entries Number of third level index blocks b 3 ceiling r 3 bfr i ceiling 3 32 1 Since the third level has only one block it is the top index level Hence the index has x 3 levels v Number of block accesses to search for a record x 1 3 1 4 e i Index record size R i V DEPARTMENTCODE P 10 6 16 bytes Index blocking factor bfr i floor B R i floor 512 16 32 index records per block ii 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 entries Number of first level index blocks b 1 ceiling r 1 bfr i ceiling 100 32 4 blocks iv Number of second level index entries r 2 number of first level index blocks b 1 4 entries Number of second level index blocks b 2 ceiling r 2 bfr i ceiling 4 32 1 Hence the index has x 2 levels v total number of blocks for the index b i b 1 b 2 b indirection 4 1 100 105 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 f i Index record size R i V DEPARTMENTCODE P 10 6 16 bytes Index blocking factor bfr i fan out fo floor B R i floor 512 16 32 index records per block ii Number of first level index entries r 1 number of distinct DEPARTMENTCODE values 100 entries Number of first level index blocks b 1 ceiling r 1 bfr i ceiling 100 32 4 blocks iii Number of second level index entries r 2 number of first level index blocks b 1 4 entries Number of second level index blocks b 2 ceiling r 2 bfr i ceiling 4 32 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 4 1 5 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 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 32 For 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 30 ii Assuming that nodes are 69 full on the average the average number of key values in a leaf node is 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 23 Number of second level tree blocks b 2 ceiling b 1 fo ceiling 143 23 7 blocks Number of third level tree blocks b 3 ceiling b 2 fo ceiling 7 24 1 Since the third level has only one block the tree has x 3 levels counting the leaf level iv Total number of blocks for the tree b i b 1 b 2 b 3 b 4 143 7 1 …
View Full Document
Unlocking...