索引本質(zhì)上就是一種加快檢索數(shù)據(jù)的存儲結(jié)構(gòu)，就像書本的目錄一下。

為了更好的理解正排索引和倒排索引，我們借由一個 **唐詩宋詞比賽，**這個比賽一共有兩個項目：

1. 給定詩詞名稱，背誦整首
2. 給詩詞中幾個詞語，讓你說出帶這些詞語的詩詞。

不難想到，1比較簡單，就是一個正向索引，2比較難，屬于逆向索引

正排索引

如果想贏得第一個項目，我們怎么設(shè)計，我們可以把詩詞名作為key，然后詩詞內(nèi)容作為value，然后放到hash中存儲起來。像這種我們吧實體id到數(shù)據(jù)內(nèi)容實體的關(guān)聯(lián)關(guān)系的索引我們稱之為正排索引

倒排索引

但是如果說我們想通過詞語來找出哪些詩詞中含有這些詩詞，這個怎么做哪？不能用hash這種來存儲了，這里就可以考慮倒排索引，

1. 將所有詩詞的內(nèi)容進(jìn)行分詞
2. 建立各個詞語到詩詞名稱的索引

根據(jù)倒排索引，我們可以

1. 獲取詩詞（詞項）對應(yīng)的文檔id
2. 如果有多個詩詞（詞項）也就會獲取到多個文檔id，然后做交集即可。
3. 最后通過交集的文檔id去文檔里面找
   

用hash行不行

如上圖，我們看起來用hash實現(xiàn)也是可以的，但是哪，如果數(shù)據(jù)量非常大，你想想詩詞中取這個key得多少，更別說其他需求了。所以簡單的使用hash是不行的，因為在存儲海量數(shù)據(jù)的時候，系統(tǒng)將會面臨下面這些問題：

1. 分詞形成的詞項（term）可能是海量的，需要可以在內(nèi)存和磁盤上高效存儲
2. 既然詞項是海量的，那么如何快速找到對應(yīng)的詞項也是個問題
3. 每個詞項對應(yīng)的文檔可能非常多，也就是上圖中的文檔列表很長
4. 在詞項對應(yīng)的文檔多的情況下，多個文檔列表做交集也是一個很大的問題

是不是感覺很難？
其實就是詞項和文檔列表的問題

1. Lucene的倒排索引的實現(xiàn)中，使用詞項索引（Term Index）解決了問題1和問題2
2. Lucene使用Roaring Bitmaps、跳表等技術(shù)解決了問題3和問題4

倒排索引的原理

倒排索引的組成一共有3個部分：

1. Term Index
2. Term Dictionary
3. Posting List

Term Dictionary放的是詞項，如果詞項越來越多查詢肯定不行，所以就有了**Term Index，它是Term Dictionary的索引，最好設(shè)計得越小越好，這樣緩存在內(nèi)存中也沒有壓力。**Posting LIst保存了每個詞項對應(yīng)的文檔Id列表

Segment

在了解 Term Index、Term Dictionary、Posting List 的具體實現(xiàn)前，我們先來看看 Segment、文檔、Field、Term 與它們的關(guān)系。

默認(rèn)情況下，ES每秒會把緩存中的數(shù)據(jù)寫入到Segment，然后根據(jù)某些規(guī)則進(jìn)行刷盤，并且合并這些Segment。所以Segment的數(shù)據(jù)一旦寫入就不變了，采用不變形有2個好處：

1. 更新對磁盤來說不友好
2. 一個可變的數(shù)據(jù)有并發(fā)寫的問題

邏輯上，一個Segment上會有多個文檔，一個文檔有多個字段。如下圖中的Segment就有兩個文檔，文檔1和文檔2都有兩個Field。這些字段的內(nèi)容會被分詞器形成多個Term，然后以塊的形式保存到Term Dictionary中，并且系統(tǒng)會對Term Dictionary的內(nèi)容做索引形成Term Index。在搜索的時候，通過

1. Term Index找到Block
2. 之后進(jìn)一步找到Tem對應(yīng)的Posting List中的文檔Id
3. 然后計算出符合條件的文檔Id列表

需要注意的是，Segment中的每個字段（Field）都會有自己的Term Index、Term Dictionary、Posting List結(jié)構(gòu)，也就是說每個Field中的這些結(jié)構(gòu)都是獨立的

Term Index的實現(xiàn)

