Inverted index data structure in Elasticsearch - Step-by-Step Execution

Concept Flow - Inverted index data structure

Documents Collection

↓

Tokenize Text into Words

↓

For each Word

↓

Add Document ID to Word's List

↓

Build Inverted Index

↓

Search Queries Use Index to Find Docs

The inverted index takes documents, breaks text into words, and links each word to the documents containing it, enabling fast search.

Execution Sample

Elasticsearch

Doc1: "cat dog"
Doc2: "dog mouse"
Doc3: "cat mouse dog"
Build inverted index

Create an inverted index from three documents showing which words appear in which documents.

Execution Table

Step	Action	Word Processed	Document ID Added	Current Inverted Index
1	Process Doc1	cat	Doc1	{"cat": ["Doc1"]}
2	Process Doc1	dog	Doc1	{"cat": ["Doc1"], "dog": ["Doc1"]}
3	Process Doc2	dog	Doc2	{"cat": ["Doc1"], "dog": ["Doc1", "Doc2"]}
4	Process Doc2	mouse	Doc2	{"cat": ["Doc1"], "dog": ["Doc1", "Doc2"], "mouse": ["Doc2"]}
5	Process Doc3	cat	Doc3	{"cat": ["Doc1", "Doc3"], "dog": ["Doc1", "Doc2"], "mouse": ["Doc2"]}
6	Process Doc3	mouse	Doc3	{"cat": ["Doc1", "Doc3"], "dog": ["Doc1", "Doc2"], "mouse": ["Doc2", "Doc3"]}
7	Process Doc3	dog	Doc3	{"cat": ["Doc1", "Doc3"], "dog": ["Doc1", "Doc2", "Doc3"], "mouse": ["Doc2", "Doc3"]}
8	Finish			Inverted index complete with all words and document lists

💡 All documents processed and all words indexed with their document IDs.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
inverted_index	{}	{"cat": ["Doc1"]}	{"cat": ["Doc1"], "dog": ["Doc1"]}	{"cat": ["Doc1"], "dog": ["Doc1", "Doc2"]}	{"cat": ["Doc1"], "dog": ["Doc1", "Doc2"], "mouse": ["Doc2"]}	{"cat": ["Doc1", "Doc3"], "dog": ["Doc1", "Doc2"], "mouse": ["Doc2"]}	{"cat": ["Doc1", "Doc3"], "dog": ["Doc1", "Doc2"], "mouse": ["Doc2", "Doc3"]}	{"cat": ["Doc1", "Doc3"], "dog": ["Doc1", "Doc2", "Doc3"], "mouse": ["Doc2", "Doc3"]}	{"cat": ["Doc1", "Doc3"], "dog": ["Doc1", "Doc2", "Doc3"], "mouse": ["Doc2", "Doc3"]}

Key Moments - 3 Insights

Why does the inverted index store document IDs instead of the full text?

The inverted index stores only document IDs for each word to quickly find which documents contain that word without storing all text repeatedly. See execution_table rows 1-7 where only IDs are added.

What happens if a word appears multiple times in the same document?

The document ID is added only once per word to avoid duplicates. The execution_table shows each document ID appears once per word, e.g., 'dog' has Doc1 only once.

How does the inverted index help with search queries?

It lets the search engine quickly find all documents containing a word by looking up the word in the index instead of scanning all documents. This is shown in the final inverted index in execution_table row 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. Which document IDs are associated with the word 'dog'?

A ["Doc1", "Doc2"]

B ["Doc2"]

C ["Doc1"]

D ["Doc1", "Doc3"]

💡 Hint

Check the 'Current Inverted Index' column at step 4 in the execution_table.

At which step does the word 'mouse' first get associated with a document?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look for when 'mouse' first appears in the 'Word Processed' column in the execution_table.

If a new document Doc4 with words 'cat' and 'elephant' is added, what happens to the inverted index?

A "cat" list stays the same, "elephant" list stays empty

B "cat" list adds Doc4, "elephant" list starts with Doc4

C "cat" list adds Doc4, "elephant" list stays empty

D "cat" list stays the same, "elephant" list adds Doc4

💡 Hint

Refer to variable_tracker showing how document IDs are added for new words and existing words.

Concept Snapshot

Inverted Index:
- Maps each word to a list of document IDs containing it.
- Built by tokenizing documents and recording IDs per word.
- Enables fast search by word lookup.
- Avoids storing full text repeatedly.
- Document IDs appear once per word to prevent duplicates.

Full Transcript

An inverted index is a data structure used in search engines like Elasticsearch. It takes a collection of documents and breaks their text into words. For each word, it records which documents contain it by storing document IDs. This allows quick searching by looking up words in the index instead of scanning all documents. The process involves reading each document, splitting text into words, and adding the document ID to each word's list in the index. The final inverted index maps words to lists of document IDs, enabling fast and efficient search queries.