Course contentsShow
← Computer Science
Lesson 1402 of 2,87232. File SystemsFree lesson

Multi-Level Index Structures

Learn how Unix inodes use direct, indirect, double-indirect, and triple-indirect pointers for large files.

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.