GATE CS 2020 Set 1 — Question 64
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.NAT+2 / -0MediumB+ Tree NumericalsIndexing & File OrganizationDatabases
Databases → Indexing & File Organization → B+ Tree Numericals
Last updated
Question
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 _______.
Correct answer
4 to 4
Solution
Given:
An internal node of order stores at most pointers and keys.So, the maximum order (branching factor) is .Step 2: Calculate the maximum capacity of leaf nodes ()
A leaf node stores (Key, RecordPointer) pairs and a next-leaf pointer.
Let be the number of records per leaf.So, a leaf node can hold at most record pointers.Step 3: Calculate the minimum height of the B+ tree
To minimize disk accesses, we assume the tree is full (minimum height).
To retrieve a record:
- Block size () = 4 KB = 4096 bytes
- Search key size () = 12 bytes
- Pointer size () = 8 bytes
- Number of records () = 1,000,000
- Each record fits into one disk block
An internal node of order stores at most pointers and keys.So, the maximum order (branching factor) is .Step 2: Calculate the maximum capacity of leaf nodes ()
A leaf node stores (Key, RecordPointer) pairs and a next-leaf pointer.
Let be the number of records per leaf.So, a leaf node can hold at most record pointers.Step 3: Calculate the minimum height of the B+ tree
To minimize disk accesses, we assume the tree is full (minimum height).
- Number of leaf nodes required: .
- Number of internal nodes at level above leaves: .
- Number of internal nodes at root level: .
To retrieve a record:
1.Access Root node (1 disk I/O)
2.Access Internal node (1 disk I/O)
3.Access Leaf node (1 disk I/O)
4.Access the actual Data Block pointed to by the leaf (1 disk I/O)
Total accesses = .Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Indexing & File Organization
2026 Set 2 Q15In the context of DBMS, consider the two sets T and S given below. | T | S | |---|---| | I:…2026 Set 2 Q20Consider concurrent execution of two transactions and in a DBMS, both of which access a…2026 Set 1 Q30Let and be the attributes of a relation in a relational schema. Let…2026 Set 1 Q31In the context of relational database normalization, which of the following statements is/are true?2026 Set 2 Q42In the context of schema normalization in relational DBMS, consider a set F of functional…