Self-checkedTier 1 9 min readdbms.file-organisation

File organisation and blocking factor

How records are stored on disk: blocks, records per block (the blocking factor), the number of blocks of a file for fixed-length records (unspanned and spanned), the cost of a block access, and the three basic file organisations (heap, sorted, hashed) with the number of block accesses for search, insertion, deletion and range queries; the textbook binary-search formula ceil(log2 b) against the exact count floor(log2 b) + 1, checked by measuring searches on generated files.

Why it exists

A database lives on disk, and a disk is read and written in blocks. The time of a query is dominated by the number of blocks it touches, so the basic questions of file organisation are numerical: how many records fit in a block, how many blocks does the file need, how many blocks must be read to find a record. These calculations appear in almost every GATE paper.

Prerequisites

You need the structure of a disk: surfaces, tracks, sectors and blocks, and the three delays of an access (secondary storage and disks). The essentials are repeated below.

Precise definitions

Block (page): the unit of transfer between disk and memory; size $B$ bytes (typical $512$ B to $8$ KB).
Block access time = seek time (move the head to the track) + rotational latency (wait for the sector; on average half a rotation) + transfer time ( $B$ divided by the transfer rate). Example: 7200 rpm gives $60\,000/7200 = 8.33$ ms per rotation and $4.17$ ms average rotational latency; with an average seek of $9$ ms and a transfer of a $4$ KB block at $100$ MB/s ( $0.041$ ms) a block access takes about $13.2$ ms. Reading consecutive blocks avoids repeated seeks and is much cheaper per block.
Record: a row, stored as a sequence of fields of fixed length $R$ bytes (variable-length records need length fields or separators and are not used in the calculations below).
Blocking factor $bf = \lfloor B / R \rfloor$ : the number of records that fit completely in one block. The unused space per block is $B - bf \cdot R$ bytes.
Number of blocks for $r$ records (unspanned): $b = \lceil r / bf \rceil$ .
Spanned organisation: a record may be split over two blocks (with a pointer to the continuation). No space is wasted, so the file needs $\lceil r R / B \rceil$ blocks. Unspanned: every record lies completely in one block (the usual case; it requires $R \le B$ ).
A record pointer is a block address plus the offset inside the block.

Three basic file organisations: heap (unordered): records in insertion order; sorted (ordered): records ordered by a key field; hashed: the block of a record is computed from the key by a hash function.

How it works

Records, blocks and searches

The sizes for four parameter sets:

Records, blocks and search cost: start

Computed by a script, not typed

parameters	records per block (bf)	blocks b (unspanned)	bytes wasted per block	blocks if spanned	average blocks, unordered file	worst case, unordered file	binary search, textbook ⌈log2 b⌉	binary search, exact worst case
B = 1024, R = 100, r = 30 000
B = 4096, R = 200, r = 1 000 000
B = 512, R = 120, r = 5 000
B = 1024, R = 300, r = 10 000

Step 0

bf = ⌊B/R⌋, b = ⌈r/bf⌉. For an unordered (heap) file a search for an existing key reads (b + 1)/2 blocks on average. For an ordered file binary search needs ⌈log2 b⌉ block accesses by the usual formula; counting probes exactly gives ⌊log2 b⌋ + 1, which is larger by one when b is a power of 2.

0 / 4

computed by script: the file and index sizes are computed from their formulas, the trees are built by real insertions and deletions. python3 scripts/gen-db4-traces.py

For the first row: $bf = \lfloor 1024/100 \rfloor = 10$ , $b = \lceil 30\,000/10 \rceil = 3000$ blocks, $24$ bytes lost per block; with spanning $\lceil 30\,000 \cdot 100 / 1024 \rceil = 2930$ blocks.

Heap file. Insertion is cheap: append to the last block (read it, write it: 2 accesses, or 1 if the last block is kept in memory). A search on any field must scan the file: for a key that exists, on average $(b + 1)/2$ blocks, at most $b$ ; for a missing key always $b$ . Deleting needs the search and a rewrite of the block (the record is marked deleted; space is reclaimed by reorganising periodically).

Sorted file. The records are ordered by a key. A search on the ordering key uses binary search over the blocks: the textbooks (and GATE) give $\lceil \log_2 b \rceil$ block accesses. The exact worst case is $\lfloor \log_2 b \rfloor + 1$ , one more when $b$ is a power of two; measured on real sorted files:

Block accesses of a binary search, formula against measurement: start

