Day 2:Week 11, Day 2: Coding an Inverted Index & `Okapi BM25` Search Engine from Scratch
Battle-tested daily lesson note • 100% runnable code, interview Q&A, test suite & interactive quiz
Week 11, Day 2: Coding an Inverted Index & Okapi BM25 Search Engine from Scratch
1. How an Inverted Index Works Under the Hood
How does Elasticsearch or Lucene score 10,000,000 documents with BM25 in 2 ms without scanning all 10,000,000 documents?
It builds an Inverted Index (Posting Lists):
Forward Index (Doc -> Words):
Doc 0: ["payments", "error", "err_502"]
Doc 1: ["database", "failover", "pg_ctl"]
Doc 2: ["payments", "rollback", "kubectl"]
Inverted Index (Word -> Posting List of (doc_id, term_freq)):
"payments" ──► [(Doc 0, tf=1), (Doc 2, tf=1)]
"err_502" ──► [(Doc 0, tf=1)]
"pg_ctl" ──► [(Doc 1, tf=1)]
At query time, if the user searches "err_502", the engine looks up "err_502" in hash time and only scores the documents in its posting list ([Doc 0])!
2. Code-Aware Tokenization for Technical RAG
Standard NLP tokenizers strip underscores and numbers, turning "ERR_PG_9021" into "err" and "pg".
In technical/SRE RAG, our tokenizer must preserve alphanumeric identifiers, underscores, hyphens, and error codes (re.findall(r"[a-z0-9_/-]+", text.lower())).
In Simple English: How an Inverted Index Works Like a Textbook Back-of-Book Index
Instead of scanning every document word-by-word when someone searches "redis flushdb":
An Inverted Index builds a dictionary flipped backwards ahead of time:
"redis" -> [Doc 2, Doc 9, Doc 14]"flushdb" -> [Doc 2]Instant intersection findsDoc 2in microseconds! Check Tab 2 (Codes) to read and run our pure-Python Inverted Index + BM25 scorer directly inside your browser!