Term Index作為Term Dictionary的索引，其最好是資源消耗小，可以緩存在內(nèi)存中，而且數(shù)據(jù)查找有較低的復(fù)雜度。在討論Tem Index如何實現(xiàn)前，看下面這幾個詞語：

這兩對詞語分別有公共的前綴：co和do。如果我們把Term Dictionary中的Term排序后按公共前綴抽取出來按塊存儲，而Term Index只使用公共前綴做索引，那本身要存儲coach、cottage兩個字符串的索引，現(xiàn)在只需要存儲co一個就行了。這樣的話，擁有同一個公共前綴的Term越多，實際上就是越省空間，并且這種設(shè)計在查找的時候 復(fù)雜度是前綴公共的長度：0（length（prefix））

但是這樣的索引也有缺點，它只能找到公共前綴所在的塊的地址，所以它既無法判斷這個Term是否存在，也不知道這個Temr保存在Term Dictionary（.tim）文件具體在什么位置上。

如上圖，對于在每個塊中如何快速查找到對應(yīng)的Term，我們可以使用二分法來搜索，因為Block中的數(shù)據(jù)是有序的。但機(jī)智的你是不是也發(fā)現(xiàn)可以優(yōu)化的地方？因為前綴在Term Index中保存了，那么Block中就不要為每個Term在保存對應(yīng)的前綴了，所以Block中保存的每個Term都可以省略掉前綴了。比如，co 前綴的 block1 中保存的內(nèi)容為 ach、ttage 即可。

**對于前綴索引的實現(xiàn)，業(yè)界使用了FST 算法來解決。**FST（Finite State Transducers）是一種 FSM（Finite State Machines，有限狀態(tài)機(jī)），并且有著類似于 Trie 樹的結(jié)構(gòu)。下面來簡單了解一下 FST。

FST有以下特點：

• 通過對Term Dictionary數(shù)據(jù)的前綴復(fù)用，壓縮了存儲空間
• 高效的查詢性能，O(len(prefix))的復(fù)雜度；
• 構(gòu)建后不可變。（事實上，倒排索引一旦生成就不可變了。）

下圖是一個簡單的FST圖。從圖中可以看出，一條邊有兩個元素label和out，其中l(wèi)abel為key的元素，例如cat這個key 就有 c、a、t 這三個元素，out為此邊的值value。小圓圈為FST的一個節(jié)點，節(jié)點分為兩類-普通節(jié)點和Final節(jié)點，圖中灰黑色的為Final節(jié)點，F(xiàn)inal節(jié)點中還有Finalout，代表 Final 節(jié)點的值

當(dāng)訪問cat的時候，讀取 c、a、t 的值作和， 再加上 Final 節(jié)點的 Finalout 值即可：10 + 0 + 5 + 0 = 15；當(dāng)訪問 dog 的時候，讀取 d、o、g 的值即可，但是由于 g 為 Final，所以需要加上 g 的 Finalout：1 + 0 + 0 + 1 = 2。

簡單的可以理解為這個： 不需要看上面ABC這些大的節(jié)點，直接看邊，cat就是c+a+t，另外看這個t是不是final節(jié)點，如果dog的話還需要加上g為final out =1

Term Dictionary的實現(xiàn)

在倒排索引組成的3個部分中，Term dictionary保存了Term和Posting List的關(guān)系，存儲了Term相關(guān)的信息， 比如記錄該Term的文檔數(shù)量、Term在Segment中出現(xiàn)的頻率，還保存了指向Posting List的指針（文檔列表的id的位置、詞頻位置等），

如下圖，在對Term Dictionary 做索引的時候，先將所有的Term進(jìn)行排序，然后將Term Dictionary中有共同前綴的Term抽取出來進(jìn)行存儲，再對共同前綴索引，最后通過索引就可以找到公共前綴對應(yīng)的塊在Term Dictionary文件中的偏移地址。

由于每個塊中都有共同前綴，所以不需要再保存每個Term的全部內(nèi)容，只需要保存其后綴即可，而且這些后綴都是排好序的。

至此，我們就可以通過Term Index 和 Term Dictionary 快速判斷一個 Term 是否存在，并且存在的時候還可以快速找到對應(yīng)的 Posting List 信息

Posting List的實現(xiàn)

上面的Posting List并不是只是包含文檔ID，其實Posting List包含的信息比較多，如文檔Id、詞頻、位置等等。Lucence把這些數(shù)據(jù)分成三個文件進(jìn)行存儲：

