GATE CS Indexing and B+ Trees Previous Year Questions

GATE CS 2025 Set 2 | Question 57

NAT · 2 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 signify that these are data entries in a leaf.

Assume that a pointer between keys \(k_1\) and \(k_2\) points to a subtree containing keys in \([k_1, k_2)\), 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 __________. (Answer in integer)

Your answer

Explanation

Answer: 33

Key 23 goes to leaf C: B is the child of A for keys below 49, and C is B's child for \([19, 33)\). C is full, so the five keys 20, 22, 23, 25, 26 split into two leaves, and the smallest key of the new right leaf (23 for a 2 + 3 split, 25 for a 3 + 2 split) is copied into B.

B now has five keys, one too many, so it splits as well: its middle key (the one just copied up) moves to A, which has room, leaving (7, 19) on the left and (33, 44) on the right. The leaf holding 25* lies to the right of the promoted key, so its parent is (33, 44).

Both ways of splitting the leaf give the same parent, whose smallest key is 33.

Answer: 33

GATE CS 2024 Set 1 | Question 21

MCQ · 1 mark · −0.33

In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?

Only the root node All leaf nodes All internal nodes Only the leftmost leaf node

Explanation

Answer: (A)

Every node of a B+ tree except the root must be at least half full: an internal node of order \(p\) needs at least \(\lceil p/2 \rceil\) children, and a leaf must fill about half of its key slots. This keeps the tree shallow and its space use predictable.

The root cannot always meet the rule. When the root splits, the new root starts with a single key and two children, and a small tree may hold fewer keys than half a node. So the root alone is exempt: it needs only two children, or a single key when it is also a leaf.

Leaves, internal nodes and the leftmost leaf get no such exception, so B, C and D are wrong.

Answer: A

GATE CS 2024 Set 2 | Question 26

MSQ · 1 mark

Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?

Sorted Heap Unclustered tree index Unclustered hash index

Explanation

Answer: (A), (B)

A scan retrieves every record of the file, so the best possible cost is to read each data page exactly once.

Heap and sorted files keep their records packed in data pages, so a scan reads all \(B\) pages in sequence, one I/O per page. Both are I/O efficient.
With an unclustered index, tree or hash, the records are reached through the index entries. The order of the entries has nothing to do with where the records sit on disk, so consecutive entries usually point to different pages. The scan then costs about one page I/O per record, plus the reads of the index itself, which is far more than \(B\) when a page holds many records.

Answer: A, B