Directory structure — tree, DAG (hard links, symbolic links): Visual walkthrough

We will earn every word: box, inode number, name, link count, tree, DAG, symlink. Nothing is assumed.

Step 1 — A box of bytes with a number, but no name

WHAT. Picture a physical box on a shelf. Inside the box is your file's actual content — the bytes. Painted on the outside of the box is a number, say 42. That box-with-a-number is what Unix calls an inode (see Inodes and File Metadata).

WHY start here. Because the single most important design choice in the whole chapter is this: the box knows its number, but the box does NOT know its name. The name lives somewhere else entirely. If we don't see this separation clearly, hard links and symlinks look like magic. They aren't.

PICTURE. The box holds the bytes and a small counter we'll define in Step 3. It has a number (42) but no label saying "a.txt" — that label is off to the side, not attached.

Figure — Directory structure — tree, DAG (hard links, symbolic links)

Step 2 — A name is a sticker in a room, not part of the box

WHAT. A directory is itself just a box whose contents are a list of stickers. Each sticker is a pair:

$human name ("a.txt", which box 42)$

$"a.txt"$ — the name a human reads. This is doing the job of "what you type."
$42$ — the inode number. This is doing the job of "which box on the shelf."

Such a pair is called a directory entry or dentry.

WHY. Now we can answer the filesystem's one job — "given a name, where is the data?" — by looking up the name in the room's sticker list, reading off the number, and walking to that box. Name and box are connected only through this sticker.

PICTURE. A room (directory) contains one sticker a.txt → 42, and an arrow from the sticker to box 42. The sticker is glued to the wall of the room, never to the box.

Step 3 — The counter on the box: link count

WHAT. Every box keeps a small integer painted on it: the link count $n$ .

$n = # {stickers currently pointing at this box}$

$# {\dots}$ — "the number of things in this set," i.e. count them.
The set is every dentry (sticker) whose number equals this inode's number.

Right now, with one sticker a.txt → 42, we have $n = 1$ .

WHY a counter at all? Because we must eventually know when it is safe to throw the box away. Throwing away a box that some name still points to would corrupt the filesystem. The counter answers "is anyone still pointing here?" without scanning the entire disk. This is exactly reference counting.

PICTURE. Box 42 with its counter reading 1, one sticker arrow landing on it.

Step 4 — One name, one parent: this is a TREE

WHAT. Suppose every box has exactly one sticker, and every room sits inside exactly one parent room. Draw rooms as circles and "contains" as arrows pointing down. The result has a special shape.

WHY it matters. A shape where every node has exactly one parent (except the top, the root /) and there are no loops is called a tree (see Graphs — Trees vs DAGs). In a tree, each box is reachable by exactly one path — so a name is the file, and deleting is trivial: remove the one sticker, box hits $n = 0$ , free it.

PICTURE. Root / at top; two rooms below it; files below those. Every arrow-count into any node is exactly 1 — the signature of a tree.

Step 5 — A second sticker for the same box: the tree breaks

WHAT. Run one command: ln a.txt b.txt. This does not copy the box. It adds a second sticker b.txt → 42 and bumps the counter: $n : 1 \to 2$ .

$two stickers n = 2 = {a.txt \to 42, b.txt \to 42}$

Both stickers are equal — there is no "original" and no "copy." Both are first-class hard links.

WHY this is the turning point. Look at box 42 now: two arrows point into it. In a tree, every node has at most one arrow pointing in. A node with two incoming arrows cannot be in a tree. The shape just changed.

PICTURE. Two stickers in (possibly different) rooms, both arrows landing on box 42, whose counter now reads 2.

Step 6 — Why it's a DAG and not just "a graph": no loops allowed

WHAT. A box with several incoming arrows means several paths reach the same data — the shape is now a graph, not a tree. But it is a special graph: we forbid a directory from pointing back up to one of its own ancestors, so you can never walk in a circle. A directed graph with arrows but no cycles is a Directed Acyclic Graph (DAG).

