倒排索引Inverted Index倒排索引Inverted Index一、先從正排索引說起二、什么是倒排索引三、兩者對比四、倒排索引的組成1. 詞項字典Term Dictionary2. 倒排列表Posting List五、構(gòu)建過程第一步文檔分詞第二步建立詞到文檔的映射第三步記錄附加信息增強版六、查詢過程七、與 BM25 的關(guān)系八、在向量數(shù)據(jù)庫中的應(yīng)用九、優(yōu)缺點優(yōu)點缺點十、典型應(yīng)用場景總結(jié)倒排索引Inverted Index一、先從正排索引說起要理解倒排索引先看正排索引是什么。正排索引Forward Index是我們最自然的思考方式從文檔出發(fā)找出文檔里包含哪些詞。文檔ID → 內(nèi)容 → 提取所有詞舉個例子假設(shè)有三篇文章文檔ID內(nèi)容Doc1“蘋果手機很好用”Doc2“我喜歡吃蘋果”Doc3“手機拍照功能強大”正排索引就是按文檔整理出詞匯表文檔ID包含的詞匯Doc1蘋果、手機、很好用Doc2我、喜歡、吃、蘋果Doc3手機、拍照、功能、強大這種結(jié)構(gòu)存數(shù)據(jù)沒問題但搜索的時候很慢。比如用戶搜“蘋果”需要遍歷所有文檔逐個檢查是否包含這個詞。文檔少還好如果有幾百萬篇文章每次都全表掃描效率極低。二、什么是倒排索引倒排索引Inverted Index的思路正好反過來從詞出發(fā)記錄這個詞出現(xiàn)在哪些文檔里。把上面的數(shù)據(jù)倒過來詞匯出現(xiàn)位置蘋果Doc1, Doc2手機Doc1, Doc3很好用Doc1我Doc2喜歡Doc2吃Doc2拍照Doc3功能Doc3強大Doc3這就是倒排索引。用戶搜“蘋果”直接從倒排索引里找到這個詞對應(yīng)的文檔列表瞬間返回結(jié)果。三、兩者對比對比項正排索引倒排索引數(shù)據(jù)結(jié)構(gòu)文檔 → 詞匯詞匯 → 文檔列表查詢過程遍歷所有文檔直接查詞表查詢速度慢O(n)快O(1)存儲結(jié)構(gòu)簡單稍復(fù)雜更新成本低較高典型應(yīng)用數(shù)據(jù)庫行存儲搜索引擎、全文檢索打個比方正排索引 一本書前面的目錄按章節(jié)找內(nèi)容倒排索引 一本書后面的關(guān)鍵詞索引按詞找位置四、倒排索引的組成倒排索引由兩部分組成1. 詞項字典Term Dictionary按字母順序排列的所有詞每個詞指向它的倒排列表。蘋果 → [Doc1, Doc2] 手機 → [Doc1, Doc3] 拍照 → [Doc3] ...2. 倒排列表Posting List每個詞對應(yīng)的文檔列表通常會存儲存儲內(nèi)容作用文檔ID標識文檔詞頻TF計算相關(guān)性位置信息支持短語搜索偏移量支持高亮存儲的越詳細查詢功能越豐富但存儲空間也越大。五、構(gòu)建過程第一步文檔分詞原始文檔Doc1: “蘋果手機好用”Doc2: “我喜歡吃蘋果”分詞后Doc1: [“蘋果”, “手機”, “好用”]Doc2: [“我”, “喜歡”, “吃”, “蘋果”]第二步建立詞到文檔的映射詞文檔列表蘋果[Doc1, Doc2]手機[Doc1]好用[Doc1]我[Doc2]喜歡[Doc2]吃[Doc2]第三步記錄附加信息增強版詞(文檔, 詞頻, 位置)蘋果(Doc1, 1, 0), (Doc2, 1, 3)手機(Doc1, 1, 1)好用(Doc1, 1, 2)我(Doc2, 1, 0)喜歡(Doc2, 1, 1)吃(Doc2, 1, 2)有了位置信息就能支持“蘋果手機”這種短語搜索因為可以判斷“蘋果”和“手機”在Doc1中相鄰出現(xiàn)。六、查詢過程用戶搜索“蘋果手機”分詞[“蘋果”, “手機”]查倒排索引蘋果 → [Doc1, Doc2]手機 → [Doc1, Doc3]求交集AND兩個詞都出現(xiàn)的文檔 → [Doc1]返回結(jié)果Doc1如果是 OR 查詢則合并列表 → [Doc1, Doc2, Doc3]七、與 BM25 的關(guān)系BM25 是計算搜索結(jié)果相關(guān)性的算法它的核心就是基于倒排索引。score(D, Q) Σ IDF(q) × (TF × (k?1)) / (TF k? × (1 - b b × |D|/avgDL))用到的數(shù)據(jù)都來自倒排索引TF詞頻倒排列表里存著IDF逆文檔頻率根據(jù)詞在多少個文檔中出現(xiàn)計算所以倒排索引是搜索引擎的基礎(chǔ)BM25 是排名的算法。八、在向量數(shù)據(jù)庫中的應(yīng)用像 Milvus 支持稀疏向量底層用的就是倒排索引的思路# 稀疏向量本質(zhì)上就是 {詞: 權(quán)重} 的倒排格式sparse_vector{蘋果:0.8,手機:0.6}# 查詢時也是用倒排索引快速定位collection.search(data[{蘋果:0.7,手機:0.5}])稠密向量BERT、BGE做語義搜索倒排索引BM25、SPLADE做關(guān)鍵詞匹配兩者經(jīng)常結(jié)合使用。九、優(yōu)缺點優(yōu)點查詢速度快O(1) 級別支持布爾查詢AND/OR/NOT可擴展性強適合海量數(shù)據(jù)缺點構(gòu)建需要時間更新成本高存儲空間比原文本大需要存索引無法處理同義詞、語義匹配這一點靠稠密向量補救十、典型應(yīng)用場景場景說明搜索引擎Google、百度最核心的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫全文檢索MySQL FULLTEXT、Elasticsearch推薦系統(tǒng)用戶標簽反向索引向量數(shù)據(jù)庫稀疏向量檢索總結(jié)倒排索引的核心思想就一句話不查文檔找詞而是查詞找文檔。這種反向的思路讓全文搜索從全表掃描變成了查字典速度提升了成百上千倍。無論是 Google 搜索、數(shù)據(jù)庫索引還是向量檢索背后都離不開倒排索引。 倒排索引（Inverted Index）
倒排索引Inverted Index倒排索引Inverted Index一、先從正排索引說起二、什么是倒排索引三、兩者對比四、倒排索引的組成1. 詞項字典Term Dictionary2. 倒排列表Posting List五、構(gòu)建過程第一步文檔分詞第二步建立詞到文檔的映射第三步記錄附加信息增強版六、查詢過程七、與 BM25 的關(guān)系八、在向量數(shù)據(jù)庫中的應(yīng)用九、優(yōu)缺點優(yōu)點缺點十、典型應(yīng)用場景總結(jié)倒排索引Inverted Index一、先從正排索引說起要理解倒排索引先看正排索引是什么。正排索引Forward Index是我們最自然的思考方式從文檔出發(fā)找出文檔里包含哪些詞。文檔ID → 內(nèi)容 → 提取所有詞舉個例子假設(shè)有三篇文章文檔ID內(nèi)容Doc1“蘋果手機很好用”Doc2“我喜歡吃蘋果”Doc3“手機拍照功能強大”正排索引就是按文檔整理出詞匯表文檔ID包含的詞匯Doc1蘋果、手機、很好用Doc2我、喜歡、吃、蘋果Doc3手機、拍照、功能、強大這種結(jié)構(gòu)存數(shù)據(jù)沒問題但搜索的時候很慢。比如用戶搜“蘋果”需要遍歷所有文檔逐個檢查是否包含這個詞。文檔少還好如果有幾百萬篇文章每次都全表掃描效率極低。二、什么是倒排索引倒排索引Inverted Index的思路正好反過來從詞出發(fā)記錄這個詞出現(xiàn)在哪些文檔里。把上面的數(shù)據(jù)倒過來詞匯出現(xiàn)位置蘋果Doc1, Doc2手機Doc1, Doc3很好用Doc1我Doc2喜歡Doc2吃Doc2拍照Doc3功能Doc3強大Doc3這就是倒排索引。用戶搜“蘋果”直接從倒排索引里找到這個詞對應(yīng)的文檔列表瞬間返回結(jié)果。三、兩者對比對比項正排索引倒排索引數(shù)據(jù)結(jié)構(gòu)文檔 → 詞匯詞匯 → 文檔列表查詢過程遍歷所有文檔直接查詞表查詢速度慢O(n)快O(1)存儲結(jié)構(gòu)簡單稍復(fù)雜更新成本低較高典型應(yīng)用數(shù)據(jù)庫行存儲搜索引擎、全文檢索打個比方正排索引 一本書前面的目錄按章節(jié)找內(nèi)容倒排索引 一本書后面的關(guān)鍵詞索引按詞找位置四、倒排索引的組成倒排索引由兩部分組成1. 詞項字典Term Dictionary按字母順序排列的所有詞每個詞指向它的倒排列表。蘋果 → [Doc1, Doc2] 手機 → [Doc1, Doc3] 拍照 → [Doc3] ...2. 倒排列表Posting List每個詞對應(yīng)的文檔列表通常會存儲存儲內(nèi)容作用文檔ID標識文檔詞頻TF計算相關(guān)性位置信息支持短語搜索偏移量支持高亮存儲的越詳細查詢功能越豐富但存儲空間也越大。五、構(gòu)建過程第一步文檔分詞原始文檔Doc1: “蘋果手機好用”Doc2: “我喜歡吃蘋果”分詞后Doc1: [“蘋果”, “手機”, “好用”]Doc2: [“我”, “喜歡”, “吃”, “蘋果”]第二步建立詞到文檔的映射詞文檔列表蘋果[Doc1, Doc2]手機[Doc1]好用[Doc1]我[Doc2]喜歡[Doc2]吃[Doc2]第三步記錄附加信息增強版詞(文檔, 詞頻, 位置)蘋果(Doc1, 1, 0), (Doc2, 1, 3)手機(Doc1, 1, 1)好用(Doc1, 1, 2)我(Doc2, 1, 0)喜歡(Doc2, 1, 1)吃(Doc2, 1, 2)有了位置信息就能支持“蘋果手機”這種短語搜索因為可以判斷“蘋果”和“手機”在Doc1中相鄰出現(xiàn)。六、查詢過程用戶搜索“蘋果手機”分詞[“蘋果”, “手機”]查倒排索引蘋果 → [Doc1, Doc2]手機 → [Doc1, Doc3]求交集AND兩個詞都出現(xiàn)的文檔 → [Doc1]返回結(jié)果Doc1如果是 OR 查詢則合并列表 → [Doc1, Doc2, Doc3]七、與 BM25 的關(guān)系BM25 是計算搜索結(jié)果相關(guān)性的算法它的核心就是基于倒排索引。score(D, Q) Σ IDF(q) × (TF × (k?1)) / (TF k? × (1 - b b × |D|/avgDL))用到的數(shù)據(jù)都來自倒排索引TF詞頻倒排列表里存著IDF逆文檔頻率根據(jù)詞在多少個文檔中出現(xiàn)計算所以倒排索引是搜索引擎的基礎(chǔ)BM25 是排名的算法。八、在向量數(shù)據(jù)庫中的應(yīng)用像 Milvus 支持稀疏向量底層用的就是倒排索引的思路# 稀疏向量本質(zhì)上就是 {詞: 權(quán)重} 的倒排格式sparse_vector{蘋果:0.8,手機:0.6}# 查詢時也是用倒排索引快速定位collection.search(data[{蘋果:0.7,手機:0.5}])稠密向量BERT、BGE做語義搜索倒排索引BM25、SPLADE做關(guān)鍵詞匹配兩者經(jīng)常結(jié)合使用。九、優(yōu)缺點優(yōu)點查詢速度快O(1) 級別支持布爾查詢AND/OR/NOT可擴展性強適合海量數(shù)據(jù)缺點構(gòu)建需要時間更新成本高存儲空間比原文本大需要存索引無法處理同義詞、語義匹配這一點靠稠密向量補救十、典型應(yīng)用場景場景說明搜索引擎Google、百度最核心的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫全文檢索MySQL FULLTEXT、Elasticsearch推薦系統(tǒng)用戶標簽反向索引向量數(shù)據(jù)庫稀疏向量檢索總結(jié)倒排索引的核心思想就一句話不查文檔找詞而是查詞找文檔。這種反向的思路讓全文搜索從全表掃描變成了查字典速度提升了成百上千倍。無論是 Google 搜索、數(shù)據(jù)庫索引還是向量檢索背后都離不開倒排索引。