Unix shipped no file database. No attribute catalog, no tag store, no content index, no query language — nothing between a program and the bytes except a tree of names. The Unix namespace is the index, and that is not an omission waiting to be corrected; it is the design decision the system is built on. The path is the only key the kernel maintains, so every lookup that is not a path lookup degrades into a scan: of a file’s bytes, of a directory’s entries, or of a database somebody else agreed to rebuild overnight.
That stance is really two bets, and only one of them survived. Scan, don’t index — brute force is always correct, never stale, and cheap at 1970s data volumes. The namespace is the only metadata — organise by naming, because there is no second axis. The second bet still shapes systems that have never heard of Unix. The first has been quietly repealed, and the repeal is hiding in a file most engineers edit once a quarter without thinking of it as infrastructure.

The Only Global Catalog Unix Ever Shipped Is a Tree
Start with what is absent. A Unix filesystem records a small fixed set of per-file attributes — mode, owner, group, size, timestamps, link count, device and inode — plus one name per directory entry. No user-extensible attribute schema in the base model, no tag namespace, no full-text index, and no way to ask the kernel a question that is not “resolve this path” or “list this directory.” Extended attributes exist on modern filesystems, but nothing indexes them, so “which files carry this xattr” is still a walk.
The consequence is structural: hierarchy becomes a permanent modelling decision made at file-creation time. Every organisational question a team has — by project, by type, by owner, by lifecycle, by customer — must collapse into one tree with one answer, because the tree is the only thing the system will search for you. Choose by-project/by-type and “show me every config file” becomes a walk. Invert it and “show me everything for this customer” becomes a walk. No arrangement is right for every query, and there is no second index to rescue you.
Every inheritor inherited the problem. S3 has no directories at all — the “folders” in the console are a display convention over prefixes in a flat keyspace, and prefix listing is the only structural query the store performs natively. And every fix has the same shape: bolt on an orthogonal query dimension the hierarchy cannot express. Kubernetes label selectors are exactly that — a metadata index for objects whose names already form a hierarchy, added because names could not answer the questions operators had.
When your only index is your naming scheme, your naming scheme is your query planner. Pick it accordingly, and expect to buy a second axis later.

Brute Force Was the Right Answer to a 1.5 MB Disk
grep is the purest expression of the first bet. It consults nothing, remembers nothing, and reads every byte it is pointed at — so it is always correct and never stale, two guarantees no index offers, at a cost that is a straight line in the size of the corpus.
Its origin makes the stance explicit. grep is literally an ed command line: g/re/p, global / regular expression / print. Thompson pulled ed‘s regex engine into a standalone streaming program because ed loaded whole files into memory for random-access editing and choked on large inputs. The creation date is 3 March 1973, and it appears in the Version 4 manual of November 1973 — Fourth Edition Research Unix, not System V, which is an unrelated version line. The familiar origin story (McIlroy asked; Thompson delivered overnight a tool he largely had already) is recollection from Kernighan and McIlroy, not a documented record.
One credit routinely lands in the wrong place: the regular expression is not a Unix invention. Kleene defined regular events in RAND memorandum RM-704, December 1951, about nerve nets rather than text. Thompson published his linear-time matching algorithm in CACM 11(6), June 1968 — a compiler emitting IBM 7094 machine code for a pattern, written for his QED editor on CTSS, a year before the PDP-7 work that became Unix. Regex was carried into Unix. Russ Cox’s account also documents Unix’s own reversal: early ed and grep used recursive backtracking despite Thompson’s published linear-time result, and the DFA only returned with egrep in the Seventh Edition.
Brute force was right rather than merely simple because of the hardware. Research Unix ran on PDP-11s with RK05 disk packs of roughly 1.5 MB each. Building an index over 1.5 MB costs more than reading 1.5 MB. On that corpus the crossover between “scan it” and “maintain a structure so you don’t have to” sat firmly on the scan side.
That crossover has moved in one direction every year since, which is the question this whole argument reduces to: not “index or scan,” but “where is my crossover, and which side am I on today?” Most teams answer once, at founding — which is how a full scan survives on a hot path that was genuinely fine when the table had four thousand rows.

