Introduction

Searching every document from beginning to end for every user query becomes expensive as the number and size of documents increase.

A relational database index usually helps locate rows using structured values such as an ID, date, status, or customer number. Full-text search has a different requirement: it must quickly identify documents containing particular words or terms.

An inverted index solves this problem by creating a mapping from searchable terms to the documents in which those terms occur.

In your System Design curriculum, Inverted Indexes is Topic 6.6 under Storage, Files, Objects & Search Basics. It follows uploads and multipart transfer and precedes full-text search.

Prerequisites

Forward Index

A forward index starts with a document and records the terms contained in that document.

Document 1:

System design requires clear requirements.


Document 2:

Database design uses indexes.


Document 3:

Search systems use inverted indexes.


Forward representation:

Document 1
    -> system
    -> design
    -> requires
    -> clear
    -> requirements

Document 2
    -> database
    -> design
    -> uses
    -> indexes

Document 3
    -> search
    -> systems
    -> use
    -> inverted
    -> indexes

This representation is useful when the system starts with a document and wants to know which terms it contains.

Inverted Index

An inverted index reverses the forward relationship. It starts with a term and records which documents contain that term.

design
    -> Document 1
    -> Document 2

indexes
    -> Document 2
    -> Document 3

search
    -> Document 3

system
    -> Document 1

database
    -> Document 2

When a user searches for design, the search system can retrieve the postings for that term instead of scanning every document.

Forward vs Inverted Index

Term Dictionary

The term dictionary contains the unique searchable terms known to the index.

Term dictionary:

architecture
availability
cache
database
design
distributed
index
latency
search
storage
system

Each term entry points to information describing the documents in which the term appears.

Postings List

A postings list is the collection of document references associated with one term.

Term:

design


Postings list:

[Document 1, Document 2, Document 7, Document 12]

A simple posting can contain only a document ID. A richer posting can contain term frequency, positions, field information, and other ranking data.

Rich Posting Example

{
  "term": "design",
  "documentFrequency": 4,
  "postings": [
    {
      "documentId": 1,
      "termFrequency": 2,
      "positions": [2, 9],
      "fields": ["title", "body"]
    },
    {
      "documentId": 2,
      "termFrequency": 1,
      "positions": [4],
      "fields": ["title"]
    }
  ]
}

Document Frequency

Document frequency records how many indexed documents contain a term.

If \(df(t)\) represents the document frequency of term \(t\), then:

\[ df(t) = \left| \left\{ d : t \in d \right\} \right| \]

A very common term generally has a high document frequency. A less common term generally has a lower document frequency.

Term Frequency

Term frequency records how often a term occurs in one document.

If \(tf(t,d)\) represents the frequency of term \(t\) in document \(d\), then:

\[ tf(t,d) = \text{number of occurrences of } t \text{ in } d \]

Document:

Inverted indexes make search efficient.
Search systems use indexes for retrieval.


Term frequency:

search = 2
indexes = 2
inverted = 1
retrieval = 1

Term frequency can contribute to ranking but should not be interpreted alone. A term occurring many times in a long document can have different importance from the same frequency in a short title.

Term Positions

A positional inverted index stores the location of each term inside the document or field.

Document tokens:

0: learn
1: inverted
2: indexes
3: for
4: fast
5: full
6: text
7: search


Stored positions:

inverted -> [1]
indexes  -> [2]
full     -> [5]
text     -> [6]
search   -> [7]

Positions support phrase queries, proximity search, highlighting, and some ranking features.

Phrase Matching

To match the phrase inverted indexes, the search system can look for documents containing both terms in adjacent positions.

Term positions:

inverted -> [1, 15]
indexes  -> [2, 20]


Phrase match:

Position 1 for inverted
followed by Position 2 for indexes


Result:

Phrase found

A non-positional index can identify documents containing both words but cannot reliably confirm that the words appear together in the requested order.

Field-aware Indexing

