largest p_leaf with p_leaf·(K + P_rec) + P_next ≤ B
Min keys
internal: ⌈p/2⌉ − 1 per node; leaf: ⌈(p − 1)/2⌉
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Number of blocks / records per block
Floor the records per block, ceil the blocks.
★★★
Index size and block accesses with a sparse or multilevel index
Entries per block, levels until one block, +1 for the data block.
★★★
Order, height, or max/min keys of a B/B+ tree
Solve p·P + (p − 1)·K ≤ B; use fill rules.
★★★
Insertion into a B+ tree: shape or number of splits
Insert keys in order; split and copy/move correctly.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
9 real questions from the official GATE CSE papers (2011 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
9 questions · 0 correct of 0 attempted · marks 0 / 14
Year:
GATE 2025 CS2 · Q57NAT2 marks
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, 33, 44), C = (20*, 22*, 25*, 26*). The *-marked keys are data entries in a leaf. Assume that a pointer between keys k1 and k2 points to a subtree containing keys in [k1, k2), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+ tree. The smallest key value in the parent of the leaf that contains 25* is ______.
GATE 2024 CS1 · Q21MCQ1 mark
In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
GATE 2024 CS2 · Q26MSQ1 mark
Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q62NAT2 marks
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 the primary key occupies 15 bytes. The data file is block-aligned in that each data record is fully contained within a block. The database is indexed by a primary index file, which is also stored as a block-aligned ordered file (each index entry is a primary key and a block anchor pointer). Suppose the block size of the file system is 1024 bytes, and a pointer to a block occupies 5 bytes. The system uses binary search on the index file to search for a record with a given key. You may assume that a binary search on an index file of b blocks takes ⌈log₂ b⌉ block accesses in the worst case. Given a key, the number of block accesses required to identify the block in the data file that may contain a record with the key, in the worst case, is ______.
GATE 2021 Set 1 · Q47MSQ2 marks
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 used to index into the main hash table. (3) Initially, the main hash table entries are empty. (4) Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organised as a binary tree that grows on demand. (5) First, the 3rd least significant bit is used to divide the keys into left and right subtrees. (6) To resolve more collisions, each node of the binary tree is further subdivided into left and right subtrees based on the 4th least significant bit. (7) A split is done only if it is needed, i.e. only when there is a collision. Figure: entry 00 is empty; entry 01 has a tree whose left branch (bit 0) is one leaf and whose right branch (bit 1) is a node with two leaves; entry 10 has a node with one leaf on each side; entry 11 holds a single leaf. Which of the following sequences of key insertions can cause this state of the hash table (assume the keys are in decimal notation)?
One or more options may be correct. Select all that apply, then submit.
GATE 2020 · Q54NAT2 marks
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 ______.
GATE 2019 Set 2 · Q14MCQ1 mark
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?
GATE 2013 Code A · Q15MCQ1 mark
An index is clustered, if
GATE 2011 Code A · Q39MCQ2 marks
Consider a relational table r with sufficient number of records, having attributes A1, A2, ..., An and let 1 ≤ p ≤ n. Two queries Q1 and Q2 are given below. Q1: πA1..Ap(σAp = c(r)) where c is a constant. Q2: πA1..Ap(σc1 ≤ Ap ≤ c2(r)) where c1 and c2 are constants. The database can be configured to do ordered indexing on Ap or hashing on Ap. Which of the following statements is TRUE?
Common traps
Floor for records per block, ceil for number of blocks.
In a sparse index, search cost is index blocks plus 1 data block.
B+ tree order counts pointers, so a node of order p holds p − 1 keys.
Leaf and internal nodes of a B+ tree can have different orders because leaves also store record pointers.