File allocation — contiguous, linked, indexed (inode): Worked examples

This page is the "throw everything at it" drill for File allocation — contiguous, linked, indexed (inode). We will not learn new theory — we will exercise the three schemes across every kind of input they can face: normal cases, the boundary between two index levels, a zero-size file, a file that is exactly one block, a growth request that fails, and an exam twist. Before any example, we build a map of all the cases.

Two numbers appear in almost every example, so we pin them down once, in plain words:

The scenario matrix

Every cell below is a distinct situation. The Ex column says which worked example covers it.

Case class	Contiguous	Linked	Indexed (inode)
Normal byte-to-block lookup	Ex 1	Ex 3	Ex 5
Boundary between levels/blocks	Ex 2 (block edge)	—	Ex 6 (direct↔indirect edge), Ex 12 (single↔double↔triple)
Zero-size / degenerate input	Ex 8 (empty & 1-block)	Ex 8	Ex 8
Limiting value (max reach)	—	Ex 11 (pointer-width limit)	Ex 7 (max file size)
Growth request (can it grow?)	Ex 4 (fails)	Ex 4 (succeeds)	Ex 4 (succeeds)
Real-world word problem	—	Ex 3	Ex 9 (photo library)
Exam-style twist	—	Ex 11 (width vs count)	Ex 10 (reads for 3 blocks)

Related boundaries live in External vs Internal Fragmentation (Ex 4), Free Space Management (bitmap, free list) (Ex 4 growth), and File Systems (ext4, FAT, NTFS) (Ex 3 FAT note).

Two tools we reuse (defined before first use)

The picture below (Figure s01) shows bytes as a long ruler and blocks as the tick-marks every $B$ bytes; the amber arrow marks byte 9000 landing inside block 2 at offset 808.

Figure — File allocation — contiguous, linked, indexed (inode)

Ex 1 — Contiguous, normal lookup (matrix: Contiguous / normal)

Ex 2 — Contiguous, block-edge boundary (matrix: Contiguous / boundary)

Ex 3 — Linked, word problem + random access (matrix: Linked / normal + word)

Worked example

A log file is stored with linked allocation; its blocks on disk are the chain $7 \to 3 \to 90 \to 12$ . The directory only knows the first block, 7. A program wants logical block 3 (its data). How many disk reads to locate it, and how many usable data bytes per block if $p = 4$ ?

Forecast: guess the read count — is it 1 (like contiguous) or 4?

Read block 7; its stored pointer says "next = 3". Why? Linked allocation hides the "next" address inside the block — you cannot know block 1's location without reading block 0.
Read block 3 → next = 90; read block 90 → next = 12; read block 12 = the target. Why? No formula exists; each address is revealed only by the previous read. That's the $O (n)$ cost.
Total reads to reach logical block $i$ is $i + 1 = 3 + 1 = 4$ . Why? You touch blocks $0, 1, 2, 3$ .
Usable data per block $= B - p = 4096 - 4 = 4092$ bytes. Why? The 4-byte pointer squats inside the block, stealing data space (this is internal overhead).

Verify: the FAT fix moves pointers into RAM, so chain-walking costs 0 disk reads and usable data returns to full $B = 4096$ . Consistency check: $4092 = 4096 - 4$ . ✓

The chain and its four reads are drawn in Figure s02: each cyan box is a data block, the amber slot inside it is the next-pointer, and the amber arrows are the links you must follow one after another to reach logical block 3.

Ex 4 — Growth request, all three schemes (matrix: growth row)

Worked example

A 3-block file sits at contiguous blocks 20–22. Block 23 is already occupied by another file. The user appends data needing a 4th block. What happens under each scheme?

Forecast: which scheme(s) grow in place, and which must copy the whole file?

Contiguous: block 23 is taken, so the file cannot extend. It must be moved entirely to a free run of ≥4 blocks (say 60–63) and blocks 20–22 freed. Why? Contiguous demands consecutive blocks — no gap allowed. Cost = copy all existing data. If no run of 4 exists despite enough total free space, that is external fragmentation.
Linked: grab any free block, say block 200; write the old last block's pointer to point at 200. Why? A chain doesn't care where the next link lives. Growth = $O (1)$ , no copy.
Indexed (inode): grab any free block 200; write its address into the next empty index slot. Why? The index is just an array of addresses; appending is one slot write, no copy. Free block found via the free-space bitmap.

