File allocation — contiguous, linked, indexed (inode): Visual walkthrough

We assume nothing except: a disk is an array of numbered boxes. Let's earn every symbol.

Step 1 — A disk is just numbered boxes

WHAT. A hard disk (or SSD) is chopped into equal-sized chunks called blocks. Think of a long shelf of identical boxes, each labelled with a number: box 0, box 1, box 2, … Every box holds the same number of bytes.

WHY. The operating system never reads "byte 9000" directly from the metal — it reads a whole block at a time. So the very first thing we need is a name for "how big is one box." We call that size $B$ (bytes per block). A common value is $B = 4096$ bytes (4 KB).

PICTURE. Look at the row of pale-yellow boxes. Each is $B$ bytes wide; the number underneath is its physical block address — its box label on disk.

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

Step 2 — A file is a list of box numbers

WHAT. A file's bytes rarely fit in one box, and the boxes it uses are scattered all over the shelf. So the file is really just an ordered list of physical block addresses: "my data is in box 40, then box 7, then box 91…"

WHY. If we lose that list, the file is gone — the data is still on disk, but we don't know which boxes are ours or in what order. So the whole game of file allocation is: where do we keep this list of box numbers? Indexed allocation's answer: keep it in one dedicated place called the index block / inode.

PICTURE. The blue arrows are the list. Position 0 of the list points to box 40, position 1 to box 7, and so on. The position in the list is the logical block number $i$ ; the value stored there is the physical block number.

Step 3 — How many box numbers fit in ONE block?

WHAT. A box number (a pointer) is itself just a few bytes — call its size $p$ (pointer size, e.g. $p = 4$ bytes). If we fill an entire block with nothing but pointers, how many fit?

WHY. This ratio is the single most important number in the whole derivation, because every level of the inode multiplies its reach by exactly this many. We give it its own name: $k = \frac{B}{p}$

Term by term:

$B$ = bytes in one block (the box we're filling with pointers),
$p$ = bytes per pointer (width of one box-number),
$k$ = how many pointers fit in one block.

WHY divide? Division answers "how many things of size $p$ fit into a container of size $B$ ?" — that is the definition of $B \div p$ . With $B = 4096, p = 4$ : $k = 4096/4 = 1024$ pointers per block.

PICTURE. One block sliced into $k$ little slots, each slot holding one physical block number. The pink brace shows $k$ slots across.

Step 4 — Level 0: the 12 direct pointers (tiny files, zero extra reads)

WHAT. The inode itself has room for 12 pointers that point straight at data blocks. These are the direct pointers. No middle-men.

WHY. Real-world fact: most files are small. If the 12 direct pointers already reach $12 \times B$ bytes, a small file needs zero extra disk reads — the inode is already in memory, so following a direct pointer costs nothing extra. That is the 80/20 design: make the common case free.

$direct reach = 12 \cdot B$

$12$ = number of direct slots in the inode,
$B$ = bytes each data block holds.

With $B = 4096$ : $12 \times 4096 = 49, 152$ B ≈ 48 KB.

PICTURE. The inode on the left; 12 blue arrows shoot directly to 12 yellow data boxes. Nothing between the inode and the data.

Step 5 — Level 1: single indirect (one hop → $k$ more blocks)

WHAT. The inode has one extra pointer, the single indirect. It does not point at data — it points at a block full of pointers. That block holds $k$ pointers, each aimed at a data block.

WHY. We ran out of direct slots at 12. Instead of stuffing thousands of pointers into the inode (which would make the inode huge for every tiny file), we pay for extra pointers only when a file needs them — by spending one block as a pointer-holder. One extra read buys us $k$ more data blocks.

$single reach = k \cdot B$

$k$ = pointers in that one indirection block (from Step 3),
$B$ = bytes each of those $k$ data blocks holds.

With $k = 1024$ : $1024 \times 4096 = 4$ MB.

PICTURE. Inode → one pink "index" block → $k$ blue arrows fanning out to $k$ data boxes. Notice the one hop before reaching data.

Step 6 — Levels 2 and 3: double & triple indirect (fan-out squared, cubed)

WHAT. Same trick, stacked.

Double indirect: inode → a block of $k$ pointers, each of which points to a single-indirect block of $k$ pointers → $k \times k = k^{2}$ data blocks.
Triple indirect: one more layer → $k \times k \times k = k^{3}$ data blocks.

WHY. Each new layer of pointers-pointing-to-pointers multiplies the reach by another factor of $k$ . This is exactly why the numbers explode: $k = 1024$ , so each level is a thousand times bigger than the last. Two hops give $k^{2}$ , three hops give $k^{3}$ .

$double reach = k^{2} \cdot B, triple reach = k^{3} \cdot B$

$k^{2}$ = $k$ first-level slots $\times$ $k$ second-level slots (multiply because for each of the $k$ top pointers there are $k$ below it),
$k^{3}$ = the same reasoning stacked three deep.

PICTURE. A branching tree: root (inode's double-indirect pointer) → $k$ branches → each branches into $k$ leaves. Count the leaves: $k^{2}$ . The dashed triple-indirect adds one more level of branching for $k^{3}$ .

Step 7 — Sum the levels = the 4 TB result

WHAT. Total reach = every level added up. Each block count is turned into bytes by multiplying by $B$ : $Max = direct 12 B + single k B + double k^{2} B + triple k^{3} B$

WHY add? The four regions of the file are disjoint — a logical block lives in exactly one region — so the total addressable size is their sum (no double-counting).

Plug in $B = 4096, k = 1024$ :

Level	Blocks	Bytes	Human
Direct	$12$	$49, 152$	≈ 48 KB
Single	$1024$	$4, 194, 304$	4 MB
Double	$1, 048, 576$	$4, 294, 967, 296$	4 GB
Triple	$1, 073, 741, 824$	$4, 398, 046, 511, 104$	4 TB

The triple-indirect term ( $k^{3} B$ ) is a thousand times bigger than double, which is a thousand times bigger than single — so the total is ≈ 4 TB, and the smaller terms barely nudge it.

PICTURE. A stacked bar on a log scale — each level towers a thousand-fold over the previous. The eye sees why "4 TB + 4 GB + 4 MB + 48 KB" is basically just "4 TB."

Step 8 — Edge & degenerate cases (nothing left unshown)

WHAT & WHY, case by case:

Empty file ( $0$ bytes). No data blocks. The inode still exists (it holds metadata + all-null pointers). Max reach unchanged; actual reach = 0.
Tiny file ≤ 48 KB. Lives entirely in the 12 direct pointers. Reading any byte = 0 extra reads beyond the in-memory inode. This is the fast common case the design optimises for.
A block exactly at boundary $i = 11$ vs $i = 12$ . $i = 11$ is the last direct block; $i = 12$ is the first single-indirect block. Off-by-one here means one wrong disk read — count carefully: direct covers logical blocks $0$ through $11$ .
Bigger pointers ( $p = 8$ , 64-bit addresses). Then $k = 4096/8 = 512$ , so every level shrinks: triple reach $= 51 2^{3} \times 4096 = 549, 755, 813, 888$ B ≈ 512 GB. Fatter pointers → smaller max file. This is why the number depends on the exact filesystem, not a universal constant.
Bigger blocks ( $B = 8192$ ). Then $k = 8192/4 = 2048$ and $B$ itself doubles, so triple reach $= 204 8^{3} \times 8192$ — grows enormously. Bigger blocks → much bigger max file (but more wasted space in half-empty last blocks — see External vs Internal Fragmentation).

PICTURE. The three cases side by side: empty inode (all pointers null), tiny file (only direct used), and the "boundary" number line marking block 11 vs 12.

The one-picture summary

Everything on one board: the inode's 12 direct + single + double + triple pointers, each labelled with the block count it delivers ( $12, k, k^{2}, k^{3}$ ) and the depth of hops needed to reach data. Read left→right: fan-out compounds, sizes explode, total ≈ 4 TB.

Recall Feynman retelling — say it back in plain words

A disk is a shelf of equal boxes, each $B$ bytes. To remember a file we keep a list of box numbers. One box can hold $k = B / p$ box-numbers, because each number is $p$ bytes wide. The inode stores 12 numbers pointing straight at data (great for small files — no extra reads). When 12 isn't enough, it spends a whole box as a list of $k$ numbers (single indirect: one hop, $k$ blocks). Need more? A box of $k$ numbers where each points to another box of $k$ numbers gives $k \times k = k^{2}$ blocks (double). One more layer gives $k^{3}$ (triple). Add the four regions — they don't overlap — turn blocks into bytes by $\times B$ , and with $k = 1024$ you get $12 B + k B + k^{2} B + k^{3} B \approx 4 TB$ . Change $p$ or $B$ and the number changes, because $k$ changes.

Recall

What is $k$ and why does it matter? ::: $k = B / p$ , pointers per block; each indirection level multiplies reach by $k$ . Why is double indirect $k^{2}$ blocks, not $2 k$ ? ::: Two layers of fan-out multiply: $k$ top pointers, each to $k$ more, so $k \times k$ . Why are direct pointers "free" for small files? ::: The inode is already in memory, so a direct pointer reaches data with zero extra disk reads. If pointer size $p$ doubles from 4 to 8 bytes, what happens to max file size? ::: $k$ halves (from 1024 to 512), so every level shrinks; max drops to ≈512 GB.

Related: Directory Structure stores the mapping name→inode; Free Space Management (bitmap, free list) decides which boxes are free to hand out; File Systems (ext4, FAT, NTFS) implement these schemes in practice.