倒排索引 (Inverted Index)

Published: Sun Feb 15 2026 | Modified: Sat Feb 07 2026 , 3 minutes reading.

倒排索引：翻轉過來的世界

演算法背後的故事：19 世紀的索引卡片

在電腦出現之前，歷史學家和研究人員面臨著一個噩夢。如果妳想在擁有 10,000 本書的圖書館裡找到所有提到「自由」的地方，妳必須讀完每一本書。

為了解決這個問題，圖書館員開始創建 詞彙索引 (Concordance)。她們會拿出一本書，列出其中每一個唯一的單詞，並在一張小索引卡片上記下該單詞出現的每個頁碼。

她們不再記錄：書 A $\to$ [單詞 1, 單詞 2, 單詞 3…] 而是將其翻轉為：單詞 1 $\to$ [書 A, 書 B, 書 D…]

這次「翻轉」改變了人類知識的歷史。它讓研究人員能在幾秒鐘內從大海中撈出那根針。今天，這種起源於 19 世紀的技術——現在被稱為倒排索引——成為了 Elasticsearch、Lucene 以及妳使用的每一個搜尋框的核心技術。

為什麼需要它？

在標準資料庫（如 SQL）中，妳通常透過 ID 尋找一列數據。但在搜尋引擎中，妳是透過內容來尋找「文檔」。

痛點： 如果妳有 1 億篇部落格，搜尋「常用演算法」，標準資料庫必須掃描每一篇文章的每一個字 ( $O(N)$ )。這需要花費數分鐘。
解決方案： 倒排索引。當一篇文檔被儲存時，我們將其切碎成單詞（Token），並儲存一張「哪個單詞屬於哪篇文檔」的地圖。當妳搜尋時，我們只需要查地圖 ( $O(1)$ )。

演算法是如何「思考」的

這個演算法像是一個嚴謹的圖書館員，執行著一種「反向映射」：

分詞 (Tokenization)： 它拿出一句話，比如「To be or not to be」，將其切碎成獨立的單詞：[to, be, or, not]。它會忽略大小寫和標點符號。
大翻轉 (Inversion)： 它不再記憶「文檔 1 包含這些單詞」，而是建構一張以單詞為 Key 的巨大表格。
- to $\to$ [文檔 1, 文檔 2, 文檔 5]
- be $\to$ [文檔 1, 文檔 3]
- or $\to$ [文檔 1]
求交集 (Intersection)： 當妳搜尋「to be」時，圖書館員查看 to 和 be 的列表，找到她們的交集：即同時出現在兩個列表中的文檔。

工程決策：速度的代價

倒排索引是 Elasticsearch 搜尋極快、但寫入相對較慢的原因。

權衡： 每次妳添加一篇文檔，系統都必須更新索引中成千上萬個詞條的列表。這在計算上是昂貴的，並且會佔用大量磁碟空間。
壓縮： 因為這些列表（倒排列表 Postings List）可能非常巨大，工程師們使用了精巧的位元打包 (Bit-packing) 技術，以確保索引能足夠小，甚至能放進記憶體 (RAM)。

實作參考 (Python)

from collections import defaultdict

def create_inverted_index(documents):
    """
    documents: 字典格式 {doc_id: "內容字串"}
    """
    index = defaultdict(set)
    
    for doc_id, content in documents.items():
        # 1. 分詞：轉換為小寫並拆分為單詞
        words = content.lower().split()
        
        # 2. 翻轉：建立 單詞 -> 文檔ID 的映射
        for word in words:
            index[word].add(doc_id)
            
    return index

def search(query, index):
    query_words = query.lower().split()
    if not query_words:
        return set()
    
    # 3. 求交集：找到包含查詢中所有單詞的文檔
    results = index.get(query_words[0], set())
    for word in query_words[1:]:
        results = results.intersection(index.get(word, set()))
        
    return results

# 使用範例
# docs = {
#     1: "Common algorithms for engineers",
#     2: "The soul of a new machine",
#     3: "How to find common ground"
# }
# idx = create_inverted_index(docs)
# print(search("common", idx)) # 輸出: {1, 3}

小結

倒排索引教會我們，如果妳想快速找到東西，就必須停止透過「我有什麼」的視角觀察，轉而透過「人們想要什麼」的視角觀察。透過翻轉世界，我們將「讀完所有書」這一不可能的任務，變成了「查閱地圖」這一簡單動作。

Luke Sun