Consider a disk with block size B = 512 bytes, where a block pointer is 12 bytes

Question

Consider a disk with block size B = 512 bytes, where a block pointer is 12 bytes long. A file has r = 42,000 EMPLOYEE records of fixed length. Each record has the following fields: Name (20 bytes), ID (13 bytes), Department (3 bytes), Address (20 bytes), Phone (10 bytes), BirthDate (4 bytes), Gender (1 byte), and Salary (4 bytes). The records are stored in a file using an unspanned organization.

a. Calculate (i) the record size R in bytes, (ii) the blocking factor bfr, and (iii) the number of file blocks b.

b. Suppose that the file is ordered by the key field ID and we decide to construct a primary index on ID. Calculate (i) the number of records in the index file, (ii) the blocking factor of the index file, (iii) the number of blocks in the index file, and (iv) the number of block accesses needed to search for and retrieve a record from the data file given its ID using the primary index. Also, suppose we were to extend the primary index to construct a multilevel index. Calculate (v) the total number of index levels in the multilevel index and (vi) the total number of blocks in the entire multilevel index.

c. Suppose that the file is not ordered by the key field ID (or by any other field) and we decide to construct a secondary index on ID. Calculate (i) the number of records in the index file, (ii) the blocking factor of the index file, (iii) the number of blocks in the index file, and (iv) the number of block accesses needed to search for and retrieve a record from the data file given its ID using the secondary index. Also, suppose we were to extend the secondary index to construct a multilevel index. Calculate (v) the total number of index levels in the multilevel index and (vi) the total number of blocks in the entire multilevel index.

Explanation / Answer

block size B = 512 bytes

block pointer is 12 bytes long.

r = 42,000

Each record has the following fields:

Name (20 bytes),

ID (13 bytes),

Department (3 bytes)

Address (20 bytes)

Phone (10 bytes)

BirthDate (4 bytes)

Gender (1 byte)

Salary (4 bytes).

The records are stored in a file using an unspanned organization.

A.

(i) the record size R in bytes,

20+13+3+20+10+4+1+4 = 75

(ii) the blocking factor bfr means no of records ber block

bfr = 512/75 = 6.82 = 6 since unspanned org.

(iii) the number of file blocks b = 42000 / 6 = 7000 block.

B. File is ordered by the key field ID and we decide to construct a primary index on ID. Calculate

(i) the number of records in the index file

In primary indiexing one index entry for each block. so no of records in index file = 7000 record.

(ii) the blocking factor of the index file

for an index on key filed ID 13bytes and block pointer 12bytes.

so index entry size = 13+12 = 25 Bytes.

blocking factor of index file = 512 / 25 = 20.48 = 20 record/block

(iii) the number of blocks in the index file = 7000 / 20 = 350 blocks

(iv) the number of block accesses needed to search for and retrieve a record from the data file given its ID using the primary index

to search we need binary search so no of block accesses = log2(350) = 8.45 = 9 blocks

Also, suppose we were to extend the primary index to construct a multilevel index. Calculate

(v) the total number of index levels in the multilevel index

1st level no of records = 7000 and no of blocks = 7000 / 20 = 350

2nd level no of records = 350 and no of blocks = 350 / 20 = 18

3rd level no of records = 18 and no of blocks = 18 / 20 = 1

so total number of index level = 3

(vi) the total number of blocks in the entire multilevel index = 350 + 18 + 1 = 369

C. Suppose that the file is not ordered by the key field ID (or by any other field) and we decide to construct a secondary index on ID.

(i) the number of records in the index file

secondary index includes one entry ofr each records so the number of records in the index file = 42000

(ii) the blocking factor of the index file

for an index on key filed ID 13bytes and block pointer 12bytes.

so index entry size = 13+12 = 25 Bytes.

blocking factor of index file = 512 / 25 = 20.48 = 20 record/block

(iii) the number of blocks in the index file 42000 / 20 = 2100 blocks

(iv) the number of block accesses needed to search for and retrieve a record from the data file given its ID using the secondary index. log2(2100) = 11.03 = 12 Blocks

Also, suppose we were to extend the secondary index to construct a multilevel index. Calculate

(v) the total number of index levels in the multilevel index

1st level no of records = 42000 and no of blocks = 42000 / 20 = 2100

2nd level no of records = 2100 and no of blocks = 2100 / 20 = 105

3rd level no of records = 105 and no of blocks = 105 / 20 = 6

4th level no of records = 6 and no of blocks = 6 / 20 = 1

so total number of index level = 4

(vi) the total number of blocks in the entire multilevel index.

2100 + 105 + 6 + 1 = 2212 blocks

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.