Inverted Index Internals

Overview

An inverted index is the foundational data structure behind nearly every full-text search engine. Unlike a forward index—which maps documents to their constituent terms—an inverted index reverses this relationship, mapping each unique term to the set of documents that contain it. This inversion is what makes sub-second keyword lookups possible across corpora containing millions or even billions of documents. Systems like Lucene, Elasticsearch, Tantivy, and purpose-built search databases all rely on inverted indexes as their primary retrieval mechanism.

At a high level, the inverted index consists of two major components: a term dictionary that provides an ordered, searchable mapping from terms to their metadata, and a collection of posting lists that store the document identifiers (and optionally positions, frequencies, and payloads) associated with each term. The efficiency of a search engine is largely determined by how cleverly these two components are encoded, compressed, and laid out on disk.

This document explores the internal mechanics of inverted indexes in depth—covering posting list storage formats, integer compression schemes, term dictionary structures built on finite state transducers, field-level segmentation, doc values for columnar access, and skip lists for fast seeking. We’ll also examine how a custom Zig-based search engine implements chunked inverted indexes optimized for high-throughput ingestion and low-latency queries.

Core Concepts

Term Dictionary

The term dictionary is a sorted data structure that maps every unique term in the index to the location of its posting list on disk. Modern search engines typically use a finite state transducer (FST) for the term dictionary because FSTs provide prefix-compressed, memory-mapped lookups in O(k) time where k is the length of the search term. The FST encodes both the sorted term set and an associated output value (a byte offset into the postings file) in a single compact automaton.

Posting Lists

A posting list is an ordered sequence of document IDs that contain a given term. In practice, posting lists also carry auxiliary data: term frequencies (how many times the term appears in each document), positional information (the exact offsets within the document), and optional payloads (e.g., field boosts or custom scoring data). Posting lists are sorted by document ID to enable efficient intersection via merge-join algorithms.

Field Segments

Search engines organize their indexes into segments—immutable, self-contained mini-indexes that are created during write operations and periodically merged together. Each segment contains its own term dictionary, posting lists, stored fields, and doc values. Within a segment, fields (such as title, body, and tags) can have independent analyzers, posting formats, and storage configurations. This per-field architecture allows the engine to apply different compression strategies based on the characteristics of each field.

Doc Values

While posting lists answer the question “which documents contain this term?”, doc values answer the inverse: “what is the value of this field for a given document?” Doc values are column-oriented storage structures that enable fast sorting, faceting, and aggregation without decompressing the original stored documents. They are typically encoded as dense arrays with fixed-width or variable-width entries, indexed by document ordinal.

How It Works

Indexing Pipeline

When a document is ingested, the indexing pipeline performs the following steps:

1. Analysis: Each field’s text is tokenized, lowercased, stemmed, and filtered through an analyzer chain to produce a stream of terms.
2. In-memory buffering: Terms and their positions are accumulated in an in-memory hash map keyed by term. Each entry points to a growable buffer of (doc_id, frequency, positions) tuples.
3. Segment flush: When the in-memory buffer exceeds a threshold (typically 64–256 MB), it is sorted by term and flushed to disk as a new immutable segment.
4. Posting list encoding: During the flush, document ID deltas are compressed using variable-byte (VByte) or PFOR-delta encoding and written to the postings file.
5. Term dictionary construction: The sorted terms are compiled into an FST that maps each term to its offset in the postings file.
6. Skip list generation: For long posting lists, a skip list is built alongside the postings to allow sub-linear seeking to arbitrary document IDs.

Integer Compression: VByte Encoding

Variable-byte (VByte) encoding represents each integer as a sequence of bytes where the high bit of each byte indicates whether more bytes follow. Values under 128 fit in a single byte, values under 16,384 fit in two bytes, and so on. VByte is simple to implement and fast to decode, making it the default compression scheme for many search engines.

