The GATE Grind

GATE Databases: File Organization and Indexing (B and B+ Trees) – Previous Year Questions

23 GATE previous year questions on File Organization and Indexing (B and B+ Trees) (Databases, Computer Science) with answers and explanations, from every paper.

23 questions worth 35 marks in all (11 1-mark, 12 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q63 (2 marks, Multiple choice) – A B+ leaf’s order is its maximum number of(value, data-record-pointer) pairs. Block size1 KB; record pointer7 bytes; value9 bytes; block pointer6…
  2. GATE 2008 CS Q16 (1 mark, Multiple choice) – A clustering index is defined on fields that are
  3. GATE 2008 CS Q70 (2 marks, Multiple choice) – A file has16384 records, 32 bytes each; key field6 bytes. File is ordered by a nonkey field and unspanned. Blocks1024 bytes, block pointers10 bytes. A…
  4. GATE 2009 CS Q44 (2 marks, Multiple choice) – An initially empty B+ tree has internal-node order3 (maximum tree pointers per internal node) and leaf order2 (maximum data items per leaf). Insert…
  5. GATE 2021 CS (CS2) Q31 (1 mark, Numerical answer) – A sorted data file has 150000 student records and 4096-byte blocks. Disk record pointers are 7 bytes; candidate-key Anum is 12 bytes. A dense index…
  6. GATE 2015 CS (CS3) Q39 (2 marks, Numerical answer) – A B+ tree has 12-byte search keys, 1024-byte blocks, 10-byte record pointers and 8-byte block pointers. Find the maximum keys in a nonleaf node.
  7. GATE 2015 CS (CS2) Q32 (1 mark, Numerical answer) – For the B+ tree of order 1 shown, find the minimum number of index nodes, including the root, fetched to retrieve all records with search key ≥7 and…
  8. GATE 2010 CS Q28 (1 mark, Multiple choice) – A B+ tree allows at most five keys per node. Find the minimum number of keys in any nonroot node.
  9. GATE 2011 CS Q49 (2 marks, Multiple choice) – A large relation r has attributes A₁,…,Aₙ. Q₁ projects A₁,…,Aₙ after selecting Aₚ=c. Q₂ projects them after selecting c₁≤Aₚ≤c₂. Compare ordered…
  10. GATE 2013 CS Q25 (1 mark, Multiple choice) – An index is clustered if
  11. GATE 2017 CS (CS2) Q59 (2 marks, Numerical answer) – A B+ tree has eight-byte search keys, 512-byte blocks and two-byte block pointers. Find its maximum order.
  12. GATE 2016 CS (CS2) Q31 (1 mark, Multiple choice) – B+ trees are considered balanced because
  13. GATE 2014 CS (CS2) Q40 (2 marks, Multiple choice) – A nested-loop relational join of r(R) and s(S) uses three disk-block-sized buffers, one reserved for results. If size(r) < size(s), disk accesses are…
  14. GATE 2015 CS (CS1) Q32 (1 mark, Multiple choice) – A file is organized so that the ordering of data records is the same as or close to the ordering of data entries in some index. Then that index is…
  15. GATE 2019 CS Q24 (1 mark, Multiple choice) – Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?
  16. GATE 2026 CS (CS2) Q46 (2 marks, Multiple choice) – An index in a DBMS is said to be dense if an index entry appears for every search-key value in the indexed file. Otherwise, it is called a sparse…
  17. GATE 2025 CS (CS2) Q57 (2 marks, Numerical answer) – In a B+-tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: A = (49, 77, 83, -), B = (7, 19,…
  18. GATE 2025 CS (CS1) Q21 (1 mark, Multiple select) – Consider the following B+ tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the B+ tree. Which of the…
  19. GATE 2024 CS (CS2) Q26 (1 mark, Multiple select) – Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?
  20. GATE 2024 CS (CS1) Q21 (1 mark, Multiple choice) – In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
  21. GATE 2023 CS Q62 (2 marks, Numerical answer) – Consider a database of fixed-length records, stored as an ordered file. The database has 25,000 records, with each record being 100 bytes, of which…
  22. GATE 2021 CS (CS1) Q57 (2 marks, Multiple select) – Consider a dynamic hashing approach for 4-bit integer keys: (1) There is a main hash table of size 4. (2) The 2 least significant bits of a key are…
  23. GATE 2020 CS Q64 (2 marks, Numerical answer) – 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…