Computed by a script, not typed

file size	textbook ⌈log2 b⌉	exact ⌊log2 b⌋ + 1	measured worst case
b = 1
b = 2
b = 3
b = 4
b = 5
b = 8
b = 9
b = 16
b = 17
b = 100
b = 1024

Step 0

A sorted file is searched by binary search over its blocks, reading one block per probe. The measured worst case over all keys of the file equals ⌊log2 b⌋ + 1. The textbook formula ⌈log2 b⌉ is the same except when b is a power of 2, where it is one smaller. Exam answers follow the textbook formula.

0 / 11

computed by script: the file and index sizes are computed from their formulas, the trees are built by real insertions and deletions. python3 scripts/gen-db4-traces.py

For $b = 3000$ both formulas give $12$ . A search on any other field is a linear scan. A range query on the ordering key finds the first record by binary search and then reads consecutive blocks. Insertion is expensive: the record must go to its place and the following records shift; with all blocks full and no spare room about half the file is read and rewritten: $(b + 1)/2$ block reads and as many writes on average (measured). Practical files keep free space in each block or use an overflow area that is merged during reorganisation. Deletion uses a deletion marker.

Hashed file. The block of a record is $h(\text{key})$ ; an exact-match search reads one block (plus overflow blocks) but range queries are impossible (hash-based file organisation).

operation	heap	sorted (on the ordering key)	hashed
equality search	$(b+1)/2$ average, $b$ worst	$\lceil \log_2 b \rceil$	about $1$
range search	$b$	$\lceil \log_2 b \rceil$ + consecutive blocks	$b$
insert	$1$ to $2$	about $b$ (shift)	about $1$ to $2$
search on a non-key field	$b$	$b$	$b$

Why indexes are needed

If a table has $3000$ blocks, even a perfectly sorted file needs $12$ block accesses per search, and only for ONE field. An index is a small separate file that finds the block of a record with fewer accesses and works for other fields too (ordered indexes, B+ trees).

Worked examples

EX 1Blocks of a file

Easy

$B = 4096$ , $R = 128$ , $r = 100\,000$ . $bf = 4096/128 = 32$ ; $b = \lceil 100\,000/32 \rceil = 3125$ blocks. No wasted space ( $32 \cdot 128 = 4096$ ). Linear search for an existing key: $(3125 + 1)/2 = 1563$ blocks on average, $3125$ at worst.

EX 2Spanned or not

Easy

$B = 1024$ , $R = 300$ , $r = 10\,000$ . Unspanned: $bf = 3$ , $b = \lceil 10\,000/3 \rceil = 3334$ blocks, $124$ bytes wasted per block. Spanned: $\lceil 3\,000\,000/1024 \rceil = 2930$ blocks. Unspanned wastes about $12\%$ of the space here.

EX 3Binary search on a sorted file

Medium

$r = 30\,000$ records of $100$ bytes, $B = 1024$ : $b = 3000$ blocks. Binary search: $\lceil \log_2 3000 \rceil = 12$ block accesses. A linear search of the same file would need $1500$ on average. For $b = 4096$ the textbook formula gives $12$ and the exact count $13$ ; use the textbook formula unless told otherwise.

EX 4Cost of inserting into a sorted file

Medium

A sorted file of $b = 500$ completely full blocks. Inserting a record at a random position: read and write all blocks from the insertion point to the end to shift the records: on average $(500 + 1)/2 = 250.5$ blocks read and as many written, about $500$ accesses. An insertion into a heap file: $2$ accesses. This is why sorted files are used for relatively static data.

EX 5Typical questions

GATE level

(a) "How many records fit in a block of 1024 bytes if a record has 100 bytes?" $10$ . (b) "How many blocks for 30 000 such records?" $3000$ . (c) "Average blocks searched in an unsorted file of $b$ blocks (key present):" $b/2$ (strictly $(b+1)/2$ ). (d) "Binary search on a sorted file of $b$ blocks:" $\lceil \log_2 b \rceil$ . (e) "Which organisation gives the fastest equality search on the key?" Hashing. (f) "Which supports range queries on the key efficiently?" Sorted file (and tree indexes), not hashing.

Cheat box