A search document can contain several fields with different meanings.

{
  "documentId": 42,
  "title": "Inverted Indexes",
  "description": "Learn how search systems map terms to documents.",
  "body": "A detailed explanation of indexing and postings lists.",
  "course": "System Design",
  "language": "en",
  "status": "published"
}

The index can store term occurrences separately by field:

inverted
    -> Document 42, field: title

search
    -> Document 42, field: description

postings
    -> Document 42, field: body

system design
    -> Document 42, field: course

Field-aware indexing allows a title match to carry a different ranking weight from a body-text match.

Text Analysis Pipeline

Raw text normally passes through an analysis pipeline before terms are added to the inverted index.

Raw document text
      |
      v
Character processing
      |
      v
Tokenization
      |
      v
Normalization
      |
      v
Optional stop-word handling
      |
      v
Optional stemming or lemmatization
      |
      v
Term dictionary and postings

The same compatible analysis process must be applied to search queries so query terms can match indexed terms.

Tokenization

Tokenization divides text into searchable units called tokens.

Input:

Designing scalable, reliable systems


Possible tokens:

designing
scalable
reliable
systems

Tokenization is language-sensitive. Whitespace and punctuation splitting are insufficient for every language, writing system, identifier, email address, URL, product code, or source-code document.

Normalization

Normalization converts text into a consistent searchable representation.

Input forms:

Database
DATABASE
database


Normalized term:

database

Normalization can include:

• Case normalization
• Unicode normalization
• Accent handling
• Punctuation rules
• Whitespace normalization
• Language-specific character handling

Stop Words

Stop words are common terms that a search configuration can choose to omit or treat specially.

Possible common terms:

a
an
and
is
of
the
to

Removing common words can reduce index size, but it can also break meaningful phrases, names, quotations, titles, or domain-specific queries.

Stop-word handling should be based on measured user searches and domain requirements.

Stemming

Stemming reduces related word forms to an algorithmically produced stem.

Possible related inputs:

connect
connected
connecting
connection
connections


Possible stem:

connect

A stem does not always need to be a valid dictionary word. Aggressive stemming can merge terms that users consider different.

Lemmatization

Lemmatization attempts to reduce a word to a dictionary form using language-aware analysis.

Word forms:

is
are
was
were


Possible lemma:

be

Lemmatization can produce linguistically meaningful forms but can require more complex language processing.

Stemming vs Lemmatization

Index-time vs Query-time Analysis

Indexed text:

Scalable Databases


Index-time normalized terms:

scalable
database


User query:

SCALABLE database


Query-time normalized terms:

scalable
database


Result:

Compatible terms match

Incompatible analyzers can produce terms that never match even when the displayed text appears related.

Single-term Search

A single-term query reads the postings list associated with the analyzed term.

Query:

index


Postings:

[2, 7, 8, 15, 21]


Result candidates:

Documents 2, 7, 8, 15, and 21

The search system then applies filters, scoring, sorting, and authorization before returning results.

AND Query

An AND query requires documents to appear in every required postings list.

Term: inverted

Postings:
[2, 7, 10, 15]


Term: index

Postings:
[1, 2, 7, 8, 15, 21]


Intersection:

[2, 7, 15]

The intersection contains documents with both terms.

OR Query

An OR query accepts documents present in at least one postings list.

Term: storage

Postings:
[1, 4, 9]


Term: database

Postings:
[2, 4, 8]


Union:

[1, 2, 4, 8, 9]

NOT Query

A NOT condition removes documents that appear in the excluded term's postings.

Required term: database

Postings:
[2, 4, 8, 11]


Excluded term: relational

Postings:
[4, 11]


Result:

[2, 8]

Pure negative queries can require special treatment because the system needs a defined universe of candidate documents.

Postings-list Intersection

When postings lists are sorted by document ID, the search engine can intersect them efficiently.

List A:

[2, 7, 10, 15, 22]


List B:

[1, 7, 9, 15, 19]


