The bookkeeping problem under every file
In the previous guide you cracked open the inode: a small on-disk record holding a file's metadata — its size, owner, permissions, timestamps — and, crucially, a set of pointers to the data blocks that actually hold the file's bytes. We waved a hand at those pointers. This guide is about what they really point to. The disk, remember, is just one long flat array of fixed-size blocks numbered 0, 1, 2, and up; a file of 30 KB stored in 4 KB blocks needs eight of them. The question is deceptively simple: which eight blocks, and how does the inode remember them?
Call this the allocation problem, and notice it is the file-system twin of a question you already met in the memory rung. There, the OS had to place processes into physical RAM, and you saw the pain of external fragmentation: free space scattered into useless little gaps. The same ghost haunts the disk. An allocation method is just a strategy for assigning blocks to a file and recording the assignment, and like every design in this course it is a set of trade-offs — between how fast you can read sequentially, how fast you can jump to the middle, how much space the bookkeeping itself wastes, and how badly the disk fragments over months of use.
Contiguous: one unbroken stretch
The simplest idea is the most human one: store the whole file in one unbroken run of blocks, back to back. This is contiguous allocation, and it is exactly how you would lay tracks of an album on a tape — side by side, in order. The inode now needs to remember almost nothing: just the starting block number and the length in blocks. A file at blocks 200 through 207 is recorded as 'start 200, length 8.' That is the whole map. It is the same idea as the base-and-limit registers from the memory rung: a start and a span describe a contiguous region completely.
The payoff is wonderful on a spinning disk. Sequential reads are as fast as the hardware allows — the arm seeks once to block 200 and then just streams, because block 201 is right next door. And random access is trivial too: the i-th block of the file is simply start plus i, a single addition, so jumping to the middle costs no extra hops. For a workload that reads files start to finish, like streaming a video, contiguous allocation is essentially unbeatable. This is why it survives today in places like CD-ROMs and some media formats, where files are written once and read in order.
But two cruel problems sank it as a general scheme. The first is exactly the disease from the memory rung: external fragmentation. As files are created and deleted, free space shatters into a patchwork of small holes. You might have 100 free blocks total, yet no run of 20 in a row — so a 20-block file cannot be placed, even though the room exists. The second problem is growth: a file that fills its allotted run has nowhere to expand, because its neighbour blocks already belong to someone else. You would have to copy the whole file elsewhere to make it bigger — painful, and you rarely know a file's final size when you create it.
Linked: a treasure hunt through the disk
If insisting on one unbroken run is the trap, throw the insistence away. In linked allocation, a file's blocks can be scattered anywhere on the disk, and each block carries a little pointer to the next block in the chain. The inode just holds the address of the first block; that block ends with the address of the second; and so on, until a final block whose 'next' pointer is a special end-of-file marker. It is a treasure hunt: each clue tells you where the next clue is hidden. External fragmentation vanishes completely — any free block anywhere will do — and a file can grow by simply grabbing one more free block and linking it on.
The price is steep, and it falls on random access. To read the 5000th block, you have no choice but to follow the chain from the start — read block 1 to learn where block 2 is, read block 2 to learn where block 3 is, all 4999 hops, each one a fresh disk access that may seek to a far-flung corner. There is no arithmetic shortcut to the middle, because the only place that records 'where is block 5000' is block 4999 itself. Even pure sequential reading suffers: because the blocks can be physically anywhere, the arm may have to seek between nearly every read, paying seek time over and over instead of streaming.
There is a subtler wound too. The pointer steals room inside each data block. If a 4 KB block must spend 4 bytes on the 'next' pointer, then a file's data no longer lines up with neat powers of two, and an application that wants to read a clean 4 KB now straddles a block boundary. The classic fix pulls every pointer out of the data blocks and gathers them into one big table — which leads straight to the most famous member of this family.
Indexed: one block that lists them all
The FAT improved linked allocation by gathering the pointers together, but it gathered them for the whole volume into one giant shared table. Indexed allocation takes the idea one step further and gives each file its own private list. Set aside one block — the index block — and fill it with an ordered array of the file's data-block numbers: slot 0 holds the address of the file's first block, slot 1 the second, and so on. The inode points to this index block, and the index block points to all the data. Think of it as the index at the back of a textbook, or the page table from the memory rung: a compact directory that maps a logical position straight to a physical location.
This buys back everything linked allocation lost. Random access is fast again: to find the file's 5000th block, you read its index block and look at slot 5000 directly — one lookup, no walking the chain. External fragmentation is still gone, because the data blocks can scatter freely. And the pointers no longer pollute the data blocks; they live together in the clean index block. You get most of the flexibility of linking with most of the directness of contiguous — which is precisely why this is the scheme real Unix-style file systems are built on.
CONTIGUOUS inode: start=200, len=8 -> blocks 200 201 202 ... 207 (in a row)
LINKED inode: first=200
200 -> 312 -> 41 -> 905 -> ... -> [EOF] (each block names the next)
INDEXED inode -> index block:
[ 0 ] = 200
[ 1 ] = 312
[ 2 ] = 41 data blocks scattered anywhere;
[ 3 ] = 905 slot i -> the file's i-th block
... (one lookup jumps to any block)The catch indexed allocation hides — and how Unix fixes it
Indexed allocation has one awkward question it cannot dodge: how big is the index block? It is itself just one disk block, so it can hold only so many pointers. If a block is 4 KB and each pointer is 4 bytes, an index block holds 4096 / 4 = 1024 pointers, capping a file at 1024 blocks — about 4 MB. That is far too small. But making the index block enormous wastes space for the vast majority of files, which are tiny: a 2 KB note should not drag around a half-empty 4 KB index. We need a structure that stays cheap for small files yet scales to huge ones.
The classic Unix answer is the multilevel index, and it is beautifully pragmatic. The inode itself holds a handful of pointers — say twelve direct pointers that name data blocks straight away. A tiny file is fully described by these alone, with zero extra blocks: instant, cheap, no index block at all. When a file outgrows them, the inode reaches for an indirect block: a pointer to a whole block that is itself full of pointers to data, the way an index entry can send you to a sub-index. Need still more? A double-indirect pointer aims at a block of pointers to blocks of pointers to data, and a triple-indirect adds one more layer.
This is the genius of the scheme: it is cheap where it should be cheap and capable where it must be. Small files — the overwhelming majority — pay nothing for indirection, since their blocks fit in the direct pointers right inside the inode. Only genuinely large files climb into the single, double, and triple indirect levels, and even a triple-indirect tree reaches into the terabytes. The earlier guide promised the inode held pointers to data; now you can see those pointers are not a flat list at all but a small tree that grows exactly as deep as a file demands. The next guide opens up these indirect blocks in full and turns to the other half of the bookkeeping — keeping track of which blocks are free in the first place.