$bf = \lfloor B/R \rfloor$ ; $b = \lceil r/bf \rceil$ ; spanned: $b = \lceil rR/B \rceil$ .
Block access = seek + average rotational latency (half a rotation) + transfer.
Heap: insert ~ $1$ – $2$ ; search $(b+1)/2$ average, $b$ worst. Sorted: search $\lceil \log_2 b \rceil$ , insert ~ $b$ . Hashed: equality ~ $1$ , no ranges.
Exact binary-search worst case is $\lfloor \log_2 b \rfloor + 1$ ; the textbook gives $\lceil \log_2 b \rceil$ .
Cost is counted in block accesses, not in records.

Traps and GATE patterns

Connections

Builds on

Disk structure and access time

Unlocks

Hash-based file organisationPrerequisite ofplanned

Disk structure and access timeimplemented by Ordered, primary, clustering and secondary indexesPrerequisite of Ordered, primary, clustering and secondary indexesuses

Across subjects

Disk structure and access timeuses

Within this subject

Ordered, primary, clustering and secondary indexesimplemented-by

Hash-based file organisationimplemented-byplanned

Indexes reduce the number of accesses of a search (ordered indexes); tree indexes keep that cost low under insertions (B trees, B+ trees); hashing gives direct addressing (hash files).

PYQs

