Inverted index

Deep dive

How it works

Parts:

• analyzer — tokenizes, lowercases, optionally stems; the same at index and query time
• term dictionary — sorted terms (FST in Lucene) → document frequency and postings offset
• postings — per term, sorted doc IDs (plus frequencies, positions), delta-encoded in blocks of 128
• skip data — per block: last doc ID and byte offset, for advance(target)
• segment — immutable index file set; merged in the background like an LSM-tree
• deletion bitset — per segment until a merge drops the documents

term dict (FST / sorted)        postings (per term)
"chess"  → df=3, off=0   ──►    [3, 17, 42]   stored as gaps 3,14,25
"engine" → df=2, off=9   ──►    [17, 99]
query chess AND engine:  advance cursors to common ID → 17

1. Analyze: tokenize, lowercase, optionally stem or remove stop words. Index and query must use the same analyzer.
2. Accumulate in memory: term → growing list of (doc ID, term frequency, positions). Doc IDs arrive in increasing order because documents are numbered as they are indexed.
3. Flush a segment: sort the terms, write the dictionary (term → offset, document frequency) and the postings as delta-encoded blocks with a skip entry per block (last doc ID, byte offset).
4. Merge segments in the background, like an LSM-tree. Deleted documents are a bitset per segment until the merge drops them.
5. Query: an AND drives from the rarest term and calls advance(target) on the others. advance uses the skip data to jump straight to the block that may contain the target. For an OR with top-k ranking, keep a heap of the best k scores. WAND skips documents whose maximum possible score cannot beat the current k-th score.
6. Score: BM25: idf(t) · tf·(k1+1) / (tf + k1·(1 − b + b·len/avglen)) with k1 ≈ 1.2 and b ≈ 0.75.

Code

use std::collections::HashMap;

const BLOCK: usize = 128;

fn put_varint(out: &mut Vec<u8>, mut x: u32) {
    while x >= 0x80 { out.push(x as u8 | 0x80); x >>= 7; }
    out.push(x as u8);
}
fn get_varint(buf: &[u8], pos: &mut usize) -> u32 {
    let (mut x, mut shift) = (0u32, 0);
    loop {
        let b = buf[*pos]; *pos += 1;
        x |= ((b & 0x7f) as u32) << shift;
        if b < 0x80 { return x; }
        shift += 7;
    }
}

pub struct PostingList { skips: Vec<(u32, usize)>, bytes: Vec<u8>, len: usize } // skip = (last doc, offset)

impl PostingList {
    pub fn encode(ids: &[u32]) -> Self { // ids strictly increasing
        let (mut skips, mut bytes) = (Vec::new(), Vec::new());
        for chunk in ids.chunks(BLOCK) {
            skips.push((*chunk.last().unwrap(), bytes.len()));
            put_varint(&mut bytes, chunk[0]); // absolute base: each block decodes on its own
            for w in chunk.windows(2) { put_varint(&mut bytes, w[1] - w[0]); }
        }
        PostingList { skips, bytes, len: ids.len() }
    }
    fn decode_block(&self, b: usize, out: &mut Vec<u32>) {
        out.clear();
        let n = if b + 1 == self.skips.len() { self.len - b * BLOCK } else { BLOCK };
        let mut pos = self.skips[b].1;
        let mut doc = get_varint(&self.bytes, &mut pos);
        out.push(doc);
        for _ in 1..n { doc += get_varint(&self.bytes, &mut pos); out.push(doc); }
    }
}

pub struct Cursor<'a> { pl: &'a PostingList, block: usize, buf: Vec<u32>, i: usize }

