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 (K ) with the tree order/maximum pointer capacity (p = K + 1). Believing node count remains constant when an overflow occurs.

File Organization and Indexing

17 Qs · since 2011 · 25 marks · 1 marks/paperStandard yield

Take topic test

GATE tests file organization and indexing across two primary dimensions: exact numerical calculations of physical storage parameters (B/B+ tree order, node capacities, index blocki… Guide

Type

GATE CSE 2026 Set 2Q46MCQ2 marksMediumAn 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 index. Consider the following two statements. S1: A hash index must be a dense index S2: A $B^+$ tree index can be a sparse index Which one of the following options is…
GATE CSE 2025 Set 1Q21MSQ1 markMediumDiagramConsider 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 following options(s) is/are CORRECT?
GATE CSE 2025 Set 2Q57NAT2 marksHardIn a $\text{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$ …
GATE CSE 2024 Set 1Q21MCQ1 markEasyIn a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
GATE CSE 2024 Set 2Q26MSQ1 markEasyWhich of the following file organizations is/are I/O efficient for the scan operation in DBMS?
GATE CSE 2023Q62NAT2 marksMediumDiagramConsider 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…
GATE CSE 2021 Set 2Q21NAT1 markMediumA data file consisting of 1,50,000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is sorted on the primary key RollNo. The size of a record pointer for this disk is 7 bytes. Each student-record has a candidate key attribute called ANum of size 12 bytes. Suppose an index file with…
GATE CSE 2020Q54NAT2 marksMediumConsider 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…
GATE CSE 2019Q14MCQ1 markEasyWhich 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 CSE 2017 Set 2Q49NAT2 marksMediumIn a B+ tree, if the search-key value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B+ tree is ________.
GATE CSE 2016 Set 2Q21MCQ1 markEasyB+ Trees are considered BALANCED because
GATE CSE 2015 Set 1Q24MCQ1 markEasyA 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 called
GATE CSE 2015 Set 2Q6NAT1 markMediumDiagramWith reference to the B+ tree index of order 1 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query: "Get all records with a search key greater than or equal to 7 and less than 15" is ______.
GATE CSE 2015 Set 3Q46NAT2 marksMediumConsider a B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is _________.
GATE CSE 2014 Set 2Q30MCQ2 marksMediumConsider a join (relation algebra) between relations $r\ (R)$ and $s\ (S)$ using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming $\text{size}(r(R)) < \text{size}(s(S))$ , the join will have fewer number of…
GATE CSE 2013Q15MCQ1 markEasyAn index is clustered, if
GATE CSE 2011Q39MCQ2 marksEasyConsider a relational table $r$ with sufficient number of records, having attributes $A_1, A_2, \dots, A_n$ and let $1 \le p \le n$ . Two queries Q1 and Q2 are given below. Q1: $\pi_{A_1, \dots, A_p}(\sigma_{A_p = c}(r))$ where $c$ is a constant Q2: $\pi_{A_1, \dots, A_p}(\sigma_{c_1 \le A_p \le c_2}(r))$ …

Topic guide

What does GATE test in File Organization and Indexing?

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
common · NAT · 2 marks · 2017, 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
common · NAT · 2 marks · 2023, 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
occasional · NAT · 1 marks · 2023, 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
common · MCQ · 1 marks · 2026, 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
occasional · NAT · 2 marks · 2025
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
occasional · mixed · 1 marks · 2024, 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
common · MSQ · 1 marks · 2025
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 (K ) with the tree order/maximum pointer capacity (p = K + 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.

File Organization and Indexing

17 Qs · since 2011 · 25 marks · 1 marks/paperStandard yield

Take topic test

GATE tests file organization and indexing across two primary dimensions: exact numerical calculations of physical storage parameters (B/B+ tree order, node capacities, index blocki… Guide

Type

Topic guide

What does GATE test in File Organization and Indexing?

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
common · NAT · 2 marks · 2017, 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
common · NAT · 2 marks · 2023, 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
occasional · NAT · 1 marks · 2023, 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
common · MCQ · 1 marks · 2026, 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
occasional · NAT · 2 marks · 2025
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
occasional · mixed · 1 marks · 2024, 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
common · MSQ · 1 marks · 2025
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 (K ) with the tree order/maximum pointer capacity (p = K + 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