the multilevel index

A single index block is like one page of addresses: fine for a small file, but it runs out of room for a huge one. The classic Unix inode solves this with a clever mixed scheme that is generous to the common case (most files are small) yet can still address enormous files. It keeps a handful of direct pointers right in the inode, then adds a ladder of indirection for the rare giant file.

Inside the inode sit, say, 12 direct pointers, each naming one data block of the file. For a file that fits in 12 blocks, that is the whole story — fast, with the block addresses already in memory the moment the inode is read. If the file is bigger, the inode's next pointer is a single-indirect pointer: it points to a block that is itself full of data-block pointers. Bigger still, a double-indirect pointer points to a block of pointers to blocks of pointers to data. And one more, the triple-indirect pointer, adds a third level. So small files cost nothing extra, while large files pay one, two, or three extra block reads to reach their far regions — you only pay for the depth you actually use.

The arithmetic is striking. With 4 KB blocks holding 1024 pointers each (a pointer being 4 bytes), the 12 direct pointers cover 48 KB; single-indirect adds 1024 blocks (4 MB); double-indirect adds 1024 x 1024 blocks (4 GB); triple-indirect adds 1024^3 blocks (4 TB). That is how a small fixed-size inode can describe a file from one byte to several terabytes. The price is that reaching deep into a very large file may need up to three extra reads just to fetch the pointers — though caching the indirect blocks hides most of that cost in practice.