10.2 Directory Structures: Single-Level, Two-Level & Tree-Structured Directories

Back to Operating Systems Notes

📚Module 10: File Systems & InodesTopic 10.2⏱️20 min read

🎯High-Yield For:Computer Science Foundations • Systems Programming • Storage Hierarchy

💡 Core Intuition

🍳 The Everyday Analogy: The Evolution of a Metropolitan Library Catalog

Imagine the evolution of a city library that starts with a few dozen books and grows into a multi-million-volume research archive:

Architecture Flow

The Library Cataloging Evolution

How storage organization progresses from a flat heap to structured hierarchical namespaces

📚Single-Level

The Communal Table

Global Flat Namespace

All books dumped on one giant table. Two authors with the same book title cause immediate collision, and finding a title requires scanning the entire pile.

→

Divide by User

🗄️Two-Level

Individual Member Lockers

Master & User Catalogs

Each library patron gets a dedicated locker. Author name clashes between users vanish, but users cannot create sub-folders or easily share books.

→

Allow Sub-Folders

🌲Tree-Structured

Dewey Decimal Stacks

Recursive Directory Tree

Floors divide into wings, aisles, shelves, and book jackets. Arbitrary sub-categorization and relative pathways allow infinite organization.

→

Cross-Reference Links

🔗Acyclic Graph

Shared Cross-Reference Index

Hard & Symbolic Pointers

Multiple departments reference the identical rare manuscript without duplicating paper copies, using direct reference cards (links).

In an operating system, a directory is fundamentally a symbol table maintained by the file system. It maps human-friendly ASCII/UTF-8 file name strings to internal kernel identifiers—specifically File Control Blocks (FCBs) in Windows or Inode numbers in UNIX.

---

🏛️ Directory Implementations & Hierarchies

1. Single-Level Directory Structure

In a single-level directory system, all files reside in a single global directory shared by all users.

File Name	Inode Pointer	File Type
payroll.dat	Inode 101	Regular File
test.c	Inode 102	Regular File
report.pdf	Inode 103	Regular File
kernel.bin	Inode 104	Regular File

---

2. Two-Level Directory Structure

To eliminate name collisions between different users in multi-user environments, the file system introduces a two-tier hierarchy:

1. Master File Directory (MFD): Contains an entry for each registered user on the system, storing the user ID and a pointer to that user's private catalog.
2. User File Directory (UFD): A private catalog for each user containing all files owned by that individual.

Two-Level Directory Hierarchy (MFD -> UFD)

Isolating user namespaces to eliminate cross-user naming collisions

Tier 1: Master Directory

Master File Directory (MFD)

↓

Tier 2: User Directories

User File Directories (UFD: Alice, Bob, Carol)

↓

Tier 3: Storage Leaves

User Files (test.c, lib.a, data.db, report.pdf)

Operational Characteristics:

• Collision Resolution: Alice and Bob can both create a file named test.c simultaneously without any conflict because their entries reside in distinct UFD tables.
• Path Resolution: Files are addressed by prepending the username: /Alice/test.c or /Bob/test.c.
• System Isolation: Security boundaries are reinforced—User A cannot accidentally overwrite User B's files.
• Remaining Limitation: Users still cannot group their own files into sub-directories (e.g., separating cs101/homework1 from cs101/homework2).

---

3. Tree-Structured Directory

The modern industry standard general-purpose directory structure is a hierarchical tree of arbitrary depth.

Tree-Structured Hierarchical Directory Topology

Recursive tree of arbitrary depth supporting absolute and relative paths

Root Level

Root Directory ('/')

↓

Internal Nodes

System & User Branch Directories (/etc, /home, /home/alice, /home/bob)

↓

Leaf Nodes

Leaf Data Files (hosts, src.c, paper.pdf, main.c)

Structural Rules:

