Inverted Indexes: The Heart of Search

If you've ever typed a search query and received results in under a second, you've benefited from an inverted index. This data structure—elegant in concept, sophisticated in implementation—is the foundation of every modern search engine, from Google to Elasticsearch to the search bar in your email client.

The inverted index is to search what the B-tree is to databases: a fundamental data structure that makes the impossible possible. Without it, searching billions of documents would take days instead of milliseconds. With it, search becomes so fast that we take it for granted.

Yet despite its ubiquity, many engineers have only a surface-level understanding of how inverted indexes work. This page will change that. We'll explore not just the concept, but the implementation details that separate a toy index from a production-grade search engine.

To understand inverted indexes, we must first understand what we're inverting. Let's start with the natural way documents are stored.

The Forward Index (How Documents Are Naturally Organized):

When you store documents, they're naturally organized by document ID:

Document 1: "The quick brown fox jumps over the lazy dog"
Document 2: "Quick brown foxes are faster than lazy dogs"
Document 3: "The dog chased the fox around the park"

The Search Problem:

If a user searches for "fox", we need to find all documents containing that word. With a forward index, we must scan every document:

1. Check Document 1: Contains "fox"? Yes → match
2. Check Document 2: Contains "foxes"? Yes (with stemming) → match
3. Check Document 3: Contains "fox"? Yes → match

Time complexity: O(N × M), where N = number of documents, M = average document length.

This doesn't scale. Scanning 1 billion documents × 1000 words each = 1 trillion comparisons.

The Inverted Index (Flipped Relationship):

An inverted index maps each term to the list of documents containing it:

"the"    → [Doc1, Doc3, Doc3]  (positions matter for phrases)
"quick"  → [Doc1, Doc2]
"brown"  → [Doc1, Doc2]
"fox"    → [Doc1, Doc2*, Doc3] (*"foxes" stemmed to "fox")
"jump"   → [Doc1]              ("jumps" stemmed to "jump")
"over"   → [Doc1]
"lazy"   → [Doc1, Doc2]
"dog"    → [Doc1, Doc2*, Doc3] (*"dogs" stemmed to "dog")
"fast"   → [Doc2]              ("faster" stemmed to "fast")
"chase"  → [Doc3]              ("chased" stemmed to "chase")
"around" → [Doc3]
"park"   → [Doc3]

The Search Solution:

Now searching for "fox" is a simple dictionary lookup:

1. Look up "fox" in the term dictionary
2. Retrieve the posting list: [Doc1, Doc2, Doc3]
3. Return results

Time complexity: O(log V + P), where V = vocabulary size, P = posting list length.

For most queries, this is dramatically faster than scanning all documents.

A production inverted index consists of several interconnected components. Understanding each component is essential for optimizing search performance.

Term Dictionary Deep Dive:

The term dictionary is the entry point for every search. It must support:

1. Exact lookup: Find posting list for term "fox"
2. Prefix queries: Find all terms starting with "fox" (fox, foxes, foxy...)
3. Range queries: Find all terms between "apple" and "banana"
4. Fuzzy matching: Find terms similar to "fxo" (misspelling of "fox")

Common implementations:

Posting lists contain the actual document references for each term. Their structure and encoding significantly impact both storage efficiency and query performance.

Basic Posting List Structure:

At minimum, a posting list contains document IDs:

term "fox" → [1, 2, 3, 17, 42, 100, 105, 1000, 1001, 1005]

Enhanced Posting List with Metadata:

Production systems store additional information per posting:

term "fox" → [
  { docId: 1, freq: 2, positions: [5, 42] },
  { docId: 2, freq: 1, positions: [10] },
  { docId: 3, freq: 3, positions: [1, 15, 88] },
  ...
]

• freq (term frequency): How many times the term appears in this document. Used for TF-IDF scoring.
• positions: Where the term appears in the document. Enables phrase queries.

Why Sorted Document IDs Matter:

Posting lists are sorted by document ID. This enables:

