Postings list

A postings list is the collection of records associated with one term in an inverted index. Each record identifies a document containing the term; optional fields include its term frequency in that document and, for a positional index, occurrence positions. The number of distinct document records is the document frequency, which differs from the total number of occurrences.^[ref]

For documents 1 red red boat, 2 blue boat, and 3 red train, the document identifiers in the red postings list are $1,3$. Its document frequency is two, although red occurs three times. The boat postings list contains $1,2$. Their intersection is $1$, answering red AND boat.

With identifiers in increasing order, compare the current identifiers and advance whichever is smaller; when equal, emit that identifier and advance both. Each advancement consumes a record, so intersecting lists of lengths $m,n$ costs $O(m+n)$ comparisons in this simple merge algorithm. Ordering gives a direct route from stored evidence to a query result without reading every document's text.^[ref]