Awesome q2a theme
+1 vote
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 ______.
in Databases by (49 points) | 16 views
Let the order of the B+ tree be $n$.

$n\times(\text{block pointer})+(n-1)\times(\text{key pointer}) \leq \text{block size}$

$8n + 12(n-1) \leq 4096$

$20n – 12 \leq 4096$

$20n \leq 4108$

$n \leq 205.4$

$n = 205$

Now all the actual data elements are stored in the leaves of the B+ tree, as we have 1 million ($10^6$) records, the level number of a B+ tree with order 205 that can hold greater than or equal to 1 million elements can be found using

$204^x \geq 10^6 \implies x = 3$

So 3 disk accesses?
One access for record in database so, 1+3=4 right answer.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,105 questions
3,156 answers
95,955 users