Project ForgeConsider a database implemented using a B+ tree for file indexing, installed on a disk drive with block size 4 KB. The size of a search key is 12 bytes and the size of a tree/disk pointer is 8 bytes. Assume the database has one million records, each record fits into one disk block, and no node of the B+ tree and no records are present initially in main memory. The minimum number of disk accesses required to retrieve any record in the database is ____.
Explanation
For an internal node with fan-out p (p pointers, p−1 keys) to fit in a 4096-byte block: 8p + 12(p−1) ≤ 4096 ⟹ 20p ≤ 4108 ⟹ p ≤ 205.4, so p = 205. For a leaf node holding (key, record-pointer) pairs plus one 'next leaf' pointer: 20(p_leaf−1) + 8 ≤ 4096 ⟹ p_leaf−1 ≤ 204.4, so each leaf holds up to 204 entries. With 1,000,000 records, the number of leaves needed ≈ 1,000,000/204 ≈ 4902. One level up, with fan-out 205, covering 4902 leaves needs ⌈4902/205⌉ = 24 internal nodes; one level above that, ⌈24/205⌉ = 1 node suffices as the root. So the tree has 3 levels (root → internal → leaf). Retrieving a record requires reading root, internal node, and leaf (3 disk accesses) to find the record pointer, plus 1 more disk access to fetch the actual record block — 3 + 1 = 4 disk accesses total.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.