1. Efficient Intersection: Boolean AND queries require finding documents in ALL posting lists. With sorted lists, we use merge-join:

Query: "quick" AND "fox"
"quick" posting: [1, 2, 4, 7, 10]
"fox" posting:   [1, 3, 4, 6, 10, 15]

Merge intersection:
  Compare 1, 1 → Match! Add 1
  Compare 2, 3 → Advance first
  Compare 4, 3 → Advance second  
  Compare 4, 4 → Match! Add 4
  Compare 7, 6 → Advance second
  Compare 7, 10 → Advance first
  Compare 10, 10 → Match! Add 10
  
Result: [1, 4, 10]

Time complexity: O(m + n) for two lists of length m and n—dramatically better than O(m × n) for unsorted lists.

2. Compression: Sorted IDs allow delta encoding:

Original:       [1, 2, 3, 17, 42, 100, 105, 1000, 1001, 1005]
Delta encoded:  [1, 1, 1, 14, 25, 58, 5, 895, 1, 4]

Smaller values compress better using variable-byte encoding.

Raw posting list traversal is O(n) for a list of n documents. For long posting lists, this is too slow. Two key optimizations accelerate traversal: skip lists and block encoding.

Skip Lists: Jumping Ahead

A skip list adds express lanes that allow jumping over multiple postings:

Level 2:  1─────────────────────────42────────────────────────►1000
Level 1:  1─────────17──────42────────────105─────────────────►1000
Level 0:  1──2──3──17──42──100──105──1000──1001──1005

To find doc 105:
  Level 2: 1 → 42 (skip, 42 < 105) → 1000 (too far, go down)
  Level 1: 42 → 105 (found!)
  
Steps: 4 instead of 8

With skip lists, we can answer "is document X in this posting?" in O(log n) instead of O(n).

When skip lists help:

• Intersection of posting lists of different sizes
• Seeking to a specific document ID
• Early termination in top-K queries

Block Encoding: Compression + Speed

Modern indexes (Lucene, Elasticsearch) use block encoding:

1. Divide posting list into fixed-size blocks (e.g., 128 documents)
2. Store block metadata: min docId, max docId, compressed size
3. Compress each block using efficient integer compression

Posting list: [1, 2, 3, ..., 128, 129, 130, ..., 256, ...]

Block 0: docs 1-128, minId=1, maxId=128, compressed data
Block 1: docs 129-256, minId=129, maxId=256, compressed data
...

To find doc 200:
  Scan block metadata: Block 0 max=128 (skip), Block 1 max=256 (contains 200)
  Decompress Block 1, scan for 200

Benefits of block encoding:

• Skip entire blocks based on metadata
• SIMD-friendly decompression (process 128 integers at once)
• Balance between compression and access speed

Building an inverted index from a document collection is a multi-stage process. Understanding this process illuminates why indexing can be slow and how it's optimized.

The Basic Algorithm:

1. Parse documents — Extract text from each document
2. Analyze text — Tokenize, filter, normalize to produce terms
3. Build postings — For each (term, docId) pair, create a posting
4. Sort postings — Sort by (term, docId) to group postings by term
5. Merge and write — Merge sorted postings into final index structure

In-Memory Indexing (Simple but Limited):

index = defaultdict(list)

for doc_id, document in enumerate(documents):
    terms = analyze(document)  # tokenize, stem, etc.
    for term in terms:
        index[term].append(doc_id)

# Now index["fox"] = [1, 2, 3, ...]

This works for small collections but fails when the index doesn't fit in memory.

External Merge Sort for Large Collections:

For collections larger than memory, we use external sorting:

Phase 1: Build and Write Sorted Runs
┌─────────────────────────────────────────────────────┐
│ Read batch of docs → Build in-memory index         │
│ → Write sorted run to disk → Repeat                │
└─────────────────────────────────────────────────────┘

Run 1: [("apple", 1), ("apple", 3), ("banana", 2), ...]
Run 2: [("apple", 5), ("banana", 4), ("cherry", 6), ...]
Run 3: [("banana", 7), ("dog", 8), ("dog", 9), ...]

