Part 4 of 7 · 3 min read
Indexed allocation
Think of a book with an index. To find a topic you do not read the whole book, you look it up and jump to the page. A very large book has an index of indexes. The analogy stops in one place: a book's index is printed once, while the index of a file is rewritten when the file grows.
In plain words: In indexed allocation the inode holds a table of block numbers, so block k of the file is found by looking at entry k. A small table in the inode serves small files. For bigger files, some entries point to an indirect block, a data block that holds more block numbers. The classic Unix inode has 12 direct pointers to data blocks, one single indirect pointer to a block of pointers, one double indirect pointer to a block of pointers to blocks of pointers, and one triple indirect pointer. With 4 KiB blocks and 4-byte pointers, an indirect block holds 4,096 / 4 = 1,024 pointers.
A worked example. The reach of each level is a count of blocks times 4 KiB.
| Level | Blocks reached | Bytes reached |
|---|---|---|
| 12 direct | 12 | 48 KiB |
| Single indirect | 1,024 | 4 MiB |
| Double indirect | 1,024 x 1,024 = 1,048,576 | 4 GiB |
| Triple indirect | 1,024^3 = 1,073,741,824 | 4 TiB |
The largest file is (12 + 1,024 + 1,048,576 + 1,073,741,824) x 4 KiB = 4,402,345,721,856 bytes, about 4.004 TiB. The cost of reaching a byte grows with its depth. Block 5 is direct, so it costs 1 read (the data block, with the inode already in memory). Block 500 is in the single indirect range (12 to 1,035), so it costs 2 reads: the indirect block and the data block. A byte at offset 3 GiB is in block 3 GiB / 4 KiB = 786,432, which lies in the double indirect range, so it costs 3 reads: the double indirect block, one indirect block and the data block.
The key lines. Most files are small, so most lookups need no indirect block at all. This is one reason why the design has lasted. Its weak point is a large file, where long lists of pointers must be written and read, and every block of the file has its own pointer even when the blocks are consecutive.
Indirect block
An indirect block is a data block that holds block numbers instead of file data. A single indirect block points to data blocks, a double indirect block points to single indirect blocks, and so on. It extends the reach of an inode that has only a few direct pointers.
Example: with 4 KiB blocks and 4-byte pointers, one single indirect block adds 1,024 data blocks, which is 4 MiB.
Check yourself: 1. How many bytes do 12 direct pointers reach at 4 KiB per block? 2. How many reads does it take to reach block 500 if the inode is in memory? 3. Why does the cost grow with the size of the file?