Postings List

At its simplest, a postings list is a sorted array of document IDs where a specific term appears. This sorted structure enables fast intersection and union operations using galloping search or SIMD-accelerated algorithms. For a term like 'algorithm', the list might contain [2, 5, 17, 42, 103], indicating the documents that contain the word. The sorting is critical for efficient Boolean retrieval and allows compression via delta encoding, where only the gaps between consecutive IDs are stored.

To support ranking functions like BM25, a postings list stores the term frequency (TF) for each document. This is the raw count of how many times the term appears in that specific document. A typical entry becomes a pair: (docID, frequency). For example, (42, 3) means the term appears three times in document 42. This data is essential for the saturation function in BM25, which models the non-linear gain in relevance from additional term occurrences.

For phrase matching and proximity queries, a postings list often includes the exact byte or word positions of the term within each document. An entry expands to (docID, frequency, [pos1, pos2, ...]). If a user searches for 'machine learning', the engine can verify that 'machine' and 'learning' appear adjacently by checking their position arrays. This data structure is a significant storage overhead but is mandatory for supporting exact phrase queries.

To avoid scanning an entire postings list during intersection operations, modern implementations like Apache Lucene use skip pointers. These are additional data structures that allow the search engine to jump ahead to a specific document ID without reading every entry. A skip pointer at index i stores the document ID at that position and the byte offset to jump to. This optimization is crucial for making Boolean AND queries over high-frequency terms like 'the' and 'company' execute in sub-millisecond time.

Postings lists can consume significant memory and disk space. They are heavily compressed using techniques like Variable Byte Encoding or PForDelta (Patched Frame of Reference). Delta encoding converts the sorted document ID list [2, 5, 17, 42] into gaps [2, 3, 12, 25], which are smaller integers. These gaps are then packed into the fewest possible bits. This compression is lossless and allows the inverted index to fit in system page caches for maximum performance.

Advanced implementations allow attaching arbitrary payloads to each term occurrence. A payload is a byte array that can store custom scoring factors, such as a boost weight for terms in a document's title versus its body. In a structured document, the postings list may also encode which field the term appeared in. This enables BM25F, where a match in the 'title' field contributes more to the relevance score than a match in the 'body' field.