Skip to content

Search: tokens, ranking and index lag

Follow a query through an inverted index, reason about lexical ranking, and account for delayed indexing and shard fan-out.

18 min7 steps

By the end you can
  • Trace tokenisation and postings lookup in an inverted index
  • Explain term frequency, rarity and document-length normalization in ranking
  • Explain why committed database changes may not yet appear in search
  • Explain sharded query fan-out, result merging and partial failures

Turn terms into document lists

Documents

  • D1: red bike
  • D2: blue bike
  • D3: red boat

Postings

  • red → D1, D3
  • bike → D1, D2
  • boat → D3

The index maps each term to postings: document IDs, often with term frequencies and positions. For an AND query, intersect term lists. For OR, take their union. This avoids reading every document for each query.

Using these postings, which documents match red AND bike?

Answer this step to continue.