Three Bets About Where Search Cost Should Live
Unix shipped three tools that answer “find something,” and they differ in one dimension: when the work happens.
grep pays at query time, in bytes read. find pays at query time too, but in stat() calls — it walks the tree and interrogates inode metadata, so cost scales with the number of files rather than their size, which is why it degrades on deep trees and collapses on network filesystems. find appeared in Version 5 Unix (around June 1974), written by Dick Haight alongside cpio; its real innovation was pairing recursive traversal with an attached action via -exec. The -print0/xargs -0 convention that finally made filenames-with-whitespace safe came much later, credited to D. J. Bernstein — the text-stream interface had a sharp edge nobody designed out for two decades.
locate is the interesting one: the only content-location index Unix ever shipped, and knowingly wrong. updatedb walks the entire filesystem as slowly as find does and writes a name database — historically /var/lib/mlocate/mlocate.db — from a daily cron job or systemd timer. plocate is the modern drop-in replacement using posting lists for faster queries over a smaller index; the plocate(1) manual page documents the format and the rebuild cadence.
The property that matters is not the data structure. It is that entry lifetime is decoupled from file lifetime. A file created five minutes ago is invisible. A file deleted five minutes ago is still listed, as a phantom. locate is a cache with a worst-case staleness window of one full rebuild interval, and it fails the way caches fail.
| Tool | Where the cost is paid | What it consults | Staleness | Correctness | Characteristic failure |
|---|---|---|---|---|---|
grep (1973) | Query time — proportional to bytes read | Nothing but file contents | None — always current | Exact, over everything it reads | Unbounded time on a large corpus |
find (V5, ~1974) | Query time — one stat() per entry walked | Directory entries and inode metadata | None — always current | Exact for metadata predicates; never sees content | Scales with file count; pathological on deep or networked trees |
locate / mlocate / plocate | Ahead of time — a nightly updatedb full walk | A prebuilt name database | Up to one rebuild interval (typically 24h) | Wrong in both directions between runs | Misses new files; returns phantoms for deleted ones |
ripgrep / ag (2011–2016) | Query time, minus whatever the ignore rules prune | File contents plus .gitignore/.ignore and VCS metadata | As stale as the ignore files humans maintain | Exact over the subtree it agreed to look at | Silently skips matches the ignore rules excluded |
Shipping a knowingly-wrong-but-fast tool beside an always-correct-but-slow one, with no reconciliation and no staleness indicator in the output, is a design review worth having on its own merits. That is the contract of every materialised view, search index, and read replica you will ever ship. Unix made the trade in 1974 and then declined to help you reason about it — locate prints results with no timestamp, no “as of,” no warning.

The Brute-Force Stance Was Quietly Repealed
Here the honest version diverges from the romantic one. The tools that beat grep did not beat it by scanning faster. They beat it by not scanning.
The first move was algorithmic and stayed inside the original bet. Mike Haertel, GNU grep’s original author, explained on the FreeBSD mailing list in August 2010 that GNU grep is fast precisely because it avoids looking at most input bytes: a Boyer–Moore skip table jumps ahead by the pattern length, the program deliberately refuses to split input into lines (finding newlines would force it to touch every byte), and the unrolled inner loop executes fewer than three x86 instructions per byte actually examined. Speed came from looking at less, not looking faster.
The second move left the bet behind entirely, and nobody announced it. The Silver Searcher (ag), released by Geoff Greer on 27 December 2011, was 5–10× faster than ack — and, decisively, respected .gitignore and .hgignore automatically. ripgrep, whose author Andrew Gallant published a detailed benchmark writeup on 23 September 2016, pushed the algorithmic side much further: a lazy on-the-fly DFA with no backtracking, UTF-8 decoding compiled into the state machine so matching runs on raw bytes, literal extraction so \w+foo\d+ hunts for foo first, a rarest-byte heuristic for memchr instead of Boyer–Moore’s last-byte convention, the SIMD multi-pattern algorithm Teddy adapted from Intel Hyperscan, and a lock-free work-stealing directory walk.
The headline numbers — meaningful only with their workload attached, which was the Linux kernel tree plus a 1–1.6 GB subtitle corpus, warm page cache, a warm-up run plus ten timed runs each — were a Linux-repository search in 0.334 s while respecting .gitignore, against The Silver Searcher’s 1.588 s; a 1 GB literal search in 0.268 s against GNU grep’s 0.516 s; and case-insensitive Unicode search in 0.366 s, beating GNU grep’s ASCII-only 0.614 s.
Notice which number carries a parenthesis. The 1 GB single-file literal search is a fair fight, won by roughly 2×. The repository search — the one with the eye-catching margin — is a fight in which one competitor has agreed in advance not to read most of the files.
.gitignore is an index. Coarse, negative, hand-authored, never validated against reality — but a maintained metadata file consulted before the data, which is the definition of the thing Unix declined to ship. The brute-force stance was not overturned by a better design. It was repealed by convention, and the convention arrived from a version control system rather than the operating system.
That is the characteristic Unix failure mode, not an exception to it. Sockets cannot be open()ed by path. ioctl() is the admission that “everything is a file” ran out of verbs. And search — the one place Unix was proudest of needing no state — now leans on a state file a human edits by hand.
The operational consequence is blunt: if search correctness depends on an ignore file, that file is a production dependency with no tests. It drifts, it accumulates over-broad globs somebody added in 2019 to silence a noisy directory, and when it hides a result the tool still reports success.