• .doc文件，記錄了文檔Id信息和Term的詞頻，還記錄了跳躍表信息，用來加速文檔Id的查詢；還記錄了Term在pos和pay文件中的位置，有助于進(jìn)行快速讀取
• .pay文件，記錄了Payload信息和Term在doc中的偏移信息；
• .pos文件，記錄了Term在doc中的位置信息

因為倒排索引的主要目的就是找到文檔id，所以下面討論Posting List的時候我們就關(guān)注文檔Id的信息，其他的就忽略了。前面提到過，Posting List主要面臨2個問題：

• 如果節(jié)省存儲
• 如何快速做交集

要節(jié)省存儲，可以對數(shù)據(jù)進(jìn)行壓縮存儲；至于如何做交集，業(yè)界應(yīng)用的得比較多的是跳表、Roaring Bitmaps等技術(shù)。下面我們就針對這兩個問題以及對應(yīng)的方法分別講解一下：

節(jié)省存儲：整形壓縮

不知道你有沒有留意過，其實int類型或者long類型是可以進(jìn)行壓縮的。我們可以根據(jù)需要處理的數(shù)據(jù)的取值范圍，選擇占用更小字節(jié)數(shù)的數(shù)據(jù)類型來存儲原數(shù)據(jù)，例如下面的Int數(shù)組：

# Int數(shù)組
[8, 12, 100, 140]

# 各個元素與其二進(jìn)制表示
8 -> 00001000
12 -> 00001100
100 -> 01100100
140 -> 10001100

這個Int數(shù)組，如果每個數(shù)據(jù)都需要用4個字節(jié)來保存的話，需要16個字節(jié)。但你會發(fā)現(xiàn)，數(shù)組中最大的數(shù)140只需要用8位（一個字節(jié)）就可以表示了。這樣一來，原來需要16個字節(jié)的數(shù)據(jù)只需要4個字節(jié)就可以表示了。

整數(shù)壓縮基本就是這個思路了，當(dāng)然還有其他玩法（下面介紹的VintBlock），但核心的思想都是：用最少的位數(shù)來表示原數(shù)據(jù)，并且兼顧數(shù)據(jù)讀取效率。Lucene在Posting List中使用了2種編碼格式來對整形類型的數(shù)據(jù)進(jìn)行壓縮- PackedBlock和VinBlock，并且在對整數(shù)進(jìn)行壓縮的基礎(chǔ)上，還會對文檔Id使用差值存儲的方式來對數(shù)據(jù)進(jìn)一步的壓縮處理。

• PackedBlock

在Lucene中，每當(dāng)處理完128個包含某個Term的文檔是，就會將這個文檔Id和詞頻使用的PackedInts進(jìn)行壓縮存儲，生成一個PackedBlock。PackedBlock中使用兩個數(shù)組，一個是存儲文檔id的，一個是存儲詞頻的。所以PackedBlock是存儲固定長度的整形數(shù)組的結(jié)構(gòu)，且數(shù)組的長度為128.

下面簡單介紹一下PackedInts的實現(xiàn)，PackedInts會將Int[] 壓縮打包成一個Block，其壓縮方式是把數(shù)組中最大的那個數(shù)占用的有效位數(shù)作為標(biāo)準(zhǔn)，然后各個元素打包的數(shù)組中，每個元素都按這個有效位數(shù)來算，例如下面數(shù)組：

# Int數(shù)組
[8, 12, 100, 120]

# 各個元素與其二進(jìn)制表示
8 -> 0001000
12 -> 0001100
100 -> 1100100
120 -> 1111000

最大數(shù)120的有效位數(shù)是7，所以數(shù)組中所有數(shù)據(jù)都可以使用7位來表示。假設(shè)這個數(shù)組有128個元素，且最大位120，那么這個壓縮后的數(shù)組就如以下：

最終這個數(shù)組占用的位數(shù)位7bit * 128 = 896bit =112字節(jié)（這里沒有算len占用的空間，但是不要忽略len也是要花費空間存儲的），這比起原數(shù)據(jù)128 * 4字節(jié)=512字節(jié)確實節(jié)省了不少

PackedBlock只能存儲固定長度的數(shù)組數(shù)據(jù)，如果一個Segment的文檔數(shù)不是128的整數(shù)倍，那該怎么辦那？這時可以使用VintBlock來進(jìn)行存儲

• VintBlock

