Multi-Level Index Structures
You'll learn how Unix-like file systems use multi-level indexing (direct, indirect, double-indirect, and triple-indirect pointers) to efficiently manage both small and enormous files within a single inode structure.
The Problem with Simple Indexed Allocation
In the previous lesson, you saw indexed allocation where an inode stores pointers to data blocks. But here's the challenge: an inode has limited space (typically 128 or 256 bytes). If you stored only direct pointers to blocks, you'd quickly hit a ceiling on maximum file size.
Multi-Level Solution: The Unix Inode Approach
Unix inodes cleverly use a hybrid, multi-level indexing strategy:
Direct Pointers
The inode contains ~12 direct pointers that point straight to data blocks. For small files (most files!), this is fast and efficient—just one lookup.
Indirect Pointer
One pointer in the inode points to an indirect block—a full disk block containing only pointers to data blocks. This single level of indirection supports medium-sized files.
Double-Indirect Pointer
Another pointer references a double-indirect block, which contains pointers to indirect blocks, which in turn point to data blocks. Two hops of indirection; much larger files supported.
Triple-Indirect Pointer
For truly massive files, a triple-indirect pointer points to a block of pointers to double-indirect blocks. Three levels of indirection!
Analogy
Think of a filing cabinet: direct pointers are folders you can grab immediately. Indirect is a reference card that tells you which drawer to check. Double-indirect is a catalog that points to reference cards. Triple-indirect is an index of catalogs!
Key Takeaway:
Multi-level index structures in Unix inodes balance efficiency for small files (direct access) with scalability for huge files (triple-indirect chains), all within a fixed-size inode.