A typical laptop holds hundreds of thousands of files. Without some way to group and name them, finding your resume would mean scrolling through a single list containing every system library, photo and browser cache file on the machine.
Directories (folders) solve this. They give files names, group related files, and let many users and programs share one disk without stepping on each other.
A directory is a special file that maps file names to the files themselves. On UNIX-like systems, each directory entry maps a name to an inode number; the directory structure is the way these directories are organised and linked together.
In File Systems we learned that the inode holds everything about a file except its name, and in File Allocation Methods we saw how the inode finds the file's blocks. This chapter fills the last gap: how the OS goes from a name like /home/riya/notes.txt to an inode, and how directories are arranged.
What Is Inside a Directory?
A directory is just a file whose contents are a list of entries. In a UNIX file system, each entry is basically:
Directory "proj" (itself inode 50776)
+----------------+---------+
| name | inode # |
+----------------+---------+
| . | 50776 | ← this directory itself
| .. | 50757 | ← parent directory
| readme.txt | 50777 |
| src | 50784 |
| docs | 50796 |
| tests | 50810 |
+----------------+---------+
That is all. The name lives here, and everything else (size, owner, permissions, block locations) lives in the inode. Some systems, such as FAT, store attributes directly in the directory entry instead, because FAT has no inodes.
You can read a directory's entries from a program with opendir() and readdir():
#define _DEFAULT_SOURCE
#include <stdio.h>
#include <dirent.h>
int main(int argc, char *argv[]) {
const char *path = argc > 1 ? argv[1] : ".";
DIR *d = opendir(path);
if (!d) { perror("opendir"); return 1; }
struct dirent *e;
while ((e = readdir(d)) != NULL)
printf("inode %-8lu %s\n", (unsigned long)e->d_ino, e->d_name);
closedir(d);
return 0;
}
Running it on a directory proj containing readme.txt and three subdirectories (Linux, ext4):
inode 50777 readme.txt
inode 50757 ..
inode 50776 .
inode 50796 docs
inode 50784 src
inode 50810 tests
Two things to notice:
Every directory has the special entries
.(itself) and..(its parent).The order looks random. It is not alphabetical and not the creation order. With the
dir_indexfeature (on by default), ext4 returns directory entries fromreaddir()in the order of a hash of their names, even for a small directory. POSIX does not promise any order, which is whylssorts the names itself. Your inode numbers and order will differ.
Directory Operations
Operation | Meaning | POSIX / shell |
|---|---|---|
Search | Find the entry for a given name | done inside |
Create a file | Add a new entry |
|
Delete a file | Remove an entry |
|
List | Read all entries |
|
Rename | Change an entry's name, or move it to another directory |
|
Make / remove a directory | Create or delete a directory (must be empty to remove) |
|
Traverse | Visit every directory and file in a subtree |
|
Note that a mv within the same file system does not copy any file data: it just removes one directory entry and adds another pointing at the same inode. That is why moving a 10 GB file to another folder is instant, while moving it to a USB drive takes minutes.
Directory Structures
How should directories be arranged? The textbooks describe five designs, each fixing a problem of the previous one.
1. Single-Level Directory
One directory for everyone and everything.
Root directory
+------+------+------+-------+------+------+
| cat | bo | a | test | data | mail |
+------+------+------+-------+------+------+
↓ ↓ ↓ ↓ ↓ ↓
file file file file file file
Simple to implement and understand.
Naming problem: every file needs a unique name. If two users both want a file called
test, one loses.Grouping problem: no way to keep a project's files together. With thousands of files, remembering names becomes impossible.
Early systems and some very simple devices (old cameras, early floppy-based systems) worked like this.
2. Two-Level Directory
Give each user their own directory. A Master File Directory (MFD) lists the users; each User File Directory (UFD) lists that user's files.
MFD
+--------+--------+--------+
| user1 | user2 | user3 |
+--------+--------+--------+
↓ ↓ ↓
UFD UFD UFD
+-----+------+ +------+ +------+-----+
| cat | test | | test | | data | a |
+-----+------+ +------+ +------+-----+
Fixes naming conflicts between users: user1 and user2 can both have
test. A file is identified by a path name such asuser1/test.Isolates users, which is good for protection.
But no grouping within a user: one user's notes, code and photos are all in one flat list.
Sharing is awkward: isolation makes cooperation hard.
System programs would have to be copied into every UFD, or kept in a special "system user" directory that is searched automatically. This idea of a list of places to look became the search path (the
PATHvariable you know today).
3. Tree-Structured Directory
Generalise: let a directory contain both files and other directories (subdirectories), to any depth. This is the structure everyone uses today.
/
├── bin
│ ├── ls
│ └── cat
├── home
│ ├── riya
│ │ ├── notes.txt
│ │ └── projects
│ │ └── os
│ │ └── sched.c
│ └── arjun
│ └── notes.txt
└── etc
└── hosts
Each user can organise their files into any number of subdirectories.
Every file has exactly one path from the root, so names are unique as full paths:
/home/riya/notes.txtand/home/arjun/notes.txtare different files.Searching is efficient because the search is limited to one directory at each step.
Absolute and Relative Paths
Each process has a current working directory (cwd), stored by the kernel for that process.
Absolute path: starts at the root.
/home/riya/projects/os/sched.cRelative path: starts at the cwd. If cwd is
/home/riya, thenprojects/os/sched.cnames the same file, and../arjun/notes.txtmeans/home/arjun/notes.txt.
The weakness of a pure tree: a file belongs to exactly one directory, so it is hard to share. If Riya and Arjun work on the same project file, where does it live?
4. Acyclic-Graph Directory
Allow a file or directory to appear in more than one directory, as long as no cycles form. This is done with links.
home
/ \
riya arjun
| |
projects shared ─────┐
| │ (link)
os ←──────────────┘
|
sched.c
Now /home/riya/projects/os and /home/arjun/shared refer to the same directory. A change made by either user is immediately seen by the other, because there is only one copy. This is how UNIX works in practice, using two kinds of links, described in the next section.
Sharing brings new problems:
Multiple names (aliasing): one file now has several paths. A backup program or a disk-usage tool must be careful not to count or copy it twice.
Deletion: if Riya deletes the file, what happens to Arjun's link? If the space is freed, Arjun's link points to nothing (a dangling pointer), or worse, to a new file that reuses the space. Solutions: keep a reference count and free the file only when it reaches zero (hard links), or let the link break harmlessly (symbolic links).
5. General-Graph Directory
If links are allowed with no restrictions, a directory can end up inside itself:
/home/riya/a
|
b
|
loop ───→ back to /home/riya/a (cycle!)
Cycles cause two real problems:
Infinite traversal: a search like
findor a backup would walk round the loop forever, unless it remembers which directories it has visited.Reference counts stop working: in a cycle, each directory is referenced by another member of the cycle, so the counts never fall to zero even when the whole loop is unreachable from the root. Freeing that space needs garbage collection: traverse from the root, mark everything reachable, then free everything unmarked. On a large disk this is very slow.
This is why real systems avoid general graphs. UNIX allows hard links to files only, not to directories, so cycles cannot form through hard links. Symbolic links can form cycles, but they are not counted as real references, and tools either do not follow them or limit how many they follow (Linux gives up with the error ELOOP, "Too many levels of symbolic links").
Comparison
Structure | Same name for two users? | Grouping | Sharing | Main problem |
|---|---|---|---|---|
Single-level | No | No | Everything shared | Name collisions |
Two-level | Yes | No | Hard | No subdirectories |
Tree | Yes | Yes | Hard (one parent) | No sharing |
Acyclic graph | Yes | Yes | Yes, via links | Aliasing, deletion |
General graph | Yes | Yes | Yes | Cycles, needs garbage collection |
Hard Links and Symbolic Links
UNIX implements the acyclic graph with two kinds of links.
A hard link is an additional directory entry that points to the same inode. A symbolic (soft) link is a separate small file whose content is a path name to another file.
Seeing the Difference
This program creates a file, a hard link and a symbolic link to it, then deletes the original name:
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>
static void show(const char *path) {
struct stat st;
if (lstat(path, &st) == -1) { printf("%-10s -> (does not exist)\n", path); return; }
printf("%-10s inode=%lu links=%lu type=%s\n", path,
(unsigned long)st.st_ino, (unsigned long)st.st_nlink,
S_ISLNK(st.st_mode) ? "symlink" : "regular");
}
static void cat(const char *path) {
char buf[64] = {0};
int fd = open(path, O_RDONLY);
if (fd == -1) { printf("open(%s) failed\n", path); return; }
ssize_t n = read(fd, buf, sizeof buf - 1);
if (n > 0) printf("contents of %s: %s", path, buf);
close(fd);
}
int main(void) {
int fd = open("a.txt", O_CREAT | O_WRONLY | O_TRUNC, 0644);
if (fd == -1) { perror("open"); return 1; }
if (write(fd, "hello\n", 6) != 6) { perror("write"); return 1; }
close(fd);
link("a.txt", "hard.txt"); /* second name for the same inode */
symlink("a.txt", "soft.txt"); /* new inode that stores the path "a.txt" */
puts("--- after link() and symlink() ---");
show("a.txt"); show("hard.txt"); show("soft.txt");
unlink("a.txt"); /* remove the original NAME */
puts("--- after unlink(\"a.txt\") ---");
show("a.txt"); show("hard.txt"); show("soft.txt");
cat("hard.txt");
cat("soft.txt");
unlink("hard.txt"); unlink("soft.txt");
return 0;
}
Output on Linux (ext4), compiled with gcc -std=c17 -Wall -Wextra:
--- after link() and symlink() ---
a.txt inode=50811 links=2 type=regular
hard.txt inode=50811 links=2 type=regular
soft.txt inode=50812 links=1 type=symlink
--- after unlink("a.txt") ---
a.txt -> (does not exist)
hard.txt inode=50811 links=1 type=regular
soft.txt inode=50812 links=1 type=symlink
contents of hard.txt: hello
open(soft.txt) failed
Read it slowly, because this output explains everything:
a.txtandhard.txthave the same inode number. They are two names for one file, equally "real". Neither is the original. The inode's link count is 2.soft.txthas its own inode. It is a tiny file that just contains the texta.txt.After
unlink("a.txt"), the link count drops to 1, and the data is still reachable throughhard.txt. The file system frees an inode and its blocks only when the link count reaches 0 and no process has the file open.The symbolic link still exists, but the name it points to is gone, so opening it fails. It is now a dangling link.
This is why the system call to delete a file is called unlink: it removes one name. The file disappears only when its last name is gone.
The same experiment from the shell:
echo hello > a.txt
ln a.txt hard.txt # hard link
ln -s a.txt soft.txt # symbolic link
ls -li a.txt hard.txt soft.txt50811 -rw-r--r-- 2 imran imran 6 Nov 2 10:55 a.txt
50811 -rw-r--r-- 2 imran imran 6 Nov 2 10:55 hard.txt
50812 lrwxrwxrwx 1 imran imran 5 Nov 2 10:55 soft.txt -> a.txt
The first column is the inode number and the third is the link count. The symlink's size is 5 bytes: exactly the length of the string a.txt.
Hard Link vs Symbolic Link
Hard link | Symbolic link | |
|---|---|---|
What it is | Another directory entry for the same inode | A separate file containing a path |
Own inode? | No, shares the target's inode | Yes |
Target deleted | Data stays until the last link is removed | Link becomes dangling |
Across file systems | No (inode numbers are per file system) | Yes |
To directories | Not allowed for users (would allow cycles) | Allowed |
Cost to follow | None, it is a normal entry | Extra path lookup |
Windows equivalent | NTFS hard link ( | Symbolic link ( |
Trying to hard-link a directory on Linux is refused:
$ ln proj projlink
ln: proj: hard link not allowed for directory
Link Counts of Directories
Directories have hard links too, created automatically: the entry in the parent, the directory's own ., and the .. inside each of its subdirectories. So on traditional UNIX file systems:
link count of a directory = 2 + number of immediate subdirectories
Our proj directory has three subdirectories (src, docs, tests) and one file:
$ stat -c '%n links=%h' proj proj/src proj/readme.txt
proj links=5
proj/src links=2
proj/readme.txt links=1
5 = 2 + 3, and an empty directory like src has 2. (Some file systems, such as Btrfs, do not follow this rule, so do not rely on it in scripts.)
Path Name Resolution
How does open("/home/riya/notes.txt", O_RDONLY) find the file? The kernel walks the path one component at a time:
1. Start at the root directory's inode. (on ext4 the root is always inode 2)
2. Read root's data, find "home" → inode 16386
3. Read inode 16386, check it is a directory and that we may search it (x permission)
4. Read its data, find "riya" → inode of riya
5. Read that inode, read its data, find "notes.txt" → inode of notes.txt
6. Read notes.txt's inode, check read permission → return a file descriptor
(Our root and /home inode numbers come from ls -di / /home on the test machine.) A relative path does the same walk but starts at the process's current working directory instead of the root. At each .. the walk moves to the parent.
Numerical: Disk Reads for a Path Lookup
Count the disk reads needed to open /home/riya/notes.txt and read its first data block, assuming nothing is cached, every directory fits in one block, and each inode needs its own read:
root inode 1
root directory block 1 → finds "home"
home inode 1
home directory block 1 → finds "riya"
riya inode 1
riya directory block 1 → finds "notes.txt"
notes.txt inode 1
notes.txt data block 0 1
---
Total 8 reads
A path with k components costs about 2k reads for the lookup alone. That is exactly why open() exists (do this once, then use the descriptor), and why the kernel keeps a directory entry cache (Linux calls it the dcache) of recently looked-up names. In practice, / and /home are almost always cached, so real lookups touch the disk rarely.
Implementing a Directory: List or Hash?
Inside one directory, how are the entries stored so that a name can be found quickly?
Linear List
Entries are stored one after another. To find a name, scan from the start.
Very simple. Creating a file: scan to make sure the name is not already used, then append.
Deleting: mark the entry unused, or move the last entry into its place.
Slow for big directories: lookup is O(n). A directory with 100,000 files (a mail spool, a cache folder) needs up to 100,000 comparisons per lookup.
Keeping the list sorted allows binary search but makes insertion and deletion more expensive.
Hash Table
Hash the name to find its entry directly.
Lookup is O(1) on average.
Needs a way to handle collisions (chaining), and a fixed-size table must be rebuilt when it fills up.
Listing comes out in hash order, not name order.
Real file systems use a tree or hash-tree that grows gracefully:
ext4: a small directory is stored as a simple list of entries inside one block; once it grows beyond one block it becomes an HTree, a hashed B-tree-like index (the
dir_indexfeature). Withdir_indexon,readdir()walks entries in hash order even for one-block directories, which is why our output above came out scrambled.NTFS, XFS, Btrfs, APFS: B-tree or B+ tree indexes on file names.
FAT: a plain linear list, which is one reason FAT gets slow with thousands of files in one folder.
Linear list | Hash table / hash tree | |
|---|---|---|
Lookup | O(n) | O(1) average (O(log n) for a tree) |
Simplicity | Very simple | More complex |
Listing order | Storage order (often insertion order) | Hash order |
Used by | FAT, ext2 (no index) | ext4 HTree, NTFS/XFS/Btrfs B-trees |
Common Mistakes
"A directory is a box that contains files." It contains names that refer to inodes. The file's data is elsewhere, and the same file can be named in two directories.
"Deleting a file erases it."
rmremoves one name. The data is freed only when the link count is 0 and no process has it open. (A process that has a deleted file open can keep using it, which is why disk space sometimes is not freed until a program is restarted.)"A hard link is a shortcut to the original." There is no original. All hard links are equal names for one inode.
Thinking a symlink stores an inode number. It stores a path string, which is why it can cross file systems and why it can dangle.
Forgetting why hard links to directories are banned. They would allow cycles, which break traversal and reference counting.
Expecting
readdir()to return sorted names. No order is guaranteed.
Interview Questions
What does a directory entry contain in UNIX?
A file name and an inode number (ext4 also stores the entry length and a file-type hint). All other attributes are in the inode.
What are the disadvantages of a single-level directory?
All files must have unique names, and there is no way to group files by user or project.
What problem does a two-level directory solve, and which remains?
It lets different users use the same file names and isolates users. It still has no subdirectories within a user and makes sharing difficult.
Absolute vs relative path?
An absolute path starts at the root (/). A relative path starts at the process's current working directory.
What problems does an acyclic-graph directory introduce?
A file can have several names, so traversals may visit it twice, and deleting one name raises the question of dangling references, solved by reference counts or by allowing links to dangle.
Why are cycles in a directory graph a problem?
Traversals can loop forever, and reference counts may never reach zero for an unreachable cycle, so garbage collection is needed to reclaim space.
Hard link vs soft link?
A hard link is another name for the same inode and keeps the data alive; it cannot cross file systems or point to directories. A soft link is a separate file holding a path; it can cross file systems and point to directories but can dangle.
Why is the system call for deletion called unlink?
Because it removes one directory entry (link). The inode and data are freed only when no links and no open descriptors remain.
How do file systems make lookups fast in huge directories?
By indexing names with hash tables or trees (ext4 HTree, NTFS and XFS B-trees) and caching recent lookups in memory (the dentry cache).
The Main Idea
Directory → a file mapping names to inode numbers
Single-level → one list; name clashes
Two-level → one list per user; no grouping
Tree → subdirectories, paths, cwd; no sharing
Acyclic graph → sharing via links; aliasing and deletion issues
General graph → cycles; needs garbage collection, so avoided
Hard link → another name for the same inode (link count)
Symbolic link → a file containing a path; can dangle
Lookup → walk the path one component at a time; cached in dcache
Names live in directories, everything else lives in the inode, and a link is just one more name.
We have now followed a file from its name to its inode to its blocks. The last step is the hardware that stores those blocks. In the next chapter, Disk Structure & Disk Scheduling, we look inside a hard disk and see how the OS orders disk requests to keep the slowest part of the system moving.