Inverted index

A relational database can find rows where a column equals a value. It cannot easily find documents that contain several words and rank them. An inverted index answers that question. For each word, it stores a postings list: the sorted IDs of the documents that contain the word, often with counts and positions.

A book's index works the same way. It maps a term to page numbers. The inverted index does that for documents.

The big idea

Flip the question. Instead of "what words does document 2 contain?", store "which documents contain this word?" A query then becomes lookups and list operations.

The picture breaks in one place. A book's index is written once. Documents arrive all the time, so the index has to absorb updates. Search engines handle that with immutable segments and merges, covered in the indexing pipeline page.

Walking through it

Three documents, lowercased and split on spaces:

d1: "Fast Postgres replication"
d2: "Postgres indexing for fast queries"
d3: "Replication in Cassandra"

Postings:
  cassandra   → [d3]
  fast        → [d1, d2]
  postgres    → [d1, d2]
  replication → [d1, d3]

The runnable version below builds the same index and runs two queries:

from collections import defaultdict

docs = {
    "d1": "Fast Postgres replication",
    "d2": "Postgres indexing for fast queries",
    "d3": "Replication in Cassandra",
}

index = defaultdict(set)
for doc_id, text in docs.items():
    for term in text.lower().split():
        index[term].add(doc_id)

def search(query):
    postings = [index[t] for t in query.lower().split()]
    return sorted(set.intersection(*postings))

print(search("postgres replication"))
print(search("fast"))

Output:

['d1']
['d1', 'd2']

For postgres replication, the engine reads two postings lists, [d1, d2] and [d1, d3], and intersects them to get [d1]. An OR query unions the lists instead, and scoring then ranks the documents that match more terms higher.

Postings are sorted by document ID, so two lists can be merged in one pass. Skip pointers let the engine jump over long runs. Lucene also compresses the IDs with delta encoding, so a list of millions of IDs stays small.

Common mistakes

• Assuming the index holds the raw text. It holds analyzed terms. Queries must go through the same analysis, which text analysis explains.
• Forgetting AND versus OR. AND intersects lists and returns fewer results. OR unions them, and many engines use it by default.
• Assuming huge postings lists are free. Merging long lists still costs time, which is why skip pointers and compression exist.

Check yourself

1. Using the index above, what do fast replication return with AND, and with OR?

Answer: With AND, fast [d1, d2] intersected with replication [d1, d3] gives [d1]. With OR, the union is [d1, d2, d3], ranked by score.

2. Why are postings lists sorted by document ID?

Answer: Sorted lists can be intersected or merged in one pass, instead of comparing every pair of IDs.

Key takeaways

• Map each analyzed term to a sorted postings list of document IDs.
• AND intersects postings lists. OR unions them and then ranks the results.
• Sorted, compressed lists keep merges fast and memory small.
• Queries must be analyzed the same way as the documents.

Further learning

Arpit Bhayani builds the inverted index from first principles, a good warm-up before reading Lucene or Elasticsearch internals.

Next, see how words are normalized before they enter the index in text analysis.