Inverted Index: How Search Engines Work (BM25)

Q: What is the difference between a forward index and an inverted index?

A forward index maps each document to the terms it contains — essentially the document itself, or a processed list of its words — which is efficient for answering "what is in document 42?" but useless for search, because finding every document containing a given word would require scanning every entry. An inverted index flips the mapping: each term points to a posting list of all documents containing it, typically with per-document frequency and token positions. Answering "which documents mention kubernetes?" becomes a single dictionary lookup that returns a pre-computed list, and multi-word queries become intersections or unions of such lists. The cost moved from query time to index time: every document is analyzed once when written, and every query thereafter touches only the posting lists of its terms, making query cost proportional to the number of matching documents rather than corpus size. The name "reverse index" or "reverted index" appears informally for the same structure — the canonical term in information-retrieval literature and in Lucene, Elasticsearch, and OpenSearch documentation is inverted index. Real systems keep both: the inverted index answers the search, and forward-index-like structures (doc values, stored fields) supply the found documents' content for display and ranking features.

Q: How does BM25 scoring actually work?

BM25 ranks the documents that matched a query by combining three intuitions, each with a tunable knob. First, term frequency with saturation: a document mentioning the query term five times scores higher than one mentioning it once, but the benefit flattens quickly — the twentieth occurrence adds almost nothing — controlled by the k1 parameter (default around 1.2), which prevents keyword-stuffed documents from dominating. Second, inverse document frequency: terms that are rare across the corpus carry far more signal than common ones, so matching "kubernetes" contributes much more than matching "the"; this weighting is automatic from corpus statistics. Third, length normalization: a match inside a 100-word document is stronger evidence of relevance than the same match inside a 10,000-word document, with the b parameter (default 0.75) controlling how aggressively long documents are discounted. Each query term's contribution is computed this way and summed into the document's score, and the top-k scored documents are returned. BM25 has been Lucene's default scorer since version 6 — hence Elasticsearch's and OpenSearch's — because it is robust across corpora with the default parameters, and decades of information-retrieval evaluation have made it the baseline every newer method is measured against.

Q: Why are Lucene segments immutable and what are merges?

Lucene never modifies an index file after writing it. Documents accumulate in an in-memory buffer and are periodically flushed as a segment — a complete, self-contained mini-index that is immutable from birth. This design buys three big properties. Concurrency: readers never take locks because nothing they read can change underneath them; a search simply opens the current set of segments. Caching: immutable files are perfectly cacheable by the operating system's page cache, which is a large part of why hot indexes serve queries from memory. Durability: crash recovery is trivial since a segment is either fully written or ignored. The costs are handled by two mechanisms. Updates and deletes cannot touch existing segments, so a delete writes a tombstone marker and an update is a delete plus a re-insert into a new segment — meaning "deleted" documents still occupy space and are filtered at query time. Background merges fix this: Lucene continuously compacts small segments into larger ones, physically dropping tombstoned documents in the process, which bounds both segment count (fewer files to search per query) and wasted space. Merge policy tuning — how aggressively to compact — is one of the few genuinely operational knobs in heavy-write deployments.

Q: How is Elasticsearch related to Lucene?

Lucene is the search library — the actual inverted index implementation, analyzers, segment machinery, and BM25 scoring — embedded as a Java library with no server, no API, and no clustering of its own. Elasticsearch wraps Lucene into a distributed system: an Elasticsearch index is split into shards, and each shard is a complete, independent Lucene index; documents route to shards by ID hash; queries fan out to all shards in parallel and merge their top-k results; replicas of each shard provide redundancy and read throughput. On top it adds the REST API, JSON documents and mappings, cluster coordination, and the operational layer (snapshots, security, monitoring). OpenSearch is the Apache-2.0 fork of Elasticsearch (from version 7.10) maintained by an AWS-led community, with the same Lucene core and largely compatible APIs. The practical division for operators: core search behaviour — analysis, posting lists, BM25, segments — is Lucene and identical across both; scaling, sharding, refresh intervals, and cluster health are the distribution layer where production tuning actually happens. The famous "near-real-time" property comes from this layering too: a document becomes searchable at the next segment flush (the refresh interval, ~1 second by default), not at the instant it is written.

Q: Why does RAG still need BM25 and an inverted index in 2026?

