Back
+20 XP
Concept

The Inverted Index & Posting Lists

Regex-scanning unstructured text across millions of documents is $O(N)$ suicide. An Inverted Index maps each normalized word to a sorted array of Document IDs called a Posting List, turning search into lightning-fast array lookups 🔍📜.

python
import re

class InvertedIndex:
    def __init__(self):
        self.postings = {}

    def add_document(self, doc_id, text):
        tokens = set(re.findall(r"\b\w+\b", text.lower()))
        for token in tokens:
            self.postings.setdefault(token, []).append(doc_id)

    def search(self, token):
        return self.postings.get(token.lower(), [])

engine = InvertedIndex()
engine.add_document(1, "Postgres and SQLite engines")
engine.add_document(2, "SQLite embedded database performance")

print(f"Documents matching 'sqlite': {engine.search('sqlite')} 🚀")

# 52. The Inverted Index & Posting Lists If an e-commerce platform ran `SELECT * FROM products WHERE description LIKE '%wireless%'`, PostgreSQL would perform a sequential table scan, reading gigabytes of strings from disk on every search keystroke 🛑. ```python # Forward Index (Standard Document Store): # Doc 1 -> ["fast", "async", "python"] # Doc 2 -> ["python", "storage", "engine"] # Inverted Index (Search Engine): # "async" -> [Doc 1] # "fast" -> [Doc 1] # "python" -> [Doc 1, Doc 2] # "storage" -> [Doc 2] ``` ### The Search Engine Core 1. **Tokenization & Normalization**: Text is stripped of punctuation, converted to lowercase, and split into tokens (words). 2. **The Posting List**: An ordered list of document IDs where the token appears. Because IDs are monotonically increasing, finding documents containing both Word A and Word B is a linear merge of their posting lists 🔍. 3. **Payloads & Offsets**: Production search engines (Lucene, Elasticsearch) also record term frequency ($TF$) and token positions inside the posting list to enable phrase matching and BM25 relevance scoring 📜. --- ### Interactive Pop-Quiz 🧠 #### Why is an Inverted Index named 'inverted' compared to traditional database storage? - [ ] Traditional storage maps documents to words; an inverted index maps words to the documents that contain them 🔍 - [ ] Because it stores string byte characters in reverse endian order - [ ] Because it reads document files from the end of the file backwards - [ ] Because it inverts binary bits from 0 to 1 during compression --- ### Practical Challenge 🎯 Implement `InvertedIndex` with `index(doc_id, text)` and `query(word)`. Normalize words to lowercase. Index doc 1: `'Distributed consensus with Raft'`, doc 2: `'Consensus protocols and Paxos'`, doc 3: `'Raft log replication'`. Query `'consensus'`. Assert the returned doc IDs are `[1, 2]`, and print them. <details> <summary>Solution</summary> ```python import re class InvertedIndex: def __init__(self): self.postings = {} def index(self, doc_id, text): tokens = set(re.findall(r"\b\w+\b", text.lower())) for t in tokens: self.postings.setdefault(t, []).append(doc_id) def query(self, word): return self.postings.get(word.lower(), []) idx = InvertedIndex() idx.index(1, "Distributed consensus with Raft") idx.index(2, "Consensus protocols and Paxos") idx.index(3, "Raft log replication") res = idx.query("consensus") assert res == [1, 2] print(res) ``` </details>

Checkpoint

Why is an Inverted Index named 'inverted' compared to traditional database storage? 🧠

Practice

Implement `InvertedIndex` with `index(doc_id, text)` and `query(word)`. Normalize words to lowercase. Index doc 1: `'Distributed consensus with Raft'`, doc 2: `'Consensus protocols and Paxos'`, doc 3: `'Raft log replication'`. Query `'consensus'`. Assert the returned doc IDs are `[1, 2]`, and print them. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks