File space allocation

index blocks

Another possibility is to store all the pointers to a file's blocks in a single array, rather like a page table lists all of the frames in which a process's pages are stored. The array of disk blocks could be stored directly in the directory entry or inode, or could be stored in a disk block by itself.

If inode points to an index block, it's known as (single) indirection. If the block size is 1K, and pointers are 4bytes in size, could store up to 1024 ÷ 4 = 256 pointers per block, or represent fills of up to 256K.

Since 256K is rather limiting size for a file for most modern computer systems, a two-level system may be used, with one index block pointing to 256 other index blocks, each of which points to 256 data blocks (double indirection). This would allow file sizes of up to 256 × 256 × 1K= 64M. Three levels would allow file sizes of up to 16G, which is probably more than enough nowadays.

Advantages, allow random access (with two levels of indexing, need only three accesses to read a block---fewer for smaller files). Doesn't require a FAT---so suitable for very large disks.

Most UNIX filesystems use this technique, with some optimisations.

last updated 1 April 1998