Inside the inverted index

The Elasticsearch essays · December 2025

Anatomy of a search drew the inverted index as an idea: terms on the left, document lists on the right. This essay opens the hood. The idea only works because of three pieces of ruthless engineering: a term dictionary that finds one term among millions in a handful of steps, posting lists compressed to a few bits per entry, and intersections that skip instead of walk. Each one below is running live.

1 · The term dictionary: an automaton, not a list

Before any posting list can be read, the term itself must be found, among tens of millions. Storing them as a sorted list would work; Lucene does something better: a finite state transducer (FST), a graph in which every term is a path, and shared beginnings and endings are stored once. Type to walk it, and press Enter to add your own term:

–

status

–

letters, stored as a list

–

arcs · shared prefixes → + shared suffixes

Your keystrokes walk the arcs; a double ring means "a term ends here." Shared beginnings are drawn once; the right-hand count also merges identical endings, which is what makes it a minimal automaton rather than a tree. Add paying and pausing: each new term adds three arcs to the tree, but the shared -ing ending costs the automaton only one. Lookup costs one arc per letter however many terms exist. In Lucene, the FST indexes term prefixes: it leads to an on-disk block of roughly 25 to 48 neighboring terms, scanned to finish the lookup, and each entry there points to the term's posting list.

2 · Posting lists: bits, not integers

Found the term; now the list of documents. Stored naively, each document id costs 4 bytes, and a term appearing in 100 million documents costs 400 MB, for that one term. The fix exploits a gift: posting lists are sorted, so instead of ids you store the gaps between them, and small numbers need few bits. Lucene cuts the list into blocks of 128 gaps and packs each block at the width of its largest gap. Drag the term's popularity:

document ids

gaps between them

first block, bit-packed ·

–

naive: 4 bytes per id

–

delta + bit packing, per block

–

bits per document

term appears in

A corpus of one million documents; every id below is generated and packed for real, block by block. A rare term has huge gaps, so packing barely beats plain 32-bit integers (about 2×). The more common the term, the smaller the gaps, until a near-stopword costs one or two bits per document, an order of magnitude less. The win is largest exactly where the lists are longest. Very dense blocks can also be stored as a plain bitset.

3 · Skipping: how AND stays fast

An AND query intersects two posting lists, and the naive way walks both, entry by entry. But the lists are sorted, and sorted data invites skip pointers: express lanes over every few entries. When one list says "my next document is 63," the other doesn't crawl toward 63, it leaps. How far apart should the lanes be? Find out:

rare term · 5 documents

common term · 38 documents

–

comparisons

–

entries read

–

matches found

skip pointer every

step

Scrub through the intersection. The rare list drives: for each of its five documents, the common list must catch up. Underlined entries carry a skip pointer, and every pointer check counts as a comparison. Set the spacing to 1 and the pointers cost as much as walking; set it to 10 and they rarely let you jump; somewhere in between, comparisons fall by up to a third, even on a list this small. Lucene puts one skip entry per 128-document block and a second level every 32 blocks, and for the same reason the rarest term leads every intersection: fewer targets to catch.

Term dictionary, compressed postings, skip lists: three structures, one contract. Everything expensive happens once, at write time inside a segment; every query after that is arc walks, bit unpacks and leaps. And when the terms carry weights instead of just presence, these same lists power the ranking shortcuts in Ranking: the science of first.