VintBlock通過使用變長整形編碼方式來進(jìn)行壓縮，所以其可以存儲復(fù)合的數(shù)據(jù)類型，不需要想PackedInts那樣規(guī)定數(shù)據(jù)元素是多少位的。VintBlock采用Vint來對Int類型進(jìn)行壓縮，Vint采用可變長的字節(jié)來表示一個整數(shù)，每個字節(jié)只使用第1位到第7位來存儲數(shù)據(jù)，第8位用來作為是否需要讀取下一個字節(jié)的標(biāo)記

如上圖，本身Int 200需要4個字節(jié)，使用Vint只需要2個字節(jié)存儲即可

• 使用PackedBlock與VintBlock來解析.doc文件

Lucene在處理文檔的時候，每處理 128 篇文檔就會將其對應(yīng)的文檔 ID 數(shù)組（docDeltaBuffer）和詞頻（TermFreq）數(shù)組（freqBuffer）處理為兩個 Block：并且使用 PackedInts 類對數(shù)據(jù)進(jìn)行壓縮存儲，生成一個 PackedBlock。而把最后不足 128 篇文檔的數(shù)據(jù)采用 VIntBlock 來存儲（如果有 131 個文檔，會生成一個 PackedBlock 和 3 個 VIntBlock）。并且在生成 PackedBlock 的時候，會生成跳表（SkipData），使得在讀取數(shù)據(jù)時可以快速跳到指定的 PackedBlock。
下圖為你整理了處理 .doc 文件的數(shù)據(jù)結(jié)構(gòu)，以加深你對 Posting List 的理解。

• 使用文檔Id差值存儲來節(jié)省空間

整數(shù)的壓縮可以使當(dāng)個數(shù)值占用的空間得以減少，但數(shù)與數(shù)之間還存在著微妙的關(guān)系，兩個正整數(shù)的差一定會比它們種最大的那一個要小
利用這個特性，我們可以使需要壓縮的整數(shù)變成最小的數(shù)，從而進(jìn)一步壓縮空間。因為存儲文檔Id的數(shù)組是有序的（需要注意的是，詞頻是無序的，無法使用下面的處理方式），所以在保存文檔ID的時候，docDeltaBuffer 中存的不是文檔的 ID，而是與上一個文檔 ID 的差值，這樣做可以進(jìn)一步壓縮存儲空間！

ids = [1, 4, 6, 9, 14, 17, 21, 25]

如上面給定的數(shù)組 ids，如果用 PackedInts 的方式來對數(shù)據(jù)進(jìn)行壓縮的話，那么25（0001 1001）最少需要用 5 bit 來存儲，所以整個數(shù)組需要 5 * 8 = 40 bit 來存儲。如果數(shù)組中存儲的是文檔 ID 的差值，那么這個差值數(shù)組如下：

dtIds = [1, 3, 2, 3, 5, 3, 4, 4]

dtIds 數(shù)組中最大值為 5（0000 0101），其最少需要 3 bit 來表示，那么整個數(shù)組只需要 3 * 8 = 24 bit，相對于原來需要 40 bit 來存儲數(shù)據(jù)，差值存儲的方式可以有效降低存儲的空間。探其究竟，其實是兩個正整數(shù)間的差值會比它們間最大的那個要小，那么需要的有效位數(shù)就可能會減少了。
其實綜合了上面所有的流程，無非就是文檔 ID 使用增量編碼，數(shù)據(jù)分塊存儲、數(shù)據(jù)按需分配存儲空間，而這整個過程叫做 FOR（Frame Of Reference） 。

2.2.4.2 文檔Id列表的交集求解

如果你需要檢索朝代是唐代、詩人姓李、詩名中包含“明月”的詩，這時候系統(tǒng)會返回 3 條包含對應(yīng)文檔 ID 的列表，如下圖：

如果直接循環(huán)3個數(shù)組求交集，并不是很高效，下面對其進(jìn)行優(yōu)化。

• 位圖

如果我們將列表的數(shù)據(jù)改造成位圖會如何？假設(shè)有兩個posting list A、B和它們生成的位圖如下：

A = [2, 3, 5] => BitmapA = [0, 0, 1, 1, 0, 1]
B = [1, 2, 5] => BitmapB = [0, 1, 1, 0, 0, 1]

BitmapA AND BitmapB = [0, 0, 1, 0, 0, 1]

生成位圖的方式其實很簡單：Bitmap[A[i]] = 1，其他為 0 即可。這樣我們可以將 A、B 兩個位圖對應(yīng)的位置直接做 AND 位運算，由于位圖的長度是固定的，所以兩個位圖的 AND 運算的復(fù)雜度也是固定的，并且由于 CPU 執(zhí)行位運算效率非常高，所以在位圖不是特別大的情況下，使用位圖求解交集是非常高效的。

