File Allocation Methods (Contiguous, Linked, Indexed)

Deciding How a File's Data Blocks Are Physically Laid Out on Disk

A file's data is stored as a collection of disk blocks - the allocation method determines exactly how those blocks are physically arranged and connected on disk, directly affecting both performance and flexibility.

Contiguous Allocation: One Unbroken Run of Blocks

File "report.txt" occupies blocks 10-14, all in a row:
[9][10:report][11:report][12:report][13:report][14:report][15]

Contiguous allocation stores a file's blocks in one single, unbroken run - extremely fast to read sequentially, since the disk head barely needs to move between blocks, but suffers from exactly the same external fragmentation problem covered in the memory management fragmentation note earlier in this project, since a file can't easily grow beyond its originally allocated space.

Linked Allocation: Each Block Points to the Next

Block 4 [data | next: 9] -> Block 9 [data | next: 2] -> Block 2 [data | next: NULL]
(blocks can be scattered anywhere on disk, connected only by pointers)

Linked allocation stores a file's blocks scattered anywhere on disk, with each block containing a pointer to the next one in the sequence - no external fragmentation problem at all, since blocks don't need to be adjacent, but sequential access requires following pointers one at a time, and random access (jumping to the middle of a file) requires walking through the entire chain from the start.

Indexed Allocation: One Central Index Block Lists Every Data Block

Index Block: [ points to Block 4, Block 9, Block 2, Block 15 ]

Block 4 [data]   Block 9 [data]   Block 2 [data]   Block 15 [data]
(the index block holds direct pointers to all data blocks, in order)

Indexed allocation uses a separate index block containing pointers to every one of a file's actual data blocks - genuinely fast random access, since the index block directly gives the location of any specific block, without needing to follow a chain sequentially.

Comparing All Three Methods

Why Indexed Allocation Underlies Most Modern File Systems

Indexed allocation's combination of avoiding fragmentation while still supporting fast random access is exactly why it (or a variation of it) forms the basis of most modern file systems - directly connecting to the concept of inodes, covered in detail in the next note.