What we're building: a search engine

Step 1 of 12, and it runs nothing. This is the map: what haystack does when the track is finished, then the eleven steps between here and there. Read it once so every later article has a place to land. Each one assumes the state the previous step left behind and adds a piece to it.

A search engine is a good thing to build in Rust. Every part of it is checkable: a ranker either puts the right document near the top or it doesn’t, and you can see which with your own eyes on your own documents. The data structures are the ones that show up in every serious codebase, and the maths is short enough to implement from the paper. Nothing needs a network, either. Eight of the twelve articles use only the standard library; the two that pull in a crate (an HTTP framework at step 9, a benchmark harness at step 11) still run entirely on your own machine, against your own documents.

The finished engine

haystack indexes a folder of text files and answers questions about them. One file is one document, and its path is its id. By step 12 the command line looks like this:

haystack index ./docs --out docs.idx
haystack query --index docs.idx "borrow checker" --limit 5
haystack serve --index docs.idx --port 7878

index walks the folder, reads each file, splits the text into terms, and writes a single index file. query loads that file, ranks every document that matches, and prints the best ones with their scores. serve loads the same index and answers GET /search?q=... with JSON: the same ranking, over the wire, so a browser or another program can use it.

The one idea: invert the index

Everything in the track falls out of one move. Searching a folder of documents the obvious way means reading them. Inverting the index means keeping, for each term, the list of documents that contain it, so a search looks the term up instead of scanning. That list is a postings list, and the map from term to postings list is the engine.

The payoff is that a query costs a map lookup plus the work of merging a few lists, not a pass over every document. What goes into each posting decides what the engine can do, and each step of the track adds a field:

• Term frequency. How often the term appears in that document. A document that mentions “borrow” five times is more about borrowing than one that mentions it once. Steps 5 and 6 turn that intuition into a score, and then fix its excesses.
• Document length. Needed to stop long documents from winning by default. Step 5 shows that failure first, because the length bias in TF-IDF is the thing BM25 exists to fix, and seeing it fail makes BM25’s two constants make sense.
• Positions. Where in the document each term appeared. With positions, “borrow checker” as a phrase is a different question from “borrow” and “checker” anywhere in the text, which is exactly what step 7 needs.
• The dictionary itself. The set of terms the index knows. A typo in a query misses because the dictionary has no such key, so step 8 searches the dictionary by edit distance instead of demanding an exact match.

Two earlier steps decide what the keys are. Step 3 lowercases, drops stop words, and stems, so “Running” and “runs” land on the same term as “run”. That part of a search engine gets skipped in most tutorials, and it moves results more than any ranking tweak.

The three parts

The index. Steps 2–4 build it in memory, tokenise the text properly, then write it to disk in a format that loads back. Step 2 is a hash map and a few hundred lines. Step 4 is a binary file holding the dictionary and the postings lists, written and read by hand, with no serialisation crate.

The ranker. Steps 5–8. TF-IDF first, because its length bias is instructive. Then BM25, the ranking function Elasticsearch and Lucene use, with the two constants (k1 and b) at the values Lucene ships: 1.2 and 0.75. Then phrase and boolean queries over positions, and typo tolerance over the dictionary.

The API and the evidence. Steps 9–11. The same index served over HTTP as JSON, with readers seeing a consistent snapshot while documents are added. Incremental indexing, so adding a document doesn’t mean rebuilding everything before it. And a benchmark against a real document set with known correct answers, because a ranking you can’t measure is a ranking you can’t defend. Step 12 closes the track by naming what Lucene does that this doesn’t.

The route

#	Article	What lands
2	An in-memory inverted index	from term to document ids
3	Tokenising and normalising text	casing, stemming, and stop words
4	Persisting the index to disk	a format you can load back
5	What TF-IDF actually measures	and the document length bias it hides
6	Ranking with BM25	the two constants, and what they do
7	Phrase and boolean queries	positions in the index, AND/OR/NOT
8	Fuzzy matching and typo tolerance	edit distance on the term dictionary
9	An HTTP query API	serving results as JSON
10	Incremental indexing	adding documents without a full rebuild
11	Benchmarking against a real corpus	latency, recall, and honest comparison
12	What Lucene does that we didn’t	segments, compression, ranking models

Steps 2–4 are the data structure, 5–8 the maths and the query language, 9–11 the service and the evidence, and 12 the honest comparison. Each step ends somewhere the next one picks up from: an index that compiles, ranks a little better than the last one, and answers a slightly richer question.

What this engine is not

• Not distributed. One process, one index file, one machine. There is no cluster to join and no protocol to speak beyond step 9’s HTTP endpoint.
• Not a full Porter stemmer. Step 3 implements a small rule set, enough that “running” and “runs” meet “run”, and says where the full algorithm lives. A production stemmer is a table of exceptions as much as a set of rules.
• Not safe for two writers. Step 10 adds documents without rebuilding what came before, and readers see a consistent snapshot while it happens, but the writer is single-threaded. Two processes writing one index at the same time is a real design problem, and it is out of scope here.
• Not a Chinese or Japanese tokeniser. Case folding is Unicode-aware, but splitting text that has no spaces needs a dictionary this track doesn’t build, and faking it produces garbage matches.

What you need first

• Rust, installed and current. Every step is written and verified against rustc 1.99.0 with edition 2024, the compiler and edition the rest of this site uses. rustup.rs installs it or brings an old install up to date.
• Ownership basics. Strings move into the index and are borrowed back out of it. The first chapters of Ownership and borrowing are enough.
• Result and ?. Reading a folder of files goes wrong in more ways than a tutorial usually admits. Error handling covers the pattern the track uses.
• Hash maps and iterators, casually. The index is a map of maps, and most of the code is one iterator chain after another. Collections and Closures and iterators have what’s needed.

No search experience, and no maths beyond arithmetic. BM25 is a formula with two constants in it, and step 6 derives it from the failure step 5 demonstrates.

Where the code lives

Steps that change the project commit the result to search-engine/ in the examples repository and tag it: search-ch02 after the index step, search-ch03 after tokenising, and so on. If your build misbehaves partway through, checking out that tag in your clone puts your tree exactly where the article left it. This article commits nothing; the first tag lands with article 2.

Next

Step 2 starts the project for real: cargo new haystack, the postings list, and the first query answered from the index instead of from a scan. From that article on, every step ends with something you can run. The track overview keeps the full list current as articles land.