GATE DA

File organisation and indexing

File organisation decides how records are laid out in disk blocks, and an index is an extra, smaller file that shortens the search for a record. GATE questions turn on block arithmetic: blocking factor, number of blocks, index levels, and B-tree or B+ tree order, height and block accesses. Most answers are counts of disk-block accesses, reached through blocking factors, index sizes and tree orders, so the habit to build is stating the block, record, key and pointer sizes first and counting carefully with floors and ceilings.

3 previous-year questions · 3 solved · 6 practice questions

Records, blocks and the blocking factor

A file is a sequence of records stored in fixed-size disk blocks. The cost of a database operation is counted in block accesses, because one block transfer costs far more than any in-memory work on it. Buffering and caching are ignored unless the question says otherwise.

Convention used throughout: block size $B$ , record size $R$ , key size $V$ , block pointer size $P$ and record pointer size $P_{r}$ are all in bytes. Records are unspanned (a record never crosses a block boundary) and fixed-length unless the question says otherwise. $r$ is the number of records and $b$ the number of data blocks.

BLOCKING FACTOR (UNSPANNED)

b f r = ⌊ \frac{B}{R} ⌋

Records per block. The floor is essential: with unspanned records the leftover $B - b f r \cdot R$ bytes in each block are unused.

NUMBER OF DATA BLOCKS

b = ⌈ \frac{r}{b f r} ⌉

Blocks needed for $r$ records; round up because a partly filled last block still occupies a block.

