Directory Structure

A directory is a system-maintained mapping from file names (strings) to file references — typically inode numbers or file-control-block addresses — within some scope called a namespace. Concretely, a directory is stored on disk exactly like a regular file: it has data blocks, and those blocks hold a sequence of directory entries, each entry recording at minimum a name and a reference to the file's metadata structure. The operating system distinguishes directories from ordinary files only by a type bit in their metadata and by restricting direct writes to directories (users cannot `write()` into a directory; they must use `create`, `unlink`, `mkdir`, `rename`, and so on). A pathname is a sequence of names separated by a delimiter (`/` on POSIX systems, `\` on Windows) that specifies a route through nested directories to reach a target file. An absolute path begins at a distinguished root directory and is resolved the same way regardless of the caller's current position. A relative path is resolved starting from the caller's current working directory. The process of translating a pathname into a concrete file reference — by looking up each component in turn — is called path resolution or pathname lookup. Three structural regimes matter, in increasing order of sophistication: 1. Single-level directory — one flat namespace shared by everyone; all names must be globally unique. 2. Tree-structured directory — directories can contain subdirectories, forming a rooted tree; a file's identity is its unique path from the root, and different subtrees may reuse the same local names. 3. Acyclic-graph directory — the tree is extended by allowing a file (never a directory) to appear under multiple names/paths simultaneously via hard links, forming a directed acyclic graph rather than a strict tree; symbolic (soft) links provide a complementary, looser mechanism that stores a path rather than a direct structural edge.

Single-level directories and why they fail

In a single-level scheme, the entire filesystem's directory is one array (or list) of `(name, reference)` pairs. Lookup, insertion, and deletion are simple: ``` function LOOKUP_FLAT(dir, name): for entry in dir.entries: if entry.name == name: return entry.reference return NOT_FOUND ``` This costs O(n) per lookup in an unsorted list of n entries (O(log n) if kept sorted, O(1) amortized with a hash table) — the search cost is not the fundamental flaw. The flaw is namespace collision: with n files sharing one namespace, every creator must know every existing name to avoid clashing, an O(n) coordination burden that becomes infeasible past a few dozen files or more than one user. This scheme appeared on some of the earliest batch systems and is retained today only in constrained contexts (e.g., the flat structure inside a single ZIP central directory segment, or FAT12 floppy root directories with entry-count limits). A two-level directory (one subdirectory per user, flat inside) relieves cross-user collisions but still forces flat uniqueness within each user's files — an intermediate fix, not a general solution.

Tree-structured directories

The general solution lets any directory contain entries that are themselves directories, recursively, forming a rooted tree. Each non-root directory has exactly one parent; the root has none. A file's identity in the namespace is the sequence of names from the root down to it — its path — so two files in different subtrees may legally share a local name (`/alice/report.txt` and `/bob/report.txt` coexist without conflict).

Path resolution walks this tree component by component. Given path `p = [c0, c1, ..., ck]` (after splitting on the delimiter) and a starting directory `start` (root for absolute paths, cwd for relative paths): ``` function RESOLVE(start_dir, components): current = start_dir for i in 0 .. length(components) - 1: name = components[i] if name == "" or name == ".": continue // skip empty segments, self-reference if name == "..": current = current.parent // move up one level continue entry = LOOKUP(current, name) // O(1)-O(log n) inside one directory if entry == NOT_FOUND: return ERROR("no such file or directory") if i < length(components) - 1: // not the last component: must be a directory to descend further if entry.type != DIRECTORY: return ERROR("not a directory") current = OPEN_DIRECTORY(entry.reference) else: current = entry.reference // final component: return whatever it is return current ``` Each `LOOKUP(current, name)` call is itself a search within one directory's entries — O(1) with a hashed directory format, O(log n) with a sorted B-tree directory (as in NTFS or modern ext4's htree), or O(n) in a naive linear-scan format. For a path with k components, total resolution cost is:

