[[319291]]

 上一篇文章 ElasticSearch 術語中提到了倒排索引，那么這篇文章就來講解下什么是倒排索引，倒排索引的數據結構以及 ElasticSearch 中的倒排索引。

倒排索引

倒排索引(Inverted Index) 也常被稱為反向索引，是搜索引擎中非常重要的數據結構，為什么說它重要呢，我們首先拿一本書《重構 改善既有代碼的設計》舉個例子：

如果一本書沒有目錄的話，理論上也是可以讀的，只是合上書下次再次閱讀的時候，就有些耗費時間了。

通過給一本書加目錄頁，可以快速了解這本書的大致內容分布以及每個章節(jié)的頁碼數，這樣在查詢內容的時候效率就會非常高了，所以書的目錄就是書本內容的簡單索引。

目錄頁

想象一下你要搜索 case語句 這個關鍵詞在這本書的頁碼，你應該怎么辦呢?有些技術類的書籍會在最后提供索引頁，這本書的索引頁如下：

索引頁

只需要從索引頁中查找 case語句，就可以查找到關鍵詞在書本中的頁碼位置了。

看完這個例子，讓我們來把圖書和搜索引擎做個簡單的類比：

圖書當中的目錄頁就相當正向索引(Forward Index)，索引頁就相當于倒排索引的簡單實現，在搜索引擎中，正向索引指的是文檔 ID 到文檔內容和單詞的關聯，倒排索引就是單詞到文檔 ID 的關系。

下面來看一個很簡單的例子：

如上有三篇文檔，每篇文檔的內容都是關于 ElasticSearch 的三本書，那我們思考下怎么樣變?yōu)橐粋€倒排索引呢?

把書中內容出現所以的詞都分成不同的關鍵詞(Term)，排列在第一欄，分別是 ElasticSearch，Mastering，Server 和 Essentials;第二欄是統(tǒng)計了關鍵詞在所有內容中出現的次數，比如 ElasticSearch 在內容中出現了三次，就記為 3;第三欄標注的是文檔 ID 和文檔出現的位置，比如 ElasticSearch 在第 1,2,3 文檔中都出現了，在第一個文檔所處的位置是第二個，所以標注的為 1。

以上就是簡單的正排索引和倒排索引的結構，下面讓我們來看下倒排索引的數據結構：

倒排索引數據結構

倒排索引的核心分為兩部分，第一部分為單詞詞典(Term Dictionary)，記錄所有文檔的單詞以及單詞到倒排列表的關聯關系。在前面的例子中，單詞的量并不是很多，但是在實際生產中，單詞量會非常大，所以實際會采用 B+ 樹和哈希拉鏈法去存儲單詞的詞典，以滿足高性能的插入與查詢。

第二部分是倒排列表(Posting List)，它記錄了單詞對應文檔的結合，倒排列表是由倒排索引項(Posting) 組成，倒排索引項包含：

• 文檔 ID：用于獲取原始信息
• 詞頻(TF，Term Frequency)：該單詞在文檔中出現的次數，用于相關性評分
• 位置(Position)：單詞在文檔中分詞的位置，用于語句搜索(Phrase Query)
• 偏移(Offset)：記錄單詞的開始結束位置，實現高亮顯示(比如用 GitHub 搜索的時候，搜索的關鍵詞會高亮顯示)

下面我們來用一張圖來整體看下倒排索引：

一個倒排索引是由單詞詞典(Term Dictionary)和倒排列表(Posting List)組成的，單詞詞典會記錄倒排列表中每個單詞的偏移位置。比如當搜索 Allen 的時候，首先會通過單詞詞典快速定位到 Allen，然后從 Allen 這里拿到在倒排列表中的偏移，快速定位到在倒排列表中的位置，從而真正拿到倒排索引項 [12,15](這里只是列了下 Document ID，其實是像上面講的包含 4 項信息的項)，拿到這個項可以去索引上拿到原始信息，可以去計算打分排序返回給用戶。

再了解了倒排索引的數據結構后，讓我們來看下 ES 中的倒排索引吧!

ElasticSearch 倒排索引

那么在 ElasticSearch 中的文檔是基于 Json 格式的，其中一個文檔包含多個字段，每個字段都會有自己的倒排索引。在 Mapping 中可以去設置對某些字段不做索引，這樣做可以節(jié)省存儲空間，但同時也會導致這個字段無法搜索了。

比如一個文檔，其中包含兩個字段 username 和 job：

{ 
    "username":"wupx", 
    "job":"programmer" 
} 

在構建索引的時候是根據字段構建的，那么 ES 中 username 會有一個倒排索引，job 也會有一個倒排索引。

總結

這篇文章主要介紹了什么是倒排索引以及它的數據結構，下一篇文章將會學習如何在 ES 中分詞來形成倒排索引。

參考文獻

Elasticsearch核心技術與實戰(zhàn)

https://dwz.cn/ELv7FvuX