Inverted Index and Full-Text Search

A full-text search system finds documents that contain given words and ranks them by relevance. A B-tree index cannot serve LIKE '%word%' or relevance ranking, and scanning every document is O(total text). The data structure that solves this is the inverted index: a map from each term to the list of documents that contain it.

Inverted index

A forward index maps a document to its terms. An inverted index reverses this: a term dictionary maps each term to a posting list, the sorted list of IDs of documents containing it.

Documents:

flowchart LR
    subgraph Dictionary
        T1["brown"]
        T2["fox"]
        T3["quick"]
        T4["lazy"]
    end
    T1 --> P1["1, 2"]
    T2 --> P2["1, 3"]
    T3 --> P3["1, 3"]
    T4 --> P4["2"]

Query quick AND fox: fetch the posting lists for quick (1, 3) and fox (1, 3), and intersect them by walking both sorted lists in parallel, giving documents 1 and 3. OR is a union. NOT is a difference. Because lists are sorted, intersection costs O(m + n) for list lengths m and n, and can be sped up with skip pointers.

Posting lists usually store more than IDs:

• Term frequency in the document (used for ranking).
• Positions of each occurrence, enabling phrase queries ("quick brown") by checking adjacent positions.
• Offsets, for highlighting matches.

Lists are stored compressed, typically as differences between consecutive IDs (delta encoding) packed in blocks with variable bit widths, which works because sorted IDs have small gaps.

The term dictionary is a sorted structure that supports exact lookup and prefix or range scans. Lucene keeps an in-memory index over the on-disk dictionary blocks, implemented as a finite state transducer (a compact automaton that maps term prefixes to block locations).

Text analysis

Before indexing, and again at query time, text passes through an analyzer:

1. Character filters normalize raw text (strip markup).
2. Tokenizer splits text into tokens (on whitespace and punctuation, per language rules).
3. Token filters transform tokens: lowercasing, removing stop words (common words such as "the"), stemming (reducing "running" and "runs" to "run"), synonyms.

The query must use compatible analysis, or terms will not match: indexing "Running" as run and searching the raw string "Running" would miss it. Language-specific analyzers exist because tokenization and stemming rules differ. Languages without spaces need dictionary or n-gram tokenization.

Prefix search and typo tolerance use additional structures: n-gram or edge n-gram indexing, or automaton-based fuzzy matching over the dictionary.

Relevance ranking

Boolean matching returns a set. Ranking orders it.

TF-IDF scores a term in a document as the product of:

• Term frequency (TF): how often the term occurs in the document. More occurrences suggest higher relevance.
• Inverse document frequency (IDF): roughly log(N / df), where N is the number of documents and df the number containing the term. Rare terms get higher weight than common ones. With N = 1,000,000 documents, a term in 100 documents has log(10,000) (about 9.2 with the natural log), while a term in 500,000 documents has log(2) (about 0.7). A query for a rare term and a common word therefore ranks documents mainly by the rare term.

BM25 is the ranking function used by default in Lucene and Elasticsearch (since Lucene 6). It refines TF-IDF:

• Term frequency saturates: the tenth occurrence adds much less than the second, controlled by a parameter k1.
• Scores are normalized by document length relative to the average, controlled by a parameter b, so long documents do not win merely by containing more words.

A query's score is the sum of the scores of its terms, and fields can be given boosts. Ranking can be combined with signals such as recency or popularity. Modern systems also combine BM25 with vector similarity for semantic search.