With spanned records a record may continue into the next block, so (ignoring the pointer that links a record's pieces) no space is wasted and $b = ⌈ r R / B ⌉$ . Use this only when the question says records are spanned.

File organisations: heap, sorted and hashed

A heap (unordered) file keeps records in insertion order. A sorted (ordered) file keeps them physically ordered on an ordering field. A hashed file places each record in a bucket (a block or group of blocks) chosen by a hash function applied to the hash field.

Operation (in block accesses)	Heap	Sorted	Hashed
Equality search on a unique key (the organising field for sorted and hashed files)	$b /2$ on average, $b$ worst	$⌈ lo g_{2} b ⌉$ (binary search)	About 1 (more if the bucket has overflow blocks)
Range search on the organising field	$b$ (scan everything)	$⌈ lo g_{2} b ⌉$ plus the further blocks holding the range	$b$ (hash order is unrelated to key order)
Search on any other field	$b$ ; $b /2$ on average if the value is unique and present	$b$ ; $b /2$ on average if the value is unique and present	$b$ ; $b /2$ on average if the value is unique and present
Insert	About 1 to 2 (read and write the last block)	Costly: find the place, then shift later records, about $b /2$ blocks read and written on average	About 1 to 2 (find the bucket, write)
Delete	Find the record, then rewrite its block	Find, then rewrite (or mark as deleted)	Find in the bucket, then rewrite

BINARY SEARCH ON A SORTED FILE

binary search cost = ⌈ lo g_{2} b ⌉

Applies only to the field the file is sorted on, and counts block accesses, not record comparisons. This is the usual convention in problems; the strict worst case of binary search is $⌊ lo g_{2} b ⌋ + 1$ , which is one more only when $b$ is a power of 2. Follow the convention the question states.

EXAM TIP

A sorted file is fast only for the field it is sorted on. A search on any other field is a full scan of $b$ blocks (average $b /2$ if the value is unique and found). A file can be physically ordered on only one field.

Primary, clustering and secondary indexes; dense and sparse

An index is a separate file of entries $⟨ key value, pointer ⟩$ , kept sorted on the key value, so it can be searched by binary search and is much smaller than the data file. An index entry has size $V + P$ (or $V + P_{r}$ when the entries hold record pointers, as a dense secondary index often does; use the sizes the question gives), and the index blocking factor (also the fan-out) is the number of entries per index block.

Index type	Built on	Data file	Entries
Primary	Ordering key field	Ordered on that field	Sparse: one entry per data block (the block's first key, the block anchor)
Clustering	Ordering non-key field	Ordered on that field	One entry per distinct value, pointing to the first block holding it
Secondary	A field the file is not ordered on (key or non-key)	Any order	Dense: one entry per record for a key field; for a non-key field, one entry per record, or one per distinct value pointing to a block of record pointers (an extra level of indirection)

A file can have at most one primary or clustering index (not both), because the file can be physically ordered on only one field. It can have many secondary indexes.

A dense index has an entry for every search-key value (or every record). A sparse index has entries for only some values, typically one per block. A sparse index needs the data to be ordered on the indexed field; to search it, find the last index entry whose key is less than or equal to the search key, then read that data block.

INDEX BLOCKING FACTOR (FAN-OUT)

b f r_{i} = ⌊ \frac{B}{V + P} ⌋

Entries per index block, where an entry is a key plus a block pointer (replace $P$ by $P_{r}$ if the entries hold record pointers).

SINGLE-LEVEL INDEX SIZE

b_{i}^{dense} = ⌈ \frac{r}{b f r _{i}} ⌉, b_{i}^{sparse} = ⌈ \frac{b}{b f r _{i}} ⌉

Dense: one entry per record. Sparse primary index: one entry per data block. A clustering index on a field with $d$ distinct values needs $⌈ d / b f r_{i} ⌉$ blocks.

SEARCH WITH A SINGLE-LEVEL INDEX

accesses = ⌈ lo g_{2} b_{i} ⌉ + 1

Binary search over the $b_{i}$ index blocks (same convention as for a sorted file), plus one access to fetch the data block. A non-key secondary index with a level of indirection adds one more access for the block of record pointers.

Multilevel indexes

If the first-level index is itself large, build a sparse index on the index: the second level has one entry per first-level block, and so on until a level fits in one block (the top). The search then reads exactly one block per level, with no binary search. This idea, applied with room left in nodes for insertion, gives the B-tree and B+ tree.

Compute the first-level index blocks $b_{1}$ (dense: $⌈ r / b f r_{i} ⌉$ ; sparse primary: $⌈ b / b f r_{i} ⌉$ ).
Each next level has $⌈(blocks of previous level) / b f r_{i} ⌉$ blocks.
Stop at the level that has 1 block. The number of levels is $t$ .
Block accesses for a search is $t + 1$ (one per index level, plus the data block).

MULTILEVEL INDEX LEVELS AND COST

t = ⌈ lo g_{f o} b_{1} ⌉ + 1 = ⌈ lo g_{f o} r_{1} ⌉, accesses = t + 1

$f o = b f r_{i}$ is the fan-out, $r_{1}$ the number of first-level entries and $b_{1} = ⌈ r_{1} / f o ⌉$ the number of first-level blocks. The first form is valid for $b_{1} \geq 1$ (for $b_{1} = 1$ , $t = 1$ ); the second for $r_{1} \geq 2$ .

EXAM TIP

Compare the two ways of searching a first-level index: binary search costs $⌈ lo g_{2} b_{1} ⌉$ index-block accesses, a multilevel index costs $t = ⌈ lo g_{f o} b_{1} ⌉ + 1$ . The base is the fan-out, so the saving is large when $b_{1}$ is large.

WORKED EXAMPLE

A file has $r = 30, 000$ records of $R = 100$ bytes, block size $B = 1024$ bytes, key size $V = 9$ bytes and block pointer $P = 6$ bytes, unspanned. Find the block accesses to fetch a record by key using (a) binary search on the data file sorted on the key, (b) a single-level primary index, (c) a single-level dense secondary index on another key field, (d) a multilevel index built on (c).

Solution

$b f r = ⌊ 1024/100 ⌋ = 10$ , so $b = 30, 000/10 = 3000$ .
(a) $⌈ lo g_{2} 3000 ⌉ = 12$ , since $2^{11} = 2048 < 3000 \leq 4096 = 2^{12}$ .
Index fan-out: $b f r_{i} = ⌊ 1024/15 ⌋ = 68$ .
(b) Primary (sparse): $b_{i} = ⌈ 3000/68 ⌉ = 45$ (as $68 \times 44 = 2992$ ). Accesses $⌈ lo g_{2} 45 ⌉ + 1 = 6 + 1 = 7$ .
(c) Secondary (dense): $b_{i} = ⌈ 30, 000/68 ⌉ = 442$ (as $68 \times 441 = 29, 988$ ). Accesses $⌈ lo g_{2} 442 ⌉ + 1 = 9 + 1 = 10$ .
(d) Levels: 442, then $⌈ 442/68 ⌉ = 7$ , then 1, so $t = 3$ and accesses $= 4$ . Without an index, a search on the non-ordering field reads $b /2 = 1500$ blocks on average.
A multilevel index on (b) has levels 45 and 1, so $t = 2$ and 3 accesses.

Answer: (a) 12, (b) 7, (c) 10, (d) 4 block accesses.

B-trees and B+ trees

A B-tree or B+ tree is a balanced multiway search tree: every leaf is at the same depth, and nodes (except the root) are at least half full. Insertions split a full node and deletions merge or redistribute.

Conventions used here. The order $p$ of an internal node is its maximum number of child pointers (so at most $p - 1$ keys). Height $h$ is the number of levels, counting the root as level 1 and the leaves as level $h$ . Minimum occupancy: a non-root internal node has at least $⌈ p /2 ⌉$ children; the root has at least 2 children (if it is not a leaf); a leaf holding at most $q$ keys has at least $⌈ q /2 ⌉$ keys. Some definitions state occupancy differently, so check the question.

EXAM TIP

Questions do not all define order the same way. Some mean the maximum number of keys in a node; others give a minimum degree $t$ , with every non-root node holding between $t - 1$ and $2 t - 1$ keys (so at most $2 t$ children). Convert to this page's $p$ (maximum child pointers) before using the formulas below.

Property	B-tree	B+ tree
Record pointers	In every node, beside each key	Only in the leaves
Keys in internal nodes	Each key appears once in the whole tree	Internal keys only guide the search; every key that has a record is in a leaf (after deletions a separator may no longer be in any leaf)
Leaves	Not linked	Linked in key order, so range scans follow the chain
Fan-out of internal nodes	Smaller (each key carries a record pointer)	Larger, so the tree is usually shallower
Every search ends	Possibly in an internal node	Always at a leaf, so all equality searches read the same number of levels

B+ TREE INTERNAL NODE ORDER

p P + (p - 1) V \leq B

Largest $p$ satisfying this; internal nodes hold $p$ block pointers and $p - 1$ keys.

B+ TREE LEAF CAPACITY

q (V + P_{r}) + P \leq B

Largest number of keys $q$ in a leaf, where the extra $P$ is the next-leaf pointer.

B-TREE NODE ORDER

p P + (p - 1) (V + P_{r}) \leq B

Each key in a B-tree node carries a record pointer, so one node type serves internal nodes and leaves.

KEYS STORED IN A B+ TREE OF HEIGHT H

max keys (B+) = q p^{h - 1}, min keys (B+) = ⌈ \frac{q}{2} ⌉ \cdot 2 ⌈ \frac{p}{2} ⌉^{h - 2} (h \geq 2)

Max: every node full, so $p^{h - 1}$ leaves of $q$ keys. Min: the root has 2 children and every other internal node $⌈ p /2 ⌉$ , giving $2 ⌈ p /2 ⌉^{h - 2}$ leaves, each with $⌈ q /2 ⌉$ keys.

KEYS STORED IN A B-TREE OF HEIGHT H

max keys (B-tree) = p^{h} - 1, min keys (B-tree) = 2 ⌈ \frac{p}{2} ⌉^{h - 1} - 1

Max: all $(p^{h} - 1) / (p - 1)$ nodes full with $p - 1$ keys each. Min: the root has 1 key (2 children) and every other node $⌈ p /2 ⌉ - 1$ keys.

BLOCK ACCESSES FOR AN EQUALITY SEARCH

accesses (B+ tree, record via leaf pointer) = h + 1

One block per level down to the leaf, plus one to read the data record. Leaves holding the record itself need only $h$ .

Range search $c_{1} \leq a \leq c_{2}$ on a B+ tree: $h$ accesses to reach the leaf holding $c_{1}$ , one more for each further leaf in the range (following the leaf chain), then, when leaves hold record pointers, up to one data-block access per matching record. It costs fewer if the file is also ordered on $a$ .

Splitting on insertion. When a B+ tree leaf already holding $q$ keys receives one more, it splits into two leaves of $⌈(q + 1) /2 ⌉$ and $⌊(q + 1) /2 ⌋$ keys (which half gets the extra key is a convention, so follow the question), and the smallest key of the new right leaf is copied up into the parent. When an internal node overflows, it splits and its middle key moves up: it stays in neither half. In a B-tree every split works like the internal-node split, with the middle key moving up. A split can propagate upward; when the root splits, a new root is created, and this is the only way the height grows.

WORKED EXAMPLE

A B+ tree index has block size $B = 512$ bytes, key size $V = 10$ bytes, block pointer $P = 8$ bytes and record pointer $P_{r} = 8$ bytes. Find the order $p$ of an internal node, the leaf capacity $q$ , and the maximum and minimum number of keys in a tree with $h = 3$ levels. How many block accesses does an equality search take?

Solution

Internal node: $8 p + 10 (p - 1) \leq 512$ , so $18 p \leq 522$ and $p = 29$ .
Leaf: $18 q + 8 \leq 512$ , so $18 q \leq 504$ and $q = 28$ .
Maximum keys: $q p^{h - 1} = 28 \times 2 9^{2} = 28 \times 841 = 23, 548$ .
Minimum: leaves $= 2 ⌈ 29/2 ⌉^{1} = 2 \times 15 = 30$ ; keys per leaf $⌈ 28/2 ⌉ = 14$ ; total $30 \times 14 = 420$ .
Search: 3 index levels (root, internal, leaf) plus one data block gives 4 accesses.

Answer: $p = 29$ , $q = 28$ ; between 420 and 23,548 keys; 4 block accesses.

Hash-based indexing

Static hashing fixes $M$ buckets and sends a record with key $K$ to bucket $h (K) = K mod M$ (or another hash function). When a bucket is full, extra records go to overflow blocks chained to it, so a skewed or overloaded file degrades from about 1 access toward a chain scan.

Dynamic schemes avoid fixed size. In extendible hashing a directory of $2^{d}$ pointers is indexed by $d$ bits of the hash value, the first $d$ bits in some presentations and the last $d$ in others, so follow the question ( $d$ is the global depth). Each bucket has a local depth $d^{'} \leq d$ . When a bucket overflows, it splits and its local depth increases by 1; if the new local depth exceeds $d$ , the directory doubles. If all the bucket's records fall into the same half, the split repeats. Several directory entries may point to one bucket. Linear hashing instead splits buckets one at a time in a fixed order, with no directory.

EXTENDIBLE HASHING DIRECTORY

directory entries = 2^{d}, entries pointing to a bucket = 2^{d - d^{'}}

$d$ is the global depth and $d^{'}$ a bucket's local depth.

EXAM TIP

A hash index answers equality lookups in about one access, but it cannot answer range queries, prefix searches or ORDER BY efficiently, because hashing scatters neighbouring keys. A B+ tree handles all of these.

Choosing an index for a given query

Query shape	Useful index	Reason
`WHERE a = c`, one row expected	B+ tree or hash on `a`	Both reach the row in a few accesses; hash is about 1
`WHERE a BETWEEN c1 AND c2`	B+ tree on `a` (best if the file is also ordered on `a`, a clustering index)	Locate $c_{1}$ , then follow the leaf chain; hash cannot do this
`WHERE a = c AND b = d`	Index on `a` or `b`, or a composite $(a, b)$ index	A composite index lets one search satisfy both conditions
`ORDER BY a`	B+ tree on `a`	Leaves are already in key order (if the file is not ordered on `a`, fetching each row can cost one data access)
Condition on a function such as `a+1 = c`	Usually no index helps	The index is ordered on `a`, not on `a+1`
Condition matching a large fraction of rows (field with few distinct values)	Little benefit	The index leads to most blocks anyway, so a scan can be as good

EXAM TIP

A composite B+ tree index on $(a, b)$ helps queries that fix a (alone, or with b), but it cannot be used to search directly on b alone, because entries are sorted on a first. Also, an index speeds reads but costs extra block writes on every insert, delete and update of its field.

PREVIOUS-YEAR QUESTIONS

3 questions from the DA papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE DA 2026 · GATE DA 2024

GATE 2026 DA Q.32

GATE 2026 · DAQ.32 · 1 mark · NAT

In a relational database, a B+ Tree Index is to be constructed for a relation on a key field. In a B+ Tree, a Node Pointer points to a sub-tree and a Data Record Pointer points to a block of database records.

Let, Node size = 4096 bytes, Node Pointer size = 10 bytes, Search Key Field size = 11 bytes and Data Record Pointer size = 12 bytes.

The maximum number of Node Pointers that can be present in a non-leaf node of the B+ Tree is ________ . (Answer in integer)

Answer and solution

GATE 2026 DA Q.32: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 DA Q.32: answer and solution

GATE 2026 DA Q.41

GATE 2026 · DAQ.41 · 2 marks · MCQ

Consider a B+ Tree where the maximum number of key values in each leaf node is 2 and the maximum number of pointers in each non-leaf node is 3. Let the content of the B+ Tree be as shown in the figure.

Which of the following options denotes the key value(s) stored in the root node after inserting a key value 3 in the given B+ Tree?

GATE 2026 DA question 41: A B+ tree. — Figure from the GATE 2026 DA paper. It is part of the question.

(A)
5
(B)
8
(C)
3 and 5
(D)
3, 5 and 8

Answer and solution

GATE 2026 DA Q.41: answer and solution

GATE 2024 DA Q.55

GATE 2024 · DAQ.55 · 2 marks · MSQ

An OTT company is maintaining a large disk-based relational database of different movies with the following schema:

Movie(ID, CustomerRating)
Genre(ID, Name)
Movie_Genre(MovieID, GenreID)

(Primary keys underlined in print: Movie.ID; Genre.ID; Movie_Genre.MovieID and GenreID together.)

Consider the following SQL query on the relation database above:

SELECT *
FROM Movie, Genre, Movie_Genre
WHERE
    Movie.CustomerRating > 3.4 AND
    Genre.Name = "Comedy" AND
    Movie_Genre.MovieID = Movie.ID AND
    Movie_Genre.GenreID = Genre.ID;

This SQL query can be sped up using which of the following indexing options?

(A)
B $^{+}$ tree on all the attributes.
(B)
Hash index on Genre.Name and B $^{+}$ tree on the remaining attributes.
(C)
Hash index on Movie.CustomerRating and B $^{+}$ tree on the remaining attributes.
(D)
Hash index on all the attributes.

Answer and solution

GATE 2024 DA Q.55: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.55: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 11 mark · NAT

A file has 1000 fixed-length records of 300 bytes each, stored in disk blocks of 2048 bytes. Records are unspanned. How many data blocks does the file occupy?

Answer and solution

Answer: $167$

Blocking factor: $⌊ 2048/300 ⌋ = 6$ , since $6 \times 300 = 1800$ and $7 \times 300 = 2100 > 2048$ .
Blocks: $⌈ 1000/6 ⌉ = ⌈ 166.67 ⌉ = 167$ .

PRACTICE 22 marks · MSQ

Which of the following statements about single-level indexes on a data file are correct?

(A)
A sparse index requires the data file to be ordered on the indexed field.
(B)
The first level of a secondary index on a field by which the file is not ordered cannot be sparse.
(C)
A file can have two different clustering indexes, one on each of two different fields.
(D)
If the blocking factor is at least 2 and the file has at least two records, a sparse primary index on the ordering key field has fewer entries than a dense index on the same field.

Answer and solution

Answer: (A), (B), (D)

A is correct: a sparse index relies on finding the block whose first key is at most the search key, which works only if records are in key order.
B is correct: when the file is not ordered on the field, keys in a block are not related to the block's anchor, so every record (or every value) needs its own entry.
C is false: the file can be physically ordered on only one field, so it has at most one primary or clustering index.
D is correct: the sparse index has one entry per block, and $b = ⌈ r / b f r ⌉ < r$ when $b f r \geq 2$ and $r \geq 2$ , while the dense index has $r$ entries.

PRACTICE 32 marks · NAT

A B+ tree has internal nodes of order 10 (at most 10 child pointers and 9 keys) and leaves holding at most 9 keys. Non-root internal nodes have at least $⌈ 10/2 ⌉$ children, the root (not a leaf) has at least 2 children, and every leaf has at least $⌈ 9/2 ⌉$ keys. What is the minimum number of keys in such a tree that has exactly 3 levels (root, one level of internal nodes, leaves)?

Answer and solution

Answer: $50$

Minimum leaves: the root has 2 children, each internal node at level 2 has at least 5 children, so $2 \times 5 = 10$ leaves.
Minimum keys per leaf: $⌈ 9/2 ⌉ = 5$ .
Minimum keys: $10 \times 5 = 50$ (formula: $⌈ q /2 ⌉ \cdot 2 ⌈ p /2 ⌉^{h - 2} = 5 \cdot 2 \cdot 5 = 50$ ).

PRACTICE 42 marks · MCQ

A file has $2^{20}$ records and a dense multilevel secondary index on a key field. Each index entry is 16 bytes and each block is 4096 bytes. The top level of the index fits in one block. How many block accesses are needed to read one record by its key value, counting the data block?

(A)
3
(B)
4
(C)
5
(D)
20

Answer and solution

Answer: (B)

Fan-out $= 4096/16 = 256 = 2^{8}$ .
First level (dense): $2^{20} / 2^{8} = 2^{12} = 4096$ blocks.
Second level: $4096/256 = 16$ blocks. Third level: $⌈ 16/256 ⌉ = 1$ block, so $t = 3$ levels (check: $⌈ lo g_{256} 4096 ⌉ + 1 = 2 + 1 = 3$ ).
Accesses $= t + 1 = 4$ (three index blocks plus the data block).

PRACTICE 51 mark · MCQ

A table Emp(id, dept, salary) has only a hash index on dept. Consider these queries.

Query P:

SELECT *
FROM Emp
WHERE dept = 'CS';

Query Q:

SELECT *
FROM Emp
WHERE dept > 'CS';

Query R:

SELECT *
FROM Emp
ORDER BY dept;

Query S:

SELECT *
FROM Emp
WHERE salary = 5000;

Which query can use this index effectively?

(A)
Query P
(B)
Query Q
(C)
Query R
(D)
Query S

Answer and solution

Answer: (A)

A hash index maps an exact key value to its bucket, so an equality condition on dept (query P) is answered in about one access.
Query Q is a range condition and query R needs key order; hashing scatters neighbouring keys, so neither benefits.
Query S tests salary, which the index does not cover.

PRACTICE 61 mark · NAT

An extendible hash file has global depth 4. One of its buckets has local depth 2. How many directory entries point to this bucket?

Answer and solution

Answer: $4$

Entries pointing to a bucket $= 2^{d - d^{'}} = 2^{4 - 2} = 4$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE DA

file organization, indexing

Preparing in Kolkata? IAE Academy's course for GATE DA.