Phase 2: Merge Runs
┌─────────────────────────────────────────────────────┐
│ K-way merge: Read from all runs simultaneously     │
│ Output: Final sorted posting list per term         │
└─────────────────────────────────────────────────────┘

Final: "apple" → [1, 3, 5], "banana" → [2, 4, 7], ...

Time complexity: O(n log n) comparisons, O(n) disk I/O. Space: O(memory size) at any time, any collection size.

Inverted indexes face a fundamental challenge: they're optimized for immutability, but real systems need updates and deletes. Understanding how search engines handle mutability is crucial for schema design and performance tuning.

The Immutability Problem:

Consider updating a document with a new term:

Original: Doc 5: "the quick brown fox"
Updated:  Doc 5: "the slow brown dog"

Required changes:
- Remove Doc 5 from "quick" posting list
- Remove Doc 5 from "fox" posting list  
- Add Doc 5 to "slow" posting list
- Add Doc 5 to "dog" posting list

If posting lists are stored as compressed, sorted arrays in the middle of a file, these updates require rewriting entire lists—potentially the entire index.

Solution 1: Delete + Re-add

Most search engines treat updates as delete + add:

1. Mark old version as deleted (set a bit in deletion bitmap)
2. Index new version as a new document
3. Queries filter out deleted documents

Before update:
  "quick" → [1, 3, 5, 7]   Doc 5: active
  
After update:
  "quick" → [1, 3, 5, 7]   Doc 5: marked deleted (but still in list)
  "slow"  → [5']           Doc 5': new version (new internal ID)
  
Query for "quick":
  Get postings [1, 3, 5, 7] → Filter deleted → Return [1, 3, 7]

Pros: Simple, no posting list rewrites Cons: Deleted docs waste space until merge; extra filtering at query time

Solution 2: Segment-Based Architecture

Lucene's approach uses immutable segments:

1. New documents go into in-memory segment (fully mutable)
2. When memory fills, flush to disk as immutable segment
3. Deletes are recorded in per-segment deletion bitmaps (not in postings)
4. Merges combine small segments into larger ones, physically removing deleted docs

Timeline:
  T0: Segment 1 created [Doc1, Doc2, Doc3]
  T1: Segment 2 created [Doc4, Doc5, Doc6]
  T2: Doc2 deleted → Segment 1 delete bitmap set for Doc2
  T3: Doc5 updated → Segment 2 delete bitmap set for Doc5
                   → Segment 3 created [Doc5']
  T4: Merge (1, 2, 3) → Segment 4 [Doc1, Doc3, Doc4, Doc5', Doc6]
                       (Doc2 and old Doc5 physically removed)

This approach balances write efficiency with eventual compaction.

Compression is essential for inverted indexes. Uncompressed indexes would be larger than the original documents and too slow to traverse. Effective compression reduces storage by 5-10x while often improving query speed through better cache utilization.

Delta Encoding: The Foundation

Posting lists are sorted by document ID. Consecutive IDs are often close together. Delta encoding stores differences instead of absolute values:

Original IDs:     [100, 102, 107, 108, 150, 151, 152, 200]
Deltas (d-gaps):  [100,   2,   5,   1,  42,   1,   1,  48]

Deltas are typically much smaller than absolute IDs, requiring fewer bits.

Term Dictionary Compression:

Term dictionaries also benefit from compression:

1. Front coding: Store common prefixes once. "abstract", "abstraction", "abstracts" → "abstract" + "|ion" + "|s"

2. Block compression: Group terms into blocks, compress each block. Store first term of each block for seeking.

3. Finite State Transducers (FST): Share both prefixes AND suffixes. Achieves remarkable compression for natural language dictionaries.

Stored Field Compression:

Document content (for retrieval) is compressed using general-purpose algorithms: LZ4 (fast, moderate compression) or Zstandard (slower, better compression).