Tiny search engine
On the roadmap:Staff Engineer · step 1: Search and relevance
An inverted index with tokenising and BM25 ranking: the core of a search engine in about fifty lines.
In plain words
A table that maps each word to the documents that contain it, plus a scoring rule that puts the best-matching documents first.
Why it matters
Scanning every document for every search is too slow. Looking words up in an index is fast, and BM25 gives sensible rankings by weighing rare words and document length.
Where you meet it
- Lucene, Elasticsearch, OpenSearch and Solr
- Site search and log search
- The first stage of many recommendation systems
You will be able to
- Build an inverted index
- Rank with BM25 and pick the top k
- Explain why index size and speed change with the number of terms
In interviews
Core of 'design a search engine' and 'autocomplete' questions.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- A tokenizer that lowercases and splits on non-alphanumerics
- Postings: for each term, which documents contain it and how often
- Per-document lengths and the average length
- BM25 scoring and top-k selection
export const tokenize = (s: string): string[] => s.toLowerCase().match(/[a-z0-9]+/g) ?? [];
export class SearchIndex {
private lengths = new Map<number, number>();
private postings = new Map<string, Map<number, number>>(); // term -> doc -> count
private totalLength = 0;
constructor(private k1 = 1.2, private b = 0.75) {}
add(id: number, text: string): void {
const tokens = tokenize(text);
this.lengths.set(id, tokens.length);
this.totalLength += tokens.length;
for (const t of tokens) {
const docs = this.postings.get(t) ?? new Map<number, number>();
docs.set(id, (docs.get(id) ?? 0) + 1);
this.postings.set(t, docs);
}
}
search(query: string, k = 10): { id: number; score: number }[] {
const N = this.lengths.size, avg = this.totalLength / N;
const scores = new Map<number, number>();
for (const term of new Set(tokenize(query))) {
const docs = this.postings.get(term);
if (!docs) continue;
const idf = Math.log(1 + (N - docs.size + 0.5) / (docs.size + 0.5));
for (const [id, f] of docs) {
const norm = f + this.k1 * (1 - this.b + (this.b * this.lengths.get(id)!) / avg);
scores.set(id, (scores.get(id) ?? 0) + (idf * f * (this.k1 + 1)) / norm);
}
}
return [...scores].map(([id, score]) => ({ id, score })).sort((x, y) => y.score - x.score).slice(0, k);
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints tiny-search-engine ok when everything passes. You need Node.js installed.
mkdir tiny-search-engine && cd tiny-search-engine
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Real engines such as Lucene (inside Elasticsearch, OpenSearch and Solr) run text through analyzers first: stemming, stop words, accents, synonyms.
- Postings lists are compressed and carry skip pointers. The index is built as small immutable segments that are merged in the background.
- Big indexes are split into shards across machines, replicated, and queried in parallel with the results merged.
Ways to search
| How it works | Speed as data grows | Ranking | Pick it when | |
|---|---|---|---|---|
| Inverted index with BM25 (this lab) | Maps each word to the documents containing it | Fast | Yes, by relevance | You need text search you control |
| Scan every document | Read all the text for each query | Slows down quickly | None | The data is tiny |
| Database LIKE '%word%' | A pattern scan of the table | Slows down quickly | None | Small tables |
| Database full-text search | A built-in inverted index | Fast | Yes | Moderate data inside your database |
| Search engine (Lucene, Elasticsearch) | Sharded inverted indexes with analyzers | Fast at large scale | Yes, tunable | Large search workloads |
| Vector search | Compares meaning using embeddings | Fast with an index | By similarity | You want results by meaning, often together with BM25 |
What it cannot do
Only exact words match
'cache' and 'caching' are different terms without stemming.
No phrases or synonyms
It cannot tell 'hash ring' from 'ring hash', or know that 'car' means 'automobile'.
The index must be kept up to date
Every new or changed document has to be added or the results go stale.
It all lives in memory here
Real engines store compressed postings on disk and split the index across machines.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add phrase queries using positions in the postings
- Add field weights (title versus body)
- Shard the index and merge the shard results