Loading learning content...
Consider a database with millions of records, each stored at a known offset in a file. A query arrives requesting record #847,293. With contiguous allocation, we simply compute the byte offset and read. With linked allocation, we must traverse 847,292 block pointers—potentially taking minutes. With indexed allocation, we perform a simple calculation and read—nearly as fast as contiguous, without its fragmentation problems.
This is the magic of random access support in indexed allocation. The ability to jump directly to any position in a file, regardless of file size or fragmentation, is perhaps the single most important feature enabling modern database systems, memory-mapped files, and efficient application performance.
In this page, we'll dissect exactly how indexed allocation achieves O(1) random access, analyze the mathematical properties that make it possible, and understand the performance implications across real-world workloads.
By the end of this page, you will understand why random access is fundamentally O(1) in indexed allocation, how to calculate physical addresses from logical file offsets across direct and indirect pointers, the role of index block caching in amplifying random access performance, and why indexed allocation is essential for databases and memory-mapped files.
Before analyzing how indexed allocation supports random access, we must precisely define what random access means and why it matters.
Definition:
Random access is the ability to read or write any byte in a file without first reading the preceding bytes. The time to access byte N should be independent of N—accessing byte 1,000,000 should take the same time as accessing byte 0.
Contrast with Sequential Access:
In sequential access, data is processed in order. Magnetic tapes exemplify this: to reach minute 60 of a recording, you must spool through minutes 1-59. The access time is O(N) where N is the position.
Why Random Access Matters:
The fundamental theorem of indexed allocation is that locating any block in a file requires a constant, bounded number of index block reads—regardless of file size or the block's position within the file.
The Mathematical Foundation:
Given:
To find the physical block containing file offset X:
block_num = X / BThe number of disk reads required is bounded by the maximum indirection level (typically 3-4), not by the file size or offset. A 1TB file requires the same number of index block reads as a 1KB file to locate any block.
| File Region | Pointer Type | Index Reads | Data Read | Total Reads |
|---|---|---|---|---|
| 0 - 48KB | Direct (12 pointers) | 0 (in inode) | 1 | 1 |
| 48KB - 2MB | Single Indirect | 1 | 1 | 2 |
| 2MB - 1GB | Double Indirect | 2 | 1 | 3 |
| 1GB - 512GB | Triple Indirect | 3 | 1 | 4 |
Critical Observation:
Notice that accessing the last byte of a 500GB file requires only 4 disk reads (3 for index navigation + 1 for data). In linked allocation, this would require traversing approximately 125 million block pointers—an astronomical difference.
The O(1) property specifically means: access time is O(1) with respect to file offset and file size. The constant factor depends on the maximum indirection level, which is a fixed property of the file system design (typically 3-4 levels).
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
/* * Proof: Random Access is O(1) in Indexed Allocation * * This code demonstrates that the number of disk reads * to access any file position is bounded by a constant. */ #define BLOCK_SIZE 4096#define POINTER_SIZE 8#define POINTERS_PER_BLOCK (BLOCK_SIZE / POINTER_SIZE) /* 512 */ #define DIRECT_BLOCKS 12#define SINGLE_LIMIT (DIRECT_BLOCKS * BLOCK_SIZE)#define INDIRECT_CAPACITY (POINTERS_PER_BLOCK * BLOCK_SIZE)#define DOUBLE_CAPACITY (POINTERS_PER_BLOCK * INDIRECT_CAPACITY)#define TRIPLE_CAPACITY (POINTERS_PER_BLOCK * DOUBLE_CAPACITY) /* * Calculates the number of index block reads required * to locate the block containing file offset 'position'. * * This function PROVES that the count is bounded by 4, * regardless of how large 'position' is. */int count_index_reads_for_position(uint64_t position) { uint64_t logical_block = position / BLOCK_SIZE; if (logical_block < DIRECT_BLOCKS) { /* Direct pointer: 0 index reads (pointer is in inode) */ return 0; } logical_block -= DIRECT_BLOCKS; if (logical_block < POINTERS_PER_BLOCK) { /* Single indirect: 1 index block read */ return 1; } logical_block -= POINTERS_PER_BLOCK; if (logical_block < (uint64_t)POINTERS_PER_BLOCK * POINTERS_PER_BLOCK) { /* Double indirect: 2 index block reads */ return 2; } /* Triple indirect: 3 index block reads */ return 3; /* * Maximum reads: 3 index blocks + 1 data block = 4 total * * This holds for ANY file position up to the maximum file size! * Maximum file size ≈ 512^3 × 4KB ≈ 512TB */} /* * Comparison: Linked Allocation block count * * In linked allocation, finding block N requires reading * N-1 preceding blocks to follow the chain. */uint64_t count_reads_linked_allocation(uint64_t position) { uint64_t logical_block = position / BLOCK_SIZE; /* Must read all preceding blocks to follow links */ return logical_block; /* This is O(N), not O(1)! */} /* * Demonstration: * * Position = 500GB (500 × 1024^3 bytes) * * Indexed: count_index_reads_for_position(500GB) = 3 * Total reads: 3 index + 1 data = 4 reads * * Linked: count_reads_linked_allocation(500GB) * = 500GB / 4KB = 134,217,728 reads * * Indexed allocation is 33.5 MILLION times more efficient! */Let's implement the complete algorithm for translating a file offset to a physical disk address. This is the core routine that makes random access work.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128
/* * Complete Block Lookup Implementation * * Translates a file offset to a physical disk block address. * This is the heart of random access in indexed allocation. */ #define BLOCK_SIZE 4096UL#define POINTER_SIZE 8#define PTRS_PER_BLOCK (BLOCK_SIZE / POINTER_SIZE) /* 512 */#define DIRECT_BLOCKS 12 struct inode { uint64_t size; block_ptr_t direct[DIRECT_BLOCKS]; block_ptr_t indirect; block_ptr_t double_indirect; block_ptr_t triple_indirect;}; /* Buffer cache lookup - returns cached block or reads from disk */block_ptr_t* get_block_pointers(block_ptr_t block_num); /* * Main lookup function: file_offset → physical_block * * Returns the physical block number containing the given file offset, * or 0 if the offset is in an unallocated hole. * * Time complexity: O(1) - bounded by 4 reads maximum */block_ptr_t lookup_physical_block(struct inode *inode, uint64_t offset) { /* Bounds check */ if (offset >= inode->size) { return 0; /* Beyond end of file */ } /* Step 1: Calculate logical block number */ uint64_t logical_block = offset / BLOCK_SIZE; /* =========================================== * Case 1: Direct Blocks (0 - 11) * * Logical blocks 0-11 are addressed directly by inode. * Cost: 0 extra disk reads * =========================================== */ if (logical_block < DIRECT_BLOCKS) { return inode->direct[logical_block]; } /* Adjust for traversed direct blocks */ uint64_t remaining = logical_block - DIRECT_BLOCKS; /* =========================================== * Case 2: Single Indirect (12 - 523) * * Next 512 blocks via single indirect pointer. * Cost: 1 disk read (the indirect block) * =========================================== */ if (remaining < PTRS_PER_BLOCK) { if (inode->indirect == 0) { return 0; /* Hole */ } /* Read the single indirect block */ block_ptr_t *indirect_block = get_block_pointers(inode->indirect); return indirect_block[remaining]; } remaining -= PTRS_PER_BLOCK; /* =========================================== * Case 3: Double Indirect (524 - 262,667) * * Next 512² = 262,144 blocks via double indirect. * Cost: 2 disk reads * =========================================== */ uint64_t double_capacity = PTRS_PER_BLOCK * PTRS_PER_BLOCK; if (remaining < double_capacity) { if (inode->double_indirect == 0) { return 0; /* Hole */ } /* First level index */ uint64_t index1 = remaining / PTRS_PER_BLOCK; /* Second level index */ uint64_t index2 = remaining % PTRS_PER_BLOCK; /* Read first indirect block */ block_ptr_t *level1 = get_block_pointers(inode->double_indirect); if (level1[index1] == 0) { return 0; /* Hole */ } /* Read second indirect block */ block_ptr_t *level2 = get_block_pointers(level1[index1]); return level2[index2]; } remaining -= double_capacity; /* =========================================== * Case 4: Triple Indirect (262,668 - 134,480,395) * * Next 512³ = 134,217,728 blocks via triple indirect. * Cost: 3 disk reads * =========================================== */ if (inode->triple_indirect == 0) { return 0; /* Hole */ } /* Three-level indexing */ uint64_t index1 = remaining / (PTRS_PER_BLOCK * PTRS_PER_BLOCK); uint64_t rem1 = remaining % (PTRS_PER_BLOCK * PTRS_PER_BLOCK); uint64_t index2 = rem1 / PTRS_PER_BLOCK; uint64_t index3 = rem1 % PTRS_PER_BLOCK; block_ptr_t *level1 = get_block_pointers(inode->triple_indirect); if (level1[index1] == 0) return 0; block_ptr_t *level2 = get_block_pointers(level1[index1]); if (level2[index2] == 0) return 0; block_ptr_t *level3 = get_block_pointers(level2[index2]); return level3[index3];}While the O(1) bound guarantees reasonable worst-case performance, real-world performance is often much better due to aggressive caching. The operating system caches both data blocks and index blocks in memory, dramatically reducing actual disk I/O.
| Access Pattern | Worst Case (Cold Cache) | Warm Cache | Hot Cache |
|---|---|---|---|
| First read of direct block | 1 (inode may be cached) | 1 | 0 (all cached) |
| First read via single indirect | 2 | 1 | 0 |
| First read via double indirect | 3 | 1-2 | 0 |
| Sequential read (1000 blocks) | 3 + 1000 | 1000 | 0 (if fits in cache) |
| Random reads (same file) | Up to 4 per read | 1 per read | 0 |
Modern systems dedicate a significant portion of RAM to the buffer cache (often 50% or more of free memory). For workloads with temporal locality—repeatedly accessing the same files—the effective cost of random access approaches zero disk reads.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109
/* * Cached Block Lookup: Reality is Better than Theory * * This shows how caching transforms theoretical O(4) reads * into practical O(0) or O(1) reads for most accesses. */ /* Simple cache structure for demonstration */struct block_cache { block_ptr_t block_num; block_ptr_t pointers[PTRS_PER_BLOCK]; bool valid; uint64_t last_access;}; #define CACHE_SIZE 1024static struct block_cache indirect_cache[CACHE_SIZE];static uint64_t access_counter = 0; /* * Cache-aware block lookup with hit/miss statistics */struct lookup_stats { int cache_hits; int cache_misses; int disk_reads;}; block_ptr_t cached_lookup(struct inode *inode, uint64_t offset, struct lookup_stats *stats) { uint64_t logical_block = offset / BLOCK_SIZE; /* Direct blocks: always instant (in inode) */ if (logical_block < DIRECT_BLOCKS) { stats->cache_hits++; /* Inode is considered "cached" */ return inode->direct[logical_block]; } uint64_t remaining = logical_block - DIRECT_BLOCKS; if (remaining < PTRS_PER_BLOCK) { /* Single indirect lookup */ block_ptr_t phys = get_cached_pointer( inode->indirect, remaining, stats); return phys; } remaining -= PTRS_PER_BLOCK; /* Double indirect lookup */ uint64_t idx1 = remaining / PTRS_PER_BLOCK; uint64_t idx2 = remaining % PTRS_PER_BLOCK; /* First level */ block_ptr_t level1_block = get_cached_pointer( inode->double_indirect, idx1, stats); if (level1_block == 0) return 0; /* Second level */ return get_cached_pointer(level1_block, idx2, stats);} /* * Helper: Get pointer from block, using cache */block_ptr_t get_cached_pointer(block_ptr_t block_num, uint64_t index, struct lookup_stats *stats) { /* Check cache first */ int cache_slot = block_num % CACHE_SIZE; struct block_cache *entry = &indirect_cache[cache_slot]; if (entry->valid && entry->block_num == block_num) { /* CACHE HIT - no disk I/O needed! */ stats->cache_hits++; entry->last_access = ++access_counter; return entry->pointers[index]; } /* CACHE MISS - must read from disk */ stats->cache_misses++; stats->disk_reads++; /* Read block from disk into cache */ read_disk_block(block_num, entry->pointers); entry->block_num = block_num; entry->valid = true; entry->last_access = ++access_counter; return entry->pointers[index];} /* * Example: Scanning a 100MB file sequentially * * File: 100MB = 25,000 blocks * - Blocks 0-11: direct (0 indirect reads) * - Blocks 12-523: 1 indirect block covers all * - Blocks 524-25000: ~48 double-indirect blocks * * Total indirect block reads: ~50 * Total data block reads: 25,000 * * Without caching: 25,050 reads * With caching (once warmed): 25,000 reads (just data) * * Cache efficiency: 99.8% hit rate on indirect blocks! */Let's examine how random access enables real-world applications, focusing on databases and memory-mapped files—two domains where random access is absolutely essential.
Database Random Access Pattern:
Databases store data in pages (typically 4-16KB). A B+ tree index maps key values to page offsets. Query execution involves:
Without random access, step 2 would require reading all preceding pages—making databases impractically slow.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
/* * Simplified Database Page Access * * Demonstrates how databases rely on random access * for efficient record retrieval. */ #define PAGE_SIZE 8192 struct db_file { int fd; uint64_t num_pages;}; /* * Read a specific page by page number. * * Thanks to indexed allocation, this is O(1) regardless * of which page is requested or how large the database is. */int read_page(struct db_file *db, uint64_t page_num, void *buffer) { off_t offset = page_num * PAGE_SIZE; /* Random access: seek directly to the page */ if (lseek(db->fd, offset, SEEK_SET) == -1) { return -1; } /* Read exactly one page */ return read(db->fd, buffer, PAGE_SIZE); /* * Performance: * - Page 0: ~1ms * - Page 1,000,000: ~1ms * * With linked allocation: * - Page 1,000,000: ~1,000,000ms = 16+ minutes! */} /* * Example: Point query on 1TB database * * SELECT * FROM users WHERE id = 847293; * * 1. Index lookup: B+ tree finds page 1,234,567 * 2. Page read: seek to byte 10,113,638,400, read 8KB * 3. Record extract: find row in page * * Total time: ~2ms (with SSD), ~10ms (with HDD) * * If random access were O(N): ~1.2 million page reads * = hours instead of milliseconds! */To fully appreciate indexed allocation's random access capability, let's formally compare it with linked allocation's sequential access requirement.
| File Size | Indexed (4-read max) | Linked (avg half of n) | Speedup Factor |
|---|---|---|---|
| 1 MB (256 blocks) | 0.4 ms | 12.8 ms | 32× |
| 100 MB (25,600 blocks) | 0.4 ms | 1,280 ms | 3,200× |
| 1 GB (262,144 blocks) | 0.4 ms | 13,107 ms | 32,768× |
| 100 GB (26,214,400 blocks) | 0.4 ms | 1,310,720 ms | 3,276,800× |
| 1 TB (268,435,456 blocks) | 0.4 ms | 13,421,773 ms | 33,554,432× |
For a 1TB file with linked allocation, reading a byte in the middle would take approximately 155 days of continuous disk I/O. Indexed allocation does it in 0.4 milliseconds. This isn't a minor optimization—it's the difference between possible and impossible.
The lseek() system call repositions the file offset for subsequent reads/writes. In indexed allocation, seeking is virtually free—it's just updating a number in memory.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
/* * lseek() Implementation: O(1) Seeking with Indexed Allocation * * Seeking in indexed allocation requires NO disk I/O. * We simply update the in-memory file position. */ struct file_descriptor { struct inode *inode; /* Cached inode */ uint64_t position; /* Current file position */ int flags; /* O_RDONLY, O_WRONLY, etc. */}; /* * Seek to a new position in the file. * * Time complexity: O(1) - no disk access required! * * This is possible because indexed allocation doesn't need * to traverse any blocks to reach an arbitrary position. */off_t indexed_lseek(struct file_descriptor *fd, off_t offset, int whence) { int64_t new_position; switch (whence) { case SEEK_SET: /* Absolute position */ new_position = offset; break; case SEEK_CUR: /* Relative to current */ new_position = fd->position + offset; break; case SEEK_END: /* Relative to end of file */ new_position = fd->inode->size + offset; break; default: errno = EINVAL; return -1; } /* Validate new position */ if (new_position < 0) { errno = EINVAL; return -1; } /* Simply update the position - no I/O needed! */ fd->position = new_position; /* * Note: Seeking beyond EOF is allowed. * Reading beyond EOF returns 0 (EOF). * Writing beyond EOF creates a hole (sparse file). */ return fd->position;} /* * Contrast with hypothetical linked allocation lseek: * * off_t linked_lseek(fd, offset, SEEK_SET) { * // Must traverse from beginning of file! * block_ptr_t current = fd->inode->first_block; * uint64_t blocks_to_skip = offset / BLOCK_SIZE; * * for (uint64_t i = 0; i < blocks_to_skip; i++) { * // Read each block to get the "next" pointer * current = read_next_pointer(current); // DISK I/O! * if (current == 0) break; // Reached end * } * * fd->current_block = current; * fd->position = offset; * return offset; * } * * This would be O(n) with n disk reads - devastating for large files! */Seeking past EOF and then writing creates a sparse file with a hole. The blocks corresponding to the hole have NULL pointers in the index structure. This is another capability that indexed allocation enables naturally—linked allocation would need to materialize all intervening blocks.
Random access support is the defining characteristic that makes indexed allocation practical for modern computing. Without O(1) block lookup, databases, memory mapping, and countless other essential operations would be impossible at scale.
What's Next:
The elegance of indexed allocation comes with a cost: the index blocks themselves consume disk space. For very small files, this overhead can exceed the file's actual data. In the next page, we'll analyze index block overhead—understanding when it matters, how file systems minimize it, and the tradeoffs involved in different index block sizing strategies.
You now understand the mathematical foundations and practical implications of random access in indexed allocation. This knowledge is essential for designing efficient storage systems and understanding why certain applications—especially databases—require file systems with O(1) block lookup.