Acyclic Graph Directories
You'll learn how file systems allow sharing of files and subdirectories between multiple directories without creating circular references.
The Sharing Problem
In tree-structured directories, each file or subdirectory has exactly one parent. But what if two users want to share the same file? Do we make a copy? That wastes space and creates synchronization headaches. The solution: allow the directory structure to become a directed acyclic graph (DAG) instead of a strict tree.
How Acyclic Graphs Work
In an acyclic graph directory structure, multiple directories can contain links to the same file or subdirectory. Think of it like having multiple shortcuts to the same document on your desktop and in your downloads folder—both point to one actual file.
For example:
/home/alice/project/report.txt/home/bob/shared/report.txt
Both paths could reference the same physical file through links, not copies.
The "Acyclic" Requirement
The critical constraint is no cycles. If directory A contains directory B, and directory B contains directory A, you've created a cycle. This breaks algorithms that traverse directory trees (like search or deletion) because they could loop infinitely.
The file system must prevent cycles, typically by:
- Allowing links only to files, not subdirectories
- Or allowing subdirectory links but checking that no cycle is created before adding a link
- Using reference counts to track how many directories reference each file
Deletion Complexity
When you delete a file that multiple directories reference, the file system must check if other links still exist. Only when the last link is removed should the actual file data be deleted.
Key Takeaway: Acyclic graph directories enable efficient file sharing through links while maintaining the "no cycles" invariant to prevent infinite loops in directory traversal and management operations.