Compare values from left to right:

2 vs 1
2 vs 7
7 vs 7 -> match
10 vs 9
10 vs 15
15 vs 15 -> match


Intersection:

[7, 15]

Additional skip information or specialized algorithms can reduce comparisons for long postings lists.

Sorted Postings

Postings are commonly stored in an ordered form to support efficient intersection, union, compression, and skipping.

Term:

search


Sorted postings:

3, 8, 20, 21, 40, 100, 104

Instead of storing every complete document ID independently, the index can store differences between consecutive IDs.

Document IDs:

3, 8, 20, 21, 40


Gaps:

3, 5, 12, 1, 19

Smaller gap values can often be encoded using fewer bits.

Index Compression

Inverted indexes can become large because they store terms, document references, frequencies, positions, and field data.

Compression techniques can target:

• Term dictionary storage
• Document-ID gaps
• Term frequencies
• Position differences
• Field information
• Repeated metadata values

Compression reduces storage and I/O but adds encoding and decoding work.

Term Ordering

The term dictionary can use a sorted or otherwise searchable representation.

api
architecture
availability
cache
database
durability
index
latency
search
storage

A sorted term space can support exact lookups and some forms of prefix navigation. Specialized structures can be used for more advanced term lookup requirements.

Ranking Information

The inverted index supplies candidate documents and term statistics that can contribute to ranking.

Useful ranking signals include:

• Term frequency in the document
• Document frequency across the collection
• Field in which the term matched
• Document length
• Term proximity
• Phrase match
• Document freshness
• Business importance
• Language compatibility

The inverted index is the retrieval foundation. The complete ranking formula belongs to the full-text search layer.

IDF Intuition

Inverse document frequency gives rarer terms more distinguishing value than terms appearing in nearly every document.

A simplified form is:

\[ IDF(t) = \log \left( \frac{N}{df(t)} \right) \]

Where:

• \(N\) is the total number of indexed documents
• \(df(t)\) is the number of documents containing term \(t\)

Implementations can use smoothed or modified formulas. The equation above illustrates the intuition rather than prescribing a specific search-engine formula.

B-tree vs Inverted Index

Indexing a New Document

New document arrives
      |
      v
Validate document metadata
      |
      v
Extract searchable fields
      |
      v
Analyze each field
      |
      v
Create term occurrences
      |
      v
Add document postings
      |
      v
Publish searchable index state

The authoritative document may be stored in a relational database, document database, file store, or object-storage service. The search index is commonly a derived representation.

Updating a Document

When searchable content changes, the old indexed terms must no longer represent the current document.

Document version 1:

"Database indexing basics"


Document version 2:

"Inverted index fundamentals"


Required index update:

Remove or supersede
old version postings

Add postings for
new version terms

Some implementations write a new document version and mark the previous version deleted until segment merging removes obsolete data physically.

Deleting a Document

Delete request
      |
      v
Authorize deletion
      |
      v
Delete authoritative document
or mark it deleted
      |
      v
Publish deletion event
      |
      v
Remove or mask search-index document
      |
      v
Verify that searches no longer return it

A derived search index can lag behind the source of truth. Security-sensitive deletion or access revocation may require immediate query-time filtering in addition to asynchronous reindexing.

Immutable Index Segments

Search systems commonly write new index data into segments that are not modified in place after publication.

Segment 1:

Older indexed documents


Segment 2:

Newly indexed documents


Segment 3:

Recent updates and deletions


Search:

Query all active segments
and combine results

Immutable segments simplify concurrent reading and durable publication, but many small segments can increase search overhead.

Segment Merging

Segment merging combines smaller index segments into larger segments.

Segment A
    \
     \
      +--> Merge --> Segment D
     /
    /
Segment B


During merge:

- Combine term dictionaries
- Combine postings
- Remove obsolete documents
- Apply deletions
- Rewrite compressed structures

