What are common examiner traps in File Organization and Indexing?

Confusing the order p (maximum block/child pointers) with the maximum number of keys (p - 1) in an internal node. Mixing up floor and ceiling operations: using ⌈ B/R ⌉ for blocking factor (must use ⌊ B/R ⌋) or ⌊ N/Bfr ⌋ for number of blocks (must use ⌈ N/Bfr ⌉). Including record pointers in internal B+ tree node capacity calculations (internal nodes contain only keys and child block pointers). Forgetting to add +1 disk block access for the final data record retrieval after traversing index tree levels. Assuming secondary indices on candidate keys can be sparse (secondary indices must be dense because data records are not physically ordered on that search key). Applying AVL-tree balance criteria (heights differ by at most 1) to B+ trees (B+ tree leaf path lengths must be strictly equal). Incorrectly retaining the promoted median key in an internal node during an internal split (unlike leaf splits where the key is copied/retained, internal splits push up and remove the key). Assuming node overflow stops at the leaf level without checking whether parent/root nodes are also at maximum capacity. Failing to recognize that splitting the root creates a new root node and two child nodes, thereby increasing the tree height by 1. Confusing the maximum number of keys (Kmax) with the tree order/maximum pointer capacity (p = Kmax + 1). Believing node count remains constant when an overflow occurs.

GATE CSE File Organization and Indexing PYQs

Standard yield14.2% of Databases

