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.

Practice

1. What is the main purpose of an inverted index in Elasticsearch?

easy

A. To store documents in the order they were added

B. To map words to the documents where they appear

C. To compress data for storage efficiency

D. To encrypt documents for security

Solution

1. Step 1: Understand the role of inverted index

   An inverted index links each word to the documents containing it, enabling fast search.

2. Step 2: Compare options with definition

   Only To map words to the documents where they appear describes this mapping; others describe unrelated functions.

3. Final Answer:

   To map words to the documents where they appear -> Option B

4. Quick Check:

   Inverted index = word-to-document map [OK]

Hint: Remember: inverted index links words to documents [OK]

Common Mistakes:

• Thinking it stores documents in order
• Confusing with data compression
• Assuming it encrypts data

2. Which of the following is the correct way Elasticsearch uses an inverted index?

easy

A. It stores documents in a tree structure

B. It stores a list of words for each document

C. It stores documents as plain text files

D. It stores a list of documents for each unique word

Solution

1. Step 1: Recall inverted index structure

   Inverted index keeps a list of documents for each unique word found in the data.

2. Step 2: Match options to structure

   It stores a list of documents for each unique word matches this exactly; others describe different or incorrect storage methods.

3. Final Answer:

   It stores a list of documents for each unique word -> Option D

4. Quick Check:

   Inverted index = word to document list [OK]

Hint: Think: word first, then documents list [OK]

Common Mistakes:

• Confusing inverted index with forward index
• Assuming documents are stored as trees
• Thinking documents are stored as plain text only

3. Given these documents indexed in Elasticsearch:
Doc1: "apple banana apple"
Doc2: "banana orange"
What will the inverted index entry for the word banana contain?

medium

A. [Doc1, Doc2]

B. [Doc1]

C. [Doc2]

D. [] (empty list)

Solution

1. Step 1: Identify documents containing 'banana'

   Doc1 contains "banana" once, Doc2 contains "banana" once.

2. Step 2: List documents in inverted index for 'banana'

   Both Doc1 and Doc2 should be listed for the word "banana".

3. Final Answer:

   [Doc1, Doc2] -> Option A

4. Quick Check:

   banana appears in Doc1 and Doc2 [OK]

Hint: Check all docs containing the word, not just one [OK]

Common Mistakes:

• Listing only one document
• Confusing word frequency with document list
• Leaving the list empty

4. You have an inverted index that incorrectly shows the word orange linked only to Doc1, but Doc2 also contains "orange". What is the likely cause?

medium

A. The indexing process missed updating the inverted index for Doc2

B. The word "orange" does not exist in Doc2

C. Elasticsearch does not support multiple documents per word

D. The inverted index only stores the first document per word

Solution

1. Step 1: Verify word presence in documents

   Since "orange" is in Doc2, it should appear in the inverted index for that word.

2. Step 2: Identify indexing error

   If Doc2 is missing, likely the indexing process did not update the inverted index correctly for Doc2.

3. Final Answer:

   The indexing process missed updating the inverted index for Doc2 -> Option A

4. Quick Check:

   Missing doc means indexing error [OK]

Hint: Missing docs usually mean indexing skipped them [OK]

Common Mistakes:

• Assuming word is not in Doc2
• Thinking Elasticsearch limits docs per word
• Believing inverted index stores only one doc

5. You want to optimize search speed for a large text dataset in Elasticsearch. Which approach using the inverted index is best?

hard

A. Disable the inverted index to save storage space

B. Store all documents as plain text and scan each on search

C. Use the inverted index to quickly find documents containing search words

D. Index only the first word of each document

Solution

1. Step 1: Understand inverted index purpose

   It allows fast lookup of documents by words, speeding up search.

2. Step 2: Evaluate options for search speed

   Use the inverted index to quickly find documents containing search words uses the inverted index as intended; others slow search or lose data.

3. Final Answer:

   Use the inverted index to quickly find documents containing search words -> Option C

4. Quick Check:

   Inverted index speeds search by word lookup [OK]

Hint: Use inverted index for fast word-based search [OK]

Common Mistakes:

• Thinking scanning all text is faster
• Disabling inverted index to save space
• Indexing only part of documents