Narrow, Then Verify: The Synthesis That Resolves It
The mature answer is neither index nor scan but both, staged — and Cox published the clean version in January 2012 in Regular Expression Matching with a Trigram Index, the design behind Google Code Search.
The move is to translate the query into one the index can answer. /Google.*Search/ becomes a boolean expression over three-character substrings — Goo AND oog AND ogl AND gle AND Sea AND ear AND arc AND rch — which a posting-list index resolves cheaply into a candidate set. A linear-time engine then scans only the survivors, exactly, so no false positive can escape. The measured shape of that trade: the Linux 3.1.3 sources, 420 MB, produced a 77 MB index — about 18% overhead; searching “hello world” across 36,972 files narrowed to 25 candidates, roughly 100× faster than scanning, with case-insensitive queries still an order of magnitude ahead.
Filter cheaply, verify exactly. The shape is everywhere once you have it: a Bloom filter ahead of a disk read, an approximate vector search ahead of a reranker, a WAF prefilter ahead of full rule evaluation, partition pruning ahead of a table scan. The cheap stage may be approximate in one direction only — it can admit candidates that fail, never reject a true match — and the expensive stage is allowed to be slow because it runs on almost nothing. Retrieval systems from Postgres running as a vector database to reverse image search pipelines are this same two-phase architecture with different candidate generators.
.gitignore is the degenerate version, which is what makes it both forgivable and dangerous: a filter stage that can reject a true match, with no verification stage behind it.

The Filesystem Hierarchy Standard Is Convention, Not Mechanism
If the namespace is the index, the layout of the namespace is the schema — and what holds that schema in place is very close to nothing.
FSSTND was released on 14 February 1994 for Linux only, then broadened with BSD community input and renamed the Filesystem Hierarchy Standard. The current FHS 3.0 was published on 18 March 2015, maintained by the Linux Foundation. It is a document. No kernel reads it, no syscall consults it, no check runs at boot. macOS — a fully certified UNIX — does not follow it at all.
| Path | What the FHS says it is for | What actually enforces it |
|---|---|---|
/bin, /usr/bin | Essential vs. non-essential user commands | Nothing in the kernel — only #!/bin/sh shebang lines and paths compiled into programs. On usrmerge systems /bin is a symlink and the distinction is gone |
/lib, /usr/lib | Shared libraries and kernel modules | The only genuinely hard dependency here: every dynamically linked ELF binary embeds its interpreter path (PT_INTERP, e.g. /lib64/ld-linux-x86-64.so.2). Enforcement by binary format, not policy |
/etc | Host-specific system configuration | Convention plus each program’s compiled-in default path |
/var | Variable data — logs, spools, caches, mlocate.db | Convention and package-manager policy |
/tmp | Temporary files | Convention, TMPDIR, libc defaults. The sticky bit is kernel-enforced — but it governs who may delete, not where the directory lives |
/proc, /sys, /dev | Kernel, driver and device interfaces | Real mechanism — but the mechanism is a mount, not a path. procfs can be mounted anywhere; tools hard-code /proc by choice |
/usr | Shareable, read-only data | Nothing. The name is a 1970s accident, and usrmerge retired the split it caused |
/home | User home directories | The passwd database, not the layout. macOS uses /Users |
/opt | Add-on application software packages | Convention only, widely ignored in favour of /usr/local or /srv |
The /usr row earns its own paragraph, because the accident behind it is the best illustration of how a namespace ossifies. Per Rob Landley’s account on the busybox mailing list in December 2010: the PDP-11 had two RK05 packs; the operating system outgrew the first, so it leaked onto the second — the pack holding user home directories — which is why the mount point was called /usr, and why OS directories were replicated there as /usr/bin, /usr/lib, /usr/sbin. When a third disk arrived the users moved to /home and the OS kept both original packs. The /bin versus /usr/bin split every distribution carried into the 2020s is a fossil of a 1.5 MB disk that filled up in the 1970s, finally closed by the usrmerge symlinks. “Unix System Resources” is a back-ronym invented later; the FHS defines /usr as shareable, read-only data.
That is the house pattern surfacing in the filesystem layout: load-bearing structure is often an accident that ossified. fork was 27 lines of PDP-7 assembly because that was easy. /usr was a second disk pack. Neither was designed; both became permanent, because a namespace that thousands of programs hard-code paths into cannot be renamed without breaking all of them at once. Which is the real answer to “why doesn’t anyone fix the FHS”: nothing enforces it, and that is precisely why nothing can change it.