Because embedding-based retrieval systematically misses a class of queries that lexical matching handles trivially, and production corpora are full of them. Dense vectors represent meaning, which makes them excellent at paraphrase — "how do I make my app faster" finds performance-tuning documents — but blurry on exact tokens: product SKUs, error codes, function names, invoice numbers, legal citations, person names, and rare domain jargon all embed poorly because they are semantically thin and often out-of-vocabulary for the embedding model. A vector-only RAG system asked about "error E4402" will happily return passages about errors in general while missing the one document containing that literal string. BM25 over an inverted index has exactly the complementary profile: perfect on literal terms, blind to paraphrase. That is why production retrieval in 2026 is predominantly hybrid — both retrievers run, and reciprocal-rank fusion or a cross-encoder reranker merges results — and why measured retrieval improvements, including Anthropic's published contextual-retrieval numbers, are reported with BM25 in the loop. The operational bonus: the inverted index adds near-zero cost next to GPU-backed embedding search, so the hybrid's lexical half is usually the cheapest recall improvement available to a RAG system.

Q: How big is an inverted index compared to the original text?

A typical full-text inverted index lands at roughly 25-40% of the raw corpus size with standard settings, and the compression techniques are what make that possible. Posting lists store document IDs in sorted order, so instead of absolute IDs they store deltas — the gaps between consecutive IDs — which are small numbers, encoded in variable-length integers (or block-packed schemes like Lucene's) that use one or two bytes for most gaps. Term frequencies are small integers that compress the same way, and positions (needed for phrase queries) are again stored as deltas within a document. Concretely: a 10-million-document corpus of ~1KB articles — about 10GB of raw text — typically produces a 2-4GB index, which fits in the RAM of an ordinary server, and that residency is why query latency is 5-50ms rather than disk-bound. What moves the ratio: indexing positions and offsets grows it (phrase and highlight support), stop-word removal and aggressive stemming shrink it, and storing the original documents alongside the index (as Elasticsearch does by default in _source) roughly doubles total disk, though that part is storage, not the searchable structure. The scaling rule of thumb is linear: index size and indexing time grow proportionally with corpus size, while query latency grows far slower thanks to the lookup structure.

Q: What are analyzers and why must they match between indexing and querying?

An analyzer is the text-processing pipeline that turns raw text into the terms actually stored in the index: tokenization (splitting on whitespace and punctuation, or language-aware rules), lowercasing, and optional steps like stemming (reducing "running" to "run"), stop-word removal, synonym expansion, and character normalization. Analysis decisions define what "matching" means — stemming trades precision for recall, keeping stop-words preserves exact-phrase fidelity, keyword-type fields skip analysis entirely so identifiers like SKU-8842 match only literally. The matching rule is absolute: the query must pass through the same analysis as the indexed text, because the index contains only the processed terms. If documents were indexed with stemming ("running" stored as "run") but the query pipeline does not stem, a search for "running" looks up a term that does not exist in the index and silently returns nothing — no error, just missing results, which makes analyzer mismatch one of the most common and hardest-to-notice search bugs. The practical disciplines: define analyzers explicitly per field rather than relying on defaults, index identifiers and codes as unanalyzed keyword fields alongside analyzed text fields, and when search "randomly misses," test the analyzer output of both the indexed document and the query before touching anything else.

Q: When should I use Elasticsearch versus Postgres full-text search?

Postgres full-text search runs the same conceptual machinery — an inverted index (GIN) over processed tokens with relevance ranking — inside the database you already operate, and for a large class of applications that is the right call: corpora up to a few million rows, moderate query volume, search as a feature rather than the product, and a strong preference for one system of record with transactional consistency between data and index. It removes an entire service from your architecture, and its ranking, while simpler than BM25, is adequate for utility search. Reach for Elasticsearch or OpenSearch when any of these hold: corpus or query volume needs horizontal scaling across shards and replicas; relevance quality is product-critical and you need real BM25, per-field analyzers, language handling, synonyms, and tunable scoring; you need search-native features — aggregations/facets, highlighting, suggesters, fuzzy matching — that Postgres approximates awkwardly; or search traffic must be isolated from your transactional database's capacity. The failure mode to avoid in both directions: teams running a dedicated search cluster for ten thousand rows of utility search, and teams torturing Postgres into serving faceted product search at millions of queries per day. Size the tool to the corpus, the QPS, and how load-bearing relevance is.

Satyam Kumar

返回博客

ai-architecture

Inverted Index Architecture: How Search Engines Work (BM25, Lucene, Elasticsearch)

By Satyam KumarJuly 4, 20268 min read

inverted index reverse index bm25 lucene elasticsearch opensearch full-text search posting list search engine architecture keyword search hybrid search information retrieval text analysis rag retrieval ai architecture patterns 2026

Inverted Index Architecture: How Search Engines Work (BM25, Lucene, Elasticsearch)

Frequently Asked Questions

分享这篇文章

Twitter LinkedIn WhatsApp

Satyam Kumar

Founder & AI Architect, AppScale LLP

人工智能和云架构师。帮助团队构建可扩展到数百万的系统。

LinkedIn GitHub

Inverted Index Architecture: How Search Engines Work (BM25, Lucene, Elasticsearch)

Frequently Asked Questions

分享这篇文章

Comments

Leave a comment