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.