The hole left by indexed allocation
Guide 2 ended on a high note. Indexed allocation beat both contiguous and linked layouts: gather all of a file's block pointers into one index block, and you get fast random access (jump straight to the n-th pointer) with no FAT-style table to scan and no external fragmentation. But we glossed over a question that should have been nagging you: how big is that index block? It is just an ordinary disk block — say a 4 KB block. If each pointer is 4 bytes, one index block holds 4096 / 4 = 1024 pointers. With a 4 KB block size, that caps a file at 1024 * 4 KB = 4 MB. A single photo from a modern phone can blow past that.
You might shrug and say: just use a bigger index block. But that trades one waste for another. Most files on a real disk are tiny — a few kilobytes of config, a short script, a thumbnail. If every file paid for a giant index block up front, you would burn enormous space on near-empty pointer arrays. We want the opposite: small files should cost almost nothing, yet a huge file must still be reachable. That is the exact tension the Unix inode solves, and the solution is the heart of this guide.
The multilevel index: direct, then indirect, then more indirect
Here is the trick, and it is genuinely beautiful. The inode does not hold one kind of pointer; it holds a graded ladder of them, called a multilevel index. The first handful of pointers in the inode — say twelve of them — are direct pointers: each names a data block of the file directly. For a small file that is the whole story. A 30 KB file fits in eight 4 KB blocks, all reached by direct pointers, with zero extra reads. The common case, a tiny file, costs nothing beyond the inode itself.
When a file grows past those twelve direct blocks, the inode reaches for its next pointer: the single indirect pointer. This one does not point at a data block — it points at an indirect block, a whole disk block filled with 1024 more data-block pointers. So the single indirect pointer alone adds another 1024 blocks, i.e. another 4 MB, of reach. The cost is one extra disk read: to find data block number 100, the OS reads the indirect block, then reads the data block it points to. The inode stays tiny; the capacity only gets paid for when the file actually needs it.
Now repeat the idea one level up. The double indirect pointer points at a block of 1024 pointers, but each of those points at another indirect block of 1024 data pointers — so it covers 1024 * 1024 ≈ 1 million blocks (about 4 GB). And the triple indirect pointer adds yet another layer: 1024 * 1024 * 1024 ≈ 1 billion blocks, into the terabytes. Reaching a block through the triple level costs three extra reads (one per layer) plus the data read, but you only pay that for the deepest reaches of an enormous file. The ladder is the whole design: shallow and free for the small files that dominate, deep but reachable for the rare giants.
inode +-----------------------------+ | metadata (size, perms, ...) | | direct[0] --------------------> data block | direct[1] --------------------> data block | ... (12 direct pointers) ... | direct[11] --------------------> data block | | | single indirect ---> [ 1024 ptrs ] --> 1024 data blocks | | | double indirect ---> [ 1024 ptrs ] --> each --> [ 1024 ptrs ] --> data | | | triple indirect ---> [ 1024 ptrs ] --> [ 1024 ] --> [ 1024 ] --> data +-----------------------------+ Reach (4 KB block, 4-byte ptr, 1024 ptrs/block): 12 direct = 12 blocks (48 KB) 0 extra reads single indirect = 1024 blocks (4 MB) 1 extra read double indirect = 1024^2 blocks (4 GB) 2 extra reads triple indirect = 1024^3 blocks (4 TB) 3 extra reads
Walking a logical offset down the ladder
The mechanism becomes concrete when you trace one access. Suppose a program calls read on a file and wants the byte at offset 8 MB. The file system never works in bytes for placement — it works in fixed-size blocks, much like paging splits an address into a page number and an offset. So the first step is to turn the byte offset into a logical block number: with 4 KB blocks, block number = floor(8 MB / 4 KB) = 2048, and the byte sits at offset 0 within that block. Now the only question is: where is logical block 2048 on disk? That is what the ladder answers.
- Is the block number below 12? No (2048 is not), so it is not a direct pointer. Subtract the 12 direct blocks: 2048 - 12 = 2036.
- Does it fit in the single indirect block's 1024 pointers? 2036 is bigger than 1024, so no. Subtract 1024: 2036 - 1024 = 1012. The block lives under the double indirect pointer.
- Read the double indirect block. Index into it at 1012 / 1024 = 0 to pick the right second-level indirect block, then read that second-level block and index into it at 1012 mod 1024 = 1012 to get the final data-block pointer.
- Read that data block. Total disk reads for this access: the double indirect block, the second-level indirect block, then the data — two extra reads, exactly the cost predicted for the double level.
The other half: who keeps the free list?
So far we have only asked how a file finds the blocks it already owns. But every time a file grows, the inode needs a fresh data block from somewhere, and when a file is deleted its blocks must go back into circulation. That bookkeeping is free-space management, and it is just as essential as the ladder. Get it wrong and you either hand out a block that is already in use (corruption) or leak blocks that nobody can ever reclaim (a slow, silent loss of capacity). The file system needs a reliable answer to one question: which blocks on this disk are free right now?
The dominant answer is the free-space bitmap. Picture one long row of bits, one bit per block on the disk: a 1 means 'allocated, in use,' a 0 means 'free, available' (the exact convention varies, but the idea is symmetric). A 100 GB disk with 4 KB blocks has about 26 million blocks, so its bitmap is about 26 million bits — roughly 3 MB, a rounding error against the disk's size. Allocating a block is 'find a 0 and flip it to 1'; freeing a block on delete is 'flip its bit back to 0.' Because the bitmap is so compact, the file system can keep much of it in memory, making allocation decisions fast.
The bitmap quietly buys you a bonus the linked free list could not: locality. To place a file's blocks near each other (which makes later sequential reads faster on a spinning disk), the allocator can scan the bitmap for a run of consecutive 0 bits and grab them as a contiguous chunk. A linked list of free blocks, by contrast, hands them out in whatever scattered order they were freed, with no easy way to ask 'are these neighbours free too?' This is why the bitmap, not a free list, is what real systems like the ext family reach for.
Honest limits and a connection forward
Be honest about what the ladder is and is not. It is not a clever new idea so much as the page-table trick applied to disk: a tree of pointer blocks that stays shallow for small things and deepens only on demand — the same shape as a hierarchical page table for memory. And it has a real cost: a fragmented huge file accessed at its deepest reaches really does pay those extra reads, and the indirect blocks themselves consume disk space (one indirect block per 1024 data blocks). It is a careful trade, not a free lunch. The genius is only that the common case — the small file — pays nothing.
One more caution, because it bites real systems. The bitmap and the inode pointers are two views of the same truth — a block marked '1' in the bitmap should be reachable from exactly one inode (or be metadata). After a crash, those two views can disagree: the inode might have grabbed a block while the bitmap update was still in flight. That mismatch is precisely what a file-system checker (fsck) hunts for, and it is the problem the last guide in this rung solves more gracefully with journaling. Keep that thread in mind: the structures here are correct only as long as every update lands consistently.