Elasticsearch中的倒排索引結(jié)構(gòu)是什么

本篇內(nèi)容主要講解“Elasticsearch中的倒排索引結(jié)構(gòu)是什么”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Elasticsearch中的倒排索引結(jié)構(gòu)是什么”吧!

倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地來(lái)講，正向索引是通過(guò)key找value，反向索引則是通過(guò)value找key。

先來(lái)回憶一下我們是怎么插入一條索引記錄的：

curl -X PUT "localhost:9200/user/_doc/1" -H 'Content-Type: application/json' -d'
{
    "name" : "Jack",
    "gender" : 1,
    "age" : 20
}
'

其實(shí)就是直接PUT一個(gè)JSON的對(duì)象，這個(gè)對(duì)象有多個(gè)字段，在插入這些數(shù)據(jù)到索引的同時(shí)，Elasticsearch還為這些字段建立索引——倒排索引，因?yàn)镋lasticsearch最核心功能是搜索。

那么，倒排索引是個(gè)什么樣子呢？

倒排索引由兩部分構(gòu)成：

• 單詞詞典

• 倒排列表

它的結(jié)構(gòu)如下：

單詞詞典有兩種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：B+樹(shù)和Hash表

B+樹(shù)和Mysql索引結(jié)構(gòu)中主鍵索引數(shù)據(jù)結(jié)構(gòu)一樣，這里就不再介紹了

哈希表的key是單詞的hash值，值是單詞的鏈表，因?yàn)閔ash算法會(huì)有沖突的情況發(fā)生，所以這里的值是一個(gè)集合，里面保存著相同hash值得單詞以及改詞指向倒排列表的指針

倒排列表

倒排列表特性：

1. 記錄出現(xiàn)過(guò)某個(gè)單詞的文檔列表

2. 同時(shí)還記錄單詞在所有文檔中的出現(xiàn)次數(shù)和偏移位置

倒排列表元素?cái)?shù)據(jù)結(jié)構(gòu)：

(DocID;TF;<POS>)

其中：

• DocID：出現(xiàn)某單詞的文檔ID

• TF(Term Frequency)：?jiǎn)卧~在該文檔中出現(xiàn)的次數(shù)

• POS：?jiǎn)卧~在文檔中的位置

舉例

有下面單個(gè)文檔

則他們生成的倒排索引

比如單詞“年度”，單詞ID為2，在三個(gè)文檔中出現(xiàn)過(guò)，所以逆向文檔頻率為3，同時(shí)倒排索引中的元素也有三個(gè)：(1;1;<2>),(2;1;<4>),(3;1;<3>)。拿第一個(gè)元素(1;1;<2>)進(jìn)行說(shuō)明，他表示“年度”再文檔ID為1的文檔中出現(xiàn)過(guò)1次，出現(xiàn)的位置是第二個(gè)單詞

首先，來(lái)搞清楚幾個(gè)概念，為此，舉個(gè)例子：

假設(shè)有個(gè)user索引，它有四個(gè)字段：分別是name，gender，age，address。畫出來(lái)的話，大概是下面這個(gè)樣子，跟關(guān)系型數(shù)據(jù)庫(kù)一樣

Term（單詞）：一段文本經(jīng)過(guò)分析器分析以后就會(huì)輸出一串單詞，這一個(gè)一個(gè)的就叫做Term（直譯為：?jiǎn)卧~）

Term Dictionary（單詞字典）：顧名思義，它里面維護(hù)的是Term，可以理解為Term的集合

Term Index（單詞索引）：為了更快的找到某個(gè)單詞，我們?yōu)閱卧~建立索引

Posting List（倒排列表）：倒排列表記錄了出現(xiàn)過(guò)某個(gè)單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息，每條記錄稱為一個(gè)倒排項(xiàng)(Posting)。根據(jù)倒排列表，即可獲知哪些文檔包含某個(gè)單詞。（PS：實(shí)際的倒排列表中并不只是存了文檔ID這么簡(jiǎn)單，還有一些其它的信息，比如：詞頻（Term出現(xiàn)的次數(shù)）、偏移量（offset）等，可以想象成是Java中的對(duì)象）

（PS：如果類比現(xiàn)代漢語(yǔ)詞典的話，那么Term就相當(dāng)于詞語(yǔ)，Term Dictionary相當(dāng)于漢語(yǔ)詞典本身，Term Index相當(dāng)于詞典的目錄索引）

我們知道，每個(gè)文檔都有一個(gè)ID，如果插入的時(shí)候沒(méi)有指定的話，Elasticsearch會(huì)自動(dòng)生成一個(gè)，因此ID字段就不多說(shuō)了

上面的例子，Elasticsearch建立的索引大致如下：

name字段：

gender字段：

Elasticsearch分別為每個(gè)字段都建立了一個(gè)倒排索引。比如，在上面“張三”、“北京市”、22 這些都是Term，而[1，3]就是Posting List。Posting list就是一個(gè)數(shù)組，存儲(chǔ)了所有符合某個(gè)Term的文檔ID。

只要知道文檔ID，就能快速找到文檔?？墒?，要怎樣通過(guò)我們給定的關(guān)鍵詞快速找到這個(gè)Term呢？

當(dāng)然是建索引了，為Terms建立索引，最好的就是B-Tree索引（PS：MySQL就是B樹(shù)索引最好的例子）。