Verify: matches the comparison table — "Grows easily?" is No / Yes / Yes for contiguous / linked / indexed. ✓

Ex 5 — Indexed, normal lookup (matrix: Indexed / normal)

Ex 6 — Inode, the direct↔indirect boundary (matrix: Indexed / boundary)

Worked example

Unix inode: 12 direct pointers (logical blocks 0–11), then a single-indirect block holding $k = 1024$ pointers (logical blocks 12–1035). For logical blocks 11 and 12, how many disk reads to fetch the data (inode already in memory)?

Forecast: does crossing from 11 to 12 cost an extra read?

Block 11: it is a direct pointer — the inode already holds its address. Reads = 1 (just the data block). Why? Direct pointers live in the inode, which is in memory; zero pointer-blocks to fetch.
Block 12: first block past the 12 direct slots → it lives via the single-indirect block. Reads = 2: (1) read the single-indirect block to get the address, (2) read the data block. Why? One extra level of pointers must be dereferenced from disk.
The jump 11→12 adds exactly one disk read. Why? That is the price of leaving the direct region — the "80/20" design keeps tiny files (≤12 blocks) at 1 read.

Verify: direct region size = 12 blocks (indices 0..11); single-indirect adds $k = 1024$ (indices 12..1035). $12 + 1024 = 1036$ blocks reachable before double-indirect. ✓

Figure s03 draws exactly this boundary: the in-memory inode on the left, a cyan single-read arrow to data block 11 (direct), and an amber two-hop path (indirect block → data block) to block 12.

Ex 7 — Inode, limiting value: maximum file size (matrix: Indexed / limiting)

Worked example

With $B = 4096$ , $p = 4$ so $k = 1024$ , compute the maximum file size an inode can address.

Forecast: is it megabytes, gigabytes, or terabytes? Which level dominates?

Direct: $12 \times B = 12 \times 4096 = 49, 152$ B $\approx 48$ KB (recall $\approx$ means "close to, after rounding"). Why? 12 pointers, one block each.
Single-indirect: $k \times B = 1024 \times 4096 = 4, 194, 304$ B $=$ 4 MB. Why? One block of $k$ pointers, each a data block.
Double-indirect: $k^{2} \times B = 102 4^{2} \times 4096 = 4, 294, 967, 296$ B $=$ 4 GB. Why? $k$ pointers, each to a single-indirect block of $k$ → $k^{2}$ data blocks.
Triple-indirect: $k^{3} \times B = 102 4^{3} \times 4096 = 4, 398, 046, 511, 104$ B $\approx 4$ TB. Why? One more factor of $k$ .
Total $= 49, 152 + 4, 194, 304 + 4, 294, 967, 296 + 4, 398, 046, 511, 104 = 4, 402, 345, 721, 856$ B $\approx 4$ TB. Why? Each level multiplies reach by $k = 1024$ , so triple-indirect swamps the rest.

Verify: total in TiB $= 4, 402, 345, 721, 856/102 4^{4} \approx 4.004$ TiB — dominated by the triple term, exactly as the geometric growth predicts. ✓

Ex 8 — Degenerate inputs: empty file & one-block file (matrix: zero/degenerate)

Worked example

Handle the two smallest cases in each scheme: a 0-byte file (length $L = 0$ blocks) and a 1-block (4096-byte) file (length $L = 1$ block).

Forecast: does a 0-byte file still need an index block? Does it use any data blocks?

0-byte file, all schemes: uses 0 data blocks, i.e. $L = 0$ . Contiguous stores $(b, L = 0)$ ; linked stores "first block = none"; inode stores metadata with all pointers null. Why? $⌈ 0/ B ⌉ = 0$ blocks of data (ceiling of 0 is 0) — there is nothing to point at. The inode still exists (name, permissions), just empty.
1-block file, contiguous: $L = 1$ , byte $N$ with $0 \leq N < 4096$ gives $i = ⌊ N / B ⌋ = 0$ , phys $= b$ . Why? Only block 0 exists; every valid byte maps to it.
1-block file, linked: directory's first block is the only block; usable data $= B - p = 4092$ , so a full 4096-byte file actually needs $⌈ 4096/4092 ⌉ = 2$ linked blocks (4092 in the first, 4 in the second). Why? The in-block pointer shrinks capacity — a subtle degeneracy the ceiling catches!
1-block file, inode: direct pointer 0 holds the block; reads to fetch it $= 1$ . Why? It fits in the direct region, zero indirection.

