A disk is divided into fixed-size blocks, and a file is just some number of those blocks. The hard part isn't storing the bytes — it's *remembering which blocks belong to which file*. There are three classic schemes, and each one trades the same two things against each other: how fast you can jump to the middle of a file (random access), and how badly free space gets chopped up (fragmentation).
Three ways to track a file's blocks
1Contiguous — store the file in one unbroken run of blocks. The directory only needs to remember the start block and the length. Reading the whole file is a single fast sweep, and you can jump to any block by arithmetic (start + offset).
2Linked — scatter the blocks anywhere; each block stores a pointer to the next one in the file. Nothing has to be contiguous, so a file can grow freely and free space is never wasted — but to reach block 100 you must follow 99 pointers first.
3Indexed — give each file one index block that lists pointers to all of its data blocks. Now any block is one lookup away (random access) and there is no external fragmentation, at the cost of that extra index block.
The core tension
Contiguous is fast but leaves gaps; linked never leaves gaps but kills random access; indexed buys back random access with one extra block. There is no free lunch — pick the property the workload needs most.
Worked example
Say three files live on the same disk. Notice how differently each method describes *the very same idea* — "these blocks are mine":
To read the 3rd block of each file: contiguous computes 14 + 2 = 16 instantly; indexed reads slot [2] of block 19 and goes straight to block 7; linked must walk 9 -> 22 -> 3 one pointer at a time. That walk is exactly why linked allocation has no random access.
Contiguous fragments and can't grow
Contiguous allocation suffers external fragmentation: as files are deleted, free space splinters into runs too short to hold a new file, even when the total free space is plenty. And a file pinned between two neighbours can't easily grow. Linked and indexed sidestep both problems because their blocks needn't be adjacent.
What real systems do
Pure linked allocation is rarely used as-is. The old FAT file system pulls the pointers out into one File Allocation Table in memory, and Unix-style inodes use indexed allocation with direct plus single/double/triple indirect index blocks, so small files stay cheap while huge files are still addressable.
OperationTimeSpace
Contiguous · external fragmentation; hard to growO(1) to reach any blockstart + length
Linked · no random access; pointer can be lostO(n) to reach block n1 pointer per block
Indexed · index size caps max file lengthO(1) via the index1 index block per file
Check yourself
Which allocation method makes jumping straight to the middle of a file impossible (you must walk from the start)?
