倒排索引

Elasticsearch使用一種稱為倒排索引的結構，它適用于快速的全文搜索。一個倒排索引由文檔中所有不重復詞的列表構成，對于其中每個詞，有一個包含它的文檔列表。

es使用稱為倒排索引的結構達到快速全文搜索的目的。

一個倒排索引包含一系列不同的單詞，這些單詞出現在任何一個文檔，對于每個單詞，對應著所有它出現的文檔。

倒排索引建立的分詞（Term）和文檔（Document）之間的映射關系，在倒排索引中，數據是面向詞（Term）而不是面向文檔的。

倒排索引

根據字面意思可以知道他和正序索引是反的。在搜索引擎中每個文件都對應一個文件ID，文件內容被表示為一系列關鍵詞的集合（文檔要除去一些無用的詞，比如’的’這些，剩下的詞就是關鍵詞，每個關鍵詞都有自己的ID）。例如“文檔1”經過分詞，提取了3個關鍵詞，每個關鍵詞都會記錄它所在在文檔中的出現頻率及出現位置。
那么上面的文檔及內容構建的倒排索引結果會如下圖（注：這個圖里沒有記錄展示該詞在出現在哪個文檔的具體位置）：

如何來查詢呢？

比如我們要查詢‘搜索引擎’這個關鍵詞在哪些文檔中出現過。首先我們通過倒排索引可以查詢到該關鍵詞出現的文檔位置是在1和3中;然后再通過正排索引查詢到文檔1和3的內容并返回結果。

倒排索引組成

倒排索引主要由單詞詞典（Term Dictionary）和倒排列表（Posting List）及倒排文件(Inverted File)組成。
他們三者的關系如下圖：

?

單詞詞典（Term Dictionary）：搜索引擎的通常索引單位是單詞，單詞詞典是由文檔集合中出現過的所有單詞構成的字符串集合，單詞詞典內每條索引項記載單詞本身的一些信息以及指向“倒排列表”的指針。
倒排列表(PostingList)：倒排列表記載了出現過某個單詞的所有文檔的文檔列表及單詞在該文檔中出現的位置信息及頻率（作關聯性算分），每條記錄稱為一個倒排項(Posting)。根據倒排列表，即可獲知哪些文檔包含某個單詞。
倒排文件(Inverted File)：所有單詞的倒排列表往往順序地存儲在磁盤的某個文件里，這個文件即被稱之為倒排文件，倒排文件是存儲倒排索引的物理文件。

以查找搜索引擎查找為例：

?

單詞詞典查詢定位問題

對于一些規模很大的文檔集合來講，他里面可能包括了上百萬的關鍵單詞(term)，能否快速定位到具體單詞(term)，這會直接影響到響應速度。
假設我們有很多個 term，比如：

Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照這樣的順序排列，找出某個特定的 term 一定很慢，因為 term 沒有排序，需要全部過濾一遍才能找出特定的 term。排序之后就變成了：

Ada,Carla,Elin,Kate,Patty,Sara,Selena

這樣我們可以用二分查找的方式，比全遍歷更快地找出目標的 term。這個就是 term dictionary。有了 term dictionary 之后，可以用 logN 次磁盤查找得到目標。但是磁盤的隨機讀操作仍然是非常昂貴的（一次 random access 大概需要 10ms 的時間）。所以盡量少的讀磁盤，有必要把一些數據緩存到內存里。但是整個 term dictionary 本身又太大了，無法完整地放到內存里。于是就有了 term index。term index 有點像一本字典的大的章節表。

目前常用的方式是通過hash加鏈表結構和樹型結構（b樹或者b+）。

hash加鏈表:

?

這是很常用的一種數據結構。這種方式就可以快速計算單詞的hash值從而定位到他所有在的hash表中，如果該表是又是一個鏈表結構（兩個單詞的hash值可能會一樣），那么就需要遍歷這個鏈表然后再對比返回結果。這種方式最大的缺點就是如果有范圍查詢的時候就很難做到。

樹型結構：

B樹（或者B+樹）是另外一種高效查找結構，下圖是一個 B樹結構示意圖。B樹與哈希方式查找不同，需要字典項能夠按照大小排序（數字或者字符序），而哈希方式則無須數據滿足此項要求。
B樹形成了層級查找結構，中間節點用于指出一定順序范圍的詞典項目存儲在哪個子樹中，起到根據詞典項比較大小進行導航的作用，最底層的葉子節點存儲單詞的地址信息，根據這個地址就可以提取出單詞字符串。

?

?