Module 15 · Lesson 2 of 15Free

Inverted indexes: mapping words to documents

Level

Intermediate

Topic

Search: indexing, ranking and retrieval

Reading time

19 min

Maya searches for “red shoes” on Kartly. Its catalog has 20 million products, but the first implementation reads every title before returning anything.

An index on product ID cannot answer “which titles contain shoes?” How can search find matching products without reading every title?

Store the question’s missing direction

A product record maps an ID to its title. Search asks the reverse question: given a word, which IDs contain it?

Start with this small slice of Kartly’s catalog. Throughout this lesson, a document means one product’s searchable record.

An inverted index maps each searchable term to matching documents. A term is the representation actually stored after processing the text.

For now, lowercase each word:

The term-to-list lookup structure is the dictionary. Each document entry is a posting; the entries for one term form its postings list. PostgreSQL’s GIN text-search index uses this word-to-matching-locations structure. ^{312.9. Preferred Index Types for Text SearchPostgreSQL Global Development Group, PostgreSQL 18 Documentation}

We have not copied the catalog into a different order. We have built an additional access path, like the access paths introduced in Indexes.

That extra structure saves reads, but every catalog change now creates maintenance work.

Pay once, then reuse the work

The simplest implementation scans every title on every query. It needs no derived data and immediately sees changes in the source records.

Its limitation is repeated work. A customer searching for “shoes” makes the server rediscover the same matches that another customer just requested.

Keep document identity separate

Use numeric document IDs inside this lesson’s index. Keep a separate mapping to Kartly’s public product IDs.

The index can then return compact identifiers without repeating long public identifiers in every term list. The mapping must belong to the same published index version; otherwise ID 11 could resolve to the wrong product.

Keep postings sorted by numeric document ID in this implementation. The next lesson, Boolean retrieval and tiered indexes, uses that order to combine lists.

Sorted IDs do not mean relevant results come first. We have built a way to find matches, not a ranking.

Matching starts before the dictionary

Suppose the title contains “Shoes”, but the query contains “shoes”. Literal dictionary lookup finds different strings unless both sides apply compatible rules.

An analyzer converts text into searchable terms. It splits text into tokens and can normalize them, such as converting uppercase letters to lowercase. Analysis happens during both indexing and searching. ^{1Text analysisElastic, Elastic Docs}

For our small example, choose this explicit contract:

The implementation below recognizes only ASCII letter-and-digit runs. This is a teaching boundary, not a suitable analyzer for Kartly’s multilingual catalog.

A real field needs deliberate rules for its languages and punctuation. Elastic’s documentation describes tokenization, normalization and configurable analyzers as separate parts of that choice. ^{1Text analysisElastic, Elastic Docs}

Normalize only what you can merge

Lowercasing makes differently capitalized words share an entry. More aggressive normalization can also merge words you wanted to distinguish.

For example, splitting AB-12 into ab and 12 may help broad text search. It does not preserve an exact model-number lookup.

For this scenario, keep separate fields:

• title: analyzed words for text search.
• model_code: one preserved value for exact lookup.

Do not concatenate title and description without preserving their boundaries. Otherwise an apparent phrase could begin in the title and end in the description.

If analysis changes, old postings do not change themselves. Rebuild affected fields, or query old and new representations deliberately. The analyzer is part of the index’s data contract.

One posting can answer several questions

Our ID-only list answers “does this document contain shoes?” It cannot answer “how often?” or “where?”

For document 14, “Shoes red shoes”, a richer posting could store:

{
  "term": "shoes",
  "document_id": 14,
  "frequency": 2,
  "positions": [0, 2]
}

Term frequency counts occurrences within one document. Positions record token order, starting at zero in this lesson.

Lucene 10.3.1 exposes separate indexing options for document IDs, frequencies, positions and character offsets. These options preserve different information rather than merely changing storage size. ^{2IndexOptionsApache Lucene, Lucene 10.3.1 core API}

Trace a phrase without guessing

Consider the exact phrase “red shoes”:

For this analyzer, accept a document when a shoes position equals a red position plus one. Counts alone cannot prove that relationship.

Lucene’s ID-only and frequency-only options do not support positional queries on the field. ^{2IndexOptionsApache Lucene, Lucene 10.3.1 core API} Our example explains the missing information: neither representation records adjacency.

Frequency will matter again in TF-IDF. Here, it remains evidence stored for later use, not a relevance score.

Build the index from titles

The index builder owns the following structure:

term → document ID → ordered positions

The inner map has one entry per matching document. Its position-list length gives the frequency, avoiding a separate count in this teaching implementation.

Process documents in ID order. Process each title from left to right. Those choices produce ordered document entries and ordered positions without sorting every postings list afterward.

import re

Index = dict[str, dict[int, list[int]]]

def analyze(text: str) -> list[str]:
    return [
        token.lower()
        for token in re.findall(r"[A-Za-z0-9]+", text)
    ]

def build_index(documents: dict[int, str]) -> Index:
    index: Index = {}
    for doc_id, title in sorted(documents.items()):
        for position, term in enumerate(analyze(title)):
            postings = index.setdefault(term, {})
            postings.setdefault(doc_id, []).append(position)
    return index

