這里不涉及到源碼，只是根據(jù)網(wǎng)上的一些文章總結(jié)一下，目前不需要細究，只需要知道大概就好，除非你的工作是二次開發(fā)ES

這張圖你可以認為粗糙的描述倒排索引對應(yīng)關(guān)系，下面的文章也是主要講解這張圖各個部分含義

一、?Term Index(詞項索引)

看這個?Term Index是不是特別想樹的數(shù)據(jù)結(jié)構(gòu)？比如二叉樹或者多叉樹？其實是FST，下面看一下它是怎么出來的

1、FSM（Finite State Machine）有限狀態(tài)機

表示有限個狀態(tài)（State）集合以及這些狀態(tài)之間轉(zhuǎn)移和動作的數(shù)學(xué)模型。其中一個狀態(tài)被標記為開始狀態(tài)，0個或更多的狀態(tài)被標記為final狀態(tài)。來自[轉(zhuǎn)]ElasticSearch 查詢的秘密

這種模型使用原型的節(jié)點標示某個“狀態(tài)”，狀態(tài)之間可以互相轉(zhuǎn)換，但是轉(zhuǎn)換過程是無向的。
比如睡覺醒了可以去工作，工作累了可以去玩手機；或者工作中想去上廁所等等。
在這個模型中，標示狀態(tài)的節(jié)點是有限多個的，但狀態(tài)的轉(zhuǎn)換的情況是無限多的，同一時刻只能處于某一個狀態(tài)，并且狀態(tài)的轉(zhuǎn)換是無序切循環(huán)的。
顯然這種模型并不適用于描述Term Dictionary這樣的數(shù)據(jù)結(jié)構(gòu)，所以再看一下演變的FSA

2、FSA（Finite State Acceptor）確定無環(huán)有限狀態(tài)接收機

相較于FSM，FSA增加了Entry和Final的概念,這樣就增加了如下3個特性
1、確定：意味著指定任何一個狀態(tài)，只可能最多有一個轉(zhuǎn)移可以訪問到。
2、無環(huán)： 不可能重復(fù)遍歷同一個狀態(tài)
3、接收機：有限狀態(tài)機只“接受”特定的輸入序列，并終止于final狀態(tài)。
來自：關(guān)于Lucene的詞典FST深入剖析

我們?nèi)绾蝸肀硎局挥幸粋€key：jul 的集合。FSA是這樣的：

當查詢這個FSA是否包含“jul”的時候，按字符依序輸入。

輸入j，F(xiàn)SA從0->1
輸入u, FSA從1->2
輸入l，F(xiàn)SA從2->3
這個時候，F(xiàn)SA處于final狀態(tài)3，所以jul是在這個集合的。

增加一個key:mar 就如下表

再增加一個key:jun

遍歷算法是這樣的：

初始狀態(tài)0， key=””
->1, key=”j”
->2, key=”ju”
->3, key=”jul”, 找到j(luò)ul
2<-, key=”ju”
->3, key=”jun”, 找到j(luò)un
2<-, key=”ju”
1<-, key=”j”
0<-, key=””
->4, key=”m”
->5, key=”ma”,
->3, key=”mar”,找到mar
這個算法時間復(fù)雜度O(n),n是集合里所有的key的大小, 空間復(fù)雜度O(k),k是結(jié)合內(nèi)最長的key字段length。

再看一下更復(fù)雜的，由“october”，“november”,”december”構(gòu)成的FSA

所以FSA不光共用前綴，后綴也一樣可以共用

即使FSA已經(jīng)滿足了對Term Dictionary數(shù)據(jù)高效存儲的基本要求，但是仍然不滿足的一個問題就是，F(xiàn)SA無法存儲key-value的數(shù)據(jù)類型，

3、FST(Deterministic acyclic finite state transducer)確定無環(huán)狀態(tài)轉(zhuǎn)換器

FST在FSA基礎(chǔ)上為每一個出度添加了一個output屬性，用來表示每個term的value值，
來自：倒排索引：ES倒排索引底層原理及FST算法的實現(xiàn)過程

下面拿key:msb輸出 要輸出一個value:10 和再新增一個key:msbtech輸出一個value:5的FST是如何構(gòu)建的

當?shù)谝粋€term:msb被寫入FST中，其輸出值被保存在了其第一個節(jié)點的出度上，在數(shù)據(jù)從FST中讀取的時候， 計算其每個節(jié)點對應(yīng)的出度的輸出值以及終止節(jié)點的final output值的累加和，從而得出輸出值，此時msb的輸出值就是10+0+0+0=10，但是這里我用0來標識沒有輸出值，但實際情況沒有輸出值就是空而不是0，這里寫0只是為了方便你去理解，這一點是需要注意的。

