Understanding Elasticsearch Inverted Index and Its Optimization Techniques

When people hear "Elasticsearch" they usually think of a high‑performance distributed search engine, and indeed it is often used to implement search functionality.

Effective search should be fast, accurate, tolerant of minor typos, and provide helpful suggestions, which are the goals most search engines, including Elasticsearch, strive to meet.

Inverted Index

Abstract Model

Elasticsearch builds on Lucene, a high‑performance full‑text search library, whose core data structure is the inverted index.

Traditional full‑text search scans all documents, which becomes infeasible at millions of records; the inverted index solves this by mapping each term to the list of documents containing it.

The index stores a dictionary of all unique terms (green nodes) and, for each term, a posting list of document IDs (red nodes), optionally with term frequencies to support relevance ranking.

Example JSON documents used in a simple HelloWorld demo:

[
  {
    "id": "2",
    "name": "second Helloworld 2",
    "organizer": "wangwu",
    "version": "1.0"
  },
  {
    "id": "1",
    "name": "ElasticSearch Helloworld",
    "organizer": "qingtong",
    "version": "1.0"
  }
]

Elasticsearch creates an inverted index for each field; the table below shows the term dictionary and posting list for the name field:

Term

Posting List

second

(2:1)

Helloworld

(2:1),(1:1)

2

(2:1)

ElasticSearch

(1:1)

During search, Elasticsearch looks up the term in the dictionary, retrieves the posting list, and returns matching documents; the notation 2:1 means term appears once in document with ID 2.

Specific Implementation

In Elasticsearch, a term is called a Term ; the collection of all terms forms the Term Dictionary , and the posting lists are the Postings List that map terms to document IDs.

The term dictionary can be stored as an ordered array for binary search or as a B+‑tree; however, keeping the entire dictionary in memory is costly, so a Term Index (a prefix trie) is used to quickly locate sections of the dictionary.

Index Optimizations

Finite State Transducers

Because many terms share common prefixes, Lucene uses Finite State Transducers (FST) to compress the term dictionary by sharing these prefixes.

Example term list: ["regular", "request", "rest", "teacher", "team", "teenage", "tend"] results in a compact FST representation.

Frame of Reference

Posting lists are further compressed using Frame‑of‑Reference encoding. First, delta‑encode the sorted document IDs (e.g., [73,300,302,332,343,372] → [73,227,2,30,11,29]).

Then split the list into blocks (typically 256 IDs per block) and store the bit‑width needed for each block as a header.

These techniques dramatically reduce storage for posting lists and improve query performance.

The article provides an introductory overview of Elasticsearch’s indexing mechanisms; readers are encouraged to explore the referenced materials for deeper details.