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.