You may know heap files, primary indexes, and B+ trees, yet lose marks when a question says, "block size 4096 bytes, record size 100 bytes". File organization and indexing is a calculation-heavy part of GATE DBMS, but nearly every problem reuses one skeleton: blocking factor, number of blocks, and logarithm of blocks.
One 30,000-record EMPLOYEE file generates all of the numbers below: the heap and ordered baselines, sparse and dense index sizes, a two-level index, B+ tree node capacity computed from byte sizes, and hash bucket occupancy under static and extendible hashing.
What file organization actually decides
File organization decides how records are placed in disk blocks. Disk I/O dominates CPU work, so cost is counted mainly in block accesses.
For a b-block file:
Organization | Search behaviour | Main trade-off |
|---|---|---|
Heap, unordered | Equality search averages b/2 reads and takes b when absent | Cheap append |
Sequential, ordered on a key | Binary search takes ceil(log2 b) reads | Overflow area and periodic reorganization |
Hash | About one bucket read on its key | Inefficient range searches |
Running example: 30,000 fixed-length EMPLOYEE records of 100 bytes, in 4096-byte blocks with unspanned allocation.
Blocking factor: the arithmetic every question builds on
Unspanned allocation keeps every record inside one block. Therefore:
Blocking factor, bfr = floor(4096 / 100) = floor(40.96) = 40 records per block.
Number of data blocks, b = ceil(30,000 / 40) = ceil(750) = 750 blocks.
Each block uses 40 x 100 = 4000 bytes, so 4096 - 4000 = 96 bytes remain unused.
A heap equality search averages 750 / 2 = 375 block accesses. Ordered-file binary search takes ceil(log2 750) = ceil(9.55) = 10 block accesses. Every index must beat these baselines.
If records are spanned, capacity is treated fractionally as 4096 / 100 = 40.96 records per block, not floored to 40, which gives ceil(30,000 / 40.96) = 733 blocks instead of 750. Check the allocation rule first.
Primary, clustering, and secondary indexes
Ask two questions: is the file ordered on the indexed field, and is that field a key?
Ordered plus key means a primary index.
Ordered plus non-key means a clustering index.
An index on a non-ordering field is a secondary index.
A primary index is sparse with one entry per data block, anchored on that block's first record. A clustering index is also sparse, but it carries one entry per distinct value of the clustering field, pointing at the first block that holds that value. A secondary index must be dense, because nearby indexed values can sit in unpredictable data blocks.
Add two givens to the running example, a 10-byte key and a 6-byte block pointer. An index entry is then 16 bytes, so floor(4096 / 16) = 256 entries fit per index block. A sparse primary index needs ceil(750 / 256) = 3 index blocks. Lookup takes ceil(log2 3) = 2 index reads plus one data read, or 3 block accesses.
A dense secondary index needs 30,000 entries and ceil(30,000 / 256) = 118 index blocks. Lookup costs ceil(log2 118) + 1 = 7 + 1 = 8 block accesses. It beats 375, but costs more than the sparse index because it stores 30,000 entries instead of 750.
Multilevel indexes and B+ trees
An index is an ordered file, so it can also be indexed. The 118-block secondary index needs ceil(118 / 256) = 1 second-level block. One top-level read, one first-level read, and one data read give 3 block accesses. In general, the levels are roughly ceil(log base 256 of N).
A packed static index is awkward to update. A B+ tree adds node slack for inserts and splits. Calculate node capacity from the byte sizes a question gives you, never from a memorised order, and watch the pointer widths: an internal node stores 6-byte block pointers, while a leaf stores 7-byte record pointers that carry a block address plus an offset inside that block.
For an internal node with p pointers of 6 bytes and p - 1 keys of 10 bytes:
6p + 10(p - 1) <= 4096, so 16p <= 4106 and the largest integer is p = 256.
For a leaf with q entries, each holding a 10-byte key and a 7-byte record pointer, plus one 6-byte next-leaf pointer:
17q + 6 <= 4096, so q <= 4090 / 17 = 240.59 and q = 240.
Linked leaves make ordered scans and range queries efficient. For a key-by-key insert that overflows a leaf, splits it, and grows the root, plus the fanout-versus-height intuition behind these block counts, continue with B+ Trees and Database Indexing: Worked Insert Example.
Static hashing and extendible hashing
Let h(K) = K mod 1000. Uniform distribution puts about 30 records in each bucket. Those 30 records occupy 3,000 of a block's 4,096 bytes, so a bucket fits in one block and equality lookup costs about one access plus any overflow-chain hops. Growth lengthens those chains, while range queries may require a full scan because hashing destroys order.
Extendible hashing handles growth through a directory. Global depth 2 gives entries 00, 01, 10, and 11. If bucket 10 overflows, it splits into local-depth-3 buckets 100 and 101. Because 3 exceeds the global depth of 2, the directory doubles to 2^3 = 8 entries. A split raises local depth; exceeding global depth doubles the directory without rehashing all data.
Use hashing for equality-only workloads, a B+ tree for ranges or ordered scans, and a plain ordered file when the data is largely static.
How GATE and interviews test this topic
GATE questions ask for blocking factors, index blocks, block accesses, and B+ tree order from byte sizes. Conceptual MCQs ask which index can be sparse. Recent official GATE syllabus documents list file organization, including sequential and indexed organization, and indexing, including B and B+ trees, under Databases. Confirm the current cycle's syllabus on its official site.
Interviews turn the theory into system choices. One physical clustering order means at most one clustered index per table. B+ trees beat binary search trees on disk because greater fan-out reduces height and reads. Indexes can hurt write-heavy tables because data changes must also update index pages.
Timed numeric practice is where this topic becomes reliable. Use GATE Test Series, Mocks and Topic-wise Tests for timed application, then use DBMS MCQs for more question practice.
Traps that cost real marks
Sparse secondary index: Making a secondary index sparse copies the primary-index rule where it does not hold. Run the ordered-field and key questions first; secondary indexes are dense.
Mixed blocking factors: The data file holds 40 records per block, while the index holds 256 entries per block. Write the units beside both values.
Missing data access: Two index reads only locate the target block. Add the data read, making the sparse lookup 3, not 2.
Logarithm of records: Binary search on the ordered file works over 750 blocks, not 30,000 records. The costs are 10 reads, not 15.
Memorised B+ tree order: Some questions define order by pointers and others by keys. Rebuild the byte inequality from the given sizes.
The short version and your next step
Revise this chain: bfr = floor(B/R), blocks = ceil(N/bfr), heap average b/2, ordered search ceil(log2 b). Sparse indexes require matching file order, secondary indexes are dense, B+ trees support dynamic multilevel indexes, and hashing serves equality. The anchors are 40 records per block, 750 data blocks, 3 sparse-index accesses, 8 dense-index accesses, internal order 256, and leaf capacity 240.
For structured subject-wise planning, start with GATE Guidance by Sanchit Sir, then use the GATE CS Exam Preparation Courses and Test Series page to place DBMS inside the full preparation set.
