TLDR

TLDR: An Inverted Index maps every word to the list of documents containing it — the same structure as the back-of-the-book index. It is the core data structure behind every full-text search engine, including Elasticsearch, Lucene, and PostgreSQL full-text search.

---

📖 The Textbook Index You Already Know

Open any textbook. Flip to the index at the back. Under "Binary Tree" you see: pages 42, 78, 203. That listing tells you exactly which pages to go to without reading every page.

A database full-text search without an inverted index would mean reading every document to find which ones contain "Binary Tree." For a billion documents, that's O(N).

An inverted index turns that into O(1) lookup followed by O(k log k) sort, where k = number of matching documents.

---

🔍 Terms, Documents, and Posting Lists: The Three Building Blocks

Before seeing how an inverted index is built, it helps to understand what it stores. Three concepts are central to every inverted index:

• Term — a single searchable token: a stemmed, lowercased word after stop-word removal (e.g., "running" → "run").
• Document — any unit of content that can be retrieved: a webpage, a product description, a log line, a database row.
• Posting List — the sorted list of document IDs that contain a given term, optionally extended with term position and frequency.

The name "inverted" exists because it reverses the natural direction of a forward index, which maps document → words. That direction is useful when creating or updating a document but useless when a query asks "which documents contain this word?"

A forward index is what you write; an inverted index is what you read when searching. Most production systems maintain both internally — the forward index serves deletes and updates, while the inverted index serves every read query.

---

🔢 How an Inverted Index Is Built

Given three documents:

Doc 1: "Apple is fruit"
Doc 2: "Banana is fruit"
Doc 3: "Apple and Banana are both fruit"

Step 1 — Tokenize: Split into tokens. Apply stemming ("fruits" → "fruit") and stop word removal ("is", "are", "and" removed).

Step 2 — Build posting lists:

Each posting list entry also stores the position of the word in the document (for phrase queries) and the frequency (for TF-IDF ranking).

Step 3 — Sort posting lists by document ID. Sorted order is critical for fast intersection.

📊 Inverted Index Build Pipeline

flowchart LR
    D1[Doc 1: Apple is fruit] --> T[Tokenizer]
    D2[Doc 2: Banana is fruit] --> T
    D3[Doc 3: Apple and Banana] --> T
    T --> N[Normalize (lowercase, stem, stopwords)]
    N --> M[Map term  doc list]
    M --> P[Posting Lists apple: [1,3] banana:[2,3]]
    P --> S[Store to disk (sorted by term)]

The pipeline shows how raw documents are transformed into a queryable inverted index across five stages. Documents enter a shared tokenizer, then pass through normalization (lowercasing, stemming, stop-word removal) to produce clean terms, which are mapped to their respective document IDs and finally sorted by term and written to disk. All of this work happens at index time — paying the cost once so that every subsequent query operates only on the pre-built posting lists, never on the raw documents.

---

⚙️ Executing a Query: AND, OR, and Phrase

AND Query: "Apple AND Banana"

Intersect the two posting lists:

apple:  [1, 3]
banana: [2, 3]
intersection: [3]

Since both lists are sorted, a simple two-pointer merge achieves O(m + n) intersection — no nested loops.

i → 1, j → 2:  1 < 2, advance i
i → 3, j → 2:  3 > 2, advance j
i → 3, j → 3:  MATCH → output Doc 3

OR Query: "Apple OR Banana"

Union: [1, 2, 3] — all documents containing either word.

Phrase Query: "Apple Banana" (adjacent)

Use position data: find documents in both lists where apple's position + 1 = banana's position.

📊 Query Execution: Lookup to Ranked Results

sequenceDiagram
    participant U as User Query
    participant AN as Analyzer
    participant IX as Inverted Index
    participant INT as Intersect/Union
    participant RK as Ranker (TF-IDF)

    U->>AN: "apple AND banana"
    AN->>AN: tokenize + normalize
    AN->>IX: lookup "apple"
    IX-->>AN: posting list [1, 3]
    AN->>IX: lookup "banana"
    IX-->>AN: posting list [2, 3]
    AN->>INT: intersect [1,3]  [2,3]
    INT-->>RK: doc [3]
    RK->>RK: score by TF-IDF / BM25
    RK-->>U: ranked results [Doc 3]

