Part 0 · 1 chapters · ~8 min

Inverted Indexes

Forward and inverted indexes, postings lists with frequencies and positions, the term dictionary (FSTs in Lucene), Boolean query execution by intersecting and unioning postings, skip lists, phrase and proximity queries, postings compression, and why databases' LIKE cannot compete.

Terms to documents

code

// a tiny inverted index
const index = new Map<string, number[]>();
docs.forEach((text, id) => { for (const term of new Set(analyse(text))) (index.get(term) ?? index.set(term, []).get(term)!).push(id); });

function and(a: number[], b: number[]) {                 // both sorted: a linear merge
  const out = []; let i = 0, j = 0;
  while (i < a.length && j < b.length) a[i] === b[j] ? (out.push(a[i]), i++, j++) : a[i] < b[j] ? i++ : j++;
  return out;
}
and(index.get('yaba')!, index.get('kitchen')!);          // [1]

A database's LIKE '%kitchen%' scans every row (no B-tree can help a leading wildcard; pg_trgm helps somewhat). An inverted index answers from a postings list read, regardless of corpus size.

AN INVERTED INDEX

from documents to terms, and from terms back to documents

swipe the figure sideways, or tap expand for full screen

1/5

documents

Start with documents: merchant names, product descriptions, help articles. A forward index lists the terms in each document.

documents and their termsthe forward view