Search & inverted indexes

A job board holds 5 million open listings, each with a title and a few hundred words of description. A visitor types senior rust developer remote. The first attempt is the obvious query:

A B-tree index can't help here. It can serve a pattern anchored at the start, like 'rust%', but not one with a wildcard in front, because the B-tree is sorted by the beginning of the value (Database indexing). So the database reads all 5 million descriptions on every search. Even then the answer is wrong in ways a visitor notices immediately:

Search needs three things a table doesn't provide: a structure that goes from words to documents, rules for deciding which strings count as the same word, and a way to rank the matches. The rest of this page covers each one, then how the index is kept fresh and spread over machines.

A normal table goes from a document to its words. An inverted index goes the other way. It has two parts:

• the term dictionary: every distinct word (term) in the collection, sorted, with the number of documents that contain it (its document frequency);
• a postings list for each term: the IDs of the documents that contain it, in ascending order, usually with how often the term appears in each and at which positions.

Three tiny listings show the shape:

• listing 1: "Senior Rust developer, remote"
• listing 2: "Junior Python developer"
• listing 3: "Remote senior Python engineer"

Building it is a pipeline. Each listing is broken into terms, each term is appended to its postings list, and the dictionary is kept sorted so a term can be found quickly:

Postings are stored sorted by document ID because that makes lists cheap to combine, as the next sections show. Positions cost space, but they are what lets the engine answer a phrase like "python engineer" by checking that the two words sit next to each other.

Before text reaches the index, an analyzer turns it into terms. In Elasticsearch and Lucene, an analyzer is a fixed pipeline:

The same analyzer must run on the query. "Developers" in a listing is stored as develop; if the visitor's "developer" were not stemmed the same way, it would look up a term that isn't in the dictionary and find nothing. Analysis is a contract between index time and search time.

Every choice in the pipeline trades precision for recall:

• Stemming finds "developers" for "developer", but can merge words that differ in meaning.
• Stop words shrink the index, but a search for the band "The The" becomes empty.
• Synonyms widen matches, and need a list someone maintains.
• Typos are handled at query time instead: a fuzzy query also accepts terms within an edit or two (a changed, missing, extra or swapped letter), so "remtoe" still finds "remote".

Changing the analyzer changes the stored terms, so the whole index must be rebuilt.

A search for senior rust remote asks for listings that contain all three terms: the intersection of three postings lists. Because each list is sorted by document ID, two lists combine like a zipper. Walk a pointer down each list; when the IDs match, keep the listing and advance both, otherwise advance the pointer on the smaller ID. Two lists of lengths x and y take at most x + y steps.

The order matters. Suppose that across the 5 million listings the three terms appear in these numbers of listings, and that the terms are independent of each other:

Starting with the rarest term keeps every intermediate result no larger than its list, so engines read the document frequencies from the dictionary and order the terms before touching any postings. Long lists also carry skip pointers, shortcuts that jump over stretches of IDs that can't match, so combining 8,000 IDs with 900,000 costs far fewer than 908,000 steps.

Other query types build on the same lists:

• OR merges lists instead of intersecting them; skip pointers don't help, so a common word in an OR query is expensive.
• Phrases intersect the lists, then check that the positions are adjacent.
• Filters such as "location = Berlin" or "salary ≥ 80,000" are terms or ranges too, and are combined the same way before ranking.

Thousands of listings may match, and the visitor reads the first ten. Relevance ranking gives each match a score. Elasticsearch and Lucene use BM25 by default, which adds up a score for each query term from three ideas:

• Rare terms matter more (inverse document frequency).
• More occurrences help, with diminishing returns (term-frequency saturation).
• A match in a short field counts more than in a long one (length normalization).

Rarity is measured with the term's document frequency n in a collection of N documents: IDF = ln(1 + (N − n + 0.5) ÷ (n + 0.5)). With N = 5,000,000:

A listing that mentions Rust is worth almost four times as much as one that mentions "senior", which is what a visitor wants. Repetition is then capped. For a listing of average length, the term-frequency part is tf × (k1 + 1) ÷ (tf + k1), with the default k1 = 1.2:

Length normalization, controlled by b (default 0.75), lowers the weight in longer listings: three mentions of "rust" weigh 1.57 in a listing of average length but 1.29 in one twice as long. Real search adds business signals on top, such as freshness, location or paid placement, but text relevance is usually the base.

A recruiter posts a listing. It is saved in the job board's database, the source of truth, and must then reach the search engine. The search index is derived data: it can always be rebuilt from the database, and it is always slightly behind it.

Inside the engine, the index is written like an LSM tree (Storage engines: B-trees, LSM trees & WAL). New documents are buffered and written out as small immutable segments, each a complete inverted index of its own. A search reads every segment and merges the results. A deleted or edited listing is only marked as deleted in its old segment; background merging combines segments and finally drops those entries.

Elasticsearch makes new documents searchable with a refresh, every second by default, but only for indexes searched in the last 30 seconds. That is why it is called near real-time. A recruiter who posts a listing and searches for it immediately may not see it, so show them their own listing straight from the database.

Never update the database and the search engine as two separate writes from the app. If the second write fails, the two disagree forever. Publish the change from the database instead, with an outbox table or change data capture (CDC), which reads the database's own change log (Change data capture), make indexing idempotent so a replayed event is harmless, and keep a way to rebuild the whole index from scratch for when the analyzer changes.

One machine can't hold or serve the whole index forever, so it is split into shards. There are two ways to split an inverted index:

• By document (a local index): each shard holds every term, but only for its own share of the listings.
• By term (a global index): each shard holds whole postings lists, but only for its share of the terms.

Splitting by term sounds efficient, since a query touches only the shards that own its terms. But a multi-word query must then ship long postings lists between machines to intersect them, and popular terms overload their shards. Splitting by document is what search engines do in practice:

The number of primary shards in Elasticsearch is fixed when an index is created. Growing past it means splitting the index into a multiple of its shard count with the _split API, which needs the index read-only while it runs, or creating a new index with more shards and reindexing into it. Either way, keep the index rebuildable from the database.