WHY forbid the loops? Two reasons, both visible in the picture:

Traversal must stop. Tools like find and du walk arrows. A loop would send them around forever.
The counter would lie. If a directory could point back to its ancestor, the "how many stickers reach me" count could never fall to 0, so the box could never be freed.

That is why the kernel bans user-created hard links to directories — only the special automatic . and .. entries are allowed, and the kernel handles those carefully.

PICTURE. Left: a valid DAG — many paths to one file, all arrows flowing downward, no loop. Right (crossed out): a forbidden back-arrow from a child directory to its ancestor, forming a cycle.

Step 7 — The soft link: a signpost, not a second name

WHAT. Run ln -s a.txt s.txt. This makes a brand-new box (a new inode, say 99) whose contents are the text string "a.txt". It is a symbolic link (symlink). Resolving it means: read the string, then re-start the name lookup from that string.

Crucially, creating it does NOT touch box 42's counter:

$n_{42} = 1 (unchanged), n_{99} = 1 (its own single name)$

WHY have a second kind of link? Because a hard link stores an inode number, which is only meaningful within one filesystem and can't point at a directory (loop danger). A symlink stores only text, so it can point across filesystems and at directories freely — it just carries no guarantee the target still exists.

PICTURE. Box 99 is a little signpost holding the text "a.txt"; a dashed arrow leaves it and lands on the sticker a.txt, not directly on box 42. Box 42's counter still reads 1.

Step 8 — Degenerate cases: what happens at the edges

WHAT & WHY (each edge shown in the figure).

Delete one hard link when $n = 2$ . rm a.txt → unlink() → $n : 2 \to 1$ . Box survives, still reachable via b.txt. The box is not freed because $n > 0$ .
Delete the last hard link ( $n : 1 \to 0$ ). Now no sticker points in; if no program holds it open, the bytes are freed. This is the only way a box dies.
Open-file exception ( $n = 0$ but a program still has it open). The bytes stay alive until the last program closes it — a classic "unlinked-but-open" temp file.
Delete a symlink's target. The sticker a.txt vanishes, but the symlink box 99 still holds the text "a.txt". Resolution now fails → a dangling (broken) link. Note the target's count was never bumped, so it wasn't protected.

PICTURE. Four mini-panels: (1) $n : 2 \to 1$ survives, (2) $n : 1 \to 0$ freed, (3) $n = 0$ but open → still alive, (4) symlink left pointing at nothing.

The one-picture summary

Everything above collapses into one diagram: a tree with one extra hard link (turning it into a DAG) and one symlink off to the side pointing at a name. Trace it and you can re-derive the whole chapter.

Recall Feynman retelling — the walkthrough in plain words

Think of a shelf full of numbered boxes. A box holds your stuff and a little tally counter, but no label — the labels are stickers glued to the walls of rooms. To find your stuff you read a sticker, get the box number, and walk to that box. Step 1–2: box + sticker. Step 3: the box counts how many stickers point at it. Step 4: if every box has exactly one sticker and rooms nest neatly, the whole map is a family tree — one path to everything. Step 5: the instant you slap a second sticker (in any room) that says the same box number, the box now has two stickers, its counter reads 2, and two paths reach one box — the tree just broke. Step 6: it's now a web, but a well-behaved one: we never let a room point back up to its own grandparent, so you can never walk in circles — that's a DAG. Step 7: a soft link is different — it's a little note-box that just says "go find the sticker called a.txt." It doesn't bump anyone's counter. Step 8: peel one sticker off a two-counter box and the stuff survives; peel the last one and the stuff is thrown out — unless a friend is still holding the box open. Tear away the name a note points to, and the note points at nothing. That's the entire story.

Connections

Inodes and File Metadata
File System Implementation — Block Allocation
Path Resolution and the namei() routine
Mount points and Virtual File System (VFS)
Graphs — Trees vs DAGs
Reference Counting and Garbage Collection
Unix system calls — link, unlink, symlink, stat