A minimal inverted index

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    static List<String> tokenize(String text) {
        var tokens = new ArrayList<String>();
        for (String t : text.split("[^\\p{L}\\p{N}]+")) {
            if (!t.isEmpty()) {
                tokens.add(t.toLowerCase());
            }
        }
        return tokens;
    }

    static List<Integer> intersect(List<Integer> a, List<Integer> b) {
        var out = new ArrayList<Integer>();
        int i = 0;
        int j = 0;
        while (i < a.size() && j < b.size()) {
            int x = a.get(i);
            int y = b.get(j);
            if (x == y) {
                out.add(x);
                i++;
                j++;
            } else if (x < y) {
                i++;
            } else {
                j++;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        var docs = new TreeMap<Integer, String>(Map.of(
                1, "The quick brown fox",
                2, "The lazy brown dog",
                3, "Quick red fox"));
        Map<String, List<Integer>> index = new TreeMap<>();
        for (var doc : docs.entrySet()) {
            int id = doc.getKey();
            for (String term : tokenize(doc.getValue())) {
                var list = index.computeIfAbsent(term, k -> new ArrayList<>());
                if (list.isEmpty() || list.getLast() != id) {
                    list.add(id); // ids are added in increasing order, so lists stay sorted
                }
            }
        }
        System.out.println("brown -> " + index.get("brown"));
        System.out.println("quick AND fox -> " + intersect(index.get("quick"), index.get("fox")));
        System.out.println("brown AND fox -> " + intersect(index.get("brown"), index.get("fox")));
    }
}

brown -> [1, 2]
quick AND fox -> [1, 3]
brown AND fox -> [1]

Lucene and Elasticsearch architecture

Apache Lucene is the library that implements the inverted index, analysis, and scoring. Elasticsearch (and OpenSearch, Apache Solr) is a distributed search server built on it.

Segments

Lucene stores an index as a set of segments. Each segment is an immutable, self-contained inverted index over a subset of documents.

• New documents are buffered in memory and written to a new segment on refresh. Only then are they searchable. In Elasticsearch the default refresh interval is one second (applied to indices that are being searched), which is why search is called near real-time.
• Segments are never modified. A delete marks the document as deleted in a bitmap for its segment. An update is a delete plus a new document.
• Background merges combine small segments into larger ones and physically drop deleted documents.
• A search runs against every segment and merges the results.

This is the same immutability and merge design as an LSM-tree (see storage engines: B-tree vs LSM-tree). A translog (write-ahead log) in Elasticsearch provides durability for documents not yet flushed to segments on disk.

Shards and replicas

An Elasticsearch index is divided into primary shards, each a complete Lucene index. Documents are routed to a shard by hashing a routing value (the document ID by default): shard = hash(routing) % number_of_primary_shards. (Conceptually; the exact routing arithmetic is more elaborate.) Because of this formula, the primary shard count is fixed at index creation. Changing it requires reindexing or a split operation. See sharding and partitioning.

Each primary has replica shards on other nodes for availability and to add read capacity.

flowchart TB
    C["Client"] --> CN["Coordinating node"]
    CN -->|"query phase"| S1["Shard 1 (primary or replica)"]
    CN -->|"query phase"| S2["Shard 2 (primary or replica)"]
    CN -->|"query phase"| S3["Shard 3 (primary or replica)"]
    S1 -->|"top-k doc IDs and scores"| CN
    S2 --> CN
    S3 --> CN
    CN -->|"fetch phase: get top documents"| S1
    CN --> C

Search is a scatter-gather:

1. Query phase. The coordinating node sends the query to one copy of every shard. Each shard returns its top k document IDs and scores.
2. Merge. The coordinator merges the lists into a global top k.
3. Fetch phase. It fetches the stored fields of only those documents from their shards.

Deep pagination (large from values) is expensive because every shard must return from + size entries. Elasticsearch caps from + size at 10,000 by default (index.max_result_window). Cursor-style approaches (search_after) avoid this cost by resuming after the sort values of the last hit. Relevance scores use per-shard statistics by default, so IDF can differ slightly between shards on small data.

Search engines in a system

A search index is typically a derived data store, not the primary store. The system of record is a database, and changes flow to the search index through events or change data capture. Consequences:

• Search results lag the source by the pipeline delay plus the refresh interval.
• The index can be rebuilt from the source of truth.
• Search engines are poor primary stores: no multi-document transactions, and mapping or analyzer changes require reindexing.

Interview questions

• Why is a search query on an inverted index faster than scanning? The query touches only the posting lists of its terms, whose sizes are far smaller than the corpus, and the dictionary locates them without scanning documents.
• Why does a newly indexed document not appear in search immediately in Elasticsearch? Documents become searchable only after a refresh writes the in-memory buffer as a new segment, which defaults to about once per second.
• How is a phrase query answered? Intersect the posting lists of the words, then check that positions stored in the postings are consecutive.
• What does BM25 improve on TF-IDF? It saturates the contribution of repeated terms and normalizes for document length with tunable parameters.
• Why can the number of primary shards not be changed freely? Documents are placed by hashing the routing key modulo the shard count, so a different count would change where existing documents belong.