How it works
Turn documents into searchable terms using an analyzer. For example, document 12 contains “Red running shoes” and document 27 contains “Red hiking shoes.” After lowercasing and tokenization, the index includes red → [12, 27], running → [12], hiking → [27], and shoes → [12, 27]. Apply compatible analysis to queries so their terms match the indexed terms.
Each term points to a posting list, usually ordered by document ID. A posting can include term frequency and word positions, not just the document ID. Positions let the engine distinguish the phrase “running shoes” from a document that contains those words far apart. Field-specific postings distinguish matches in a title from matches in the body.
Combine posting lists according to query semantics. For “red AND hiking,” intersect the lists to get document 27; for “running OR hiking,” take their union. Starting with the shortest list often reduces intersection work. Sorted lists, compressed document-ID gaps, and skip data help avoid reading and comparing every posting.
Rank matching documents and return a bounded set of results. A scorer such as BM25 uses signals including term frequency, term rarity, and document length; business rules may add recency or quality. Optimized top-k retrieval can skip candidates that cannot beat the current results rather than fully scoring every match. Fetch display content from stored fields or the document store.
In a common segment-based implementation, new documents enter an in-memory buffer that is periodically published as searchable segments. Updates typically add a new document version and mark the old one deleted; background merges consolidate segments and reclaim space. A durable change stream can feed this pipeline, with document versions preventing delayed events from overwriting newer state.
At scale, commonly partition by document ID so each shard owns an inverted index for its documents. A coordinator sends the query to relevant shards and merges their ranked candidates. Filters can narrow retrieval, but stale indexed permissions are not authoritative: enforce current visibility before returning content, and fetch more candidates when filtering leaves too few results.
A worked example
Searching a large post collection
Suppose a service has 100 million posts across 20 document shards. A user searches for “solar battery” with AND semantics. On one shard, “solar” appears in 80,000 posts and “battery” in 200,000. The engine intersects their sorted posting lists, using skips where possible, rather than scanning all 5 million posts on that shard. Each shard returns its top 50 candidates, giving the coordinator at most 1,000 candidates to merge. Before returning 20 results, the service verifies current visibility and requests more candidates if necessary. A two-second refresh target means a successful post write need not be searchable immediately.
Trade-offs to say out loud
- Fast retrieval, extra storage
- Posting lists avoid full-document scans, but terms, frequencies, positions, and stored fields can consume substantial space even with compression.
- Freshness versus indexing efficiency
- Frequent refreshes expose writes sooner but create more small segments and increase search and merge overhead.
- Richer matching versus index size
- Positions, additional analyzed fields, and n-grams enable more query features but increase storage and write work.
- Common terms remain expensive
- A very frequent term can have a huge posting list, so bounded top-k retrieval, selective filters, and query limits still matter.
- Distributed capacity versus coordination
- Document sharding spreads indexing and search work but adds query fan-out, slow-shard sensitivity, and cross-shard ranking considerations.
- Derived search state versus correctness
- Asynchronous indexing improves write isolation, but stale content, deletes, and permissions require explicit freshness and enforcement policies.
When to reach for it
- Users need keyword search across a large collection of posts, documents, reviews, or listings.
- Queries combine multiple terms, phrases, or field-specific matches rather than looking up one exact key.
- The product needs relevance-ranked results instead of only exact matches or ordered range scans.
- Search combines text with categorical filters such as brand, category, or status, which can also use posting lists or bitmaps.
How to bring it up in the interview
- Start with query semantics: AND versus OR, phrases, searchable fields, language handling, ranking, and acceptable indexing delay. These determine what each posting must store.
- Draw a tiny term-to-document example and walk through an intersection. Interviewers often probe why a B-tree on the original text does not solve arbitrary word search.
- Separate the source of truth from the search index. Explain how committed changes reach indexing workers, how replay is made safe, and how deletes and out-of-order updates are handled.
- State the sharding choice explicitly. Document partitioning usually means query fan-out; term partitioning instead distributes posting lists and can require cross-machine intersections while concentrating popular-term traffic.
- Defend latency and correctness separately: discuss common-term queries, bounded candidate retrieval, slow shards, current authorization checks, and stable pagination using a search snapshot or equivalent mechanism.
Common mistakes
- Describing the index as document → words, which is the forward direction rather than term → documents.
- Claiming every indexed query is constant time, ignoring posting-list length, ranking work, filters, and shard fan-out.
- Assuming a set of document IDs supports phrase search without storing positions or verifying the original text.
- Treating an asynchronously updated index as authoritative for current permissions, deletion state, or inventory availability.
- Listing a search engine product without explaining tokenization, posting-list operations, update propagation, and retrieval costs.
Where it comes up
Interview questions where inverted index is part of a strong answer, and why.
- Design Facebook post searchAn inverted index is the core structure for distributed keyword retrieval, with freshness, ranking, and permission-correct results shaping its design.
- Design a restaurant review app like YelpRanked restaurant search combines text or category posting lists with geographic constraints while review and restaurant updates propagate into the index.
- Design Facebook MarketplaceListing discovery uses searchable terms and attribute posting lists alongside geographic filtering, while authoritative listing state can differ from stale index entries.
Questions people ask
What is an inverted index in a search engine?
It is a mapping from searchable terms to the documents containing those terms. The search engine combines these posting lists to find candidates, then ranks and filters the candidates to produce results.
How is an inverted index different from a B-tree index?
A B-tree organizes indexed keys in sorted order, making equality and range lookups efficient. An inverted index records a document's membership under many searchable terms, which supports word-based retrieval and term combinations. A search engine can still use a tree or another lookup structure for its term dictionary.
How are updates and deletions handled in an inverted index?
Many search engines write new document versions into new segments and mark older versions deleted rather than rewriting every affected posting list immediately. Refreshes make changes searchable, while merges later reclaim obsolete data. Version checks and retained delete markers prevent delayed indexing events from restoring old content.