7 previous year questions from your book. I re-solved each one myself (3 by running or simulating, 4 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2014 · Set 2 · MCQ · 1 markQ15 · page 391 of the book

Consider 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 size(r(R)) < size(s(S)), the join will have
fewer number of disk block accesses if:

(a)relation r(R) is in the outer loop.
(b)relation s(S) is in the outer loop.
(c)join selection factor between r(R) and s(S) is more than 0.5.
(d)join selection factor between r(R) and s(S) is less than 0.5.

GATE 2006 · MCQ · 2 marksQ28 · page 408 of the book

Consider the relation enrolled(student, course) in which
(student, course) is the primary key, and the relation
paid(student, amount), where student is the primary
key. Assume no null values and no foreign keys or
integrity constraints. Assume that amounts 6000, 7000,
8000, 9000 and 10000 were each paid by 20% of the
students. Consider these query plans (Plan 1 on left,
Plan 2 on right) to "list all courses taken by students
who have paid more than x".

A disk seek takes 4ms, disk data transfer bandwidth is
300 MB/s and checking a tuple to see if amount is greater
than x takes 10 micro-seconds. Which of the following
statements is correct?

(a)Plan 1 and Plan 2 will not output identical row sets for all databases.
(b)A course may be listed more than once in the output of Plan 1 for some databases
(c)For x = 5000, Plan 1 executes faster than Plan 2 for all databases.
(d)For x = 9000, Plan I executes slower than Plan 2 for all databases.

GATE 2006 · MCQ · 2 marksQ31 · page 409 of the book

Consider a database with three relation instances shown
below. The primary keys for the Drivers and Cars
relation are did and cidrespectively and the records are
stored in ascending order of these primary keys as
given in the tables. No indexing is available in the
database.

D: Drivers relation

did
dname
rating
age
22
Karthikeyan
7
25
20
Salman
1
33
31
Boris
8
55
32
Amoldt
8
25
58
Schumacher
10
35
64
Sachin
7
35
71
Senna
10
16
74
Sachin
9
35
83
Rahul
3
25
95
Ralph
3
53

R: Reserves relation

did
cid
day
22
101
10/10/06
22
102
10/10/06
22
103
08/10/06
22
104
07/10/06
31
102
10/11/06
31
103
06/11/06
31
104
12/11/06
64
101
05/09/06
64
102
08/09/06
74
103
08/09/06

C: cars celation

cid
cname
colour
101
Renault
blue
102
Renault
red
103
Ferrari
green
104
Jaguar
red

select D.dname

from Drivers D

where D.didin  (

DATABASE MANAGEMENT  SYSTEM

select R.did

from Cars C, Reserves R

where R.cid = C.cid and C.colour = 'red'

intersect

select R.did

from Cars C, Reserves R

where R.cid  =C.cid and C.colour = 'green'
Let n  be the number of comparisons performed when
the above SQL query is optimally executed. If linear
search is used to locate a tuple in a relation using
primary key, then n  lies in the range.

(a)36-40
(b)44-48
(c)60-64
(d)100-104

GATE 2026 · Set 2 · MCQ · 1 markQ2 · page 422 of the book

In the context of DBMS, consider the two sets T and S
given below.

T
S
I:Logical Schema
Ii:Physical Schema
III: External Schema
 L: Views
M: File organization and
indexes
N: Relations

Which one of the following is the correct match from T
to S?

(a)I – L, II – M, III – N
(b)I – M, II – L, III – N
(c)I – N, II – M, III – L
(d)I – N, II – L, III – M

GATE 2024 · Set 2 · MSQQ5 · page 422 of the book

Which of the following file organizations is/are I/O
efficient for the scan operation in DBMS?

(a)Sorted
(b)Heap
(c)Unclustered tree index
(d)Unclustered hash index DATABASE MANAGEMENT SYSTEM

GATE 2005 · MCQ · 2 marksQ27 · page 426 of the book

A database table T1 has 2000 records and occupies 80
disk blocks. Another table T2 has 400 records and
occupies 20 disk blocks. These two tables have to be
joined as per a specified join condition that needs to be
evaluated for every pair of records from these two
tables. The memory buffer space available can hold
exactly one block of records for T1 and one block of
records for T2 simultaneously at any point in time. No
index is available on either table. If Nested-loop join
algorithm is employed to perform the join, with the
most appropriate choice of table to be used in outer
loop, the number of block accesses required for reading
the data are  .

(a)800000
(b)40080
(c)32020
(d)100

GATE 2005 · MCQ · 2 marksQ28 · page 426 of the book

A database table T1 has 2000 records and occupies 80 disk
blocks. Another table T2 has 400 records and occupies 20
disk blocks. These two tables have to be joined as per a
specified join condition that needs to be evaluated for every
pair of records from these two tables. The memory buffer
space available can hold exactly one block of records for
T1 and one block of records for T2 simultaneously at any
point in time. No index is available on either table. If,
instead of Nested-loop join, Block nested-loop join is used,
again with the most appropriate choice of table in the outer
loop, the reduction in number of block accesses required
for reading the data will be

(a)0
(b)30400
(c)38400
(d)798400

Self-check

Question 1

$B = 2048$ , $R = 300$ , $r = 50\,000$ . How many blocks (unspanned)?

Show answer

$bf = \lfloor 2048/300 \rfloor = 6$ , $b = \lceil 50\,000/6 \rceil = 8334$ .

Question 2

A sorted file has 1024 blocks. How many block accesses does a binary search need by the textbook formula? By exact counting?

Show answer

$\lceil \log_2 1024 \rceil = 10$ ; exactly $\lfloor \log_2 1024 \rfloor + 1 = 11$ .

Question 3

Why is inserting into a sorted file expensive?

Show answer

The records after the insertion point must be shifted, so about half the blocks are read and rewritten.

Question 4

What is the average rotational latency of a 6000 rpm disk?

Show answer

One rotation is $60\,000/6000 = 10$ ms, so the average latency is $5$ ms.

Revision card

One-screen revision

$bf = \lfloor B/R \rfloor$ , $b = \lceil r/bf \rceil$ ; spanned $\lceil rR/B \rceil$ .
Access time = seek + half rotation + transfer.
Heap $(b+1)/2$ search; sorted $\lceil \log_2 b \rceil$ ; hash ~1.
Sorted insertion ~ $b$ block accesses.

References

·Silberschatz, Korth, Sudarshan, Database System Concepts (7th edition), Chapter 13 (data storage structures), Sections 13.1 to 13.3
·Elmasri, Navathe, Fundamentals of Database Systems (7th edition), Chapter 16 (disk storage, basic file structures and hashing), Sections 16.1 to 16.7

Verification

scripts/enum-checks/db_index_check.py: for 400 random parameter sets the number of blocks obtained by packing records into blocks one by one equals ceil(r / floor(B / R)) (unspanned) and ceil(r R / B) (spanned); on generated sorted files of 1 to 100 blocks the worst-case number of blocks read by a binary search over the blocks, measured over every key of the file, equals floor(log2 b) + 1, which is one more than the textbook ceil(log2 b) exactly when b is a power of two; a linear search of an unordered file with full blocks reads exactly (b + 1) / 2 blocks on average over the existing keys and b blocks at worst; inserting into a sorted file with full blocks and no spare room rewrites (b + 1) / 2 blocks on average; the disk-time arithmetic (7200 rpm: 8.33 ms per rotation, 4.17 ms average rotational delay) was recomputed. The textbook formula ceil(log2 b) is what exam answers use. Disk parameters are typical numbers, not measurements. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and re-derived against the textbook definitions and the sample database. No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Lossless join and dependency preservation

Ordered, primary, clustering and secondary indexes