impl<'a> Cursor<'a> {
    pub fn new(pl: &'a PostingList) -> Self { Cursor { pl, block: usize::MAX, buf: Vec::with_capacity(BLOCK), i: 0 } }
    /// Smallest doc >= target (targets must not decrease). Whole blocks are skipped undecoded.
    pub fn advance(&mut self, target: u32) -> Option<u32> {
        let b = self.pl.skips.partition_point(|&(last, _)| last < target);
        if b == self.pl.skips.len() { return None; }
        if b != self.block { self.pl.decode_block(b, &mut self.buf); self.block = b; self.i = 0; }
        self.i += self.buf[self.i..].partition_point(|&d| d < target);
        Some(self.buf[self.i])
    }
}

/// AND of non-empty term list: leapfrog, driven by the rarest term.
pub fn intersect(lists: &mut [&PostingList]) -> Vec<u32> {
    lists.sort_by_key(|l| l.len);
    let mut cs: Vec<Cursor> = lists.iter().map(|l| Cursor::new(l)).collect();
    let (mut out, mut target) = (Vec::new(), 0u32);
    'outer: loop {
        let Some(d) = cs[0].advance(target) else { break };
        target = d;
        for c in &mut cs[1..] {
            match c.advance(target) {
                None => break 'outer,
                Some(x) if x > target => { target = x; continue 'outer; } // re-check from the rarest
                _ => {}
            }
        }
        out.push(target);
        if target == u32::MAX { break; }
        target += 1;
    }
    out
}

pub fn build(docs: &[&str]) -> HashMap<String, PostingList> {
    let mut tmp: HashMap<String, Vec<u32>> = HashMap::new();
    for (id, d) in docs.iter().enumerate() {
        for t in d.split(|c: char| !c.is_alphanumeric()).filter(|t| !t.is_empty()) {
            let list = tmp.entry(t.to_lowercase()).or_default();
            if list.last() != Some(&(id as u32)) { list.push(id as u32); }
        }
    }
    tmp.into_iter().map(|(t, ids)| (t, PostingList::encode(&ids))).collect()
}

Complexity and constants

• Intersecting lists of sizes m ≤ n costs O(m log(n/m)) with galloping or skips, and O(m + n) with a linear merge. Skipping wins when the ratio n/m exceeds about 10-100.
• Varint gap coding: about 1 byte per posting for dense lists, decoded at order of 1-3 ns per integer (branchy). SIMD bit-packing decodes at under 1 ns per integer.
• Positions for phrase queries usually make the index 2-4× larger than doc IDs plus frequencies (order of).
• The term dictionary is small next to the postings. An FST shares prefixes and suffixes and often fits in RAM.

Efficiency

• Cost: order of 2-8 bits per posting; decoding order of 1-3 ns per integer for branchy varints, under 1 ns with SIMD bit-packing (Lemire and Boytsov 2015). An AND costs O(m log(n/m)) with skips, so cost follows the shortest list. Bound: memory or I/O bandwidth for reading postings, then decode and compare.
• Levers:
  • gap-coded, bit-packed 128-ID blocks — under 1 ns per integer vs 1-3 ns for varints (order of) — all lists
  • galloping or skip pointers from the shortest list — O(m log(n/m)) instead of O(m + n) — AND with unequal lists
  • WAND and Block-Max WAND — skip blocks that cannot reach the current top-k threshold — ranked OR queries
  • reorder doc IDs so similar documents are adjacent — index smaller by order of 10-30 % — large static corpora
  • immutable memory-mapped segments, merge policy bounding segment count — lock-free reads — live indexes
• Naive → standard → state of the art:
  • scan all documents · O(corpus) per query
  • gap-coded postings with skip pointers · cost follows the shortest list
  • SIMD blocks, Block-Max WAND, reordered IDs · scores a small fraction of the matches

Implementation notes

• Block layout: fixed blocks of 128 doc IDs bit-packed with one bit width per block (frame of reference). Store frequencies in a parallel block. Lucene encodes the tail (fewer than 128) with varints.
• Doc ID reordering: sort documents so that similar ones get nearby IDs (by URL, by cluster). Gaps shrink and the index can shrink by order of 10-30 %.
• Block-max metadata: store the maximum term score per block next to the skip entry. Block-Max WAND then skips blocks that cannot reach the top-k threshold.
• Segments are immutable: they cache well, can be memory-mapped and read without locks. Updates are delete plus re-add.
• Very frequent terms (stop words, status:200): keep them as bitmaps, or drop them and answer phrase queries from positions.
• n-gram indexes (trigrams) turn substring and regex search into postings intersections (Google Code Search, pg_trgm).

Pitfalls

• Intersecting from the longest list instead of the shortest, which is order-of-magnitude slower for skewed terms.
• Mismatched analyzers at index time and query time give silent misses.
• Many tiny segments: every query touches every segment. Merge policy (tiered, about 10 segments per tier) bounds this.
• Deep pagination (from = 10000) forces a top-(from + size) heap on every shard. Use search-after cursors.
• Running BM25 statistics (df, avglen) per shard skews scores when shards are small or unbalanced.

Variants and alternatives

In production

• Web and site search: Lucene (Elasticsearch, OpenSearch, Solr), Vespa, Sphinx/Manticore.
• Log search: Elasticsearch/OpenSearch; Tantivy in Quickwit.
• Code search: Zoekt (trigram index, used by Sourcegraph).
• Databases: PostgreSQL GIN indexes (full-text, pg_trgm, arrays, jsonb), ClickHouse text and skip indexes.

Implementations

Sources

• J. Zobel, A. Moffat, Inverted Files for Text Search Engines, ACM Computing Surveys, 2006. paper
• C. Manning, P. Raghavan, H. Schütze, Introduction to Information Retrieval, 2008. book
• A. Broder et al., Efficient Query Evaluation Using a Two-Level Retrieval Process (WAND), CIKM, 2003. paper
• S. Ding, T. Suel, Faster Top-k Document Retrieval Using Block-Max Indexes, SIGIR, 2011. paper
• D. Lemire, L. Boytsov, Decoding Billions of Integers per Second through Vectorization, Software: Practice and Experience, 2015. paper · code
• S. Robertson, H. Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond, Foundations and Trends in IR, 2009. paper