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 you are about to see was computed when this page loaded, by the same engine the chapters describe.
Build fast structures. Then use them.
A search engine builds structures that make retrieval fast, then uses those structures to find and rank documents. Click any stage to jump to its chapter — hover to see what it does.
How a search engine actually works under the hood
Live animated step-throughs of core algorithms and structures. Watch how raw unstructured text is parsed, how postings lists intersect, how automata prune tries, and how range queries work.
Source document text arrives with mixed case, punctuation, and delimiters
Text to Terms: Step-by-step tokenization, delimiter expansion, case folding, and stemming before tokens reach inverted index postings.
"kubernetes" AND "deployment"Iterators step in docId lockstep. Both posting lists must contain the doc for an AND match.
DocId Lockstep & Scoring: Multi-term AND queries advance iterators across sorted posting lists and calculate live BM25 saturation scores.
fuzzy("kubernets")Shared trie prefixes allow the automaton to eliminate thousands of non-matching terms in one step.
Fuzzy Search Without Scanning: The Levenshtein DFA walks the trie and prunes entire subtrees the moment edit distance exceeds the max threshold (d > 2).
price: [100 TO 200]Numeric ranges don't scan text. Sorted point leaves isolate matching documents in O(log N) time.
Fast Numeric Retrieval: Numbers and dates use 1D/2D spatial trees instead of text terms, isolating target doc ranges in O(log N) time.
There is not one search data structure
Different questions need different structures. This is the spine of the whole book.
FST is not postings. BKD is not a text dictionary. BM25 does not find documents; it scores candidates.
Thirteen parts, forty-three chapters
Foundations
3 chaptersWhat a search engine is actually doing, and what a document turns into before anything can find it.
The First Search Engine
3 chaptersA hash map, a set of document ids, and suddenly you no longer scan every document.
Relevance
3 chaptersRetrieval says which documents match. Ranking says which ones are worth showing.
Query Language
3 chaptersField types and query types are different things, and confusing them is the most common search bug there is.
Fuzzy Search
3 chaptersFrom a dynamic-programming table you can read, to an automaton that never builds one.
Term Dictionaries
4 chaptersPrefix sharing, then suffix sharing, then outputs. Each step is a measurable size reduction.
Numeric & Spatial Search
3 chaptersSorting solves one dimension. Two dimensions need you to partition space itself.
Storage Engine
4 chaptersImmutable segments, a real byte format, compression that you can decode by hand, and the page cache.
Production Query Engine
4 chaptersPlanning, caching, concurrency and scripts — the difference between working and working under load.
Distributed Search
4 chaptersOne index becomes many, and coordination becomes the hard part.
Cluster & Operations
3 chaptersRefresh, flush and commit are three different promises. Failure is part of the architecture.
Production Engineering
3 chaptersOptimise in order, size from the workload, and measure the percentiles users actually feel.
The Kaus Project
3 chaptersThe build order, the testing strategy, and the map back to Lucene and OpenSearch.
Fifteen stages, one replacement each
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 |