How does an inverted index work?

Question

IT Interview Practice · Accepted Answer

**An inverted index maps a term to the documents containing it.** This lets a search engine find candidate documents without reading every document from beginning to end for each search.

Think of the index at the back of a book: look up a word, then go to the listed pages. For a search engine, document identifiers take the place of page numbers.

## 1. Start with a small collection

Suppose we have three documents and use a simple analyzer that lowercases text and separates words. An analyzer is the set of steps that turns text into searchable terms.

```text
D1: Red apple
D2: Green apple
D3: Red car

apple -> D1, D2
car   -> D3
green -> D2
red   -> D1, D3
```

The original direction is document to words. The index reverses that direction to word to documents, which explains the name. Each term's list of matching documents is called a posting list.

## 2. Use those lists to answer a query

For a query requiring both red and apple, read the two posting lists and keep their intersection: D1 appears in both. For a query accepting either term, take their union: D1, D2 and D3 are candidates.

This example explains matching, not ranking. If several documents match, the engine can score them using information such as term frequency and how common a term is across the collection. Finding matches and deciding their order are related but separate steps.

## 3. Make indexing and searching agree

The query must be analyzed in a way compatible with the indexed terms. If indexing turns Red into red but the search looks for the literal term Red, the intended match can be missed.

The right analysis depends on the field. Product descriptions benefit from text analysis; an exact order identifier usually needs exact matching. Splitting an identifier into ordinary words can change its meaning. See Elastic's explanation of [full-text search](https://www.elastic.co/docs/solutions/search/full-text/how-full-text-works).

## 4. Store enough information for the question being asked

A document containing both red and apple does not necessarily contain the phrase red apple. To answer phrase queries, the index needs word positions so the engine can check order and adjacency.

- Document identifiers answer which documents contain the term.
- Frequencies can help describe how often the term occurs.
- Positions support questions about where terms occur relative to one another.

Storing more information supports richer queries but increases index size and indexing work. The useful index is determined by the searches the application must support.

## 5. Understand the cost of keeping it current

When source text changes, its search index must also be updated. Systems such as Elasticsearch manage indexed data in segments and merge them over time; an update does not mean every existing posting list is rewritten immediately in place. Search visibility also depends on the engine's refresh behavior.

Therefore, account for extra storage, indexing cost and possible delay between writing a document and finding it in search. An inverted index is especially useful for term-based text search; it is not a universal replacement for the indexes used for exact lookup, ranges or transactional access.

1. Start with a small collection

2. Use those lists to answer a query

3. Make indexing and searching agree

4. Store enough information for the question being asked

5. Understand the cost of keeping it current

Powiązane pytania