The sequence diagram traces a single "apple AND banana" query from the user through the full retrieval pipeline. The analyzer normalizes the query tokens, the inverted index performs two O(1) lookups to fetch both posting lists, and the intersection step merges them with a two-pointer algorithm to find matching documents; the ranker then scores the surviving document IDs by TF-IDF before returning an ordered result list. The key takeaway: query latency comes entirely from this read-time path — the raw documents are never scanned again after indexing.

---

🧠 Deep Dive: Skip Pointers and Scoring

When posting lists are large (millions of documents), pointer-by-pointer traversal is slow.

Skip pointers index every $\sqrt{n}$ entries in the list, allowing jumps:

apple: [1, 3, 7, 11, 15, 22, ...] with skip pointer at 7 → jump over 3,7 if needed

If apple[i]=3 and banana[j]=22, the skip pointer can jump directly to the first entry ≥ 22 in the apple list without touching 7, 11, 15.

---

⚙️ TF-IDF: Why "the" Ranks Lower Than "quantum"

A search for "quantum computing" should rank documents that specifically discuss quantum computing higher than documents that just happen to contain the word "quantum" once.

TF-IDF (Term Frequency – Inverse Document Frequency):

$$\text{score}(d, t) = TF(d, t) \times IDF(t)$$

$$TF(d, t) = \frac{\text{count of } t \text{ in doc } d}{\text{total tokens in doc } d}$$

$$IDF(t) = \log \frac{N}{\text{docs containing } t}$$

Intuition:

• TF: High if the term appears often in this document.
• IDF: High if the term appears in few documents overall (rare = discriminative).

"The" appears in every document → IDF ≈ 0 → score ≈ 0. "Quantum" appears in 100/1M documents → high IDF → high score in docs with high TF.

---

📊 From Raw Document to Search Results

The indexing and querying pipelines are entirely separated — a query never re-reads raw documents.

flowchart LR
    Doc["Raw Document \"Apple is fruit\""] --> Tokenize[Tokenizer split into words]
    Tokenize --> Normalize[Normalize lowercase, stem, remove stop words]
    Normalize --> Index[Inverted Index word  [docId, position, freq]]
    Index --> Query[Query: 'apple AND banana']
    Query --> Intersect[Posting List Intersection two-pointer merge]
    Intersect --> Results[Ranked Results]

The pipeline has two distinct halves: indexing (write time, left side) and querying (read time, right side).

At indexing time: raw text enters the analyzer pipeline. The tokenizer splits on whitespace and punctuation. The normalizer lowercases, applies stemming, and strips stop words. What comes out is a compact set of terms with positions and frequencies — written into the inverted index on disk.

At query time: the query string runs through the same analyzer pipeline to produce search terms. Each term is looked up directly in the index (O(1)). The resulting posting lists are intersected, unioned, or position-filtered, and the surviving document IDs are ranked by TF-IDF or BM25 before returning results.

Every millisecond of query latency comes from the query half only. The indexing half runs asynchronously and never blocks a read.

---

🌍 Real-World Applications: Inverted Indexes in Production

The inverted index pattern appears at every scale — from a smartphone notes app to a search engine crawling trillions of pages.

The pattern is consistent across all of them: the index is built offline or asynchronously, and reads are fast because they touch only the inverted index — never the raw documents.

---

🧪 Designing for Full-Text Search: Practical Decisions

When you reach for Elasticsearch or PostgreSQL full-text search, a few concrete decisions directly affect query accuracy and performance.

Keyword vs. text fields in Elasticsearch. A text field runs through the full analyzer pipeline — tokenised, lowercased, stemmed. A keyword field is stored verbatim and supports exact matching, aggregations, and sorting. Use text for long prose (product descriptions, articles) and keyword for structured values (status codes, tags, user IDs). Fields that need both behaviours use Elasticsearch's multi-field mapping, creating a text sub-field and a keyword sub-field from the same source value.

