GATE 2020 CS – Question 64
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 ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 4 to 4
Explanation
A node holds $p$ child pointers and $p-1$ keys. Size constraint: $8p+12(p-1)\le4096\Rightarrow20p\le4108\Rightarrow p\le205$. So the order is $p=205$.
For $10^6$ records, a B+ tree with fan-out about 205 has height 3 (levels): $205^2=42{,}025<10^6\le205^3\approx8.6\times10^6$. So an index lookup visits **3 index/leaf blocks**.
Since each record occupies its own disk block, one more access reads the record block.
Minimum disk accesses $=3+1=\mathbf4$.
More File Organization and Indexing (B and B+ Trees) questions
- GATE 2019 CS Q24
- GATE 2015 CS (CS1) Q32
- GATE 2014 CS (CS2) Q40
- GATE 2016 CS (CS2) Q31
- GATE 2017 CS (CS2) Q59
- GATE 2013 CS Q25
All File Organization and Indexing (B and B+ Trees) questions →