Hierarchical file systems, and what they replaced

1960sWhat came before the tree

A file system with no nesting gives every user one place to put things. When one place is not enough, the structure moves into the name itself, and names acquire punctuation that means something to people and nothing to the system.

That arrangement is the same pattern as the fixed-width directory entry elsewhere in this document: a limit in the storage answered by a convention in the text, maintained by everyone separately and enforced by nobody.

1965 onwardsThe system that generalised it

The design that introduced a directory tree of arbitrary depth treated a directory as an ordinary object that happened to contain entries. Nesting was not limited, and a path was a sequence of names rather than a fixed number of levels.

The system that borrowed it kept the idea and threw away most of the apparatus, which is the usual relationship between those two projects and worth stating without either reverence or dismissal.

1970sThe decision underneath

A directory is a file whose contents are pairs of a name and a number identifying the object. The name lives in the directory, and not in the object.

Everything characteristic follows from that. One object can have several names in several places, because nothing about it records what it is called. Deleting a name is not deleting the object, only the entry, and the object survives until the last entry goes. The self-referential entries for the current and parent directory are just two more pairs.

What the tree costs

A tree admits exactly one classification. A file is in one place, and every other way of grouping it has to be built on top.

That is why links, tags, saved searches, and per-application libraries all exist. Each is a way of saying that a photograph is in one folder and also belongs with several other sets, which the tree cannot express and which almost every user wants.

Why it won anyway

Because a tree is the cheapest structure that scales without agreement. A person can create a level without asking anybody, the meaning of a path is local to the person who made it, and no central vocabulary has to be maintained.

Every richer scheme requires somebody to define the categories, and definitions age badly. The same argument decided the shape of the connection between programs elsewhere in this part.

What the shape enables that is rarely noticed

Because the path is interpreted from left to right by whoever holds the reference, subtrees can be attached from elsewhere and behave as if they were always there. Mounting a second disk, in the entry about the directory named for users, is exactly that mechanism.

A modern machine leans on it heavily. Network shares, container images and virtual file systems presenting kernel state as text all appear in the tree as ordinary directories, and nothing above them needs to know.

The part that is not a tree

Strictly the structure is not a tree at all, because one object may be reachable by several paths. What prevents it from being a general graph is a rule rather than a mechanism: ordinary directories are not permitted to have more than one parent.

That rule exists because a cycle among directories would make walking the structure non-terminating and reference counting insufficient to know when to delete anything. So the tree is a deliberate restriction of something more general, imposed to keep simple algorithms correct.

Where the restriction is relaxed and what it costs

Symbolic links relax it by holding a path rather than a reference, which permits cycles and dangling targets and pushes the problem to whoever follows one. Every tool that walks a directory tree therefore has to decide whether to follow them, and tools disagree.

That disagreement is the source of a long tail of surprising behaviour: an archive that unpacks differently than expected, a recursive delete that leaves or removes more than intended, a search that visits the same files repeatedly.

Names as the only metadata everyone agreed on

Because the system holds so little about a file beyond its name, the name carries the rest. Dates, versions, status and ownership are routinely encoded into names by people who need them visible and portable.

Which returns exactly to the pattern this entry began with. Structure that the system does not hold moves into the text, is maintained by convention, and is enforced by nobody, sixty years later.

present dayWhere the tree quietly stopped being the interface

Most people no longer navigate one. Phones present applications and libraries; desktop work increasingly starts from search rather than from a path; and a large share of documents live in systems where the location is a detail of the storage rather than a thing a person chooses.

The tree is still underneath all of it. What changed is that the single classification it forces is now imposed on the software rather than on the user, which is a reasonable division of labour and took about forty years to arrive at.

What we cannot verify

The designs and their dates are documented in published papers and manuals. Which specific ideas passed from one system to the other, and in what form, is recounted mainly by participants long afterwards and is disputed in places. Claims about what any individual intended should be read as recollection.