上一篇文章 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核心技術與實戰
https://dwz.cn/ELv7FvuX
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/26145.html
標籤：大數據