where $L_i$ is the lookup cost inside the i-th directory visited. Since real paths have small, bounded depth (k is a small constant in practice, rarely more than 10–15), tree resolution behaves close to O(k) in the number of directory-lookup operations, dominated by k disk/cache accesses rather than by n, the total file count — this is the entire point of the tree structure over the flat one. Two special entries make `..` (parent) traversal possible without storing full paths: every directory conventionally contains entries `.` (itself) and `..` (its parent), materialized as actual directory-entry rows pointing at the appropriate inode. The root's `..` conventionally points to itself.

The acyclic-graph directory: hard links

A pure tree forbids sharing: a file cannot have two names, and no subdirectory can be reachable via two different paths, because every entry has exactly one parent. Real systems relax this for plain files via a hard link: an operation that creates a new directory entry pointing to the same underlying file object (same inode), rather than creating a new file. ``` function LINK(existing_path, new_path): inode = RESOLVE(existing_path) if inode == NOT_FOUND or inode.type == DIRECTORY: return ERROR // directories may not be hard-linked (see below) parent_dir = RESOLVE(directory_of(new_path)) if LOOKUP(parent_dir, basename(new_path)) != NOT_FOUND: return ERROR("name exists") ADD_ENTRY(parent_dir, basename(new_path), inode) inode.link_count += 1 return SUCCESS ``` Now the same inode is reachable by multiple paths, and the graph of "directory contains file" edges is no longer a tree — it is a directed acyclic graph (DAG): multiple parents are possible for a file, but directories are still restricted to exactly one parent (with the sole exception of the `.`/`..` self/parent bookkeeping entries, which are not counted as extra structural parents). This restriction is deliberate and is the crux of why hard links do not admit cycles. Deletion under hard links requires reference counting. `UNLINK(path)` removes the directory entry and decrements `link_count`; the underlying data blocks are reclaimed only when `link_count` reaches zero and no process holds the file open (many systems track a separate open-file reference count for this reason — POSIX explicitly allows unlinking a file that a process still has open, deferring reclamation until the last file descriptor closes). ``` function UNLINK(path): parent_dir = RESOLVE(directory_of(path)) entry = LOOKUP(parent_dir, basename(path)) if entry == NOT_FOUND: return ERROR REMOVE_ENTRY(parent_dir, basename(path)) entry.reference.link_count -= 1 if entry.reference.link_count == 0 and entry.reference.open_count == 0: FREE_BLOCKS(entry.reference) FREE_INODE(entry.reference) return SUCCESS ```

Why directories cannot be hard-linked. If directories could have multiple parents, or worse, a directory could be linked as a child of one of its own descendants, path resolution using `..` would become ambiguous (which parent does `..` mean?) and, more seriously, cycles become constructible: link directory D as a child inside its own subtree, and a tree-walking program (recursive delete, `du`, backup tools) would loop forever, since these tools rely on the graph being acyclic to guarantee termination. Banning directory hard-links is precisely what keeps the containment graph a DAG (in fact, in every real system it is kept a strict tree for directories, with sharing allowed only among leaves/files) and keeps recursive traversal provably terminating.

Symbolic links: an escape hatch, with new hazards

A symbolic (soft) link is a small special file whose content is a path string, not a direct structural reference. Resolution treats it specially: ``` function RESOLVE_WITH_SYMLINKS(start_dir, components, depth_limit): if depth_limit <= 0: return ERROR("too many levels of symbolic links") current = start_dir for i in 0 .. length(components) - 1: entry = LOOKUP(current, components[i]) if entry == NOT_FOUND: return ERROR if entry.type == SYMLINK: target_path = READ_SYMLINK_CONTENTS(entry.reference) base = ROOT if IS_ABSOLUTE(target_path) else current result = RESOLVE_WITH_SYMLINKS(base, SPLIT(target_path), depth_limit - 1) if result is ERROR: return result current = result continue // ... same directory/last-component logic as before return current ``` Because a symlink's target is just text, it can point to a nonexistent file (dangling link), across filesystem boundaries (unlike hard links, which require the same filesystem since inode numbers are only unique per-filesystem), and even to a directory. This flexibility is exactly why symlinks can form cycles (`a → b`, `b → a`), so every real resolver enforces a bounded recursion depth (Linux historically capped total symlink dereferences at 40 during one path resolution) instead of relying on structural acyclicity, trading a guarantee (no cycles) for flexibility plus an explicit runtime check.

