How a folder tree is stored on a flat disk

A disk is a numbered sequence of blocks. There are no folders on it, no names, no tree. All of that is invented by the file system.

Allocation

Contiguous. Blocks in a row. Fast to read sequentially, fast to seek, and it suffers external fragmentation and cannot grow a file that has a neighbour.

Linked. Each block points at the next. Grows freely, no fragmentation, and reading block 900 means reading 899 blocks first. Random access is impossible in practice.

Indexed. One index block lists every block of the file. Random access is one lookup, at the cost of a block per file and a maximum size set by how many pointers fit.

The inode

Unix uses indexed allocation with a twist. An inode holds:

• Permissions, owner, timestamps, size.
• Twelve direct block pointers.
• One single indirect pointer, to a block of pointers.
• One double indirect, to a block of blocks of pointers.
• One triple indirect.

Small files use the direct pointers and cost one lookup. Large files reach through indirection, and the cost is paid only by files that are large.

With 4 KB blocks and 4-byte pointers, one indirect block holds 1024 pointers:

direct           12 x 4 KB   =  48 KB
single indirect  1024 x 4 KB =  4 MB
double indirect  1024^2      =  4 GB
triple indirect  1024^3      =  4 TB

The filename is not in the inode. A directory is a file whose contents are name-to-inode pairs. That is why a Unix file can have several names, all equal, all pointing at one inode: that is a hard link, and deleting one leaves the others working.