GATE tests file organization and indexing across two primary dimensions: exact numerical calculations of physical storage parameters (B/B+ tree order, node capa… Read the guide

Take topic test

Questions: 17
Asked: since 2011
Total marks: 25
Marks / paper: 1

17 GATE CSE File Organization and Indexing PYQs with solutions, from Databases. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in File Organization and Indexing

Concepts, patterns, formulas and traps distilled from past papers.

GATE tests file organization and indexing across two primary dimensions: exact numerical calculations of physical storage parameters (B/B+ tree order, node capacities, index blocking factors, tree height, and disk I/O costs) and conceptual comparisons of indexing structures (dense vs. sparse, clustered vs. unclustered, hash vs. tree-based indices). Recent papers increasingly emphasize multi-step numerical analysis and operational execution tracing, such as B+ tree node splitting dynamics and exact leaf-level range traversals.

Core concepts

Distinction between B-trees and B+ trees (B+ trees store data pointers exclusively at leaves; internal nodes store routing keys and tree pointers).
Index classification: Dense (entry for every search-key value) vs. Sparse (entry per block/subset of keys).
Physical organization: Clustered (data file physically sorted in search-key order) vs. Unclustered (data file order differs from index key order).
Primary index (sparse on ordering primary key) vs. Secondary index (dense on non-ordering key).
Strict height-balance property of B+ trees (all leaf nodes reside at identical depth).
Node occupancy constraints: minimum ⌈ p/2 ⌉ pointers for internal nodes, relaxed only for the root node (which needs ≥ 2 children).
Hash indexing characteristics: O(1) point lookups, failure to natively support range queries without scanning all buckets, must be dense.
B+ tree split mechanics: leaf splits duplicate the smallest right key into the parent (copy-up), internal splits promote the median key (push-up).
B+ tree node capacity and maximum keys per node
Leaf node overflow and split mechanism
Propagation of median keys to parent/internal nodes
Root node split and increase in tree height
Node count and structural changes post-insertion

Recurring question patterns

B/B+ Tree Order and Node Capacity Calculation
CommonNAT2 marks2017, 2015
Given block size, key size, and pointer sizes (tree pointer vs. record pointer), determine the maximum order p or maximum number of keys an internal or leaf node can accommodate.
Multi-Level Index and B+ Tree Disk Access Sizing
CommonNAT2 marks2023, 2020, 2015
Given relation cardinality, record size, block size, and index entry format, compute the number of index blocks, minimum B+ tree levels/height, and total disk I/Os needed to fetch a record or range of records.
Index Sizing for Primary and Secondary Indices
OccasionalNAT1 marks2023, 2021
Determine the number of blocks occupied by a primary (sparse) or secondary (dense) index file using blocking factors with floor and ceiling divisions.
Structural and Conceptual Properties of Indexing
CommonMCQ1 marks2026, 2024, 2019, 2016
Evaluate correctness of statements regarding index definitions (clustered vs. unclustered, dense vs. sparse), tree balance guarantees, root occupancy relaxations, and hash vs. B+ tree capabilities for range/point queries.
B+ Tree Mutation and Split Tracing
OccasionalNAT2 marks2025
Trace the insertion of a key into an existing B+ tree node configuration, determining leaf splitting (copy-up) and cascading internal node splitting (push-up) to find resulting key arrangements in target nodes.
File Organization Scan & Join I/O Cost Analysis
Occasionalmixed1 marks2024, 2014
Assess disk block accesses for relational operations (e.g., nested loop join outer/inner relation selection, table scan efficiency across heap, sorted, and unclustered indices).
B+ Tree Key Insertion and Structural Mutation
CommonMSQ1 marks2025
Given a diagrammatic representation of a B+ tree with a specified maximum key capacity per node, trace the insertion of a new search key to determine whether leaf/internal/root nodes split, whether redistribution occurs, how the total node count changes, and whether the overall tree height increases.

Formulas GATE uses

Internal Node Capacity Inequality (B+ Tree)

p \cdot P + (p - 1) \cdot K \le B

Determining the maximum order $p$ or maximum key capacity $(p - 1)$ of an internal node given block size $B$ , tree pointer size $P$ , and search key size $K$ .

Leaf Node Capacity Inequality (B+ Tree)

n \cdot (K + R_p) + P_{next} \le B

Calculating the maximum number of data entries $n$ that fit in a leaf node with key size $K$ , record pointer size $R_p$ , block size $B$ , and optional sibling pointer $P_{next}$ .

Data File Blocking Factor

Bfr = \left\lfloor \frac{B}{R} \right\rfloor

Computing the number of data records that fit within a single disk block of size $B$ with record size $R$ (unspanned).

Total Data/Index Blocks

b = \left\lceil \frac{N}{Bfr} \right\rceil

Computing the total number of blocks required to store $N$ records or index entries when each block holds $Bfr$ items.

Binary Search Block Accesses on Index

\text{Accesses} = \left\lceil \log_2 b \right\rceil

Calculating worst-case block accesses to locate a target block using binary search over an ordered index of $b$ blocks.

Block Nested-Loop Join Cost

\text{Cost} = B(R) + B(R) \times B(S)

Computing total disk block accesses for a nested-loop join with minimum buffer allocation (1 buffer outer, 1 buffer inner) where $R$ is the outer relation.

Node Overflow Condition

\text{Number of keys after insertion} > K_{\max}

Determining whether a leaf node or internal node exceeds its maximum key capacity and must undergo a split.

Tree Height Growth Condition

\text{Split}(\text{Root}) \implies h_{\text{new}} = h_{\text{old}} + 1

Determining if an insertion propagates all the way to the root and forces the creation of a new root level.

Examiner traps in File Organization and Indexing

Confusing the order p (maximum block/child pointers) with the maximum number of keys (p - 1) in an internal node.
Mixing up floor and ceiling operations: using ⌈ B/R ⌉ for blocking factor (must use ⌊ B/R ⌋) or ⌊ N/Bfr ⌋ for number of blocks (must use ⌈ N/Bfr ⌉).
Including record pointers in internal B+ tree node capacity calculations (internal nodes contain only keys and child block pointers).
Forgetting to add +1 disk block access for the final data record retrieval after traversing index tree levels.
Assuming secondary indices on candidate keys can be sparse (secondary indices must be dense because data records are not physically ordered on that search key).
Applying AVL-tree balance criteria (heights differ by at most 1) to B+ trees (B+ tree leaf path lengths must be strictly equal).
Incorrectly retaining the promoted median key in an internal node during an internal split (unlike leaf splits where the key is copied/retained, internal splits push up and remove the key).
Assuming node overflow stops at the leaf level without checking whether parent/root nodes are also at maximum capacity.
Failing to recognize that splitting the root creates a new root node and two child nodes, thereby increasing the tree height by 1.
Confusing the maximum number of keys (Kmax) with the tree order/maximum pointer capacity (p = Kmax + 1).
Believing node count remains constant when an overflow occurs.

How questions are asked

Parameter calculation NAT (solving inequalities for tree order, capacity, or index blocks)
Total disk access NAT (computing tree height + record block I/O)
Concept validation MCQ/MSQ (evaluating clustered, dense, sparse, or hash index properties)
Tree operation trace NAT (state of B+ tree node after insertion and split)
Visual index/tree traversal NAT (counting fetched nodes along horizontal/vertical paths)
Diagram-based insertion trace with multi-statement structural verification (MSQ)
Counting node splits or total nodes after insertion

Paper trends

Shift from direct 1-mark definitional MCQs (clustered index definition, B+ tree balance property) toward multi-step 2-mark NATs requiring chained floor/ceiling divisions and height computations.
2023, 2020, 2017, 2015, 2013, 2011
Introduction of deep algorithmic state-tracing problems in NAT format, requiring precise understanding of copy-up vs. push-up split rules during B+ tree insertions.
2025
Expansion into MSQ and multi-statement comparative formats evaluating fundamental indexing constraints (e.g., why hash indices must be dense and B+ trees can be sparse, or file scan I/O efficiency).
2026, 2024
Recent trends utilize Multi-Select Questions (MSQ) paired with graphical tree figures to test multiple structural invariants (node splitting, node count invariance, and height growth) simultaneously.
2025

Difficulty notes

Easy questions test direct definitions (clustered index, tree balance, root occupancy relaxation, hash vs. B+ tree query suitability). Medium questions require setting up algebraic inequalities to find B+ tree orders, calculating multi-level index heights, computing binary search accesses across blocks, or evaluating MSQs on file scan efficiency. Hard questions require executing multi-step insertion/split simulations (cascading leaf copy-up and internal push-up splits) while tracking key redistribution across parent/child nodes.