Search-Optimized Stores & Inverted Indexes (Elasticsearch / Lucene)

In standard relational databases, tables use a Forward Index: documents or rows map to their contained attributes and words (Document ID → Content). To perform a keyword search like SELECT * FROM articles WHERE content LIKE '%distributed%', the database must execute a full table scan across millions of rows (O(N) complexity).

Search engines like Elasticsearch, Apache Lucene, and Meilisearch invert this relationship using an Inverted Index: words map to the list of documents containing them (Term → List of Document IDs).

The Inverted Index Structure

• Term Dictionary: A sorted, in-memory Finite State Transducer (FST) containing every unique term across all documents.
• Posting List: A compressed array of Document IDs, term frequencies, and word offsets associated with each term.

When querying for multiple words (e.g., "distributed cache"), the search engine simply looks up the posting lists for "distributed" and "cache" and performs a fast bitset intersection in microseconds (O(log N) time).