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 _______.
4
Given: B+ tree
Block size = 4 KB
Search key = 12B
Tree/disk pointer = 8B
No of records = 1 million
Let P is the order of B+ Tree (no. of children)
In B+ Trees,
P * size_of_pointer + (P-1) * size_of_key ≤ block_size
⇒ P*8 + (P-1)*12 ≤ 4 * 1024
⇒ 8P + 12P - 12 ≤ 4096
⇒ 20P ≤ 4108
⇒ P ≤ 4108/20
⇒ P ≤ 205.4
⇒ P = 205
Number of Keys at a node = P - 1 ⇒ 205 - 1 = 204
At level 1, No. of keys = 204.
At level 2, No. of keys = 204 * 205 = 41820
At level 3, No. of keys = 204 * 205 * 205 = 8.5 * 106
As the database has 1 million records (=106).
In the Worst Case, 3 disk accesses are required to reach the record and one disk access to access the actual record.
Total 4 disk accesses are required to retrieve any record in the database.