Inverted Index and Full-Text Search
1. Overview
Definition: An inverted index inverts the "document → word" relationship and instead stores "word (term) → the list of documents in which that word appears (posting list)", so that documents containing a specific word can be found instantly in large text without a full scan. Full-text search is a retrieval technique that, on top of this inverted index, combines tokenization, normalization, and ranking to return documents sorted by relevance for a natural-language query.
A relational database's B-tree index is optimized for quickly finding "rows whose column value exactly equals or falls within a range." However, it is not suited to a request to find documents containing the words "cloud security" among millions of posts, product descriptions, and logs. LIKE '%cloud%' cannot use an index and scans the entire table, and it also fails to reflect the nature of natural language, where a word appears multiple times and in multiple forms within one document. The inverted index solves this problem by splitting documents into words in advance and inverting the storage to "which word is in which document."
The core insight of the inverted index is that it exploits the workload characteristic that "search is overwhelmingly read-heavy and relatively write-light." If you pay the cost up front at indexing time to sort and compress the document list per word, then at query time you only need to read the posting list of that word and perform intersection/union operations. For example, "cloud AND security" merges the posting lists of the two words to find common documents, incurring a cost proportional not to the total number of documents but to the lengths of the two lists.
The reason full-text search goes beyond mere containment lies in relevance. Even when the same word is included, its importance differs depending on whether it is in the title or at the end of the body, and on how common the word is across the whole corpus. Therefore a full-text search engine sorts documents with scoring models such as TF-IDF and BM25, and absorbs the diversity of natural language through morphological analysis, synonyms, and typo correction. In a professional engineer's answer, do not explain the inverted index merely as a data structure; instead weave the indexing pipeline, query processing, ranking, compression, and operations together into a single search system.
1.1 Background and Necessity
The explosion of web and enterprise data has increased demand for unstructured text search. Portal search, e-commerce product search, log analysis (ELK), internal document search, and customer-inquiry search all need to find "documents that contain a keyword and have high relevance, quickly." A relational DB's LIKE/regex scan slows down linearly as data grows, and cannot handle the inflectional variation of natural language (search/searches/searched), spacing, and typos.
The inverted index is an old data structure from the field of Information Retrieval; it was popularized through Apache Lucene and became the core engine of Elasticsearch, OpenSearch, and Solr. The necessity is clear. If finding a specific error message among 100 million logs took several minutes with a full scan, incident response would be impossible, but with an inverted index it responds within tens of ms. In terms of search quality as well, results without ranking fail to put the documents the user wants at the top and are practically useless.
That said, an inverted index is not free. It entails operational burdens such as index storage space (tens of % to several times the original), index build/update cost, near-real-time reflection delay, and management of morphological dictionaries and synonyms. Therefore one must design "what to index, how real-time it must be, and how to tune ranking" to fit the characteristics of the work.
1.2 Core Goals
The first goal is minimizing query latency. Finding documents containing a word in time proportional to the size of that word's posting list, independent of the total number of documents, is the very reason the inverted index exists. The second goal is relevance-based sorting, placing documents the user is likely to want at the top beyond simple matching. The third goal is absorbing natural-language diversity, normalizing inflection, synonyms, typos, and multiple languages at the analysis stage to balance recall and precision. The fourth goal is storage/update efficiency, compressing posting lists and managing update cost through segment merging.
2. Structure of the Inverted Index and Index Construction
2.1 The Overall Indexing Pipeline
A full-text search system is divided into an indexing pipeline that takes documents, runs analysis, and reflects them into the inverted index, and a search pipeline that analyzes queries and merges/ranks posting lists. The indexing pipeline decomposes the original text into tokens, normalizes them, and then adds document IDs and position information to each word's posting list.
flowchart TB
DOC["Original document(title/body)"] --> CA["Character filter(HTML removal/normalization)"]
CA --> TOK["Tokenizer(morpheme/whitespace split)"]
TOK --> TF["Token filter(lowercasing/stopwords/stemming/synonyms)"]
TF --> TERMS["Normalized term list"]
TERMS --> DICT["Term Dictionary"]
TERMS --> POST["Posting list update(docID/frequency/position)"]
DICT --> SEG["Immutable Segment"]
POST --> SEG
SEG --> MERGE["Segment merge/compression"]
The analysis stage is the key that determines search quality. The character filter performs HTML-tag removal and Unicode normalization, and the tokenizer splits text into tokens. English is relatively simple on whitespace/punctuation boundaries, but Korean, as an agglutinative language, attaches particles and endings, so a morphological analyzer (mecab-ko, Nori, etc.) must extract meaning units such as "검색하다 → 검색/하다." Token filters apply lowercasing, stopword removal (the, 은, 는), stemming/lemmatization, and synonym expansion. If the same analyzer is not used at index time and search time, matching goes awry, so analyzer consistency is a basic principle of operation.
2.2 Core Data Structures — Term Dictionary and Posting List
An inverted index largely consists of a term dictionary and posting lists. The term dictionary sorts and stores all unique indexed words, and holds where in the posting list each word points (a pointer) along with the document frequency. For fast word lookup, Lucene uses a compressed dictionary based on an FST (Finite State Transducer). A posting list stores, in ascending order, the document IDs in which that word appears, and for ranking and phrase search it also holds in-document term frequency and position information.
For example, with three documents, the posting list of the word "security" is stored in the form [doc1(tf=2, pos=3,9), doc3(tf=1, pos=5)]. When the query "security" arrives, the dictionary finds "security" and reads this list immediately. The phrase search "cloud security" selects only cases from the two words' posting lists where the document IDs are the same and the positions are adjacent. In this way position information enables phrase/proximity search but increases index size.
| Component | Stored content | Role | Cost factor |
|---|---|---|---|
| Term dictionary | Unique words/DF/pointer | Entry point for word lookup | Number of unique words |
| Posting list | docID/TF/position | Matching/ranking/phrase search | Total tokens/whether positions stored |
| Segment | Immutable inverted-index unit | Physical unit of indexing/search | Number of segments/merge frequency |
| Norms/field data | Document length/sort values | Ranking normalization/sorting | Number of documents |
2.3 Immutable Segments and Near-Real-Time Updates
Lucene-family engines manage the inverted index in units of immutable segments. New documents accumulate in a memory buffer and are periodically (by default, every 1 second) flushed to a new segment, becoming searchable (near-real-time). Existing segments are not modified, and deletions are handled with deletion markers (tombstones). When many small segments accumulate, search slows, so in the background segment merging combines them into larger segments and cleans up deleted documents. This immutable/merge structure follows the same philosophy as the [[lsm-tree]]: it sequences writes and simplifies reads, but incurs merge cost and reflection delay.
3. Query Processing and Ranking
3.1 Query Processing Flow
The search query is also converted into tokens through the same analyzer as the index, and then candidate documents are obtained by reading each token's posting list and applying boolean operations (AND/OR/NOT). Next, candidate documents are scored and the top K are returned.
flowchart LR
Q["User query(cloud security)"] --> QA["Query analysis(same analyzer as index)"]
QA --> T1["Posting lookup: cloud"]
QA --> T2["Posting lookup: security"]
T1 --> MG["List merge(AND/OR)"]
T2 --> MG
MG --> SC["Score computation(BM25)"]
SC --> TOPK["Top-K sort(heap)"]
TOPK --> RES["Return results/highlights"]
Because posting lists are sorted in ascending docID order, the intersection of an AND query is computed within O(list length) by a merge that advances both lists simultaneously. To skip long lists, skip pointers are placed to reduce unnecessary comparisons. Since only the top K are needed, instead of fully sorting, a heap of size K keeps the top documents, and techniques such as WAND and Block-Max WAND prune documents that cannot make the top early, accelerating the query.
3.2 Ranking Models — TF-IDF and BM25
The basic intuitions of the relevance score are twofold. One is term frequency (TF): if a word appears often in a document, that document is more likely to be about the subject. The other is inverse document frequency (IDF): a word common to all documents (e.g., "information") has low discriminating power, so its weight is lowered. [[tf-idf]] multiplies these two to make a term-document weight. However, pure TF-IDF has limits in that the score increases linearly as frequency grows without bound and it does not correct for document length.
The default ranking of modern search engines is BM25. BM25 saturates TF so that whether a word appears 10 times or 100 times the score does not grow infinitely (parameter k1), and normalizes by document length so that a long document is not favored merely for being long (parameter b, relative to average document length). For example, Elasticsearch uses defaults k1=1.2, b=0.75. In practice, one gives extra weight (boost) to the title field and combines non-text signals such as recency/popularity via function score to adjust the final ranking.
3.3 Phrase, Proximity, Typo, and Wildcard Search
Full-text search supports various query types beyond mere word containment. In phrase search "cloud security," the two words must not only be in the document together but also appear in adjacent positions, so position information in the posting list is used to select only cases where the position difference is 1. Proximity search is a relaxed form that matches when two words are within N words of each other. Position information is included in the index for such queries, but since it enlarges the index accordingly, it is chosen based on necessity.
Typo correction (fuzzy) uses edit distance to catch even typo documents like "securty" with the query "security," and Lucene uses Levenshtein automata for this. Wildcard/prefix search finds all words starting with a prefix, as in "cloud*," for which the term dictionary is kept in a structure that allows prefix traversal. However, wildcard and fuzzy queries can cause the number of candidate matching words to explode and are therefore costly in performance, so they are complemented by separate strategies such as n-gram indexing or suffix handling. In this way, index design and cost differ by query type, so which search features to provide must be decided in advance at index time.
4. Compression and Performance Optimization
The posting list is the largest storage element in a search system, so compression is essential. The core technique is delta encoding, which stores sorted docIDs not as absolute values but as the difference from the previous value. For example, changing [1024, 1028, 1035] into [1024, 4, 7] yields small numbers, which variable-length integer compression such as VByte, PForDelta, and FOR greatly reduces in byte count. There is a natural advantage that the more frequently a word is used, the denser the docID gaps and the higher the compression ratio.
In concrete numbers, indexing 100 million documents of 500 tokens on average yields tens of billions of total posting entries, but delta encoding and VByte reduce it to about 1–2 bytes per docID on average, so the inverted index can be contained in 20–40% of the original's space. The longer the list of a frequently used word, the denser the gaps, so it is compressed to even less than 1 byte per docID.
From a performance standpoint, the inverted index turns disk I/O into sequential reads and leverages the OS page cache. Frequently used postings are kept resident in memory, skip lists skip over, and top-K pruning reduces the amount of computation. In a distributed environment, documents are divided into shards; each shard has a local inverted index, searches in parallel, and then merges the results (scatter-gather). However, global statistics such as IDF can differ per shard, causing score variance, so when precise ranking is needed, distributed frequency aggregation (DFS query-then-fetch) is used. In large log-analysis cases, indexing tens of TB of logs and processing keyword search in tens of ms is the typical effect of the ELK stack.
5. Comparison and Application Cases
5.1 Inverted Index vs. Sequential Scan vs. B-Tree
The three approaches differ in "what they are optimized for." A sequential scan (LIKE) is simple because it has no index, but it is proportional to data size linearly and unsuitable at large scale. A B-tree excels at exact-match/range search but cannot handle multiple words within one cell, inflectional variation, or relevance sorting. The inverted index is specialized for "word containment + relevance sorting + natural-language analysis" and is suited to full-text search, but it incurs index-build/storage cost and sacrifices transactional immediacy (real-time reflection delay).
| Category | Sequential scan (LIKE) | B-tree index | Inverted index |
|---|---|---|---|
| Suited queries | Small/simple | Exact/range match | Word containment/relevance search |
| Natural-language analysis | Not possible | Not possible | Tokenization/morpheme/synonyms |
| Relevance sorting | None | None | TF-IDF/BM25 |
| Large-scale performance | Linear degradation | Excellent (by key) | Excellent (by word) |
| Write immediacy | Immediate | Immediate | Near-real-time (segment) |
The crux of the comparison is not superiority but division of roles. In practice, a common hybrid structure has the relational DB handle source data and transactions, flowing changes to the search engine via [[change-data-capture]] to maintain the inverted index.
5.2 Application Cases
First, logging/observability (ELK/OpenSearch). Application logs are inverted-indexed and searched instantly by error message or transaction ID and analyzed on dashboards. [[elk-stack]] is the representative combination for this purpose. Second, e-commerce product search. Product names, descriptions, and attributes are indexed, and ranking combines BM25 with stock, popularity, and ads, while synonyms/typo correction catch "notebook/laptop" and "iphone/아이폰" together. Third, Korean document search. Morphological analysis (Nori) removes particles/endings and decomposes compound nouns to raise recall, while user dictionaries and compound-word handling are tuned so that over-decomposition does not lower precision.
6. Deep Dive — Hybrid of Keyword Search and Vector Search
The core of the latest trend is combining sparse inverted-index search and dense vector search. The inverted index's BM25 matches only when words exactly match, so it is weak on synonyms and semantic similarity (a query "car" misses an "automobile" document). Conversely, embedding-based [[vector-database]] search captures semantic similarity well but is weak on rare keywords, proper nouns, and exact matches. Thus hybrid search, which fuses the two results via RRF (Reciprocal Rank Fusion) and the like, is becoming standard, and Elasticsearch and OpenSearch also provide the ability to combine BM25 and kNN vector search in a single query.
In addition, learned sparse representations (such as SPLADE) use a neural network to convert documents into expanded word weights and store them directly in the inverted index, aiming at both the inverted index's efficiency and semantic expansion simultaneously. In the [[rag]] pipeline as well, a combination that uses a BM25 inverted index for first-stage candidate retrieval and reinforces it with vector search is common. As for likely exam directions, combined forms are strong, such as "① Explain the structure and query processing of the inverted index and discuss BM25 ranking, ② Compare keyword search and vector search and propose a hybrid design, ③ Design a large-scale log search system based on an inverted index."
7. Considerations and Implications
First, analyzer design and consistency. Most of search quality is determined by tokenization, morpheme, synonym, and stopword design. The analyzer at index time and search time must be matched, and for Korean, recall and precision must be weighed through the choice of morphological analyzer, user dictionaries, and compound-noun handling. Changing the analyzer requires a full reindex, so a change-management procedure must be in place.
Second, relevance tuning and an evaluation system. BM25 parameters, field boosts, and recency/popularity combinations must differ per task, and rather than arbitrary adjustment, they must be A/B evaluated with metrics such as NDCG/MRR based on click logs and ground-truth sets. Ranking is an engineering target improved by measurement, not by "feel."
Third, consistency and architectural boundaries. Because the inverted index is near-real-time and deletions/updates are not reflected immediately, values requiring strong consistency such as money/inventory should not treat search results as the source of truth but be re-verified against the source DB. Duplication of the source DB and the search engine maintains consistency via [[change-data-capture]] and [[transactional-outbox-pattern]], and reindexing and failure-reprocessing paths are included in the design.
Fourth, cost/operations and a scaling strategy. Index storage space, memory, and segment-merge load grow with data growth. Cost and performance are adjusted via the number of shards, replicas, and hot/warm/cold tiers (ILM), and trade-offs between feature and capacity, such as whether to index position information, are chosen to fit business requirements. Too many shards cause overhead and too few cause a scaling limit, so capacity design based on data-volume forecasting is needed.
Fifth, outlook and related technologies. Going forward, search converges into a hybrid where the BM25 inverted index (precise/efficient) and vector/LLM (semantic/conversational) coexist, and understanding it together with [[vector-database]], [[rag]], [[tf-idf]], and [[lsm-tree]] gives a view of the entire information-retrieval landscape. The inverted index is a decades-old technology, yet even in the era of generative AI it remains sound as an efficient foundation for first-stage candidate retrieval.
References
- Manning, Raghavan, Schütze, Introduction to Information Retrieval (Cambridge): https://nlp.stanford.edu/IR-book/
- Robertson & Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond: https://www.staff.city.ac.uk/~sbrp622/papers/foundations_bm25_review.pdf
- Apache Lucene official documentation: https://lucene.apache.org/core/documentation.html
- Elasticsearch Reference — Text analysis & Relevance: https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis.html
- Formal, Piwowarski, Clinchant, SPLADE: Sparse Lexical and Expansion Model: https://arxiv.org/abs/2107.05720
In one line: The inverted index is the core structure of full-text search that inverts the relationship into "word → document list" to instantly find documents containing a keyword in large text and sort by relevance with BM25; analyzer design, compression, and near-real-time updates determine quality and performance, and today it is evolving into a hybrid with vector search.