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