Directory operations summary

``` CREATE(path, type): add entry (name, new_inode) to parent directory; init link_count = 1 DELETE / UNLINK(path): remove entry; decrement link_count; free when 0 and unopened LINK(old, new): add entry (new_name, existing_inode); increment link_count SYMLINK(target, path): create a special file whose content is the string `target` RENAME(old, new): atomically move/replace a directory entry (same inode, new name/location) MKDIR(path): create new directory inode with entries `.` -> self, `..` -> parent RMDIR(path): remove directory entry; require directory to contain only `.`/`..` LIST(path): return the sequence of entries in a directory ``` `RENAME` deserves a note: on POSIX systems it is required to be atomic with respect to concurrent lookups — a reader must never observe the name missing entirely — which is why it is usually implemented as a single directory-entry-table update rather than a delete-then-create pair.

Time complexity of resolution. For a path with k components, resolution performs k directory lookups. Let $L$ be the per-directory lookup cost: $O(1)$ expected for hashed directory formats, $O(\log m)$ for balanced-tree directory formats (m = entries in that directory), or $O(m)$ for naive linear scan. Total cost is $O(k \cdot L_{\max})$, i.e., proportional to path depth, independent of total files n in the whole filesystem — this is the structural payoff of trees over flat namespaces, where lookup was $\Theta(n)$ or $\Theta(\log n)$ against the entire file population. In practice operating systems also cache resolved (path-component → inode) mappings (e.g., the Linux dentry cache), making repeated resolutions of hot paths effectively O(1) amortized.

Space complexity. A directory occupies space proportional to the number of entries it holds and the length of stored names: $O\!\left(\sum_i (|name_i| + c)\right)$ for a constant per-entry metadata overhead c (inode number, type bits, entry length). The directory tree overall uses $O(n)$ total space for n files, same asymptotic order as any scheme, but organizes it so per-operation cost depends on local directory size, not global file count.

Correctness of tree resolution — invariant argument. Define the invariant: at every point during `RESOLVE`, `current` denotes a directory (or, at the final step, any file type) reachable from `start_dir` by the path traversed so far, or the function has already returned an error. This holds by induction: it is true initially (`current = start_dir` trivially reachable by the empty prefix), and each loop iteration either (a) moves `current` to `.parent`, which is well-defined because every directory has exactly one parent pointer maintained by the filesystem, or (b) performs `LOOKUP`, which either finds an entry genuinely stored under `current` (preserving reachability) or returns `NOT_FOUND`, in which case the function returns an error immediately rather than continuing with a stale `current`. Termination follows because the loop bound is the fixed, finite list of components — no unbounded recursion exists in the plain tree case.

Why directories must form a tree (not just a DAG) for traversal to terminate. Suppose, for contradiction, a directory D could have two parents, one of which is a descendant of D itself (a cycle in the containment relation). A depth-first traversal algorithm (used by `du`, recursive delete, backup) that marks directories visited-in-current-path and recurses into children would re-enter D from that descendant parent, and since the visited-marking is typically per-root-to-leaf-path (not global, because the same directory legitimately shouldn't be visited twice as a sibling under two different top-level directories in the false hard-link scenario — but here it's the same path re-entering itself) the recursion depth is unbounded and the traversal never terminates. This is precisely why every mainstream filesystem's `mkdir`/`link` semantics forbid creating a second hard-linked parent for a directory: it is the load-bearing invariant that makes "acyclic" true for the containment structure and guarantees every tree-walking algorithm halts. (Historically, only the superuser could hard-link directories on some early Unix systems for creating `..` bookkeeping; this is now disallowed everywhere in practice.)