首先，讓我們來(lái)回憶一下MyISAM存儲(chǔ)引擎中的索引是什么樣的：

我們查找Term的過(guò)程跟在MyISAM中記錄ID的過(guò)程大致是一樣的

MyISAM中，索引和數(shù)據(jù)是分開(kāi)，通過(guò)索引可以找到記錄的地址，進(jìn)而可以找到這條記錄

在倒排索引中，通過(guò)Term索引可以找到Term在Term Dictionary中的位置，進(jìn)而找到Posting List，有了倒排列表就可以根據(jù)ID找到文檔了

（PS：可以這樣理解，類比MyISAM的話，Term Index相當(dāng)于索引文件，Term Dictionary相當(dāng)于數(shù)據(jù)文件）

（PS：其實(shí)，前面我們分了三步，我們可以把Term Index和Term Dictionary看成一步，就是找Term。因此，可以這樣理解倒排索引：通過(guò)單詞找到對(duì)應(yīng)的倒排列表，根據(jù)倒排列表中的倒排項(xiàng)進(jìn)而可以找到文檔記錄）

實(shí)際的 term index 是一棵 trie 樹(shù)：

例子是一個(gè)包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 樹(shù)。這棵樹(shù)不會(huì)包含所有的 term，它包含的是 term 的一些前綴。通過(guò) term index 可以快速地定位到 term dictionary 的某個(gè) offset，然后從這個(gè)位置再往后順序查找。再加上一些壓縮技術(shù)（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有 term 的尺寸的幾十分之一，使得用內(nèi)存緩存整個(gè) term index 變成可能。整體上來(lái)說(shuō)就是這樣的效果。

以上是三個(gè) posting list。我們現(xiàn)在需要把它們用 AND 的關(guān)系合并，得出 posting list 的交集。首先選擇最短的 posting list，然后從小到大遍歷。遍歷的過(guò)程可以跳過(guò)一些元素，比如我們遍歷到綠色的 13 的時(shí)候，就可以跳過(guò)藍(lán)色的 3 了，因?yàn)?3 比 13 要小。

整個(gè)過(guò)程如下

Next -> 2
Advance(2) -> 13
Advance(13) -> 13
Already on 13
Advance(13) -> 13 MATCH!!!
Next -> 17
Advance(17) -> 22
Advance(22) -> 98
Advance(98) -> 98
Advance(98) -> 98 MATCH!!!

最后得出的交集是 [13,98]，所需的時(shí)間比完整遍歷三個(gè) posting list 要快得多。但是前提是每個(gè) list 需要指出 Advance 這個(gè)操作，快速移動(dòng)指向的位置。什么樣的 list 可以這樣 Advance 往前做蛙跳？skip list：

考慮到頻繁出現(xiàn)的 term（所謂 low cardinality 的值），比如 gender 里的男或者女。如果有 1 百萬(wàn)個(gè)文檔，那么性別為男的 posting list 里就會(huì)有 50 萬(wàn)個(gè) int 值。用 Frame of Reference 編碼進(jìn)行壓縮可以極大減少磁盤占用。這個(gè)優(yōu)化對(duì)于減少索引尺寸有非常重要的意義。當(dāng)然 mysql b-tree 里也有一個(gè)類似的 posting list 的東西，是未經(jīng)過(guò)這樣壓縮的。

因?yàn)檫@個(gè) Frame of Reference 的編碼是有解壓縮成本的。利用 skip list，除了跳過(guò)了遍歷的成本，也跳過(guò)了解壓縮這些壓縮過(guò)的 block 的過(guò)程，從而節(jié)省了 cpu。

利用 bitset 合并

Bitset 是一種很直觀的數(shù)據(jù)結(jié)構(gòu)，對(duì)應(yīng) posting list 如：

[1,3,4,7,10]

對(duì)應(yīng)的 bitset 就是：

[1,0,1,1,0,0,1,0,0,1]

每個(gè)文檔按照文檔 id 排序?qū)?yīng)其中的一個(gè) bit。Bitset 自身就有壓縮的特點(diǎn)，其用一個(gè) byte 就可以代表 8 個(gè)文檔。所以 100 萬(wàn)個(gè)文檔只需要 12.5 萬(wàn)個(gè) byte。但是考慮到文檔可能有數(shù)十億之多，在內(nèi)存里保存 bitset 仍然是很奢侈的事情。而且對(duì)于個(gè)每一個(gè) filter 都要消耗一個(gè) bitset，比如 age=18 緩存起來(lái)的話是一個(gè) bitset，18<=age<25 是另外一個(gè) filter 緩存起來(lái)也要一個(gè) bitset。

所以秘訣就在于需要有一個(gè)數(shù)據(jù)結(jié)構(gòu)：

• 可以很壓縮地保存上億個(gè) bit 代表對(duì)應(yīng)的文檔是否匹配 filter；

• 這個(gè)壓縮的 bitset 仍然可以很快地進(jìn)行 AND 和 OR 的邏輯操作。

Lucene 使用的這個(gè)數(shù)據(jù)結(jié)構(gòu)叫做 Roaring Bitmap。

到此，相信大家對(duì)“Elasticsearch中的倒排索引結(jié)構(gòu)是什么”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！