Storage basics: disk, blocks, block access cost, records, blocking factor, spanned vs unspanned

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Which normal form always allows a lossless, dependency-preserving decomposition? from Lesson 4.4.4
2. In the three-schema architecture, which level describes how data is stored? from Lesson 0.1.3
3. What is physical data independence? from Lesson 0.1.3

1 · The Hook

Every query so far ran on tables as if they lived in thin air. They live on disk, and a disk is millions of times slower than memory. A query that touches 3,000 disk blocks takes seconds; one that touches 4 takes milliseconds. Phase 5 is about counting block accesses, the unit every GATE indexing question uses.

2 · Predict First

STUDENT has 30,000 records of 100 bytes each. A disk block holds 1,024 bytes, and a record may not be split across blocks. How many records fit in one block, and how many blocks does the file need?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

⌊1024 / 100⌋ = 10 records per block (24 bytes wasted). ⌈30000 / 10⌉ = 3,000 blocks.

Disks and blocks

A hard disk stores data on spinning platters; a read/write head on an arm moves over tracks; each track is divided into sectors. The DBMS reads and writes whole blocks (pages) of fixed size B, such as 512, 1024, 4096 bytes.

Time to read one block = seek time (move the arm to the track) + rotational latency (wait for the sector to come under the head; on average half a rotation) + transfer time. Example: 6,000 rpm → one rotation = 60,000 / 6,000 = 10 ms → average rotational latency 5 ms.

Because block access dominates every other cost, query cost in GATE is measured in number of block accesses.

Records and the blocking factor

A record is the stored form of a tuple; record size R bytes (fixed-length records unless stated).

Blocking factor bfr = number of records per block = ⌊B / R⌋ (unspanned).

Number of blocks for r records: b = ⌈r / bfr⌉.

Spanned vs unspanned

• Unspanned: a record must fit entirely inside one block; leftover space B − bfr × R is wasted. Needed when R ≤ B; simpler to access.
• Spanned: a record may continue into the next block (a pointer marks the continuation). No waste, so b = ⌈r × R / B⌉. Needed when R > B.

Worked numbers

r = 30,000, R = 100, B = 1024:

• Unspanned: bfr = 10, b = 3,000, waste 24 bytes per block.
• Spanned: b = ⌈3,000,000 / 1024⌉ = ⌈2929.7⌉ = 2,930 blocks.

Pointers

A block pointer (P) holds a block's disk address. A record pointer (Pr) holds a block address plus the position inside it, so it is usually a little larger. Index questions give their sizes in bytes.

4 · Visual

Block of 1024 bytes, records of 100 bytes (unspanned)

| R1 | R2 | R3 | R4 | R5 | R6 | R7 | R8 | R9 | R10 |waste 24|
  bfr = floor(1024 / 100) = 10           b = ceil(30000 / 10) = 3000 blocks

Spanned: records run across block boundaries, no waste: b = ceil(30000*100/1024) = 2930

5 · Worked Examples

Example 1 Easy

B = 512 bytes, R = 60 bytes, r = 10,000, unspanned. Find bfr and b.

Solution

bfr = ⌊512/60⌋ = 8. b = ⌈10000/8⌉ = 1,250.

Example 2 Medium

Same file, spanned. How many blocks?

Solution

⌈10000 × 60 / 512⌉ = ⌈1171.875⌉ = 1,172.

Example 3 GATE

A disk rotates at 7,200 rpm. What is the average rotational latency in milliseconds (to one decimal)?

Solution

One rotation = 60,000 / 7,200 = 8.33 ms; average latency = half = 4.2 ms.

8 · Connect the Dots

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Blocking factor

B = 4096 bytes, R = 300 bytes, unspanned. What is bfr?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Blocks

r = 20,000 records, R = 150 bytes, B = 2048 bytes, unspanned. How many blocks?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Spanned

Same file stored spanned. How many blocks?

Numerical answer: ________

Q4 · NAT · 1 mark(s) — Latency

A disk spins at 12,000 rpm. Average rotational latency in ms?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Spanned

Spanned organisation is required when:

1. (A) the file is sorted
2. (B) R > B
3. (C) R < B
4. (D) the file has an index

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

disk block (page)seek timerotational latencytransfer timeblock accessrecord sizeblocking factor bfrunspanned / spanned recordsblock pointerrecord pointer