IAE Academy

GATE 2020 CS Q.54: solution and answer

GATE 2020 · CSQ.54 · 2 marks · NAT

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 ______.

See the question in the paper

Answer and solution

ANSWER

The minimum number of disk accesses is 4.

Official answer: 4Source: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Block size bytes. An internal node of order holds tree pointers and search keys.

  2. Largest fan-out: .

  3. A leaf holds (key, record pointer) pairs plus one next-leaf pointer: entries per leaf.

  4. The fewest accesses come from the shortest possible tree, so assume every node is packed full. Leaves needed for records: .

  5. Nodes reachable by level: root , level 2 , level 3 .

  6. With two levels (root and leaves) there are at most leaves, which is less than . With three levels the bottom level can hold up to leaves, and . So the shortest tree has three levels: root, one internal level, leaves.

  7. Nothing is in main memory at the start, so reading the root, one internal node and one leaf costs disk accesses.

  8. The leaf gives the address of the record's block. Each record fits in one block, so fetching it costs more access.

  9. Total minimum accesses .

KEY IDEA

Work out the fan-out of a B+ tree node from the block size, find the fewest levels that can index all the records, then add one access for the record's own block.

WATCH OUT FOR

Forgetting the final access to the data block (answering 3), or assuming the root is already in memory when the question says no node is.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 9 Indexing questions, with notes

More Indexing questions