Behind every file sits an inode — a fixed-size record (128 or 256 bytes in ext4) holding everything about the file except its name: its owner, permissions, timestamps, size, link count, and, crucially, where its data lives on disk. The name is kept in the directory; the inode is the file. Now the classic engineering puzzle: an inode is tiny and fixed-size, yet it must be able to locate the blocks of a file that might be 3 bytes or 3 terabytes. You cannot store a terabyte's worth of block addresses in 256 bytes. How do you point at an unbounded amount of data from a bounded record?
The answer, invented in early Unix and still shaping ext4 today, is the multi-level indirect block tree — a beautiful piece of design that makes small files cheap and huge files possible with the same structure. This lesson is about that tree, the modern extent alternative that replaced it, and the allocation ideas (FFS locality, bitmaps) that decide which physical blocks a file gets.
The inode holds a small array of block pointers — classically 15 of them. But they are not all equal. The first twelve are direct pointers: each names one data block. The thirteenth is a single indirect pointer — it names a block that itself is full of pointers to data. The fourteenth is double indirect (a block of pointers to blocks of pointers to data), and the fifteenth is triple indirect. Each level multiplies the reach by the number of pointers that fit in one block.
This is the master stroke: a tiny file (say 8 KB, two blocks) uses only direct pointers, so reading it costs one inode fetch and no extra hops. A giant file grows into the deeper levels only as it needs them, and the deepest level is reached in at most three extra block reads. The structure is an imbalanced tree that is shallow for the common (small) case and deep only where it must be — the same "make the common case fast" instinct that runs through all of systems.
where
Each row below is one class of pointer. Notice how the depth (number of hops to reach data) grows by one at each level, while the fan-out multiplies — that geometric growth is what lets three indirect levels cover terabytes.
The runnable model below plugs numbers into the formula and prints how much each level contributes. Change the
block or pointer size and watch the maximum file size swing by orders of magnitude — bigger blocks and smaller
pointers both fatten
The indirect scheme has an ugly cost: a 1 GB contiguous file still needs a quarter of a million individual block
pointers, one per 4 KB block, even though the blocks are all in a row. Reading them means chasing indirect blocks
all over the disk. Modern file systems — ext4, XFS, btrfs —
replace pointer lists with extents: a single record saying "logical blocks 0…262143 live at
physical block
| Scheme | Describes a big file with… | Best when… |
|---|---|---|
| Block list (indirect) | one pointer per block | files are fragmented / sparse |
| Extents | a few (start, length) runs | files are large and contiguous |
Extents only pay off if the file system can actually allocate long contiguous runs — which is exactly what good block allocation is about.
The original Unix file system scattered inodes at one end of the disk and data everywhere else, so reading a file meant a long seek from inode to data and back. Berkeley's Fast File System (McKusick, 1984) fixed this with a single dominating idea: keep related things close. FFS divides the disk into cylinder groups, each with its own inodes, bitmap, and data blocks, and it follows two rules: put a file's inode in the same group as its directory, and put a file's data blocks in the same group as its inode. Related data ends up physically near each other, so the disk head barely moves.
Free space is tracked with a bitmap: one bit per block,
Because a null block pointer is legal. If a program seeks to offset 1 GB and writes one byte, the file system
allocates a data block for that byte and the handful of indirect blocks needed to reach it — but every
other block pointer in the tree stays zero, meaning "a hole." The file's logical size
is 1 GB, but only a few kilobytes are actually on disk; reading a hole returns zeros without any block existing.
This is how virtual-machine disk images, database files, and core dumps can claim enormous sizes while occupying
almost nothing — and why
A tempting mistake is to imagine the indirect pointers as a free lookup — as if the inode magically knows all the addresses. It does not. A single indirect block is an ordinary data block that must be fetched from disk before you can read the pointers inside it, and a double-indirect access reads two such blocks before touching any data. So the byte at offset 100 GB in a huge file costs an inode read plus three indirect-block reads plus the data read — four seeks, not one. This is precisely why extents (which describe millions of blocks in one record) and aggressive caching of indirect blocks matter so much for large files, and why the depth of the tree, not just its total reach, is part of a file system's performance story.
You can now say precisely which disk blocks make up a file and how the inode reaches them. But writing a
file touches several of these structures at once — the inode, a bitmap bit, and a data block — and if the machine
crashes between those writes, the file system is left inconsistent. That is the