Consider storing a database table of 5,000,000 records each of which is 500 byte

Question

Consider storing a database table of 5,000,000 records each of which is 500 bytes long. The disk block size is 4096 bytes, and the read bandwidth is 2 GB/sec. Records are stored using no spanning and in sorted order using an integer key field.

a) Calculate the number of blocks used to store the table. (1 mark)

b) Calculate the number of blocks to find a given record using linear search and binary search. (2 marks)

c) Assume an index record occupies 8 bytes (4 for key, 4 for disk pointer). What is the size and number of blocks read to find a record for the following primary index configurations: (2 marks)

Dense, primary index

Sparse, primary index

d) There is an integer foreign key in the table that is a candidate for secondary indexing.

What is the time required to retrieve one record with the foreign key value without an index? (1 mark)

What is the time required to retrieve a record with a secondary index? What is the size of the secondary index? (2 marks)

e) Determine how many levels of multi-level index are required for both the primary key index and foreign key index, so that the minimum # of disk accesses are performed to find a record. (2 marks) Hint:Determine the index level where all index pointers at that level fit into a single block.

Explanation / Answer

          4096 / 500 = 8.

We can have at most 8 records in a block.

2.

Calculate the number of blocks to find a given record using linear search and binary search.

5,000,000 / 8 = 625,000 blocks are required to store the entire file.

A track has 25 blocks; a cylinder has 25*10=250 blocks. Therefore, we need 625,000 / 250=2500 cylinders to store the file sequentially.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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