Understanding Elasticsearch’s Inverted Index: Core Structure and Search Process

Inverted index maps each term to the list of documents that contain it, enabling direct term lookup instead of scanning all documents as required by a forward index.

What is an Inverted Index

A forward index stores documents sequentially with a document ID; locating a term requires scanning the entire collection. An inverted index maintains a term list where each term points to a posting list of document identifiers, allowing efficient retrieval.

Inverted Index in Elasticsearch

Elasticsearch builds its inverted index using the Lucene library. Each field of a document is indexed as an independent inverted index.

When a search query is executed, Elasticsearch parses it into one or more query terms.

For each term, Elasticsearch first looks up the term in the term dictionary. Because the dictionary can be large, a term index (stored as an FST) accelerates this lookup.

Once the term is found, Elasticsearch retrieves the associated posting list, which records the IDs of all documents containing the term and additional metadata such as term positions and frequencies.

Multiple posting lists may be merged, and the combined results are sorted by relevance before being returned.

The inverted index consists of three main components: posting list, term dictionary, and term index.

Posting List

The posting list is the core of the inverted index. For every term that appears in the collection, an entry stores the document IDs and auxiliary information (e.g., term positions, frequencies).

Example document set:

Doc1: "The quick brown fox"
Doc2: "Quick foxes jump over lazy dogs"
Doc3: "Brown foxes are not quick"

For the term quick , a possible posting list entry is:

quick → Doc1:1; Doc3:3  (the numbers indicate the term position within the document)

Posting lists are typically compressed using delta encoding, bitmaps, or other techniques to reduce storage space.

Term Dictionary

The term dictionary contains all unique terms in the collection, ordered (e.g., lexicographically). Each term holds a pointer to its posting list entry.

Using the example collection, the term dictionary would be:

The
quick
brown
fox
foxes
jump
over
lazy
dogs
are
not

Term Index

Challenges of term dictionary lookup

Full‑text systems handle massive text data, making the term dictionary extremely large. Traditional structures such as hash tables or B‑trees require loading the entire dictionary into memory, which can exhaust available RAM.

Even when loaded, random memory accesses are slower than CPU operations, limiting lookup performance.

Purpose of the term index

A term index provides a compact, fast way to locate terms. It commonly uses a Trie (prefix tree) to store prefix information.

Because a plain Trie can be memory‑heavy, Elasticsearch employs a compressed Trie called a Finite State Transducer (FST) to represent string mappings with much lower memory consumption.

Lookup flow based on the term index

Term Index positioning: The FST stored in memory quickly identifies the block in the term dictionary that may contain the target term.

Dictionary search: Within the identified block, Elasticsearch performs an exact lookup using the dictionary’s internal structure (sorted array or B‑tree), which is fast because the search range is narrow.

The combination of term index and dictionary enables high‑performance term lookup without large memory overhead.

Extensions and Optimizations

Compression : Posting lists are compressed (e.g., delta encoding, bitmaps) to reduce storage and accelerate query processing.

Skip lists : For large posting lists, Elasticsearch uses skip‑list data structures to speed up traversal during merging.

Prefix sharing : Terms in the dictionary share common prefixes, reducing the memory footprint of the term dictionary.