Elasticsearch
A distributed search engine: inverted indexes, immutable Lucene segments, near-real-time.
Elasticsearch stores JSON documents in shards built on Apache Lucene. Text is analyzed into terms that fill an inverted index — term to document list — inside immutable segments. Writes go to an in-memory buffer and a transaction log, become a searchable segment on refresh, and segments merge in the background. Search is scatter-gather across shards.
The inverted index
An analyzer tokenizes and normalizes text; each unique term points to the list of documents containing it. Search intersects postings lists instead of scanning documents.
Immutable segments
New documents buffer in memory and land in a new segment on refresh; deletes are tombstone bits; background merges rewrite small segments into fewer large ones.
Aggregations
Doc-values column caches make group-bys and stats over matching documents fast — the analytics half of the engine next to full-text search.
Shards and replicas
An index is split into primary shards, each a self-contained Lucene instance, replicated for failover. Queries fan out to every shard of the index and merge.
The inverted index: search built backwards
A relational index maps a row to its values so rows can be found by value; an inverted index maps each term to the documents that contain it, so text queries start from the matching documents. The analyzer splits text into terms (lowercased, stemmed), and the index stores term → [doc1, doc3, …] plus term positions for phrase queries.
This is a different logical data representation from rows or documents: the unit of search is the term, and relevance scoring (BM25) ranks the postings candidates before results return.
PUT /articles
POST /articles/_doc
{ "title": "LSM + merges" }
GET /articles/_search
{ "query": { "match": { "title": "merges" } } }
Segments: write once, merge later
Indexing writes to an in-memory buffer plus a transaction log; when the refresh interval fires (one second by default) the buffer becomes a new immutable Lucene segment and the documents become searchable — near-real-time, not immediate. Deletes flip tombstone bits; merges fold segments together and drop the tombstoned docs.
The write path is unmistakably LSM-shaped: log, buffer, immutable run, background merge. The tradeoffs repeat too — merge cost and deleted-document space versus search speed.
Diagrams
[caption] LSM shape, inverted-index payload.
Documents are tokenized into terms, buffered, written as an immutable segment on refresh, and merged in the background. The transaction log covers the un-refreshed window.
| structure | term → sorted postings list |
| AND query | sorted-list intersection |
| exactness | no false positives or negatives |
| built | once at write time, by the analyzer |
All steps
- index "wired" → [d1, d3] — The analyzer tokenizes document text into normalized terms; the index stores one postings list per term pointing at the documents that contain it. Built once at write time — search never scans documents.
- index "tiger" → [d1, d2] — The analyzer tokenizes document text into normalized terms; the index stores one postings list per term pointing at the documents that contain it. Built once at write time — search never scans documents.
- index "lsm" → [d3, d5] — The analyzer tokenizes document text into normalized terms; the index stores one postings list per term pointing at the documents that contain it. Built once at write time — search never scans documents.
- index "merge" → [d2] — The analyzer tokenizes document text into normalized terms; the index stores one postings list per term pointing at the documents that contain it. Built once at write time — search never scans documents.
- Query "wired lsm" — tokenize to two terms — The same analyzer runs on the query: two terms, each with its own postings list. The AND in the query means: a document must appear in BOTH lists.
- Fetch postings: [d1, d3] ∩ [d3, d5] — Both lists are already sorted, so the intersection walks them side by side — candidate sets shrink with every term added. Only 1 of the 3 candidate ids survive.
- Intersection → d3 — Documents appearing in both postings answer the AND exactly. No false positives, no false negatives — unlike bloom filters, this is a precise membership structure.
- Rank and return — Postings carry scores (term frequency, field length); ranking sorts the exact matches. Search answered without opening a single source document — that is why search engines lead with the index.
An inverted index: terms in, document lists out. The trace builds four postings lists, then answers a two-term AND query by sorted intersection — exact matches only. This is the core structure of the search family (Lucene keeps one per analyzed field per segment).
Teaching model: 5 documents, 4 terms. Lucene adds scores, positions, and per-segment posting lists on top of the same shape.
[caption] Teaching model: 5 documents, 4 terms. Lucene adds scores, positions, and per-segment posting lists on top of the same shape.
Watch the analyzer fill four postings lists, then answer a two-term AND query by sorted intersection — exact matches only, the structure every search engine leads with.
Many small young segments collapse into fewer large ones; deleted documents are dropped at merge time.
[caption] Illustrative segment tiers for a busy write index — real tier counts follow the merge policy and indexing rate.
Many small young segments collapse into fewer large ones; deleted documents are dropped at merge time.