Indexing questions in GATE are counting questions in disguise. Once you separate dense from sparse and ordering fields from non-ordering fields, the remaining work is floor, ceiling, and block-access arithmetic.
A single data file settles most of them: 10,000 records of 100 bytes, stored in 1024-byte blocks. From those three numbers come the file's block count, the size of a sparse primary index over it, the extra level that index needs, and the far larger dense secondary index a non-ordering field would demand.
Primary, clustering, secondary, dense, and sparse
Start with the field that controls the physical order of the data file.
A primary index is built when the file is ordered on a key field, commonly the primary key. Because records are physically sorted on that field, the index can be sparse.
A clustering index is built when the file is ordered on a non-key field. Duplicate values form runs, and an entry can point to the first block containing each value's run.
A secondary index is built on a field that does not control the file's physical order. Matching records may be scattered, so a secondary index must provide dense coverage.
These categories describe the relationship between the search field and file order. An index on a declared primary key is not a primary index in this file-organization sense if the file is physically ordered on some other field.
Dense means there is an index entry for every record, or one per distinct search-key value with a bucket of record pointers for duplicates. Sparse means only selected search values have entries, typically one anchor per data block. Sparse search works only when file order tells the system which block can contain the missing values.
The block-access model
File organization is the choice of how records sit in disk blocks, and it decides what an index is allowed to do. A heap file appends each record wherever there is room, so any index on it has to be dense: nothing about the file tells you which block a missing value would have occupied. Order the file on one field and that field, and only that field, becomes sparse-indexable at one anchor per block.
Let block size be B bytes and fixed record size be R bytes. Records are stored unspanned, so no record straddles a block boundary, and the file blocking factor is:
bfr = floor(B/R)
If there are r records, the number of data blocks is:
b = ceil(r/bfr)
An index entry contains a search key and a pointer. If its size is I bytes, the index blocking factor is:
bfri = floor(B/I)
Use floor for the number of complete records or entries that fit in one block. Use ceiling for the number of blocks needed to store all records or entries.
In a multilevel index, the lowest index level points to data blocks. The next level has one sparse entry per block of the level below. Repeat until the top level fits in one block. A lookup then reads one block at each index level and one final data block:
block accesses = number of index levels + 1
Fully worked index-block numerical
Suppose a file has 10,000 records. Each record is 100 bytes, each block is 1024 bytes, the ordering key is 9 bytes, and a block pointer is 6 bytes.
First count records per data block:
bfr = floor(1024/100) = floor(10.24) = 10 records per block
Then count data blocks:
b = ceil(10000/10) = 1000 data blocks
A sparse primary index has one entry per data block, so it has 1,000 entries. Each entry is:
I = 9 + 6 = 15 bytes
Its blocking factor is:
bfri = floor(1024/15) = floor(68.266...) = 68 entries per block
The first index level therefore needs:
ceil(1000/68) = ceil(14.705...) = 15 index blocks
If we binary-search the 1,000 sorted data blocks directly, the model gives ceil(log2(1000)) = 10 block accesses. If we binary-search the 15 index blocks, it takes ceil(log2(15)) = 4 index-block accesses, followed by one data-block access:
4 + 1 = 5 block accesses
Now make the index multilevel. The second level needs one entry for each of the 15 first-level blocks. All 15 entries fit in one block because its capacity is 68. There are now two index levels, so a search reads:
1 top-level block + 1 first-level block + 1 data block = 3 blocks
For contrast, build a dense secondary index on a different non-ordering unique field whose key is also 9 bytes. It needs one entry per record, or 10,000 entries:
ceil(10000/68) = ceil(147.058...) = 148 index blocks
That is the central count difference: 1,000 sparse entries and 15 blocks versus 10,000 dense entries and 148 blocks.
For the tree structure that maintains a dynamic multilevel index efficiently, continue with B+ Trees and Database Indexing.
Dense versus sparse on a tiny file
Take a sorted file containing three blocks:
Block | Keys |
|---|---|
B1 | 10, 20, 30 |
B2 | 40, 50, 60 |
B3 | 70, 80, 90 |
A dense index has nine entries: 10, 20, 30, 40, 50, 60, 70, 80, and 90. Each entry identifies the matching record.
A sparse index can use only three anchors: 10 points to B1, 40 points to B2, and 70 points to B3. To find 50, locate the greatest anchor not exceeding 50, which is 40, follow it to B2, and search that block.
Without physical ordering, the 40 anchor gives no guarantee that 50 is in the same block or even nearby. That is why a secondary index cannot use this sparse shortcut.
The traps GATE plants
Do not mix the data-file blocking factor with the index blocking factor. One uses record size; the other uses key-plus-pointer entry size. Apply floor when calculating capacity, then ceiling when calculating required blocks.
Remember the final data read. Two index levels mean three block accesses, not two. Also separate a primary index on an ordering key from a clustering index on an ordering non-key field. For duplicates in a clustering index, an entry commonly points to the first block of that value's run.
A secondary index is on a non-ordering field and needs dense coverage. A sparse index is possible only when the data file's ordering makes the gaps searchable. Keep this physical-order question separate from the SQL-level key and join concepts covered in SQL Queries and Joins in DBMS.
How indexing appears in GATE
Questions provide record count, record size, block size, key size, and pointer size, then ask for data blocks, index entries, index blocks, levels, or access cost. A conceptual variant asks whether a proposed index can be sparse or whether it is primary, clustering, or secondary.
Write bfr, data blocks, entry size, and bfri on four separate lines. That prevents a record size from leaking into index arithmetic. Then build levels until one block remains and add the final data-block read. For the current DBMS scope, confirm the syllabus on the official GATE portal of the organising IIT.
The short version and next step
Dense means coverage per record or distinct value; sparse usually means one anchor per block and requires ordering. Use floor for capacity, ceiling for blocks and levels, and count one access per index level plus one for data.
Practise the numericals in the GATE Test Series, then build indexing and B+ tree theory with GATE Guidance by Sanchit Sir. The DBMS practice set runs to about 2,000 questions, file organization and indexing included. The GATE preparation category provides the wider study path.