Phrase queries are more expensive than term queries. A single-term query (apple) looks up one posting list — O(1). A phrase query ("apple banana") additionally filters on position data inside the matching posting lists. For high-frequency terms, this position filter scans a large fraction of a very long list. Phrase-heavy workloads often benefit from dedicated n-gram or edge_ngram indexes that trade storage for query speed.

Segment count affects search latency. Elasticsearch writes new documents to an in-memory buffer, periodically flushing it to a new Lucene segment on disk. Searching involves scanning all segments on a shard and merging their partial results. A shard with 500 tiny segments is meaningfully slower than one with 5 merged segments of equivalent total size. The force_merge API exists specifically to reduce segment count on write-cold indexes — such as archived log indexes that will only be read, never updated.

Analyzer symmetry is non-negotiable. If you index with English stemming ("running" → "run") but query without it, the query token "running" will never appear in the index and you will get zero results. Analyzer configuration is part of the index schema — define it once, apply it at both write and query time.

---

⚖️ Trade-offs & Failure Modes: Inverted Index in Elasticsearch

Elasticsearch (built on Lucene) stores inverted indexes per shard:

flowchart LR
    Doc[New Document (JSON)] --> Analyze[Text Analyzer (tokenize, stem, stop-words)]
    Analyze --> Index[Inverted Index (term  [docId, position, freq])]
    Index --> Segment[Immutable Segment flushed to disk]
    Segment --> Merge[Merge Segments (background, periodic)]

Segments are immutable — new documents go into a new segment, not into existing ones. Periodic merging consolidates segments for query efficiency.

---

🧭 Decision Guide: When to Build an Inverted Index

Use an inverted index when your queries are term-based and the dataset is read-heavy. The build cost is paid once; fast lookups are the ongoing dividend.

---

🛠️ Apache Lucene and Elasticsearch: Building and Querying Inverted Indexes in Java

Apache Lucene is the Java library that powers Elasticsearch, Solr, and OpenSearch under the hood — it provides the exact inverted index, analyzer pipeline, and posting list machinery described in this post. Elasticsearch wraps Lucene in a distributed REST layer, sharding the inverted index across nodes and merging results from multiple shards.

How they solve the problem in this post: The snippet below builds a minimal in-memory inverted index in pure Java using HashMap (to mirror the theory), then shows how the same operation maps to a real Lucene IndexWriter — demonstrating that Lucene's abstraction maps directly to the build steps (tokenize → normalize → posting list).

import java.util.*;

// ─── Part 1: Minimal in-memory inverted index in plain Java ───────────────────
public class SimpleInvertedIndex {

    // term → sorted list of docIds
    private final Map<String, List<Integer>> index = new HashMap<>();

    /** Index a document: tokenize, lowercase, add to posting lists */
    public void addDocument(int docId, String text) {
        String[] tokens = text.toLowerCase().split("\\W+"); // basic tokenizer
        for (String token : tokens) {
            if (token.isBlank()) continue;
            index.computeIfAbsent(token, k -> new ArrayList<>()).add(docId);
        }
    }

    /** AND query: sorted-list intersection via two-pointer merge O(m+n) */
    public List<Integer> and(String term1, String term2) {
        List<Integer> left  = index.getOrDefault(term1.toLowerCase(), List.of());
        List<Integer> right = index.getOrDefault(term2.toLowerCase(), List.of());

        List<Integer> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < left.size() && j < right.size()) {
            int cmp = Integer.compare(left.get(i), right.get(j));
            if (cmp == 0) { result.add(left.get(i)); i++; j++; }
            else if (cmp < 0) i++;
            else j++;
        }
        return result;
    }

    public static void main(String[] args) {
        SimpleInvertedIndex idx = new SimpleInvertedIndex();
        idx.addDocument(1, "Apple is fruit");
        idx.addDocument(2, "Banana is fruit");
        idx.addDocument(3, "Apple and Banana are both fruit");

        System.out.println(idx.and("apple", "banana")); // → [3]
        System.out.println(idx.and("apple", "fruit"));  // → [1, 3]
    }
}

// ─── Part 2: Same operation using Apache Lucene (lucene-core 9.x) ─────────────
// Dependencies: org.apache.lucene:lucene-core:9.10.0
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.search.*;
import org.apache.lucene.store.ByteBuffersDirectory;

public class LuceneInvertedIndex {

    public static void main(String[] args) throws Exception {
        var dir      = new ByteBuffersDirectory();   // in-memory; use FSDirectory for disk
        var analyzer = new StandardAnalyzer();       // tokenize + lowercase + stop-words
        var config   = new IndexWriterConfig(analyzer);

        // Step 1 — Build the inverted index (write side)
        try (IndexWriter writer = new IndexWriter(dir, config)) {
            writer.addDocument(doc(1, "Apple is fruit"));
            writer.addDocument(doc(2, "Banana is fruit"));
            writer.addDocument(doc(3, "Apple and Banana are both fruit"));
        }

        // Step 2 — Query: AND "apple" AND "banana" (two-pointer intersection inside Lucene)
        try (var reader = DirectoryReader.open(dir)) {
            var searcher = new IndexSearcher(reader);
            var query    = new BooleanQuery.Builder()
                    .add(new TermQuery(new Term("body", "apple")),  BooleanClause.Occur.MUST)
                    .add(new TermQuery(new Term("body", "banana")), BooleanClause.Occur.MUST)
                    .build();

            TopDocs hits = searcher.search(query, 10);
            System.out.println("Hits: " + hits.totalHits.value); // → 1
            for (ScoreDoc sd : hits.scoreDocs) {
                System.out.println("  docId=" + reader.document(sd.doc).get("id"));
                // → docId=3
            }
        }
    }

    private static Document doc(int id, String body) {
        Document d = new Document();
        d.add(new StringField("id",   String.valueOf(id), Field.Store.YES));
        d.add(new TextField  ("body", body,               Field.Store.NO));
        return d;
    }
}

StandardAnalyzer applies the same tokenize → lowercase → stop-word-removal pipeline described in the post. BooleanQuery with MUST clauses performs exactly the two-pointer AND intersection under the hood. For Elasticsearch, the equivalent is a bool query with must clauses over a match query.

For a full deep-dive on Apache Lucene internals and Elasticsearch distributed search, a dedicated follow-up post is planned.

---

📚 Key Lessons from Building on Top of Inverted Indexes

• Sort order is the entire trick. Posting lists must be sorted by document ID. That single invariant enables the O(m+n) two-pointer intersection. Storing IDs in insertion order instead of sorted order breaks the ability to merge lists without a full nested-loop join.

• TF-IDF rewards rarity, not raw frequency. A document that says "quantum" 5 times outranks one that says "the" 500 times — because IDF pushes all common words toward zero regardless of their term frequency. This is why stop-word removal is a correctness optimisation, not just a space optimisation: it prevents high-frequency noise words from drowning out meaningful signal.

• Immutable segments are the key to Elasticsearch's concurrency model. Because segments are never updated in place, they need no write locks. Readers never block writers, and writers never block readers. The deliberate cost is periodic background merging — a CPU-intensive operation scheduled during off-peak hours in exchange for lock-free query performance at all times.

• Analyzers must match at write time and query time. Asymmetric analysis is the most common beginner mistake with Elasticsearch. Define your analyzer in the index mapping, confirm the index-time output with the _analyze API, and confirm the query-time output the same way before going to production.

• Skip pointers matter at scale, not at small sizes. For a posting list of 50 documents, pointer-by-pointer traversal is fine. For a list of 50 million, skip pointers can reduce traversal from O(n) to O(√n). If your dataset is small today but expected to grow, design your index schema with that growth in mind.

---

📌 TLDR: Summary & Key Takeaways

• An Inverted Index maps term → sorted list of document IDs (posting list).
• AND queries use two-pointer sorted intersection (O(m+n)).
• Skip pointers enable O(√n) jumps in large posting lists.
• TF-IDF scores documents by term frequency within the document × rarity across all documents.
• Elasticsearch stores indexes in immutable segments — new writes go to new segments; background merge consolidates them.

---

🔗 Related Posts

• How Lucene Works
• How Bloom Filters Work
• Hash Tables Explained

---