但是位圖位圖也有其致命的缺點，總結(jié)下來有這幾點：

1. 位圖可能會消耗大量的空間。即使位圖只需要1bit就可以表示相對應(yīng)的元素是否存在，但是如果一個列表的有一個元素特別大，例如數(shù)組 [1, 65535]，則需要 65535 bit 來表示。如果用 int32 類型的數(shù)組來表示的話，一個位圖就需要 512M（2^32 bit = 2^29 Byte = 512M），如果有 N 個這樣的列表，需要的存儲空間為 N * 512M，這個空間開銷是非?？膳碌?！
2. 位圖只適合數(shù)據(jù)稠密的場景
3. 位圖只適合存儲簡單整形類型的數(shù)據(jù)，對于復(fù)雜的對象類型無法處理，或者說復(fù)雜的類型本身就無法在CPU上直接使用AND這樣的操作符

業(yè)界為了解決位圖空間消耗大的問題，會使用一種壓縮位圖技術(shù)，也就是Roading Bitmap來代替簡單的位圖。Roadring Bitmap在業(yè)界應(yīng)用廣泛，下面來看看Roaring Bitmap的實現(xiàn)

• Roaring Bitmaps

它會把一個 32 位的整數(shù)分成兩個部分：高 16 位和低 16 位。然后將高 16 位作為一個數(shù)值存儲到有序數(shù)組里，這個數(shù)組的每一個元素都是一個塊。而低 16 位則存儲到 2^16 的位圖中去，將對應(yīng)的位置設(shè)置為 1。這樣每個塊對應(yīng)一個位圖，如下圖：

Roaring Bitmaps 通過拆分?jǐn)?shù)據(jù)，形成按需分配的有序數(shù)組 + Bitmaps 的形式來節(jié)省空間。其中一個 Bitmaps 最多 2^16 個 bit，共消耗 8K。而由于每個塊中存的是整數(shù)，每個數(shù)需要 2 個字節(jié)來存儲即可，這樣的整數(shù)共有 2^16 個，所以有序數(shù)組最多消耗 2 Byte * 2^16 = 128K 的存儲空間。由于存儲塊的有序數(shù)組是按需分配的，所以 Roaring Bitmaps 的存儲空間由數(shù)據(jù)量來決定，而 Bitmaps 的存儲空間則是由最大的數(shù)來決定。舉個例子就是，數(shù)組[0, 2^32 - 1]，使用 Bitmaps 的話需要 512M 來存儲，而 Roaring Bitmaps只需要 2 * (2 Byte + 8K)。
由于 Roaring Bitmaps 由有序數(shù)組加上 Bitmaps 構(gòu)成，所以要確認(rèn)一個數(shù)是否在 Roaring Bitmaps 中，需要通過兩次查詢才能得到結(jié)果。先以高 16 位在有序數(shù)組中進(jìn)行二分查找，其復(fù)雜度為 O(log n)；如果存在，則再拿低 16 位在對應(yīng)的 Bitmaps 中查找，判斷對應(yīng)的位置是否為 1 即可，此時復(fù)雜度為 O(1)。所以，Roaring Bitmaps 可以做到節(jié)省空間的同時，還有著高效的檢索能力。
但是機(jī)智的你不知道有沒有看出來，如果每個塊的 Bitmaps 一直消耗 8K 的存儲是不是超級浪費？如果這一個塊中的數(shù)據(jù)很少，或者很稀疏，那還不如把 Bitmaps 做成數(shù)組呢。那到底用數(shù)組還是用 Bitmaps，閾值在哪里呢？當(dāng)數(shù)據(jù)量達(dá)到 4096 的時候，我們發(fā)現(xiàn) 4096 * 16 bit(2 Byte) = 8K，所以當(dāng)一個塊的數(shù)據(jù)量小于 4096 的時候，可以使用 short 類型的有序數(shù)組存儲數(shù)據(jù)，并且使用變長數(shù)組進(jìn)一步節(jié)省空間。

業(yè)界除了使用 Roaring Bitmaps 來求交集外，還使用了跳表。

• 使用跳表加速多個列表交集的求解

跳表是一種有序的數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其他節(jié)點的索引，從而達(dá)到快速訪問的目的。

