File Systems Explained

The Library Without a Catalog

Imagine a library with 500,000 books but no catalog, no shelving system, no librarian. Every visitor who wants a book must physically walk through every shelf until they find it — or don't. New books get placed wherever there is empty space. Old books are "removed" by putting a sticky note on them that says "available," but the book stays in place until someone puts a new book there.

This would be chaos. The Dewey Decimal System (or Library of Congress Classification) exists precisely to bring structure: every book gets a unique identifier, a fixed location, and metadata (title, author, subject) that makes retrieval predictable and fast.

A file system is that organizational system for your storage device. Without it, your 1 TB hard drive is just a flat sequence of 2 billion 512-byte sectors with no way to find anything.

What Is a File?

A file is a named, typed collection of data stored persistently on a storage device. Every file has attributes maintained by the file system:

Directory Structure

Directories organize files into a hierarchical tree. Each directory is itself a file — its content is a list of (name, inode_number) pairs mapping file names to their metadata.

/
├── etc/
│   ├── passwd
│   └── hosts
├── home/
│   └── alice/
│       ├── documents/
│       │   └── report.pdf
│       └── .bashrc
└── var/
    └── log/
        └── syslog

Absolute path: starts from root (/): /home/alice/documents/report.pdf

Relative path: starts from current directory: documents/report.pdf

Path resolution: the OS traverses directory entries one component at a time, looking up each name in the current directory's inode until reaching the final file.

File Allocation Methods

How does the file system store file data across physical disk blocks?

1. Contiguous Allocation

All blocks of a file are stored in consecutive disk locations.

File A: blocks 10, 11, 12, 13
File B: blocks 20, 21, 22

Pros: Fast sequential access, simple to implement (just store start block + length)

Cons: External fragmentation (holes between files); files cannot grow easily without moving

2. Linked Allocation

Each block contains a pointer to the next block. File is a linked list of blocks.

Block 10 → Block 25 → Block 3 → Block 47 → NULL

Pros: No external fragmentation; files can grow freely

Cons: Random access is O(n) — must follow pointers; pointer takes space in each block; pointer corruption loses entire file tail

FAT (File Allocation Table): a linked allocation system that moves pointers into a central table (the FAT) rather than in each block. Used in FAT16, FAT32, and exFAT (USB drives, SD cards).

3. Indexed Allocation (inode)

A dedicated index block (or inode) stores all pointers to the file's data blocks.

inode:
  direct[0]   → block 120
  direct[1]   → block 345
  ...
  direct[11]  → block 892
  indirect    → [block of pointers to more blocks]
  dbl_indirect→ [block of pointers to indirect blocks]
  trbl_indirect→ [block of pointers to double indirect blocks]

Pros: Fast random access (any block reachable in 1–3 steps); no external fragmentation

Cons: Small files waste an entire inode block; large files need multiple levels of indirection

This is the foundation of Unix/Linux file systems (ext2, ext3, ext4, XFS, ZFS).

The Inode: Unix File System Foundation

An inode (index node) stores all metadata about a file except its name. It contains:

• File type and permissions
• Owner (uid, gid)
• Timestamps (created, modified, accessed)
• File size
• Link count (number of directory entries pointing to this inode)
• Pointers to data blocks (12 direct, 1 indirect, 1 double-indirect, 1 triple-indirect in ext2)

The directory entry stores: (filename → inode number). The inode stores everything else.

stat /etc/passwd
# Output:
# File: /etc/passwd
# Size: 2847       Blocks: 8          Inode: 524308
# Access: -rw-r--r--  Uid: 0   Gid: 0
# Access: 2026-05-28 10:12:03
# Modify: 2026-05-01 09:33:21

Hard Links vs Symbolic Links

Hard link: creates a new directory entry pointing to the same inode. Both names refer to the same physical data. Deleting one name does not delete the data — only when link count reaches 0 is the inode freed.

ln file.txt hardlink.txt    # same inode, both equally valid names

Symbolic link (symlink): a special file whose content is a path string pointing to another file. Like a shortcut. If the target is deleted, the symlink becomes dangling (broken).

ln -s /etc/hosts hosts_link  # symlink — stores the string "/etc/hosts"

Journaling: Surviving Crashes

Without journaling, a power failure mid-write can leave the file system in an inconsistent state — a file half-written, a directory update incomplete, an inode partially updated. fsck (file system check) on a large disk takes minutes to hours.

Journaling solves this by writing a log (journal) before modifying the actual data structures:

1. Write the intended changes to the journal
2. Commit the journal entry (mark it complete)
3. Apply the changes to the actual file system
4. Mark the journal entry as done

On crash recovery, the OS replays any committed but not-yet-applied journal entries. Recovery takes seconds instead of hours.

File System Comparison

Summary

The file system is the invisible infrastructure that makes storage usable:

• Files have attributes that describe their metadata
• Directories create a hierarchical namespace for finding files
• Allocation methods (contiguous, linked, indexed) make different tradeoffs
• Inodes are the Unix metadata foundation — separate from file names
• Hard vs symbolic links offer different levels of name-to-data binding
• Journaling ensures consistency survives power failures

Every time you save a file, open a document, or run a program, the file system performs dozens of these operations transparently in microseconds.