// VByte encoding example (conceptual)
// Value: 300 = 0b100101100
// Split into 7-bit groups: [0000010, 0101100]
// Encode with continuation bits:
//   Byte 1: 0_0101100 = 0x2C (more bytes follow)
//   Byte 2: 1_0000010 = 0x82 (final byte)
// On disk: [0x2C, 0x82]

Integer Compression: PFOR-Delta

Patched Frame-of-Reference (PFOR-delta) encoding compresses blocks of integers (typically 128 or 256 values) by finding the minimum number of bits needed to represent most values in the block. Outliers that don’t fit are “patched” into an exception list. PFOR-delta achieves higher throughput than VByte on modern CPUs because it enables SIMD-parallel decoding of entire blocks at once.

Skip Lists for Fast Seeking

When intersecting two posting lists (e.g., for a query like "distributed" AND "consensus"), the engine needs to advance one list to match the current document ID of the other. Without skip lists, this requires sequential scanning. A skip list adds a hierarchy of forward pointers at regular intervals (e.g., every 128 documents), enabling the decoder to jump ahead in O(log n) time rather than O(n).

Segment Merging

Over time, the number of on-disk segments grows, which degrades query performance because the engine must merge results from each segment at query time. A background merge process periodically combines smaller segments into larger ones using a tiered or logarithmic merge policy. During merging, deleted documents are physically purged, posting lists are re-delta-encoded, and the term dictionary is rebuilt. The merge is atomic—readers continue using the old segments until the new merged segment is fully written and registered.

Practical Applications

Chunked Inverted Index Design

A custom Zig-based search engine can implement a chunked inverted index designed for high-throughput vector & full-text hybrid queries. Rather than using monolithic segments, posting lists are split into fixed-size chunks (typically 4 KB) that align with the storage engine’s page size. Each chunk is independently compressed with PFOR-delta and prefixed with a small header containing the chunk’s min/max document IDs and the byte length of the compressed payload. This design enables:

• Page-aligned I/O that minimizes read amplification on SSDs
• Parallel decompression of independent chunks across CPU cores
• Incremental garbage collection—individual chunks can be rewritten without touching the entire posting list
• Memory-mapped access with predictable page-fault behavior

Hybrid Search

A hybrid search engine extends the inverted index with support for combining keyword matching (BM25 scoring over the inverted index) with vector similarity (HNSW graph traversal). The query planner evaluates both paths in parallel and merges results using reciprocal rank fusion (RRF). The inverted index component provides the initial candidate set, which is then re-ranked by the vector similarity score. This architecture leverages the inverted index’s strength at precise term matching while using vector search for semantic understanding.

Field-Level Indexing Strategies

In a typical search engine implementation, each field within a document can be configured with a distinct indexing strategy. The title field might use positional indexing (to support phrase queries) with VByte compression, while the body field uses frequency-only indexing with PFOR-delta compression for better throughput. The tags field might skip frequency data entirely, storing only document IDs, since tag fields typically don’t benefit from TF-IDF scoring.

Implementation Patterns

Pattern 1: Write-Optimized Buffering

Batch incoming documents in an in-memory buffer organized as a hash map from terms to posting accumulators. When the buffer exceeds a configurable memory threshold, sort the terms lexicographically, encode each posting list with delta + VByte compression, build an FST over the sorted terms, and flush the entire segment to disk atomically. This write-ahead pattern ensures that the on-disk index always contains complete, queryable segments.

Pattern 2: Block-Based Posting List Layout

Organize posting lists into fixed-size blocks of 128 document IDs each. Each block is independently compressed (PFOR-delta or bit-packing) and preceded by a block header containing the last document ID in the block. This layout enables:

• Block-level skip seeking—jump directly to the block containing the target doc ID
• SIMD-accelerated batch decoding of 128 integers at once
• Predictable memory allocation (each decoded block fits in a known buffer size)

Pattern 3: Tiered Merge Policy

Group segments into tiers by size (e.g., <1 MB, 1–10 MB, 10–100 MB, >100 MB). Merge segments within the same tier when the count exceeds a fanout threshold (typically 10). This policy limits write amplification to O(log n) while keeping the total segment count bounded. A well-designed merge scheduler runs on a dedicated thread and respects I/O bandwidth limits to avoid starving query threads.