apropos Is the One Index Unix Actually Shipped
There is exactly one place Unix built a real searchable database into the base system, and it is not for your files. It is for the manual.
Man pages exist because a manager insisted. Ritchie and Thompson wrote the first ones at the insistence of Doug McIlroy, then head of the Computing Techniques Research Department; the UNIX Programmer’s Manual, First Edition, is dated 3 November 1971. The system had run roughly two years with no documentation at all.
What McIlroy imposed was a schema. Fixed headings — NAME, SYNOPSIS, DESCRIPTION and the rest — plus numbered sections 1 through 8, which makes the NAME line’s one-sentence summary a mechanically extractable field at a known position in every document on the system. A precursor called manwhere appeared in 1BSD (1978); apropos and whatis shipped in 2BSD in May 1979, out of Bill Joy’s Berkeley work; today mandb builds the database from a timer or a manual run, and man -k is simply apropos. Note the split credit: the man-page format is Bell Labs, the search layer over it is Berkeley’s.
The ordering is the lesson: structure first, index second. apropos is not clever. It works because someone forced every document into a constrained format before anyone tried to search them.
Watch the counter-example run in real time. --help output has no schema — headings, ordering, and the presence of a one-line summary are at each program’s discretion — so nothing indexes it and nothing will without per-program normalisation. Minimal container images strip man pages to save a few megabytes, leaving the local database empty inside exactly the environments engineers now live in. info, project websites and tldr pages all sit outside the database. The local index dies with the local documents, which is the actual reason most engineers now search the web for a flag they could have looked up offline in 1985.
The generalisation has nothing to do with Unix: free-text log lines, unstructured commit messages and config comments never become queryable no matter what gets bolted on later, because there is no field to index. The structured-logging movement is this lesson relearned at cost. What makes an artifact searchable in three years is the format imposed at write time, not the search engine bought afterwards.