如上圖，有序鏈表不能像有序數(shù)組那樣使用二分法進(jìn)行快速訪問，但可以對有序鏈表維護(hù)一層或者多層索引使其快速訪問。
在求解兩個有序列表 A 和 B 的交集時，可以使用歸并排序的方法來遍歷兩個列表，將復(fù)雜度從 O(M * N) 降低到 O(M + N)，這里的 M、N 分別為這兩個列表的長度。
鏈表歸并求交集的過程可以總結(jié)為以下三個步驟。

1. 第一步：將指針 p1 和 p2 分別指向列表 A 和 B 的開頭。
2. 第二部：比較 p1 和 p2 指向的數(shù)據(jù)，會出現(xiàn) 3 種情況，如果內(nèi)容相等，說明是公共元素，需要加入到結(jié)果集中；如果 p1 的內(nèi)容小于 p2 的內(nèi)容，p1 向后移；如果 p1 的內(nèi)容大于 p2 的內(nèi)容，p2 向后移?？偨Y(jié)起來就是，誰小誰就往前走，相等就一起往前走，直到有一方結(jié)束！
3. 第三步：重復(fù)第二步，直到 p1 或者 p2 到達(dá)鏈表尾為止。

這里我們再結(jié)合以下示意圖和例子來加深一下對歸并流程的理解。指針 p1 和 p2 的原位置如下圖所示，下面我們就來看看它們是怎么移動的。

1. p2 的內(nèi)容小于 p1 的內(nèi)容（2 < 3），基于誰小誰就往前走的原則，所以 p2 往后移動一位，移動后的結(jié)果如下圖：

2. p1 的內(nèi)容小于 p2 的內(nèi)容（3 < 4），基于誰小誰就往后走的原則，所以 p1 往后移動一位，移動后的結(jié)果如下圖：

3. p2 的內(nèi)容小于 p1 的內(nèi)容（4 < 5），基于誰小誰就往后走的原則，所以 p2 往后移動一位，移動后的結(jié)果如下圖：

4. p2 的內(nèi)容等于 p1 的內(nèi)容（5 = 5），所以 5 為公共元素，需要記錄下來，并且基于相等就一起往后走的原則，所以 p2 和 p1 都往后移動一位，移動后的結(jié)果如下圖：

就這樣，一直繼續(xù)上述的流程直到鏈表B結(jié)束

歸并排序的方式可以降低鏈表求交集的復(fù)雜度，但上述的算分還用優(yōu)化的的地方。從下圖中可以看出，此時 p1 要從 10 開始找直到多次才能找到 1000 這個大于或者等于 p2 的元素

要優(yōu)化這個問題，可以使用前面介紹的跳表，給鏈表做索引。下圖中，p1 使用跳表索引經(jīng)過比較少的次數(shù)就可以找到 1000 了。

那既然鏈表 A 和 B 都有跳表索引的結(jié)構(gòu)，那在鏈表 B 中查找數(shù)據(jù)也同樣可以使用跳表索引的結(jié)構(gòu)進(jìn)行加速。如下圖，當(dāng) p1 的值大于鏈表 B 當(dāng)前值時，用 p1 的值當(dāng)作 key，在鏈表 B 中使用二分查找，這樣 p2 就可以使用跳表索引快速往前跳了。

這種二分查找法可以總結(jié)為：誰當(dāng)前值大，就用其作為 key 到其他列表中做二分查找。但是，需要說明的是，雖然使用跳表索引可以降低查詢的復(fù)雜度，但是跳表索引是要消耗空間的，并且在構(gòu)建跳表的時候，也需要消耗額外的時間！

總結(jié)

ES 中的倒排索引主要分為 3 個部分：Term Index、Term Dictionary 和 Posting List。文章來源地址http://www.zghlxwxcb.cn/news/detail-846888.html

• Term Index 是 Term Dictionary 的索引，使用它可以快速判斷一個 Term 是否存在，并且可以找到這個 Term 在 Term Dictionary 存儲的塊地址。Term Index 使用了 FST 來實現(xiàn)，其有著小巧且復(fù)雜度低的特點。
• 而 Term Dictionary 是存儲 Term 信息的地方，其內(nèi)容包括 Term、包含該 Term 的文檔的數(shù)量、Term 在整個 Segment 中出現(xiàn)的頻率等。
• 我們還學(xué)習(xí)了 Posting List 的實現(xiàn)，了解了 Lucene 使用 PackedBlock 和 VIntBlock 對整數(shù)進(jìn)行壓縮的思路，也介紹了業(yè)界使用 Roaring Bitmaps 和跳表來解決列表求交集的方案。

到了這里，關(guān)于ES入門十一：正排索引和倒排索引的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！