Consider a database implemented using B+ tree for file indexing and installed…
2020
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 ___________ .
Attempted by 107 students.
Show answer & explanation
Correct answer: 4
Key insight: compute the leaf capacity and internal-node fanout to get the tree height, then add one disk access to fetch the actual record block.
Leaf entry size = search key + record pointer = 12 + 8 = 20 bytes. Maximum entries per leaf = floor(4096 / 20) = 204.
Number of leaf nodes needed = ceil(1,000,000 / 204) = 4,902.
Internal-node fanout (maximum pointers) = floor((block size + key size) / (pointer size + key size)) = floor((4096 + 12) / (8 + 12)) = floor(4108 / 20) = 205.
Find tree height H (root level = 1): need smallest H with 205^(H-1) >= 4,902. Since 205^1 = 205 < 4,902 and 205^2 = 42,025 >= 4,902, we get H = 3.
Disk accesses = H (to read root, internal level, and leaf) + 1 (to read the record block) = 3 + 1 = 4.
Answer: 4 disk accesses.