Course contentsShow
← System Design
Lesson 1745 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Posting Lists and Document IDs

Storing document references and positions for each term efficiently in posting lists.

Posting Lists and Document IDs

What you'll learn: How inverted indexes efficiently store references to documents containing each term, along with position information.


The Core Structure

A posting list is the data structure that stores all occurrences of a specific term across your document collection. For each term in your inverted index, the posting list answers: "Which documents contain this word, and where?"

Think of it like a library card catalog: when you look up "python," the posting list is the card showing every book containing that word, plus which pages it appears on.

What Goes in a Posting List

At minimum, a posting list contains document IDs (unique identifiers for each document). But for effective search, you typically store:

  • Document ID: Reference to the document (e.g., doc_42)
  • Term Frequency: How many times the term appears in that document
  • Positions: List of word positions within the document (for phrase queries)

Example for the term "search":

"search" → [
  (doc_1, freq=3, positions=[5, 47, 102]),
  (doc_8, freq=1, positions=[23]),
  (doc_15, freq=7, positions=[2, 18, 34, 56, 89, 90, 91])
]

Efficiency Considerations

Posting lists must be compact because popular terms appear in millions of documents. Common optimizations:

  • Sorted by document ID for faster intersection operations during multi-term queries
  • Delta encoding for document IDs (store differences, not absolute values)
  • Compression using algorithms like VarByte or Simple9

When someone searches "search engine," your system intersects the posting lists for both terms to find documents containing both words.

Key Takeaway: Posting lists are the heart of an inverted index, storing compressed document IDs, frequencies, and positions for each term to enable fast, relevant search results.