Symlinks trade the invariant for a runtime check. Because a symlink's target is arbitrary text re-resolved from scratch, no structural invariant prevents a cycle (`/a` → `/b`, `/b` → `/a`); the correctness argument shifts from "acyclic by construction" to "bounded by an explicit recursion-depth counter," which is why `RESOLVE_WITH_SYMLINKS` must carry `depth_limit` and fail loudly (`ELOOP` in POSIX) rather than loop forever — a weaker but still sound guarantee, since it guarantees termination, not absence of surprising redirection.

Tradeoffs, honestly stated:

Trace resolving the absolute path `/home/alice/notes/todo.txt` on a tree-structured filesystem, then show what changes once a hard link and a symlink are added.

Setup. Root `/` contains entry `home → inode 10`. Inode 10 (directory) contains `alice → inode 22`. Inode 22 (directory) contains `notes → inode 47`. Inode 47 (directory) contains `todo.txt → inode 91` (a regular file).

Result: `RESOLVE` returns inode 91, in 4 directory lookups (k = 4), each O(1) with a hashed directory format — matching the O(k·L) bound derived above, and never touching the other (potentially millions of) files elsewhere in the tree.

Now add a hard link: `LINK("/home/alice/notes/todo.txt", "/home/bob/shared_todo.txt")`. 1. `RESOLVE("/home/alice/notes/todo.txt")` → inode 91 (as traced above); check `type != DIRECTORY` → passes (it's a file). 2. Resolve parent of new path: `/home/bob` → inode 65 (directory). 3. `LOOKUP(inode 65, "shared_todo.txt")` → NOT_FOUND, so the name is free. 4. `ADD_ENTRY(inode 65, "shared_todo.txt", 91)`; `inode 91.link_count` goes from 1 to 2. Now inode 91 has two parents in the containment graph — `/home/alice/notes/` and `/home/bob/` — a legal DAG structure precisely because inode 91 is a file, not a directory.

Unlinking one name: `UNLINK("/home/alice/notes/todo.txt")` decrements `link_count` to 1 and removes only that one directory entry. The data survives, reachable now solely as `/home/bob/shared_todo.txt`, exactly as reference counting promises — the file is destroyed only when the count reaches zero.

Adding a dangling symlink: `SYMLINK("/home/alice/notes/todo.txt", "/home/carol/old_link")` after the unlink above. Resolving `/home/carol/old_link` succeeds in finding the symlink entry, reads its stored text `/home/alice/notes/todo.txt`, and re-resolves that path — which now fails at the `todo.txt` lookup step inside inode 47 (that entry was removed), correctly returning `ERROR("no such file or directory")` rather than crashing, exactly the dangling-reference behavior symbolic links must tolerate.

The directory-structure abstraction crystallized across the transition from batch systems with flat file catalogs to interactive, multi-user timesharing systems that demanded namespace isolation and sharing.

Every mainstream filesystem — ext4, XFS, Btrfs, APFS, NTFS, ZFS — implements exactly the tree-plus-hard-links-plus-symlinks model described here, differing mainly in the internal directory encoding (linear list vs. hashed vs. B-tree, covered in File-System Implementation and Layout) rather than the logical namespace model. Package managers and deduplicating backup tools (e.g., `rsync --link-dest`, many container image layers) exploit hard links to share unchanged files across snapshots without duplicating storage, relying precisely on reference counting to reclaim space safely. Container runtimes and `chroot`/mount-namespace mechanisms manipulate the effective root of path resolution, showing that "the root directory" is itself a per-process, configurable starting point for the `RESOLVE` algorithm rather than an immutable global constant. Symbolic links underpin versioning conventions (`/usr/lib/libfoo.so → libfoo.so.1.2.3`) letting a stable name track a changing target, and dangling-symlink and symlink-cycle handling is a recurring source of real security advisories (symlink race attacks, path-traversal exploits) — motivating kernel mitigations like `O_NOFOLLOW` and restricted symlink-following in world-writable directories. The whole discussion here sets up File-System Implementation and Layout, where directories' on-disk encoding is examined, and Inodes and File Metadata, where the file-reference objects that directory entries point to are defined in full.

Ask the tutor: How does the actual on-disk format of a directory (linear list, hash table, or B-tree) affect these complexity bounds in a real filesystem like ext4 or NTFS?