Merging consumes CPU, storage bandwidth, and temporary disk space. Search and indexing performance should be monitored during merge activity.

Near-real-time Search

A document can be committed in the authoritative database before it becomes visible in the search index.

Document transaction commits
        |
        v
Indexing event is published
        |
        v
Search consumer processes event
        |
        v
New index segment becomes visible
        |
        v
Document appears in search

This delay is commonly called indexing lag or search freshness delay.

Indexing Pipeline

Authoritative content
      |
      v
Change event or scheduled retrieval
      |
      v
Content extraction
      |
      v
Metadata validation
      |
      v
Text analysis
      |
      v
Search-document construction
      |
      v
Index write
      |
      v
Searchable publication

The pipeline should be idempotent because events and indexing requests can be delivered more than once.

Idempotent Indexing

A search document should use a stable identifier so repeated processing updates the same logical index entry instead of creating duplicates.

{
  "searchDocumentId": "tenant-17:article-981",
  "sourceVersion": 12,
  "title": "Inverted Indexes",
  "status": "published"
}

The consumer can compare source versions to avoid replacing newer indexed content with an older event.

Out-of-order Updates

Version 12 event:

Delayed in queue


Version 13 event:

Processed first


Version 12 arrives later


Unsafe result:

Version 12 overwrites Version 13


Safe result:

Index consumer compares source version
and rejects the stale update

Stable document IDs and monotonic source versions support safer indexing under delayed or reordered events.

Security Trimming

Search results must be limited to documents the caller is allowed to discover.

Text query
      |
      v
Retrieve candidate documents
      |
      v
Apply tenant filter
      |
      v
Apply publication and visibility filters
      |
      v
Apply user or group access rules
      |
      v
Return authorized results

Authorization can be applied through indexed access-control fields, query-time authorization checks, or a combination of both.

Tenant-aware Indexing

{
  "documentId": "article-981",
  "tenantId": "tenant-17",
  "visibility": "course",
  "courseId": "course-42",
  "status": "published",
  "title": "Inverted Indexes",
  "body": "Searchable article content"
}

Every search query should apply trusted tenant scope rather than accepting an arbitrary client-supplied tenant filter as authorization.

Structured Filters with Full-text Terms

Search queries commonly combine inverted-index text retrieval with structured metadata filters.

Text:

"inverted index"


Filters:

tenant_id = tenant-17
status = published
language = en
course_id = course-42
visibility permits current learner

Structured filters reduce the candidate set and enforce business or security requirements.

Simplified SQL Representation

Production full-text engines use specialized compressed structures, but a simplified relational model can demonstrate the terms and postings concept.

CREATE TABLE search_terms
(
    term_id BIGINT PRIMARY KEY,
    normalized_term VARCHAR(200) NOT NULL,

    CONSTRAINT uq_search_terms_value
        UNIQUE (normalized_term)
);

CREATE TABLE search_documents
(
    document_id BIGINT PRIMARY KEY,
    tenant_id BIGINT NOT NULL,
    source_type VARCHAR(50) NOT NULL,
    source_id BIGINT NOT NULL,
    source_version BIGINT NOT NULL,
    language_code VARCHAR(20) NOT NULL,
    document_status VARCHAR(30) NOT NULL,

    CONSTRAINT uq_search_document_source
        UNIQUE
        (
            tenant_id,
            source_type,
            source_id
        )
);

CREATE TABLE search_postings
(
    term_id BIGINT NOT NULL,
    document_id BIGINT NOT NULL,
    field_name VARCHAR(50) NOT NULL,
    term_frequency INT NOT NULL,

    PRIMARY KEY
    (
        term_id,
        document_id,
        field_name
    ),

    CONSTRAINT fk_postings_term
        FOREIGN KEY (term_id)
        REFERENCES search_terms (term_id),

    CONSTRAINT fk_postings_document
        FOREIGN KEY (document_id)
        REFERENCES search_documents (document_id)
        ON DELETE CASCADE,

    CONSTRAINT ck_postings_frequency
        CHECK (term_frequency > 0)
);

This schema is educational. Storing every term position and executing full-text ranking through ordinary SQL tables is generally not equivalent to a purpose-built full-text search implementation.

Simplified PHP Tokenizer

<?php

declare(strict_types=1);

function tokenizeForSearch(
    string $text
): array {
    $normalized =
        mb_strtolower(
            trim(
                $text
            ),
            'UTF-8'
        );

    $tokens =
        preg_split(
            '/[^\p{L}\p{N}]+/u',
            $normalized,
            -1,
            PREG_SPLIT_NO_EMPTY
        );

    if (!is_array($tokens)) {
        return [];
    }

    return array_values(
        $tokens
    );
}

This basic example is not a universal tokenizer. Production analysis should account for language, Unicode normalization, domain terms, identifiers, punctuation, and the selected search engine's analyzer.

Build a Simplified Inverted Index

<?php

declare(strict_types=1);

function buildInvertedIndex(
    array $documents
): array {
    $index = [];

    foreach ($documents as $documentId => $text) {
        $tokens =
            tokenizeForSearch(
                (string)$text
            );

        $frequencies =
            array_count_values(
                $tokens
            );

        foreach (
            $frequencies
            as $term => $frequency
        ) {
            $index[$term][$documentId] = [
                'termFrequency' =>
                    $frequency
            ];
        }
    }

    ksort(
        $index
    );

    return $index;
}

Example Input

$documents = [
    1 => 'System design needs clear requirements.',
    2 => 'Database design uses indexes.',
    3 => 'Search systems use inverted indexes.'
];

$index =
    buildInvertedIndex(
        $documents
    );

A real search engine also manages positions, fields, compression, persistence, segments, deletion, ranking, concurrency, and distributed execution.

Sharding the Index

A large search index can be divided into shards.

Document-based Sharding

Shard 1:

Documents 1 through 1,000,000


Shard 2:

Documents 1,000,001 through 2,000,000


Each shard contains:

Its own term dictionary
and postings for its documents

A query is sent to relevant shards, and the results are merged.

Term-based Sharding

Shard A:

Terms beginning with A through F


Shard B:

Terms beginning with G through M


Shard C:

Terms beginning with N through Z

Term-based partitioning can complicate multi-term queries because different terms can reside on different shards.

The best partitioning strategy depends on workload, document distribution, query fan-out, update patterns, tenant boundaries, and search-engine design.

Index Replication

Primary shard
    |
    +-- Replica 1
    |
    +-- Replica 2

Replicas can support read capacity and failure recovery. Search freshness and replica synchronization should be monitored.

Rebuilding the Index

Because an inverted index is commonly derived from authoritative content, it should have a documented rebuild process.

Read authoritative documents
        |
        v
Build replacement index
        |
        v
Validate document counts,
sample queries,
security filters,
and freshness
        |
        v
Switch searches to replacement index
        |
        v
Retire old index safely

Rebuilding can be necessary after analyzer changes, schema changes, corruption, ranking-field changes, or major data correction.

Reindexing after Analyzer Changes

Changing tokenization, normalization, stemming, or stop-word rules changes the terms generated from existing documents.

Old analyzer:

"databases" -> databases


New analyzer:

"databases" -> database


Existing index:

Contains old term


Required action:

Reprocess source documents
and build terms using new analyzer

Query-time changes alone do not rewrite previously indexed terms.

Schema and Analyzer Versioning

{
  "documentId": "tenant-17:article-981",
  "sourceVersion": 12,
  "indexSchemaVersion": 3,
  "analyzerVersion": 2,
  "indexedAt": "indexing-time"
}

Version metadata helps identify which search documents require reindexing.

Indexing Performance

Indexing performance depends on:

• Document size
• Number of indexed fields
• Token count
• Position storage
• Analyzer complexity
• Indexing batch size
• Segment creation and merging
• Storage throughput
• Replication
• Refresh frequency

