Skip to content
GATEiit

GATE CSE 2020 Q64: Disk accesses to fetch a record via a B+ tree of one million keys

Question

Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is _______.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 4 (official GATE 2020 final answer key)

Concept used: Disk accesses = height of the B+ tree (one block per level) plus one for the data block.

First step: Order: 8p+12(p−1)≤40968p + 12(p - 1) \le 4096 gives p=205p = 205 pointers per node; find how many levels are needed to index 10610^6 records.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

More Databases PYQs

PracticePractise Databases questions →Full paperAll GATE CSE 2020 questions →