Search Engine Internals

A traditional database stores data as (row_id → fields). Searching for all rows containing the word "database" requires scanning every row. For 10 million documents, that scan takes seconds.

An inverted index flips this: it maps (term → list of document IDs containing that term). The posting list for "database" contains [doc_3, doc_7, doc_91, doc_204, ...]: all documents where "database" appears. Finding documents containing "database" becomes a hash table lookup on the term dictionary, returning the pre-computed posting list. The lookup is O(1) in the dictionary plus the size of the posting list.

Before indexing, documents go through an analyzer pipeline: tokenization (split "PostgreSQL connection pooling" into ["postgresql", "connection", "pooling"]), normalization (lowercase), stemming (optional, "running" → "run"), and stop word removal (remove "the", "a", "is"). The indexed tokens are the processed outputnot the raw text. A query using the same analyzer produces the same tokens, enabling consistent matching.

Multi-term queries combine posting lists. "PostgreSQL connection" intersects the posting lists for "postgresql" and "connection": the intersection gives documents containing both terms. This set operation is fast because posting lists are sorted by document ID, enabling merge-sort intersection in O(N+M).

Key Takeaways

• →Inverted index: term → posting list. Term lookup is O(1); posting list merge is O(N+M)
• →Analyzer pipeline normalizes text at index and query time: must use the same analyzer for both
• →Multi-term queries intersect sorted posting lists: why Elasticsearch handles boolean queries efficiently