當?shù)诙€term:msbteach被寫入的時候，其輸出值5與msb的輸出值10發(fā)生了沖突，這時，通用最小化算法法則發(fā)揮了功效。數(shù)字雖然不能像字符那樣以前綴作為復(fù)用手段，但是數(shù)字是可以累加的，10可以拆成兩個數(shù)字5，這樣10和5就產(chǎn)生了公共部分，即5，所以這個時候m的輸出值就需要改成5，那另一個5就需要找一個合適的位置，然而把它存放在任何一個節(jié)點的出度上似乎都會影響msbtech的計算結(jié)果，為了避免這個問題，可以把這個多出來的屬于msb的輸出值存入msb的final節(jié)點的final output中，節(jié)點的final output只會在當前出度是輸入值的最后一個字符并且出度的target指向的是final節(jié)點的時候，才會參與計算。因此此時的msb和msbtech就各自把輸出值存入了合適的位置，互不影響而且做到了“通用最小化”原則。

所以大體上就知道了?Term Index 中的FST是怎樣的數(shù)據(jù)結(jié)構(gòu)了

二、Term Dictionary(詞項字典)

這個就比較直白，就是各個分詞后的字段列表
來自：倒排索引：ES倒排索引底層原理及FST算法的實現(xiàn)過程

下面拿右邊的做一個例子，這樣Term Dictionary會把右邊的表中product字段的內(nèi)容分詞，分成左邊的表格中的樣例

但是既然都已經(jīng)知道上面的term index了，那看存儲詞項索引的文件.tip數(shù)據(jù)結(jié)構(gòu)和輸出如何映射到詞項字典文件.tim

詞項字典包含了index field的所有經(jīng)過normalization token filters處理之后的詞項數(shù)據(jù)，最終存儲在.tim文件中。
所謂normalization其實是一個如去重、時態(tài)統(tǒng)一、大小寫統(tǒng)一、近義詞處理等類似的相關(guān)操作；詞項索引就是為了加速詞項字典檢索的一種數(shù)據(jù)結(jié)構(gòu)，落地文件為.tip

所以，詞項字典也是存儲了很多東西的，一個block代表像小米、手機這樣的分詞塊

三、Posting List(倒排表)

倒排表這里主要說一下兩種壓縮算法，因為都知道倒排表存儲的是詞項字典對應(yīng)的文檔的id，那如何存儲的呢？因為要考慮到量的問題，雖然不是文檔本身，但是id這個字段存儲幾十億的量還是挺大的

1、FOR（Frame Of Reference）壓縮算法(差值存儲)

即不存儲原本的數(shù)值，而是存儲每個數(shù)值與前一個數(shù)字的差值，這個適用于id之間差值都很小，或者只有幾個id之間差值大的場景，這種數(shù)組也叫稠密數(shù)組
下面以某個id的集合是[1,2,3…100萬]和[73，300，302，332，343，372]舉例

如果是[1,2,3…100萬]，用差值存儲你可能就知道為什么這么做了，節(jié)省的空間存儲很多，壓縮了32倍。

下面又用了一個特殊的例子[73，300，302，332，343，372]來演示特殊的情況，就是某兩個id之間差值之間太大的情況，數(shù)組經(jīng)過拆分，分為了兩個數(shù)組，第一個數(shù)組每個數(shù)字占用1個Byte，共兩個數(shù)字，總占用為2Bytes，記錄數(shù)組單位大小的Record Space大小為1Byte，第二個數(shù)組每個數(shù)字占用5個bit，一共四個數(shù)字，共計20bit，但是計算空間的最小單位是Byte，所以實際占用的大小為3Bytes，第二個數(shù)組的Record Space大小也是1Byte，因此壓縮后的數(shù)據(jù)總大小為1B+2x1B+3B+1B=7Bytes，相比壓縮之前，大小不到原先的三分之一。

但是可能還有更特殊的，每一個id之間相差都很大，就有了下面這種壓縮算法RBM

2、RBM（RoaringBitmap）壓縮算法(32位int拆成兩個16位的short存儲)

針對id數(shù)據(jù)大部分id之間差值都很大，用差值存儲壓縮不了多少的情況，這里稱這種數(shù)組為稀疏數(shù)組，Lucene對于這種稀疏數(shù)組采用了另一種壓縮算法
下面用 [1000，62101，131385，132052，191173，196658] 這種典型稀疏數(shù)組為例

RBM算法本身的設(shè)計思路是將原數(shù)字的的32個bit分為了高16位和低16位。以原數(shù)組中的196658這個id為例，將其轉(zhuǎn)化為二進制結(jié)果為 110000000000110010，我們看到其實結(jié)果是不足32bits的，但因為每個int型都是有32個bit組成的，不足32bit會在其前面補0，實際其占用的空間大小仍然為32bits，如果這一點不理解，打個比方，公交車有32個座位，無論是否坐滿，都是使用了32個座位。最終196658轉(zhuǎn)換成二進制就是0000 0000 0000 0011 0000 0000 0011 0010，前16位就是高16位，轉(zhuǎn)換成十進制就是3，后16位也就是低16位，轉(zhuǎn)換成十進制就是50

