Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 43 ยท How Search Works

The Inverted Index

See how Elasticsearch finds documents so fast: terms, postings lists, the term dictionary, doc values, and immutable segments, with a runnable index in Node.

Why can Elasticsearch search ten million documents in a few milliseconds, when a LIKE '%word%' query in a database has to read every row? The answer is a data structure called the inverted index. It is the central idea of every search engine, from Lucene (inside Elasticsearch) to the one in your phone's mail app.

This lesson explains the inverted index, the term dictionary and postings lists that make it up, why a second structure called doc values exists, and why the files on disk are never edited in place. You will build a working inverted index in Node on Piston. That code is a stand-in that shows the principle; Lucene's real file formats are far more compact and sophisticated, and the real engine is not running here.

From documents to terms

Start with three tiny documents:

id text
1 the quick brown fox
2 the lazy brown dog
3 quick quick dog

A normal ("forward") index maps each document to its words: document 1 contains the, quick, brown, fox. To find "dog" you have to open every document and look.

An inverted index flips this around. It maps each word, called a term, to the list of documents that contain it:

term documents
brown 1, 2
dog 2, 3
fox 1
lazy 2
quick 1, 3
the 1, 2

Now a search for "dog" is a lookup of one row, and the answer (documents 2 and 3) is already there. Searching is no longer proportional to the amount of data, only to the number of matching documents.

The list of document ids for a term is called a postings list. Real postings also store extra information: how many times the term occurs in each document (needed for scoring, see Relevance Scoring with BM25) and, optionally, the positions of each occurrence (needed for phrase search such as "quick brown").

The term dictionary

All distinct terms of a field are kept in a sorted term dictionary. Sorting lets the engine find a term with a fast search instead of a scan. Lucene stores the dictionary in a compact structure (a finite state transducer held mostly in memory) that supports:

  • exact lookups ("dog");
  • prefix lookups ("qu" finds quick), because sorted terms with the same prefix sit next to each other;
  • range and wildcard-style traversals over terms.

Each dictionary entry points to its postings list on disk. Postings lists are sorted by document id and compressed (differences between consecutive ids are stored, in small blocks). Sorted lists also make combining terms cheap: to answer "quick AND dog", the engine walks the two sorted lists together and keeps the ids that appear in both. For "OR" it merges them.

Combining postings

The stand-in below builds the index above in code. It also answers AND and OR queries by walking sorted lists, the way a search engine does. Note that the code works on the terms and the postings, never on the original text, once the index exists.

Node.js Build an inverted index and query it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

The output shows quick -> 1(x1) 3(x2): term quick appears once in document 1 and twice in document 3. The AND query returns only document 3, because it is the only one with both words. cat has no postings, so the answer is empty without reading any document.

Doc values: the other direction

The inverted index is superb for "which documents contain this term?" but poor for the opposite question: "what is the value of price in document 17?". Sorting by price, computing an average or grouping by country all need exactly that, for many documents in a row.

For these jobs Elasticsearch builds a second structure at index time, doc values. It is a column-oriented, on-disk store: all values of one field are laid out together, indexed by document number. Doc values are enabled by default for almost every field type (not for analyzed text fields). They power:

Because they are on disk and read through the operating system's file cache, they do not need to fit in the JVM heap. The trade is disk space: a field with both structures is stored twice, in two different shapes. If you will never search a field, you can turn off its index; if you will never sort or aggregate on it, you can turn off its doc values. See Mappings and Field Types.

Two structures, two questions

Inverted index Term to documents. Powers search.
Doc values Document to value. Powers sort and aggregations.
_source The original JSON, for display.

One document is stored in several shapes.

1 / 2

Immutable segments

Lucene never edits an index file after writing it. New documents are collected in memory and written out as a complete, self-contained, read-only unit called a segment. A shard is a set of segments; a search runs over each segment and merges the results.

Immutability has large benefits:

  • no locks are needed for readers, so many searches run in parallel;
  • the operating system can cache segment files very effectively;
  • compression and structures can be tuned once, at write time.

It also explains behavior that surprises newcomers. Deleting a document does not remove it from its segment; the document is only marked in a "deleted" list and skipped by searches. Updating is delete plus add. Over time, background merges combine small segments into larger ones and finally drop the deleted documents for good. The details are in Segments, Refresh and Near-Real-Time Search.

The last stand-in shows the effect: a new segment is built per batch, deletes are just marks, and a search consults every segment.

Node.js Immutable segments and lazy deletes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Notice that deleting document 1 changed no segment: it only added a mark, yet searches stopped returning it. The merge then produced a single new segment that does not contain the deleted document at all. The real process is the same idea with much more machinery.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an inverted index map?

    Inverting the document-to-words relation lets the engine jump straight from a term to its matching documents.
  2. 2. Which structure is mainly used for sorting and aggregations?

    Doc values are column-oriented: given a document, they give the field's value, which is what sorts and aggregations need.
  3. 3. Why does deleting a document not shrink the index immediately?

    Lucene never edits a segment in place. Merges later copy only the live documents into a new segment.
  4. 4. Why do phrase queries need more than a plain postings list of ids?

    To check that 'quick' is right before 'brown', the index must store the position of each occurrence.

Summary

  • An inverted index maps terms to postings lists of documents, so search cost depends on matches, not on the size of the data.
  • The sorted term dictionary supports exact and prefix lookups; sorted postings are merged for AND and OR.
  • Doc values store field values by document and serve sorting and aggregations; analyzed text fields do not have them.
  • Segments are immutable: deletes are marks, updates are delete plus add, and merges clean up.
  • The Node code here is a teaching model of the idea, not Lucene's real format.

Next: Analysis, Tokenizers and Analyzers.