Building a search engine from first principles.
Every structure in this book is implemented here, in TypeScript, running in your browser — an inverted index over 28 real documents, BM25 with the arithmetic shown, Levenshtein automata, minimized automata, FSTs with outputs, BKD trees, a byte-level segment format with real checksums, and a cluster you can break.
Nothing on this site is a recorded screenshot. Every number is computed when you load the page, by the same engine the chapter is describing.
The two jobs
A search engine builds structures that make retrieval fast, then uses those structures to find and rank documents. Everything in the book sits on one side of that line or the other.
There is not one search data structure
This table is the spine of the whole book. Different questions need different structures, and confusing them is where most search bugs come from.
| Question | Structure | Chapter |
|---|---|---|
| Does this term exist? | Term dictionary | 19 |
| Which documents contain this term? | Postings | 4 |
| Where does the term occur? | Positions | 5 |
| What terms start with this prefix? | Trie / FST / term dictionary | 16 |
| Which terms are within edit distance 1? | Levenshtein automaton + dictionary | 14 |
| Which prices are between 100 and 200? | Point index | 20 |
| Which geo points are inside a region? | BKD | 22 |
| Which matching documents are most relevant? | BM25 | 8 |
| How is the index persisted? | Segments / files | 23 |
| How is it distributed? | Shards / replicas | 31 |
FST is not postings. BKD is not a text dictionary. BM25 does not find documents; it scores candidates.
Thirteen parts, forty-three chapters
Foundations
What a search engine is actually doing, and what a document turns into before anything can find it.
The First Search Engine
A hash map, a set of document ids, and suddenly you no longer scan every document.
Relevance
Retrieval says which documents match. Ranking says which ones are worth showing.
Query Language
Field types and query types are different things, and confusing them is the most common search bug there is.
Fuzzy Search
From a dynamic-programming table you can read, to an automaton that never builds one.
Term Dictionaries
Prefix sharing, then suffix sharing, then outputs. Each step is a measurable size reduction.
Numeric & Spatial Search
Sorting solves one dimension. Two dimensions need you to partition space itself.
Storage Engine
Immutable segments, a real byte format, compression that you can decode by hand, and the page cache.
Production Query Engine
Planning, caching, concurrency and scripts — the difference between working and working under load.
Distributed Search
One index becomes many, and coordination becomes the hard part.
Cluster & Operations
Refresh, flush and commit are three different promises. Failure is part of the architecture.
Production Engineering
Optimise in order, size from the workload, and measure the percentiles users actually feel.
The Seeker Project
The build order, the testing strategy, and the map back to Lucene and OpenSearch.
The build order
Fifteen stages, each replacing exactly one component. Do not skip an intermediate structure merely because you already know the name of the final one — experience the problem first.
| Stage | Build | Replace later with | Chapter |
|---|---|---|---|
| 1 | documents + tokenizer | real analyzer | 3 |
| 2 | term → set(docID) | compressed postings | 25 |
| 3 | positions | position codecs | 5 |
| 4 | AND/OR/phrase | iterator execution | 6 |
| 5 | toy score | BM25 | 8 |
| 6 | sorted terms | trie | 16 |
| 7 | trie | minimized automaton | 17 |
| 8 | automaton + outputs | FST | 18 |
| 9 | term blocks | BlockTree-style dictionary | 19 |
| 10 | sorted numeric values | BKD | 22 |
| 11 | simple files | versioned segment codec | 24 |
| 12 | file reads | mmap reader | 26 |
| 13 | single node | shards | 31 |
| 14 | shards | replicas / recovery | 36 |
| 15 | basic metrics | production observability | 40 |