Search & IR · core
Inverted Index
Term → posting list mapping that powers fast keyword lookup.
Mental model
An inverted index flips documents inside out: instead of doc → terms, you store term → list of docs (postings). Query answering becomes intersecting/merging sorted posting lists.
How to study Inverted Index
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Stanford IR Book — A first take at building an inverted index to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Inverted Index with BM25, TF-IDF, Search Systems. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Build an inverted index and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Lucene, Tantivy, PostgreSQL GIN indexes, every full-text search system.
Common mistakes
- Storing postings unsorted, making intersection O(n*m)
- Forgetting document frequency, which ranking later needs
- Not separating the dictionary from the postings on disk
Learn from primary sources
Practice and explain it back
Build an inverted index
From a list of documents, build a term → sorted posting list map. Support a boolean AND query by intersecting posting lists. Track document frequency per term.
Expected evidence: Query 'quick fox' returns docs containing both terms, found by list intersection.
Open the interactive drill →Review prompts
- How does an inverted index differ from a forward index, and why is it faster for search?
Build evidence
Implement BM25 search in HighSignal
Index a corpus of articles and serve ranked keyword search using BM25.
- Index at least 100 documents
- Support keyword search with a tokenizer shared by index and query
- Return top-k ranked results scored by BM25
- Add a small set of eval queries with expected results
Object-storage-backed index
Store index segments in object storage with a hot in-memory cache.
- Index segments persisted as immutable objects
- A cache in front of object storage
- Cold-read latency measured and noted