The Road Not Taken That Containers Took Anyway
The radical version of “the namespace is the index” was built at Bell Labs — in Plan 9, by several of the same people — and the paper describing it reads like a critique of the system they had already given the world.
Pike, Presotto, Thompson, Trickey and Winterbottom presented The Use of Name Spaces in Plan 9 at the 5th ACM SIGOPS European Workshop in 1992. The thesis: “a user or process assembles a private view of the system by constructing a file name space that connects these resources.” Not the filesystem — a filesystem, per process, assembled at creation time from mount() and bind() calls, with union directories letting several trees occupy one path and a 17-message 9P protocol making local and remote services indistinguishable. Network interfaces (/net/tcp), processes (/proc), the console (/dev/cons) and graphics all appeared as file trees — what “everything is a file” looks like when someone actually means it.
The paper takes an explicit swing at Unix’s search-path hack. A private binary directory, it notes, “is usually unioned with /bin. (Compare this to the ad hoc and special-purpose idea of the PATH variable, which is not used in the Plan 9 shell.)” That is the argument in one aside: PATH is a search index for executables implemented as a colon-separated string in a shell variable, living outside the namespace because the namespace could not express it. Plan 9 dissolved it back in.
Plan 9 went nowhere commercially. The idea did not.
chroot(2) | Plan 9 namespace (1992) | Linux mount namespace | |
|---|---|---|---|
| What it changes | The calling process’s root directory | The process’s entire view of every resource | The process’s mount table |
| Composition primitives | One pivot; no unions | bind/mount with union directories — the namespace is the search path | mount --bind, pivot_root, propagation modes; no union of binary directories |
| Network, devices, processes | Still global | Files: /net/tcp, /dev/cons, /proc | A separate namespace type per resource (CLONE_NEWNET, CLONE_NEWPID, …) |
| Intended as a security boundary | No — “never intended to be security mechanism as such,” per Kamp and Watson | No — a composition mechanism | Not alone; one ingredient in a sandbox |
| Where you meet it today | Build sandboxes, daemon privilege dropping | Nowhere in production, everywhere in ideas | Every container running anywhere |
Linux mount namespaces (CLONE_NEWNS, documented in mount_namespaces(7)) arrived in the early 2000s and made the mount table a per-process value, but the capability only got used seriously once container tooling made it convenient a decade later. The position today is that “the filesystem” is no longer a system-wide fact; it is a per-process view — the Plan 9 idea arriving thirty years late and without the coherence.
That missing coherence is why working inside a container still produces confusion around /proc, /sys and /dev: Plan 9 made every resource a namespaced file tree from the start, while Linux bolted on a separate namespace type per resource, at different times, with different semantics and escape hatches. The lineage deserves honesty too — calling Linux namespaces “inspired by Plan 9” without qualification overstates it. The goals differ, and chroot is the nearer ancestor of the mount namespace, right down to inheriting a mechanism its own maintainers say was never meant to be a security boundary.

What Transfers Out of a System That Refused to Build an Index

Your naming scheme is your query planner. If the hierarchy is the only maintained index, every question that does not match it costs a full scan. Decide which questions you are optimising for before you pick the tree.
Locate your crossover, and re-locate it annually. Scan-versus-index is arithmetic whose inputs change every year, not a philosophy. The team that answered correctly at founding is the one most likely to be wrong now.
Every index is a cache, and staleness is the contract. locate returns phantoms and misses newborns for up to a day, and says so nowhere in its output. That is a materialised view, a read replica, a search cluster. If the interface hides the staleness window, callers will assume there is none.
Structure precedes indexability. apropos works because man pages have a schema; --help never will, because it does not.
And the uncomfortable one underneath all of them: an index you did not design will appear anyway. Unix declined to ship one, so the ecosystem grew .gitignore and let a version-control artifact become the pruning index of the world’s fastest search tools. When a system refuses a capability users genuinely need, they do not stop needing it — they build a worse version outside your control, and then you support it forever.
❓ Frequently Asked Questions
Why doesn’t Unix have a built-in file database or tagging system?
Because it bet that the path would be the only key the system maintains, and at 1970s data volumes that was correct — building an index over a 1.5 MB RK05 disk pack cost more than reading it. The design is not an unfinished feature; it is a choice to keep the kernel’s search surface at “resolve this path” and push everything else into user-space tools that scan. The cost only became visible once corpora grew by six or seven orders of magnitude.
Is locate safe to rely on?
Only if you understand its staleness contract. updatedb walks the whole filesystem on a daily schedule and writes a name database, so locate is wrong in both directions between runs — blind to files created since the last walk, and still reporting files deleted since then. It is a cache, and it prints no “as of” timestamp with its results. plocate makes the same design faster with posting lists; it does not make it fresher.
Does .gitignore really count as an index?
Yes, in the sense that matters architecturally: it is a maintained metadata file consulted before the data, to avoid reading most of it. It is coarse, negative and hand-authored rather than derived, but the effect is identical — search speed that depends on external state a human keeps current. The practical consequence is that a match hidden by an over-broad ignore rule looks exactly like no match, and the tool exits successfully either way.
Is the Filesystem Hierarchy Standard enforced by anything?
Almost nothing. FHS 3.0 (18 March 2015, Linux Foundation) is a document; no kernel or syscall consults it, and macOS ignores it entirely while being certified UNIX. The one genuinely hard dependency is the dynamic linker path embedded in every dynamically linked ELF binary, which is enforced by the binary format rather than by policy. Everything else is held in place by hard-coded paths inside programs — simultaneously why the layout is not enforced and why it cannot be changed.
What is the difference between a Plan 9 namespace and a Linux mount namespace?
Plan 9 made the entire per-process view of every resource — files, network, devices, processes, graphics — one namespace assembled from bind and mount, with union directories that dissolved PATH into the namespace itself. Linux made the mount table per-process and then added separate namespace types for network, PIDs, users and the rest, at different times with different semantics. The result is the same capability without the unifying model, which is why /proc and /sys inside a container behave in ways that need explaining.
Why does apropos work when searching --help output doesn’t?
Because man pages have a schema and --help output does not. Numbered sections and fixed headings put the NAME line’s one-sentence description at a known position in every page on the system, so mandb can extract it mechanically. --help text has no required structure, so there is no field to index — the searchability gap is a formatting decision made in 1971, not a tooling gap.
📚 Further Reading
- What Is a Container? The Idea That Powers Modern Software (and AI) — the mount namespace in its production form, and the clearest place to watch “the filesystem is a per-process view” in practice.
- Postgres as a Vector Database: What Benchmarks Say — narrow-then-verify with an approximate-nearest-neighbour index as the candidate generator.
- How Reverse Image Search Works: From Pixels to Meaning — another two-phase retrieval pipeline: filter cheaply, verify exactly.
- From Indexing to Internal Thought: How Continuous Thought Machines May Reinvent Search Itself — where the index-versus-scan trade goes when the candidate generator stops being a data structure.
- The Best Books on Distributed Systems (Beginner to Expert) — the staleness-contract and materialised-view reading that the
locateargument generalises into.
📚 Recommended Resources
Disclosure: some links below are Amazon affiliate links. If you buy through them, I earn a small commission — at no extra cost to you — which helps keep this site running.
Start with the free primary sources. The normative definition of what a pathname resolves to, what find and grep are required to do, and what a directory actually guarantees lives in POSIX.1-2024 / Base Specifications Issue 8, free to read in full at pubs.opengroup.org. If you want to see how small the original namespace really was, the Unix Heritage Society hosts the V1–V7 sources at tuhs.org, free under the 24 January 2002 Caldera BSD-style licence — the First Edition manual dated 3 November 1971 is in the same archive, and reading a 1971 man page next to a modern one is the fastest way to see how little the schema has changed.
UNIX: A History and a Memoir
Brian Kernighan, 2019 · Book
The best single account of why the decisions in this article were made, from someone in the room. Kernighan is the primary source on McIlroy’s insistence that man pages exist at all — the decision that produced the one searchable database Unix shipped — and on the working culture that made “just scan it” a defensible default for a decade.
The Unix Programming Environment
Brian Kernighan & Rob Pike, 1983 · Book
The tools in it are dated; the thinking is not. This is where the composition model behind find … -exec, grep in a pipeline, and the shell as an ordinary program is taught properly rather than as flag trivia. Read it for the reasoning about interfaces, not for the command syntax — and note that one of its authors went on to co-write the Plan 9 namespace paper this article closes on. (The hardcover is a separate listing, ASIN 0139376992.)
The Linux Programming Interface
Michael Kerrisk, 2010 · Book
The reference for the syscall layer underneath everything here — stat(), directory traversal, mount(), chroot(), and the namespace machinery that turns “the filesystem” into a per-process value. Kerrisk also maintains the Linux man-pages project, so the book and the man7.org pages cited throughout this article share an author and a standard of precision.
The UNIX-HATERS Handbook
Simson Garfinkel, Daniel Weise & Steven Strassmann, 1994 · Book
The free PDF is the canonical edition — read that first. The print listing is a convenience, and be aware there is a 979-8828518296 reprint impostor circulating that is not this book. It is a polemic, and some of its complaints have been fixed in the thirty years since, but its central grievance is the subject of this article: a system whose only structural answer to “where is my stuff” is a tree you were expected to organise correctly on the first try. Take the technical complaints seriously even where the tone is doing the arguing.
If you want the theory underneath the “narrow, then verify” section rather than more Unix history, Operating Systems: Three Easy Pieces is free at ostep.org and covers filesystem structure and indexing properly — there is no verified Amazon listing for it, so there is no affiliate link here.