1. Internal Nodes vs. Leaf Nodes:
   • Internal nodes are Directories (folders). They contain a list of directory entries pointing to subordinate directories or files.
   • Leaf nodes are Regular Files (data blocks) or empty directories.
2. Directory Flag:
   • Every file control block (inode) maintains a type bit (S_ISDIR vs S_ISREG). If the bit is set, the operating system treats the file's data blocks as directory entries.

Absolute vs. Relative Path Resolution

---

🔗 Acyclic-Graph Directories: Shared Files & Links

In modern operating systems, multiple users or independent projects frequently need to collaborate on identical files or shared libraries. Copying the file wastes disk blocks and creates inconsistency when one party edits their copy.

An Acyclic-Graph Directory allows directories to share subdirectories and files by allowing a node to have multiple parent paths, strictly prohibiting circular cycles.

Link Abstraction Layer in POSIX Filesystems

Comparing Direct Inode Pointer Sharing vs. Path Indirection

Directory Entries (dentry)

↓

Inode Table (Index Nodes)

↓

Disk Data Blocks

---

Hard Links vs. Soft (Symbolic) Links

The two link mechanisms operate at fundamentally different architectural boundaries:

---

⚙️ Directory Implementation: Linear Lists vs. Hash Tables

A directory file must support fast searches, insertions, and deletions. Operating systems employ two primary data structures to store directory entries:

1. Linear List of Directory Entries

The simplest organization is a linear array or linked list of directory entries (struct dirent).

struct dirent {
    uint32_t d_ino;       // Inode number (4 bytes)
    uint16_t d_reclen;    // Length of this directory record
    uint8_t  d_type;      // File type (regular, directory, symlink)
    char     d_name[256]; // Null-terminated filename string
};

Linear List Directory Operations

Algorithmic complexity for basic namespace maintenance

1

→

Search (Open / Stat)

Sequentially scans records from offset 0 to EOF matching d_name strings.

2

→

Insertion (Create / Touch)

Must scan all N records to guarantee no duplicate name exists, then appends to EOF or reuses a deleted slot.

3

→

Deletion (Unlink / RM)

Finds matching entry, sets d_ino = 0 or marks entry as free, merges unused space with adjacent record.

---

2. Hash Table & Indexed Structures (ext4 HTree & B-Trees)

To eliminate the $O(N)$ lookup barrier, modern enterprise file systems index directory records using hash tables or search trees:

---

🧪 Real-World Engineering: POSIX Directory System Calls

Below is a complete, production-grade C implementation illustrating POSIX directory operations: creating directories, navigating the hierarchy, reading directory entries, and tracking hard link counts via stat:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <unistd.h>

void inspect_directory(const char *dir_path) {
    DIR *dir = opendir(dir_path);
    if (!dir) {
        perror("opendir failed");
        return;
    }

    printf("======================================================================\n");
    printf("Listing Directory: %s\n", dir_path);
    printf("%-20s %-10s %-12s %-10s %-10s\n", "Name", "Inode", "Type", "Links", "Size (B)");
    printf("======================================================================\n");

    struct dirent *entry;
    while ((entry = readdir(dir)) != NULL) {
        char full_path[1024];
        snprintf(full_path, sizeof(full_path), "%s/%s", dir_path, entry->d_name);

        struct stat st;
        // lstat does NOT follow symbolic links, inspecting the link itself
        if (lstat(full_path, &st) == -1) {
            continue;
        }

        const char *type_str = "Unknown";
        if (S_ISREG(st.st_mode))  type_str = "Regular";
        else if (S_ISDIR(st.st_mode))  type_str = "Directory";
        else if (S_ISLNK(st.st_mode))  type_str = "Symlink";
        else if (S_ISCHR(st.st_mode))  type_str = "Char Device";
        else if (S_ISBLK(st.st_mode))  type_str = "Block Device";

        printf("%-20s %-10lu %-12s %-10lu %-10ld\n",
               entry->d_name,
               (unsigned long)entry->d_ino,
               type_str,
               (unsigned long)st.st_nlink,
               (long)st.st_size);
    }

    closedir(dir);
}

int main(int argc, char *argv[]) {
    const char *target = (argc > 1) ? argv[1] : ".";
    inspect_directory(target);
    return 0;
}

---

💣 Production Pathology: The Dangling Symlink and Build Cache Poisoning

---

🧮 Numerical & Conceptual Exam Problems

Problem 1: Hard Link Count Dynamics in Directory Trees

Question:
In a standard UNIX file system, when an empty directory /home/student/project is created using mkdir, what is its initial st_nlink (hard link count)? If two subdirectories src and tests are subsequently created inside project, what does project's link count become? Explain every link source precisely.

Step-by-Step Solution:

1. Initial Directory Creation (mkdir project):

   • Link 1: The parent directory (student) has an entry pointing to this new directory: student/project.
   • Link 2: The newly created directory contains the special entry . (dot) pointing to itself: project/..
   • Initial Link Count = 2.

2. Creating Subdirectory project/src:

   • The directory src contains the special entry .. (dot-dot), which points back to its parent directory (project).
   • This increments project's link count by 1 (now 3).

3. Creating Subdirectory project/tests:

   • The directory tests also contains .. (dot-dot), pointing back to project.
   • This increments project's link count by 1 (now 4).

$\text{Link Count of Directory } D = 2 + \text{Number of Subdirectories in } D$

$\text{Final Link Count} = 2 + 2 = 4$

---

Problem 2: Disk I/O Cost in Directory Traversals

Question:
Consider a hierarchical tree directory on a system where each directory entry requires 32 bytes and disk blocks are 4 KB (4096 bytes).
A user issues a command to read /usr/bin/python. Assume:

• The root directory / contains 10 entries.
• /usr contains 250 entries.
• /bin contains 800 entries.
• The OS disk cache is completely cold (no inodes or directory blocks are cached in RAM).
• Each directory and file has its inode located in a separate inode disk block.

How many total disk block read operations are required to open /usr/bin/python?

Step-by-Step Solution:

1. Traverse Root Directory (/):

   • Read Root Inode: $1\text{ I/O}$.
   • Number of blocks for / directory data: $\lceil (10 \times 32) / 4096 \rceil = \lceil 320 / 4096 \rceil = 1\text{ block} \implies 1\text{ I/O}$.
   • Locate usr entry to obtain its inode number.

2. Traverse /usr Directory:

   • Read /usr Inode: $1\text{ I/O}$.
   • Number of blocks for /usr directory data: $\lceil (250 \times 32) / 4096 \rceil = \lceil 8000 / 4096 \rceil = 2\text{ blocks}$.
   • In the worst case (entry at the end): $2\text{ I/Os}$.
   • Locate bin entry to obtain its inode number.

3. Traverse /bin Directory:

   • Read /bin Inode: $1\text{ I/O}$.
   • Number of blocks for /bin directory data: $\lceil (800 \times 32) / 4096 \rceil = \lceil 25600 / 4096 \rceil = 7\text{ blocks}$.
   • In the worst case: $7\text{ I/Os}$.
   • Locate python entry to obtain its inode number.

4. Access Target File python:

   • Read python Inode: $1\text{ I/O}$.

$\text{Total Disk Reads (Worst Case)} = (1 + 1) + (1 + 2) + (1 + 7) + 1 = 2 + 3 + 8 + 1 = 14\text{ Disk I/Os}$

In-Memory Dentry Cache Eliminates Traversal Latency

This massive mechanical disk traversal overhead (14 I/Os just to find the file inode!) explains why operating systems maintain an aggressive in-memory Dentry Cache (dcache) and Inode Cache. In warm cache environments, all 13 path resolution I/Os hit RAM instantly at sub-microsecond latencies.

---

🏁 Summary & Mental Model

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic10.1 File Attributes & OperationsNext Topic →10.3 File Allocation Methods