File Allocation Methods
IntermediateFilesystems use contiguous, linked, or indexed allocation to map logical file blocks to physical disk blocks, each with different trade-offs in performance, fragmentation, and random-access speed.
Overview
When a file is stored on disk, the OS must track which disk blocks belong to it. Contiguous allocation assigns consecutive blocks — great for sequential reads but causes external fragmentation and makes growing files difficult. Linked allocation chains blocks via pointers embedded in each block — no fragmentation but poor random access (must follow the chain). FAT (File Allocation Table) improves linked allocation by moving the chain into an in-memory table. Indexed allocation (used by Unix inodes) stores all block pointers in an index block, enabling O(1) random access at the cost of extra space for the index. Modern filesystems like ext4 use extents (runs of contiguous blocks) for efficiency.
Contiguous, Linked, and FAT Allocation
Contiguous allocation stores file blocks sequentially. Linked allocation stores a next-block pointer in each block. FAT moves those pointers into a table in memory, so the head of each chain (stored in the directory) is enough to navigate the whole file without reading every block.
// Contiguous Allocation simulation
// File "report.pdf" starts at block 10, length 5
class ContiguousEntry {
String name;
int startBlock;
int length;
// Access block i: disk[startBlock + i] — O(1) random access
int blockAddress(int i) { return startBlock + i; }
}
// Linked Allocation: each block stores index of next block
int[] linkedBlocks = new int[100]; // disk blocks 0-99
// File chains: block 5 → 12 → 34 → 67 → -1 (end)
linkedBlocks[5] = 12;
linkedBlocks[12] = 34;
linkedBlocks[34] = 67;
linkedBlocks[67] = -1; // EOF
// To read block i (0-indexed): must traverse from head — O(i)
int readLinkedBlock(int head, int i, int[] blocks) {
int current = head;
for (int k = 0; k < i; k++) {
current = blocks[current];
if (current == -1) throw new IndexOutOfBoundsException("Block " + i + " out of range");
}
return current;
}
// FAT (File Allocation Table): pointer table in memory, O(1) table lookup
int[] fat = new int[100]; // FAT for 100 blocks
fat[5] = 12; // block 5's next = 12
fat[12] = 34;
fat[34] = 67;
fat[67] = -1; // EOF marker
// With FAT cached in memory: navigate to block i via table traversal
// Much faster than disk-based linked traversalIndexed Allocation & Inode Max File Size
Indexed allocation dedicates one block (the index block) to storing pointers to all data blocks. Unix inodes use a hybrid: 12 direct pointers, then single/double/triple indirect blocks for large files. This gives O(1) access for small files (direct blocks) and handles multi-terabyte files via indirect levels.
// Indexed Allocation
class IndexedFile {
int indexBlock; // block number of the index block
// indexBlock on disk contains: [dataBlock0, dataBlock1, ..., dataBlockN]
// Random access block i: read indexBlock, then read indexBlock[i] — 2 disk reads
}
// Unix Inode Hybrid: max file size calculation
// Assumptions: 4 KB block size, 4-byte block pointers
final int BLOCK_SIZE = 4096; // 4 KB
final int PTR_SIZE = 4; // bytes per pointer
final int PTRS = BLOCK_SIZE / PTR_SIZE; // 1024 pointers per indirect block
long direct = 12L * BLOCK_SIZE; // 48, KB
long single = (long) PTRS * BLOCK_SIZE; // 4 MB
long dbl = (long) PTRS * PTRS * BLOCK_SIZE; // 4 GB
long triple = (long) PTRS * PTRS * PTRS * BLOCK_SIZE; // 4 TB
long maxSize = direct + single + dbl + triple;
System.out.printf("Max file size with hybrid inode: %.2f TB%n",
maxSize / (1024.0 * 1024 * 1024 * 1024)); // ≈ 4.00 TB
// ext4 actually caps at 16 TB due to 32-bit block counter in inode
// XFS and Btrfs support much larger files via 64-bit extentsKey Points to Remember
- 1Contiguous allocation gives the best sequential performance but suffers from external fragmentation.
- 2Linked allocation eliminates fragmentation but requires O(n) traversal for random access.
- 3FAT improves linked allocation by caching the entire pointer chain in an in-memory table.
- 4Indexed allocation (Unix inodes) provides O(1) random access and supports large files via indirect blocks.
- 5Modern filesystems use extents (start block + length) to reduce inode block pointer overhead for large files.
- 6With 4 KB blocks and 4-byte pointers, an inode with 12 direct + 1 single + 1 double + 1 triple indirect can address ~4 TB.
Interview Questions
Sign in to ask AriaCompare contiguous, linked, and indexed file allocation methods.
Why does FAT perform better than pure linked allocation for random access?
Calculate the maximum file size for an inode with 12 direct, 1 single-indirect, and 1 double-indirect block pointer with 4 KB blocks.
What are extents in ext4 and how do they differ from traditional block pointers?
Ask Aria about File Allocation Methods
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.