Elasticsearch — Inverted Index Fundamentals

What makes Elasticsearch (and Lucene underneath) fast at text search. Senior interviews probe the mechanism, not just the API.

The inverted index

Instead of “document → terms” (a forward index, like a book), an inverted index is “term → documents” (like a book’s index at the back).

Document 1: "the quick brown fox"
Document 2: "the lazy dog"

Forward index:
  doc1: ["the", "quick", "brown", "fox"]
  doc2: ["the", "lazy", "dog"]

Inverted index:
  the   -> [doc1, doc2]
  quick -> [doc1]
  brown -> [doc1]
  fox   -> [doc1]
  lazy  -> [doc2]
  dog   -> [doc2]

Searching for “lazy” is now an O(log N) lookup on the dictionary plus an O(matches) iteration through the postings list — instead of scanning every document.

For each term, the index also stores:

• Postings list — doc IDs that contain the term.
• Term frequency (TF) per doc — how often the term appears in each doc.
• Position — where in the doc (for phrase queries).
• Offsets — byte positions (for highlighting).

Why this beats SQL LIKE

SELECT * FROM docs WHERE body LIKE '%lazy%';   -- O(N), full scan

vs

es.search(index="docs", query={"match": {"body": "lazy"}})  # O(log N) on dictionary

A B-tree index on body only helps LIKE 'foo%' (anchored prefix). The general LIKE needs full scan. Inverted indexes are built for the unanchored case.

Analyzers — turning text into tokens

Indexing isn’t word-level; it’s token-level after the analyzer chain. An analyzer has three stages:

1. Character filters — preprocess raw text (strip HTML, normalize unicode).
2. Tokenizer — split into tokens (typically by whitespace + punctuation).
3. Token filters — transform tokens (lowercase, stemming, stop-word removal).

"The quick BROWN fox <p>jumped</p>!"
  ↓ HTML strip filter
"The quick BROWN fox jumped!"
  ↓ standard tokenizer
["The", "quick", "BROWN", "fox", "jumped"]
  ↓ lowercase filter
["the", "quick", "brown", "fox", "jumped"]
  ↓ stop filter (remove "the")
["quick", "brown", "fox", "jumped"]
  ↓ stemmer
["quick", "brown", "fox", "jump"]

Final tokens indexed: [quick, brown, fox, jump]. Searching for “jumps” or “jumping” → stemmed to jump → matches.

Built-in analyzers

Pick by language: documents in English should use english for stemming benefits (“running” matches “run”). For exact-match fields (user IDs, status codes), use keyword.

Tokenizers

Token filters

Custom analyzer example

PUT /products
{
  "settings": {
    "analysis": {
      "analyzer": {
        "english_autocomplete": {
          "tokenizer": "standard",
          "filter": ["lowercase", "asciifolding", "english_stop", "english_stemmer", "edge_ngram_filter"]
        }
      },
      "filter": {
        "english_stop":   { "type": "stop",   "stopwords": "_english_" },
        "english_stemmer":{ "type": "stemmer","language": "english" },
        "edge_ngram_filter":{ "type": "edge_ngram", "min_gram": 2, "max_gram": 20 }
      }
    }
  },
  "mappings": {
    "properties": {
      "name": { "type": "text", "analyzer": "english_autocomplete" }
    }
  }
}

Now “running shoes” indexes as: runn, runni, …, running, sho, shoe, shoes. A query for “run” finds it via the edge_ngram prefix.

Index-time vs query-time analyzers

By default, the same analyzer runs at both index time and query time — the query is tokenized the same way as documents, so they match.

You can override per-query:

"match": {
  "name": { "query": "running", "analyzer": "keyword" }
}

A common pattern: aggressive index-time analyzer (edge_ngram for autocomplete), simpler query-time analyzer (just lowercase) — so “fox” matches fo, fox, etc., but doesn’t itself get edge_ngrammed.

The _source field

Elasticsearch stores the original JSON document in _source. The inverted index is for searching; _source is for retrieving. You can disable _source to save space, but you lose the ability to return the original doc and to reindex without re-supplying source.

Segments and merging

Each shard is composed of immutable segments (Lucene indexes). Writes create new segments; deletes mark documents as deleted (don’t actually remove). Periodic background merging combines small segments into larger ones, applying deletes.

Implications:

• Deletes don’t free space immediately.
• Heavy update workload → many small segments → query overhead.
• _forcemerge after bulk loads is a real tuning lever.

Refresh interval

Newly indexed documents aren’t searchable immediately. They become searchable when the index is refreshed (default every 1 second). Trade-off:

• Short interval (1s): low write throughput.
• Longer interval (30s, 60s): higher throughput, staler searches.

For bulk indexing, set refresh_interval: -1 to disable, bulk-load, then re-enable.

Common gotchas

• text vs keyword confusion. text is analyzed (tokenized); keyword is exact-match. Sorting / aggregating on a text field doesn’t work as expected; you need a keyword sub-field.
• No transactions. Elasticsearch is not your source of truth; it’s a search/analytics layer over data that lives elsewhere.
• Near-real-time. 1-second refresh interval means writes aren’t immediately visible to searches.
• No JOINs. Denormalize at index time. Parent-child and nested are limited substitutes with performance costs.
• Wildcard at the start of a term (*foo) is expensive. Hits the dictionary by prefix; leading wildcard scans the whole dictionary.

Interview angle

• “What is an inverted index and why is it fast?” — term → documents map. Looking up a term is O(log N) on the dictionary, plus iterating its postings list. Beats LIKE-scan (O(N)) for anything unanchored.
• “What does an analyzer do?” — converts raw text into the tokens that go into the inverted index. Stages: character filters → tokenizer → token filters (lowercase, stemming, stop-words). Applied at index time and query time so both sides match.
• “text vs keyword?” — text is analyzed (tokenized for full-text search). keyword is one token (exact match, sortable, aggregatable). Most fields are mapped as text with a keyword sub-field via multi-fields for both behaviors.
• “What’s stemming?” — reducing tokens to a root form (“running” → “run”). Lets queries match grammatical variants. Language-specific (use english analyzer for English).
• “How do you do autocomplete?” — edge_ngram token filter at index time produces r, ru, run, runn, etc. Query at runtime as plain text against the analyzed field. Or use completion suggester for true prefix-completion with weights.
• “Why aren’t my just-inserted docs searchable?” — refresh interval (default 1s). Documents become searchable on the next refresh. For tests, force refresh: POST /index/_refresh.