Pattern 4: Two-Phase Query Execution

Split query execution into a collection phase and a scoring phase. During collection, intersect or union posting lists using doc ID–ordered iteration with skip list acceleration. During scoring, load doc values and term statistics to compute BM25 or other relevance scores. This separation allows the engine to prune low-scoring candidates early and avoid loading doc values for documents that won’t make the top-K result set.

Pattern 5: Memory-Mapped Segment Access

Memory-map the entire segment file and access posting lists, term dictionaries, and doc values via pointer arithmetic. The operating system’s page cache handles eviction and prefetching transparently. In a typical implementation, segment files are opened with mmap and advised with MADV_RANDOM for term dictionary lookups (random access pattern) and MADV_SEQUENTIAL for posting list scans (sequential access pattern).

Code Examples

Zig: Chunked Posting List Reader

This example shows how a Zig-based search engine decodes a chunked posting list, advancing through compressed blocks and applying delta decoding to reconstruct document IDs.

const std = @import("std");

const ChunkHeader = packed struct {
    min_doc_id: u32,
    max_doc_id: u32,
    compressed_len: u16,
    num_docs: u16,
};

const PostingListReader = struct {
    data: []const u8,
    offset: usize,
    current_doc: u32,
    block_buf: [128]u32,
    block_pos: usize,
    block_len: usize,

    pub fn init(data: []const u8) PostingListReader {
        return .{
            .data = data,
            .offset = 0,
            .current_doc = 0,
            .block_buf = undefined,
            .block_pos = 0,
            .block_len = 0,
        };
    }

    /// Advance to the next document ID in the posting list.
    /// Returns null when the list is exhausted.
    pub fn next(self: *PostingListReader) ?u32 {
        if (self.block_pos < self.block_len) {
            const delta = self.block_buf[self.block_pos];
            self.current_doc += delta;
            self.block_pos += 1;
            return self.current_doc;
        }

        // Try to load the next chunk
        if (self.offset >= self.data.len) return null;

        const header = @as(
            *const ChunkHeader,
            @ptrCast(@alignCast(self.data[self.offset..].ptr)),
        );
        self.offset += @sizeOf(ChunkHeader);

        // Decode PFOR-delta compressed block
        self.block_len = decodePforDelta(
            self.data[self.offset..][0..header.compressed_len],
            &self.block_buf,
            header.num_docs,
        );
        self.offset += header.compressed_len;
        self.block_pos = 0;

        // Recurse to return the first doc from the new block
        return self.next();
    }

    /// Skip forward to the first document >= target_doc.
    /// Uses chunk headers to skip entire blocks.
    pub fn advanceTo(self: *PostingListReader, target_doc: u32) ?u32 {
        // Skip chunks whose max_doc_id is below our target
        while (self.offset < self.data.len) {
            const header = @as(
                *const ChunkHeader,
                @ptrCast(@alignCast(self.data[self.offset..].ptr)),
            );
            if (header.max_doc_id >= target_doc) break;
            self.offset += @sizeOf(ChunkHeader) + header.compressed_len;
        }

        // Linear scan within the current block
        while (true) {
            const doc = self.next() orelse return null;
            if (doc >= target_doc) return doc;
        }
    }
};

fn decodePforDelta(
    compressed: []const u8,
    output: *[128]u32,
    count: u16,
) usize {
    // Simplified PFOR-delta decoding (production code uses SIMD)
    var i: usize = 0;
    var pos: usize = 0;
    while (i < count) : (i += 1) {
        var value: u32 = 0;
        var shift: u5 = 0;
        while (pos < compressed.len) {
            const byte = compressed[pos];
            pos += 1;
            value |= @as(u32, byte & 0x7F) << shift;
            if (byte & 0x80 != 0) break;
            shift += 7;
        }
        output[i] = value;
    }
    return count;
}

Python: Building an In-Memory Inverted Index