documents = {
    11: "Red running shoes",
    12: "Blue running shoes",
    13: "Red leather bag",
    14: "Shoes red shoes",
}
index = build_index(documents)
print(list(index.get(analyze("SHOES")[0], {})))
# [11, 12, 14]

type Index = Map<string, Map<number, number[]>>;

function analyze(text: string): string[] {
  return (text.match(/[A-Za-z0-9]+/g) ?? [])
    .map(token => token.toLowerCase());
}

function buildIndex(documents: Map<number, string>): Index {
  const index: Index = new Map();
  const ordered = [...documents].sort(([a], [b]) => a - b);
  for (const [docId, title] of ordered) {
    analyze(title).forEach((term, position) => {
      let postings = index.get(term);
      if (postings === undefined) {
        postings = new Map();
        index.set(term, postings);
      }
      const positions = postings.get(docId) ?? [];
      positions.push(position);
      postings.set(docId, positions);
    });
  }
  return index;
}

const documents = new Map<number, string>([
  [11, "Red running shoes"],
  [12, "Blue running shoes"],
  [13, "Red leather bag"],
  [14, "Shoes red shoes"],
]);
const index = buildIndex(documents);
const term = analyze("SHOES")[0]!;
console.log([...(index.get(term)?.keys() ?? [])]);
// [11, 12, 14]

There are 12 token occurrences in the sample. The builder performs one position append per occurrence.

For N documents and T analyzed tokens, document sorting costs O(N log N). Building the maps then takes expected O(T) map operations, plus text-analysis work.

A single-term lookup finds its dictionary entry, then reads the matching postings. Returning M document IDs still requires O(M) output work. A dictionary lookup does not make a large result set free.

The code handles repeated terms and empty titles. It does not implement updates, persistence or ranking. An empty query also needs an explicit API policy; do not index into an empty analyzed query as the fixed demonstration does.

Trace reads and writes separately

Place this structure inside the search service from Search system architecture. The following view represents one logical index partition, not all of Kartly’s deployment.

Write path

1. Read a product record with its ID and version.
2. Analyze the searchable fields.
3. Build postings under field-specific terms.
4. Publish a complete index generation for readers.

Read path

1. Analyze the query using compatible field rules.
2. Look up its terms in the dictionary.
3. Read postings and select matching document IDs.
4. Resolve those IDs into product cards.

A missing dictionary entry means no match under this index’s representation. It does not prove the customer’s intended product does not exist.

If the catalog call fails, do not turn that failure into “no results”. Distinguish a dependency error from a successful search with no matches.

The paths also expose a correctness boundary: an indexed product may no longer be available when the customer opens it.

Measure the work you moved

Use these illustrative assumptions for Kartly’s 20-million-product catalog:

• Average encoded title: 160 bytes.
• Average distinct indexed title terms: 12 per product.
• “Shoes” occurs in 40,000 titles.
• Packed document ID: 4 bytes.

These are scenario inputs, not measured production values.

The term list names 500 times fewer documents than the catalog contains. That is not a claim of 500-times lower latency: the operations and downstream costs differ.

The 960 MB figure also does not describe the code above. Its maps and lists store objects rather than packed four-byte entries.

The decision is therefore narrower than “put everything in memory”: prepare term access paths, then measure their full representation and query costs.

Updates must not expose half a document

Suppose a seller changes document 11 from “Red running shoes” to “Blue running shoes”.

Appending its ID under blue is insufficient. Leaving it under red creates a stale match. Removing the entire shoes list would also remove unrelated products.

For a simple correct update design, rebuild a replacement snapshot for a bounded partition. Give readers an immutable snapshot handle, then switch new requests to the replacement only after it is complete.

An in-flight request keeps its old handle. It sees either the old title representation or the new one, never half of each.

This design spends extra storage and rebuild work to simplify reader consistency. It is an explanatory baseline, not a proposal to rebuild Kartly’s whole catalog for every edit.

For incremental updates, retain enough document-to-term information to remove that document’s old memberships. Publish the removals and additions as one reader-visible change. Compare source versions so a late retry cannot replace newer text with older text.

Recover without trusting incomplete output

If the builder crashes, keep serving the previous complete generation. Track the last successful publication and source progress; a widening gap signals that customers are searching older data.

Build into a new destination. Validate it before publication, including known-term lookups and document counts. A failed build must not replace a working index.

If the serving index is unavailable, return a search error or use an available serving copy. Do not start unlimited catalog scans during a traffic peak.

The source-to-index delivery protocol belongs in Index synchronization. This lesson’s requirement is that readers never mistake partial construction for a complete index.

Where this shows up

• Design: search autocomplete: retrieving matching vocabulary is a separate step from retrieving its document postings.
• Design: in-app search for a large product: field analysis and posting detail determine supported matching behavior.

We can now find each word’s documents; next, Kartly must combine those lists without scanning them carelessly.

Common mistakes

• Treating repeated words as duplicate results. Keep one document entry per term, with occurrences inside that entry.
• Assuming every query becomes cheap. A common term can still have a large postings list.
• Discarding positions, then promising phrase search. Membership and frequency do not retain word order.
• Changing only the query analyzer. Existing postings still encode the old rules.
• Serving index data as catalog truth. Recheck authoritative price and availability where the product flow requires them.

Check your understanding

Summary