Posting Lists and Document IDs
You'll learn how inverted indexes store references to documents for each term, along with metadata that makes search fast and relevant.
Core Concept
When you build an inverted index (term → documents), the actual data structure stores posting lists—ordered collections of document identifiers where each term appears. Think of it like a library catalog: when you look up the word "dragon," you get a list of every book containing that word, along with notes about how many times it appears in each book.
Each entry in a posting list typically contains:
- Document ID: A unique identifier (often an integer) pointing to the actual document
- Term frequency (TF): How many times the term appears in that document
- Positional information: Where exactly in the document the term appears (optional, for phrase queries)
Why This Structure Matters
For the term "python", your posting list might look like:
"python" → [
(doc_42, tf=5, positions=[10, 45, 67, 120, 201]),
(doc_89, tf=2, positions=[3, 88]),
(doc_103, tf=8, positions=[...])
]
The list is typically sorted by document ID for efficient merging during multi-term searches. When someone searches "python tutorial", your query processor intersects the posting lists for both terms to find documents containing both.
Term frequency metadata enables relevance scoring—documents where "python" appears 8 times are likely more relevant than those with just 2 mentions, all else being equal.
Storage Optimization
Real search engines compress posting lists heavily. Document IDs are stored as deltas (gaps between consecutive IDs) rather than absolute values, since small numbers compress better than large ones.
Key Takeaway: Posting lists are the heart of inverted indexes, storing document IDs and metadata (like term frequency) that enable both fast retrieval and intelligent relevance ranking for search queries.