上一篇文章 "ElasticSearch 術語" 中提到了倒排索引，那麼這篇文章就來講解下什麼是倒排索引，倒排索引的數據結構以及 ElasticSearch 中的倒排索引。 倒排索引 倒排索引（Inverted Index） 也常被稱為反向索引，是搜索引擎中非常重要的數據結構，為什麼說它重要呢，我們 ...
上一篇文章 ElasticSearch 術語中提到了倒排索引，那麼這篇文章就來講解下什麼是倒排索引，倒排索引的數據結構以及 ElasticSearch 中的倒排索引。
倒排索引
倒排索引（Inverted Index） 也常被稱為反向索引，是搜索引擎中非常重要的數據結構，為什麼說它重要呢，我們首先拿一本書《重構 改善既有代碼的設計》舉個例子：
如果一本書沒有目錄的話，理論上也是可以讀的，只是合上書下次再次閱讀的時候，就有些耗費時間了。
通過給一本書加目錄頁，可以快速瞭解這本書的大致內容分佈以及每個章節的頁碼數，這樣在查詢內容的時候效率就會非常高了，所以書的目錄就是書本內容的簡單索引。
想象一下你要搜索 case語句 這個關鍵詞在這本書的頁碼，你應該怎麼辦呢？有些技術類的書籍會在最後提供索引頁，這本書的索引頁如下：
只需要從索引頁中查找 case語句，就可以查找到關鍵詞在書本中的頁碼位置了。
看完這個例子，讓我們來把圖書和搜索引擎做個簡單的類比：
圖書當中的目錄頁就相當正向索引（Forward Index），索引頁就相當於倒排索引的簡單實現，在搜索引擎中，正向索引指的是文檔 ID 到文檔內容和單詞的關聯，倒排索引就是單詞到文檔 ID 的關係。
下麵來看一個很簡單的例子：
| 文檔 ID | 文檔內容 |
|---|---|
| 1 | Mastering ElasticSearch |
| 2 | ElasticSearch Server |
| 3 | ElasticSearch Essentials |
如上有三篇文檔，每篇文檔的內容都是關於 ElasticSearch 的三本書，那我們思考下怎麼樣變為一個倒排索引呢？
| Term | Count | DocumentId:Position |
|---|---|---|
| ElasticSearch | 3 | 1:1，2:0，3:0 |
| Mastering | 1 | 1:0 |
| Server | 1 | 2:1 |
| Essentials | 1 | 3:1 |
把書中內容出現所以的詞都分成不同的關鍵詞（Term），排列在第一欄，分別是 ElasticSearch，Mastering，Server 和 Essentials；第二欄是統計了關鍵詞在所有內容中出現的次數，比如 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 中可以去設置對某些欄位不做索引，這樣做可以節省存儲空間，但同時也會導致這個欄位無法搜索了。
比如一個文檔，其中包含兩個欄位 username 和 job：
{
"username":"wupx",
"job":"programmer"
}在構建索引的時候是根據欄位構建的，那麼 ES 中 username 會有一個倒排索引，job 也會有一個倒排索引。
總結
這篇文章主要介紹了什麼是倒排索引以及它的數據結構，下一篇文章將會學習如何在 ElasticSearch 中分詞來形成倒排索引。
參考文獻
Elasticsearch核心技術與實戰