Verify: blocks needed for 4096 data bytes $= ⌈ 4096/ B ⌉ = 1$ for contiguous/indexed (full block usable), but $⌈ 4096/ (B - p)⌉ = ⌈ 4096/4092 ⌉ = 2$ for plain linked. ✓

Ex 9 — Word problem: a photo library (matrix: Indexed / word)

Worked example

A phone stores 6,000 photos, each 3 MB, in one directory using inodes ( $B = 4096$ , $k = 1024$ ). (a) How many data blocks does one photo use? (b) Which inode region holds a photo's blocks — direct, single, or double? (c) Reads to fetch a photo's last block?

Forecast: 3 MB — will 12 direct pointers be enough?

Blocks per photo $= ⌈ 3, 000, 000/4096 ⌉ = ⌈ 732.4 ⌉ = 733$ blocks (ceiling rounds the partial 733rd block up to a whole block). Why? $732 \times 4096 = 2, 998, 272 < 3, 000, 000$ , so a 733rd partial block is needed.
Region: direct covers 0–11 (12 blocks), single-indirect covers 12–1035. Since $733 \leq 1035$ , the photo fits within direct + single-indirect — the last logical block index is $733 - 1 = 732$ , which is $\geq 12$ , so it lives in the single-indirect region. Why? $732$ is past the 12 direct slots but under 1036.
Reads for the last block: (1) read single-indirect block, (2) read the data block $= 2$ reads. Why? One level of indirection, inode already in memory.

Verify: $732 \times 4096 = 2, 998, 272$ bytes covered by 732 blocks; the 733rd block holds the remaining $3, 000, 000 - 2, 998, 272 = 1, 728$ bytes. And $12 \leq 732 \leq 1035$ ⇒ single-indirect. ✓

Ex 10 — Exam twist: reads to fetch a range (matrix: Indexed / exam twist)

Worked example

Inode, $k = 1024$ . A program reads logical blocks 10, 11, 12 in sequence. Assuming no caching of pointer blocks between reads, count total disk reads. Then say what changes with caching.

Forecast: is it $1 + 1 + 2 = 4$ , or does block 12 cost more?

Block 10 → direct: 1 read (data only). Block 11 → direct: 1 read. Why? Both indices are below 12, so they sit in the 12 direct slots held by the in-memory inode; no pointer-block to fetch.
Block 12 → single-indirect: read the single-indirect block (1) + the data block (1) $=$ 2 reads. Why? Index 12 is the first past the direct region, so one pointer-block must be dereferenced from disk before the data — exactly the boundary of Ex 6.
No-cache total $= 1 + 1 + 2 = 4$ reads. Why? With no caching each fetch is independent, so we simply add the per-block costs.
With caching: the single-indirect block, once read for block 12, stays in memory; blocks 13, 14, … then cost only 1 read each (their addresses are already in the cached pointer block). Why? The pointer block is reused instead of re-read — this is why real filesystems cache indirect blocks aggressively, turning a sequential scan into one pointer-block read plus one read per data block.

Verify: without cache, 3 blocks cost 4 reads; block 12 is the only one crossing into indirection (index $12 \geq 12$ ). Direct blocks (indices $< 12$ ) cost 1 each ⇒ $1 + 1 + 2 = 4$ . ✓

Ex 11 — Linked, limiting value + width-vs-count twist (matrix: Linked / limiting + exam twist)

Worked example

In plain linked allocation the "next block" address is $p = 4$ bytes wide. (a) What is the largest disk (in blocks, then in bytes) that a 4-byte pointer can even name? (b) What does that cap the maximum linked file at? (c) Twist: why is this ceiling a different kind of limit from the inode ceiling in Ex 7?

Forecast: linked files can grow one block at a time forever — so is there any size ceiling at all?

