The Inverted Index

In one line: this is the single data structure that makes search possible. Everything else in the chapter is about distributing it — but if you cannot explain what it holds and why, none of that matters.

Starting with the obvious structure

A basic approach assigns a unique ID to each document and stores the text in a database table — a forward index. First column document ID, second column text:

In production, documents are significantly larger than single sentences. Storing full text in a table creates a massive dataset. Searching this document-level index is slow because the system must scan every document to count occurrences of the search string.

Search query response time depends on:

• Data organization strategy
• Data volume
• Hardware resources (processing speed and RAM)

The forward index is O(corpus) per query — which violates the requirement outright

A forward index answers "what is in document 7?" in one lookup. But search asks the opposite question: "which documents contain 'analytics'?" — and the forward index has no answer except read everything.

That makes every query linear in the corpus, directly violating Lesson 2's "low latency regardless of data volume." It is the shelf-of-a-million-books problem, and no amount of hardware fixes an asymptotic mismatch.

The fix is not a faster scan. It is inverting the mapping so the question you actually ask becomes the key you actually look up.

Fuzzy search makes the forward index even worse

A fuzzy search adds complexity. The system must identify unique candidate strings across all documents, determine approximate matches, and locate them, significantly increasing latency.

Exact matching over a forward index is one pass. Approximate matching means comparing the query against every distinct term in every document with an edit-distance calculation — the cost multiplies by the vocabulary size.

This is worth knowing because it explains a real property of search systems: typo tolerance is expensive, and it is implemented against the index's term dictionary (a bounded set of unique terms) rather than against documents. Inverting the index does not just speed up exact match; it makes fuzzy match tractable at all.

The inverted index

It parses documents into individual words, creating a document-term matrix. It identifies unique words and discards frequent stop words — "the", "is" — to create a compact term-level index.

For each term, the index stores:

• A list of documents containing the term.
• The frequency of the term in each document.
• The position of the term in each document.

The three lists per term are: documents where the term appears, frequency of the term in each document, and a two-dimensional list pinpointing the term's position in each document (handling multiple occurrences).

Note: mappings can also use tuples, such as (doc, freq, loc).

Check a row against the documents — this is how you verify you understand it

Take distributed → ([1, 3], [1, 1], [[4], [4]]) and count words:

Doc 1: Elasticsearch(1) is(2) the(3) distributed(4) RESTful(5) search(6) and(7)
       analytics(8) engine(9) at(10) the(11) heart(12) of(13) the(14)
       Elastic(15) Stack(16)

Doc 3: Elasticsearch(1) is(2) a(3) distributed(4) search(5) and(6)
       analytics(7) engine(8) built(9) on(10) Apache(11) Lucene(12)

distributed is at position 4 in both — matching [[4], [4]]. It appears once in each — matching [1, 1]. And it is absent from doc 2, which is why doc 2 is missing from the list.

Do this once with a real row and the structure stops being abstract. It is also the fastest way to check an index in an interview: pick a term and count.

Position data is what makes phrase search possible — and it's why the index is large

The document list alone answers "which documents contain both 'search' and 'engine'?" — that is boolean retrieval and it is cheap.

Positions answer a strictly harder question: "which documents contain the phrase search engine, in that order, adjacently?" You get that by intersecting the document lists, then checking whether any position of engine equals a position of search plus one.

Check it against doc 2: search at 4, engine at 5 — adjacent, so doc 2 contains the phrase. In doc 1, search is at 6 and engine at 9 — matching terms, but not the phrase.

That capability is not free. Positions dominate index size for common terms: a document list entry costs one integer per document, while positions cost one integer per occurrence. It is the single biggest lever on Lesson 2's 50% index overhead, and search engines make it configurable for exactly that reason.

Frequency exists for the third purpose — ranking. Lesson 8's merger sorts results on it, and it is the raw input to TF-IDF-style scoring.

The name is confusing and the idea is simple: build the index around the question you ask, not around the shape of the data. Nobody searches by document id, so an index keyed by document is the wrong way round.

Stop words

Frequent stop words are discarded — "the", "is" — to create a compact index.

Removing stop words is a real trade, not a free optimization

"If stop words are removed to shrink the index, what design trade-off does that reveal about search behaviour?"

Stop words are the most frequent terms, so their posting lists are the longest — often appearing in nearly every document. Dropping them removes a disproportionate share of index size for terms that carry almost no discriminating power. A query for "the" matching 99% of documents tells you nothing.

The trade is that you can no longer search for them, and sometimes they matter:

• Phrases where stop words are the content. "To be or not to be" is entirely stop words. "The Who", "Take That", "Let It Be" — all lost.
• Phrases where they change the meaning. "flights to London" versus "flights from London".
• Code and identifiers, where short common tokens are significant.

The deeper lesson: stop-word removal encodes an assumption that frequency implies unimportance. That is usually true and occasionally badly wrong. Modern engines therefore tend to keep stop words and handle their cost with compression and skip lists instead — storage got cheaper faster than the assumption got safer.

Advantages and disadvantages

The inverted index is the standard for document retrieval. It enables boolean, extended boolean, proximity, and relevance searches.

The maintenance cost is why indexing is offline and batched

"Adding, updating, or deleting documents requires processing terms and updating the index structure" sounds mild. It is not.

Adding one document means touching the posting list of every term it contains — a thousand terms per document, per Lesson 2's assumption. Deleting is worse: you must find and remove that document from a thousand scattered lists.

Which is why real systems do not update indexes in place. They build immutable index segments in batches and merge them periodically, treating deletion as a tombstone rather than a removal. That is exactly the write-once-read-many pattern object storage described, and it is why Lesson 2 chose a blob store to hold index files.

Fast reads were bought with expensive writes — and the design's response is to move all the writing offline.

Interview signal by level

Next: querying it, and what makes an index design good.