到這一步其實你有疑問？拆開空間也沒有變小啊，還是32bits?。磕强梢岳^續(xù)往下看

對數(shù)組中每個數(shù)字進行相同的操作，會得到以下結(jié)果：（0,1000）（0,62101）（2,313）（2,980）（2,60101）（3,50），其含義就是每個數(shù)字都由一個很大的數(shù)字變?yōu)榱藘蓚€很小的數(shù)字，并且這兩個數(shù)字都不超過65536，更重要的是，當前結(jié)果是非常適合壓縮的，因為不難看出，出現(xiàn)了很多重復(fù)的數(shù)字，

比如前兩個數(shù)字的得數(shù)都是0，以及第2、3、4個數(shù)字的得數(shù)都是2。RBM使用了非常適合存儲當前結(jié)果的數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)是一種類似于哈希的結(jié)構(gòu)，只不過Key值是一個short有序不重復(fù)數(shù)組，用于保存每個商值，value是一個容器，保存了當前Key值對應(yīng)的所有模，這些模式不重復(fù)的，因為同一個商值的余數(shù)是不會重復(fù)的。

這里的容器官方稱之為Container,RBM中包含三種Container，分別是ArrayContainer、BitmapContainer和RunContainer，

(1)ArrayContainer

ArrayContainer，顧名思義，Container中實際就是一個short類型的數(shù)組，其空間占用的曲線如圖3-4中的紅色線段，注意這里是線段，因為docs的數(shù)量最大不會超過65536，其函數(shù)為 y（空間占用）=x（docs 長度） x 2Bytes，當長度達到65536極限值的時候，其占用的大小就是16bit * 65536 / 8 /1024 = 128KB，乘以65536是總bit數(shù)，除以8是換算成Byte，除以1024是換算成KB。

(2)BitmapContainer

第二種是BitmapContainer，理解BitmapContainer之前首先要了解什么是bitmap。以往最常見的數(shù)據(jù)存儲方式都是二進制進位存儲，比如我們使用8個bit存儲數(shù)字，如果存十進制0，那二進制就是 0 0 0 0 0 0 0 0，如果存十進制1，那就是 0 0 0 0 0 0 0 1，如果存十進制2，那就是 0 0 0 0 0 0 1 1，用到了第二個bit。這種做法在當前場景下存儲效率顯然不高，如果我們現(xiàn)在不用bit來存儲數(shù)據(jù)，而是用來作為“標記”，即標記當前bit位置商是否存儲了數(shù)字，出的數(shù)字值就是bit的下標，如下圖所示，就表示存儲了2、3、5、7四個數(shù)字，第一行數(shù)字的bit僅代表當前index位置上是否存儲了數(shù)字，如果存儲了就記作1，否則記為0，存儲的數(shù)字值就是其index，并且存儲這四個數(shù)字只使用了一個字節(jié)。

不過這種存儲方式的問題就是，存儲的數(shù)字不能包含重復(fù)數(shù)字，并且Bitmap的大小是固定的，不管是否存儲了數(shù)值，不管存儲了幾個值，占用的空間都是恒定的，只和bit的長度有關(guān)系。
但是我們剛才已經(jīng)說過，同一個Container中的數(shù)字是不會重復(fù)的，因此這種數(shù)據(jù)類型正好適合用這種數(shù)據(jù)結(jié)構(gòu)作為載體，而因為我們Container的最大容量是65536，因此Bitmap的長度固定為65536，也就是65536個bit，換算成千字節(jié)就是8KB，如圖的藍色線段所示，即Lucene的RBM中BitmapContainer固定占用8KB大小的空間，
通過對比可以發(fā)現(xiàn)，當doc的數(shù)量小于4096的時候，使用ArrayContainer更加節(jié)省空間，當doc數(shù)量大于4096的時候，使用BitmapContainer更加節(jié)省空間

(3)RunContainer

第三種Container叫RunContainer，這種類型是Lucene 5之后新增的類型，主要應(yīng)用在連續(xù)數(shù)字的存儲商，比如倒排表中存儲的數(shù)組為 [1,2,3…100W] 這樣的連續(xù)數(shù)組，如果使用RunContainer，只需存儲開頭和結(jié)尾兩個數(shù)字：1和100W，即占用8個字節(jié)。這種存儲方式的優(yōu)缺點都很明顯，它嚴重收到數(shù)字連續(xù)性的影響，連續(xù)的數(shù)字越多，它存儲的效率就越高。文章來源地址http://www.zghlxwxcb.cn/news/detail-776164.html

到了這里，關(guān)于Elasticsearch 查詢命令執(zhí)行時，如何通過詞項索引、詞項字典、倒排表定位文檔邏輯介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！