Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Digital systems, linear algebra, introduction to formal proof / 2 / c / Solution

A traditional inode uses a fixed number of direct pointers to file data blocks, followed by singly, doubly and sometimes triply indirect block pointers. A singly indirect block pointer reaches one address block whose entries point to file data blocks. A doubly indirect block pointer reaches a block of pointers to singly indirect address blocks; a triply indirect one adds another level. The file data blocks need not be physically contiguous.

This multilevel inode indexing keeps the inode compact. A small file uses direct pointers without allocating address blocks, while a large file allocates deeper address blocks only as needed. If each address block holds $q$ addresses, the successive levels cover $q,q^2,q^3$ file data blocks. The logical file offset selects a path arithmetically, so random access does not require walking through all preceding file data blocks.