Indexing every available field can increase index size and processing cost without improving useful search.

Stored Fields vs Indexed Fields

Avoid storing large original content in the search index when the application can retrieve authoritative content after obtaining authorized document IDs.

Highlighting

Term positions and offsets can help generate result snippets with matched text highlighted.

Original text:

An inverted index maps searchable terms
to documents containing those terms.


Query:

searchable terms


Highlighted snippet:

An inverted index maps
[searchable terms]
to documents containing those terms.

Highlighted snippets should be encoded safely before being rendered in HTML.

Prefix Search

Prefix search matches terms beginning with a supplied prefix.

Prefix:

data


Possible matching terms:

data
database
datacenter
dataset

Prefix expansion can produce many matching terms. Apply length, expansion, and resource limits.

Fuzzy Search

Fuzzy search attempts to match terms within a configured edit distance.

Query:

databse


Possible candidate:

database

Fuzzy expansion is a query feature built over indexed terms. Excessively broad fuzzy settings can increase query cost and reduce result precision.

Index-design Workflow

1. Identify the authoritative document sources.
2. Define a stable search-document identifier.
3. Choose searchable fields.
4. Choose structured filter fields.
5. Identify each field's language.
6. Define tokenization and normalization.
7. Decide whether stop words should be retained.
8. Decide whether stemming or lemmatization is appropriate.
9. Decide whether term positions and offsets are required.
10. Define security-trimming fields.
11. Define source and analyzer versions.
12. Build an idempotent indexing pipeline.
13. Define freshness and deletion objectives.
14. Define rebuild and reconciliation procedures.
15. Measure relevance, index size, latency, and indexing throughput.

Inverted-index Observability

Useful index metrics include:

• Indexed document count
• Unique-term count
• Postings count
• Index size
• Indexing throughput
• Indexing failure count
• Indexing lag
• Documents awaiting indexing
• Deleted documents pending merge
• Segment count
• Segment-merge duration
• Search latency
• Query fan-out
• Replica synchronization delay
• Authorization-filter failures
• Documents using obsolete analyzer versions

Alert Conditions

Alert when:

• Indexing lag exceeds its objective
• The failure or retry backlog grows
• Deleted or restricted content continues appearing in search
• Segment count increases unexpectedly
• Merges consume excessive storage or processing resources
• Replica synchronization fails
• Indexed document counts diverge from authoritative sources
• Security-filter fields are missing
• Reindexing stops before all documents reach the current schema version

Inverted-index Troubleshooting

1. Identify the query and caller's trusted tenant scope.
2. Analyze the query using the configured analyzer.
3. Inspect the resulting query terms.
4. Confirm the expected terms exist in the dictionary.
5. Inspect the relevant postings lists.
6. Confirm the document was indexed.
7. Compare source and indexed document versions.
8. Check language and analyzer configuration.
9. Check stop-word, stemming, and normalization rules.
10. Check metadata and security filters.
11. Check indexing lag and failed events.
12. Reindex or rebuild from the authoritative source when required.

Common Inverted-index Mistakes

Recommended Test Cases

Inverted-index Best Practices

Practice Exercise

Build a simplified inverted index for articles on your online learning platform.

Requirements

1. Create sample articles containing title, description, body, language, and status.
2. Assign one stable search-document ID to each article.
3. Normalize text to lowercase using a defined Unicode strategy.
4. Tokenize the title, description, and body separately.
5. Record term frequency by document and field.
6. Record positions for phrase matching.
7. Create a term dictionary.
8. Create sorted postings lists.
9. Support single-term queries.
10. Support AND and OR queries.
11. Support a two-term phrase query.
12. Filter results by tenant, language, and publication status.
13. Update one article and replace its indexed terms.
14. Delete one article from search.
15. Reject an out-of-order indexing event.
16. Measure index size and retrieval time.

Search-document Template

Frequently Asked Questions