+1 vote
16 views
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 ______.
| 16 views
+1
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?
+1
One access for record in database so, 1+3=4 right answer.