What is an inverted index and why is it faster than scanning documents?
An inverted index maps terms to the list of document IDs containing them. Instead of scanning every document for a query term (linear in corpus size), you look it up once in the index and get all matching documents instantly—O(log terms) to find the term, plus one disk seek to read the posting list.
Answered in
The Inverted IndexA sorted dictionary mapping terms to document IDs. Transform search from O(corpus size) to O(1) lookup, enabling full-text search at scale.
Read the full analysisOther questions this article answers
More system design questions
- Why doesn't Google just run Dijkstra faster?
- What is a shortcut edge and when is it precomputed?
- How much space do shortcut edges take compared to the original graph?
- Can Contraction Hierarchies handle dynamic graphs like traffic or road closure?
- Why contract low-degree nodes first instead of high-degree ones?
- What is a CRDT and why does it matter for real-time collaboration?
- How do CRDTs handle concurrent edits without a central server referee?
- Why did Figma move from operational transforms to CRDTs?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design beat.