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

Given that
Ordered file of r = 5,000,000 records
Block size B = 4096 bytes
Record fixed sized and unspanned with record length R = 500 bytes

a. Number of Blocks = b = r/bfr (where r= no.of records and bfr = Blocking Factor)
a. i. bfr = B/R = 4096/500 = 8 records / block
a. ii. Number of Blocks b = r/ bfr = 5000000/ 8 = 625,000 Blocks

b. i. Number of blocks for binary search = log2 b = ~19 block access
b. ii. Number of blocks for linear search = b/2 = 312,500 block access.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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