A $p = 4$ -byte pointer is $4 \times 8 = 32$ bits, so it can hold at most $2^{32}$ distinct block numbers. Why? Each bit doubles the count of addresses; 32 bits name $2^{32} = 4, 294, 967, 296$ blocks. This is the true ceiling — not the chain length, but the width of the pointer that stores the chain.
Total addressable disk $= 2^{32} \times B = 4, 294, 967, 296 \times 4096 = 17, 592, 186, 044, 416$ B $=$ 16 TiB. Why? Every block the pointer can name is $B$ bytes; multiply.
A single linked file can be no larger than the whole addressable disk, so its cap is also $\approx$ 16 TiB (minus the pointer overhead $p$ eaten from every block, and minus space other files use). Why? A file is a subset of the disk's blocks; you cannot chain to a block whose number the pointer cannot express.
Twist answer: the linked limit comes from pointer width (how big a single block number can be), while the inode limit in Ex 7 comes from pointer count across indirection levels (how many pointers you can arrange). Widen the pointer to 8 bytes and the linked disk jumps to $2^{64} \times B$ ; the inode instead grows by adding indirection levels. Why does this matter? On an exam, "increase max file size" has two totally different answers depending on scheme.

Verify: $2^{32} = 4, 294, 967, 296$ blocks; $\times 4096 = 17, 592, 186, 044, 416$ B; dividing by $102 4^{4}$ gives exactly 16 TiB. ✓

Ex 12 — Inode, single↔double↔triple boundaries (matrix: Indexed / deep boundary)

Worked example

Inode, $k = 1024$ , all pointer blocks uncached (inode itself in memory). Find the disk reads to fetch the first logical block of each region: the last single-indirect block, the first double-indirect block, the last double-indirect block, and the first triple-indirect block.

Forecast: each region crossing should add exactly one more pointer-block read. True?

Region indices (built from Ex 6/7): direct $= 0 \dots 11$ ; single $= 12 \dots 1035$ (that's $12 + k - 1$ ); double $= 1036 \dots (1036 + k^{2} - 1) = 1036 \dots 1, 049, 611$ ; triple starts at $1, 049, 612$ . Why? Single adds $k$ blocks, double adds $k^{2}$ , so each region's last index is the previous last plus its span.
Last single-indirect block (index 1035): read single-indirect block (1) + data (1) $=$ 2 reads. Why? One pointer level.
First double-indirect block (index 1036): read the double-indirect block (1) → read the single-indirect block it points to (1) → read data (1) $=$ 3 reads. Why? Two pointer levels: the double block lists single-indirect blocks, so we dereference twice.
Last double-indirect block (index 1,049,611): still 3 reads — same two-level path, just the last slot of the last single-indirect block under the double. Why? Staying inside the double region never changes the level count.
First triple-indirect block (index 1,049,612): read triple block (1) → double block (1) → single block (1) → data (1) $=$ 4 reads. Why? Three pointer levels stack up.

Verify: reads per region = 2, 3, 3, 4 — each region boundary (single→double, double→triple) adds exactly one pointer-block read, matching "one extra level = one extra read". Region spans: single $= 1024$ , double $= 102 4^{2} = 1, 048, 576$ ; last double index $= 1036 + 1, 048, 576 - 1 = 1, 049, 611$ ; triple starts $1, 049, 612$ . ✓

Figure s04 stacks the four regions as nested pointer-block ladders; the amber count beside each shows reads climbing 1 → 2 → 3 → 4 as you descend into deeper indirection.

Recall Quick self-test

Contiguous phys of byte 9000, start block 50, B=4096? ::: block 52, offset 808. Linked: reads to reach logical block 3 of chain 7→3→90→12? ::: 4 reads. Inode with B=4096, p=4, k=1024 — max file size? ::: about 4 TB (49152 + 4 MB + 4 GB + 4 TB bytes). Reads to fetch logical block 12 in an inode (inode in RAM)? ::: 2 (single-indirect block + data block). Reads to fetch the first triple-indirect block (uncached)? ::: 4 (triple + double + single + data). Blocks a 3 MB photo needs at B=4096? ::: 733 blocks. Does a 0-byte file need any data blocks? ::: No — all pointers null, but the inode still exists. Largest disk a 4-byte linked pointer can name? ::: 2^32 blocks × 4096 B = 16 TiB.