A minimal inverted index implementation that demonstrates term extraction, delta encoding, VByte compression, and boolean query intersection.

import struct
from collections import defaultdict
from typing import List, Dict, Optional


class VByteCodec:
    """Variable-byte encoding for non-negative integers."""

    @staticmethod
    def encode(value: int) -> bytes:
        buf = bytearray()
        while value >= 0x80:
            buf.append(value & 0x7F)
            value >>= 7
        buf.append(value | 0x80)  # high bit signals final byte
        return bytes(buf)

    @staticmethod
    def decode(data: bytes, offset: int = 0) -> tuple[int, int]:
        value = 0
        shift = 0
        while offset < len(data):
            byte = data[offset]
            offset += 1
            value |= (byte & 0x7F) << shift
            if byte & 0x80:
                return value, offset
            shift += 7
        raise ValueError("Truncated VByte sequence")


class InvertedIndex:
    """In-memory inverted index with delta-encoded posting lists."""

    def __init__(self):
        self._postings: Dict[str, List[int]] = defaultdict(list)
        self._doc_count = 0

    def add_document(self, doc_id: int, text: str) -> None:
        """Tokenize and index a document."""
        terms = set(text.lower().split())
        for term in terms:
            postings = self._postings[term]
            if not postings or postings[-1] != doc_id:
                postings.append(doc_id)
        self._doc_count += 1

    def compress_postings(self, term: str) -> bytes:
        """Delta-encode and VByte-compress a posting list."""
        postings = self._postings.get(term, [])
        buf = bytearray()
        prev = 0
        for doc_id in postings:
            delta = doc_id - prev
            buf.extend(VByteCodec.encode(delta))
            prev = doc_id
        return bytes(buf)

    def intersect(self, term_a: str, term_b: str) -> List[int]:
        """Boolean AND intersection of two posting lists."""
        list_a = self._postings.get(term_a, [])
        list_b = self._postings.get(term_b, [])
        result = []
        i, j = 0, 0
        while i < len(list_a) and j < len(list_b):
            if list_a[i] == list_b[j]:
                result.append(list_a[i])
                i += 1
                j += 1
            elif list_a[i] < list_b[j]:
                i += 1
            else:
                j += 1
        return result


# Usage example
idx = InvertedIndex()
idx.add_document(0, "the quick brown fox")
idx.add_document(1, "the lazy brown dog")
idx.add_document(2, "quick fox jumps high")

# Find documents containing both "quick" AND "fox"
matches = idx.intersect("quick", "fox")
print(f"Matched doc IDs: {matches}")  # [0, 2]

# Show compressed posting list for "brown"
compressed = idx.compress_postings("brown")
print(f"Compressed 'brown' postings: {len(compressed)} bytes")

Common Pitfalls

1. Forgetting to delta-encode before compression. Compressing raw document IDs wastes bits because the values are large and irregularly spaced. Always sort the posting list and compute deltas first—this typically reduces the compressed size by 50–70%.
2. Neglecting skip lists on long posting lists. Without skip structures, intersecting a 10-million-doc posting list with a 100-doc list degrades to a full linear scan of the larger list. Skip lists reduce this to O(n log m) where n is the short list’s length and m is the long list’s length.
3. Over-merging segments during peak ingestion. Triggering aggressive segment merges while the system is under heavy write load causes I/O contention that slows both indexing and queries. Use a tiered merge policy with backpressure—defer large merges to off-peak hours or rate-limit merge I/O bandwidth.
4. Storing high-cardinality fields as doc values without compression. Fields like UUIDs or timestamps with unique values per document produce dense, incompressible doc value columns. Apply dictionary encoding for low-cardinality fields and bitpacking or GCD-step encoding for numeric fields with regular stride patterns.
5. Using a single posting format for all fields. A positional posting format (which stores term offsets for phrase queries) is 3–5x larger than a frequency-only format. Fields that never participate in phrase or proximity queries should use the lighter format to save disk space and improve cache utilization.

Key Takeaways