GATE 2015 CS (CS2) – Question 32

Databases · File Organization and Indexing (B and B+ Trees) · 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 <15.

Diagram for GATE 2015 CS (CS2) question 32

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 5

Explanation

Search for seven visits the root, the left internal node and leaf [5,7]. Follow the leaf chain to [9,11] and then [13,15], taking the qualifying key thirteen but stopping before fifteen. Thus five index nodes are fetched. The right internal node need not be fetched because the leaves are linked.

More File Organization and Indexing (B and B+ Trees) questions

GATE 2015 CS (CS3) Q39 – A B+ tree has 12-byte search keys, 1024-byte blocks, 10-byte record pointers and 8-byte…
GATE 2021 CS (CS2) Q31 – A sorted data file has 150000 student records and 4096-byte blocks. Disk record pointers…
GATE 2026 CS (CS2) Q46 – An index in a DBMS is said to be dense if an index entry appears for every search-key…
GATE 2025 CS (CS1) Q21 – Consider the following B+ tree with 5 nodes, in which a node can store at most 3 key…
GATE 2025 CS (CS2) Q57 – In a B+-tree where each node can hold at most four key values, a root to leaf path…
GATE 2024 CS (CS1) Q21 – In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for…

All File Organization and Indexing (B and B+ Trees) questions →