今天面試有問到倒排索引爪模，以前只是有個大概概念哗戈，看了這篇文章之后清晰了不少糖驴，特意轉(zhuǎn)過來分享給大家霉猛！
如何快速檢索淆党？
Elasticsearch 是通過 Lucene 的倒排索引技術(shù)實現(xiàn)比關(guān)系型數(shù)據(jù)庫更快的過濾酷师。特別是它對多條件的過濾支持非常好，比如年齡在 18 和 30 之間染乌，性別為女性這樣的組合查詢山孔。倒排索引很多地方都有介紹，但是其比關(guān)系型數(shù)據(jù)庫的 b-tree 索引快在哪里荷憋？到底為什么快呢台颠？
籠統(tǒng)的來說，b-tree 索引是為寫入優(yōu)化的索引結(jié)構(gòu)勒庄。當(dāng)我們不需要支持快速的更新的時候串前，可以用預(yù)先排序等方式換取更小的存儲空間，更快的檢索速度等好處实蔽，其代價就是更新慢荡碾。要進(jìn)一步深入的化，還是要看一下 Lucene 的倒排索引是怎么構(gòu)成的局装。
這里有好幾個概念坛吁。我們來看一個實際的例子，假設(shè)有如下的數(shù)據(jù)：
這里每一行是一個 document铐尚。每個 document 都有一個 docid拨脉。那么給這些 document 建立的倒排索引就是：
可以看到，倒排索引是 per field 的塑径，一個字段由一個自己的倒排索引女坑。18,20 這些叫做 term，而 [1,3] 就是 posting list统舀。Posting list 就是一個 int 的數(shù)組匆骗，存儲了所有符合某個 term 的文檔 id劳景。那么什么是 term dictionary 和 term index？
假設(shè)我們有很多個 term碉就，比如：
Carla,Sara,Elin,Ada,Patty,Kate,Selena
如果按照這樣的順序排列盟广，找出某個特定的 term 一定很慢，因為 term 沒有排序瓮钥，需要全部過濾一遍才能找出特定的 term筋量。排序之后就變成了：
Ada,Carla,Elin,Kate,Patty,Sara,Selena
這樣我們可以用二分查找的方式，比全遍歷更快地找出目標(biāo)的 term碉熄。這個就是 term dictionary桨武。有了 term dictionary 之后，可以用 logN 次磁盤查找得到目標(biāo)锈津。但是磁盤的隨機(jī)讀操作仍然是非常昂貴的（一次 random access 大概需要 10ms 的時間）呀酸。所以盡量少的讀磁盤，有必要把一些數(shù)據(jù)緩存到內(nèi)存里琼梆。但是整個 term dictionary 本身又太大了性誉，無法完整地放到內(nèi)存里。于是就有了 term index茎杂。term index 有點像一本字典的大的章節(jié)表错览。比如：
A 開頭的 term ……………. Xxx 頁
C 開頭的 term ……………. Xxx 頁
E 開頭的 term ……………. Xxx 頁
如果所有的 term 都是英文字符的話，可能這個 term index 就真的是 26 個英文字符表構(gòu)成的了煌往。但是實際的情況是倾哺，term 未必都是英文字符，term 可以是任意的 byte 數(shù)組携冤。而且 26 個英文字符也未必是每一個字符都有均等的 term悼粮，比如 x 字符開頭的 term 可能一個都沒有，而 s 開頭的 term 又特別多曾棕。實際的 term index 是一棵 trie 樹：
例子是一個包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 樹扣猫。這棵樹不會包含所有的 term，它包含的是 term 的一些前綴翘地。通過 term index 可以快速地定位到 term dictionary 的某個 offset申尤，然后從這個位置再往后順序查找。再加上一些壓縮技術(shù)（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有 term 的尺寸的幾十分之一衙耕，使得用內(nèi)存緩存整個 term index 變成可能昧穿。整體上來說就是這樣的效果。
現(xiàn)在我們可以回答“為什么 Elasticsearch/Lucene 檢索可以比 mysql 快了橙喘。Mysql 只有 term dictionary 這一層时鸵，是以 b-tree 排序的方式存儲在磁盤上的。檢索一個 term 需要若干次的 random access 的磁盤操作。而 Lucene 在 term dictionary 的基礎(chǔ)上添加了 term index 來加速檢索饰潜，term index 以樹的形式緩存在內(nèi)存中初坠。從 term index 查到對應(yīng)的 term dictionary 的 block 位置之后，再去磁盤上找 term彭雾，大大減少了磁盤的 random access 次數(shù)碟刺。
額外值得一提的兩點是：term index 在內(nèi)存中是以 FST（finite state transducers）的形式保存的，其特點是非常節(jié)省內(nèi)存薯酝。Term dictionary 在磁盤上是以分 block 的方式保存的半沽，一個 block 內(nèi)部利用公共前綴壓縮，比如都是 Ab 開頭的單詞就可以把 Ab 省去吴菠。這樣 term dictionary 可以比 b-tree 更節(jié)約磁盤空間者填。
如何聯(lián)合索引查詢？
所以給定查詢過濾條件 age=18 的過程就是先從 term index 找到 18 在 term dictionary 的大概位置做葵，然后再從 term dictionary 里精確地找到 18 這個 term幔托，然后得到一個 posting list 或者一個指向 posting list 位置的指針。然后再查詢 gender= 女 的過程也是類似的蜂挪。最后得出 age=18 AND gender= 女 就是把兩個 posting list 做一個“與”的合并。
這個理論上的“與”合并的操作可不容易嗓化。對于 mysql 來說棠涮，如果你給 age 和 gender 兩個字段都建立了索引，查詢的時候只會選擇其中最 selective 的來用刺覆，然后另外一個條件是在遍歷行的過程中在內(nèi)存中計算之后過濾掉严肪。那么要如何才能聯(lián)合使用兩個索引呢？有兩種辦法：
- 使用 skip list 數(shù)據(jù)結(jié)構(gòu)谦屑。同時遍歷 gender 和 age 的 posting list驳糯，互相 skip；
- 使用 bitset 數(shù)據(jù)結(jié)構(gòu)氢橙，對 gender 和 age 兩個 filter 分別求出 bitset酝枢，對兩個 bitset 做 AN 操作。
PostgreSQL 從 8.4 版本開始支持通過 bitmap 聯(lián)合使用兩個索引悍手，就是利用了 bitset 數(shù)據(jù)結(jié)構(gòu)來做到的帘睦。當(dāng)然一些商業(yè)的關(guān)系型數(shù)據(jù)庫也支持類似的聯(lián)合索引的功能。Elasticsearch 支持以上兩種的聯(lián)合索引方式坦康，如果查詢的 filter 緩存到了內(nèi)存中（以 bitset 的形式）竣付，那么合并就是兩個 bitset 的 AND。如果查詢的 filter 沒有緩存滞欠，那么就用 skip list 的方式去遍歷兩個 on disk 的 posting list古胆。
利用 Skip List 合并
以上是三個 posting list。我們現(xiàn)在需要把它們用 AND 的關(guān)系合并筛璧，得出 posting list 的交集逸绎。首先選擇最短的 posting list惹恃，然后從小到大遍歷。遍歷的過程可以跳過一些元素桶良，比如我們遍歷到綠色的 13 的時候座舍，就可以跳過藍(lán)色的 3 了，因為 3 比 13 要小陨帆。
整個過程如下
<pre style="margin: 0px 0px 1.5rem; padding: 0px; font-family: Courier, "Courier New", monospace; display: block; font-weight: 400; background: rgb(249, 250, 252); border-radius: 5px; overflow: hidden; color: rgb(74, 74, 74); font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; letter-spacing: normal; orphans: 2; text-align: justify; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">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!!!</pre>
最后得出的交集是 [13,98]曲秉，所需的時間比完整遍歷三個 posting list 要快得多。但是前提是每個 list 需要指出 Advance 這個操作疲牵，快速移動指向的位置承二。什么樣的 list 可以這樣 Advance 往前做蛙跳？skip list：
從概念上來說纲爸，對于一個很長的 posting list亥鸠，比如：
[1,3,13,101,105,108,255,256,257]
我們可以把這個 list 分成三個 block：
[1,3,13] [101,105,108] [255,256,257]
然后可以構(gòu)建出 skip list 的第二層：
[1,101,255]
1,101,255 分別指向自己對應(yīng)的 block。這樣就可以很快地跨 block 的移動指向位置了识啦。
Lucene 自然會對這個 block 再次進(jìn)行壓縮负蚊。其壓縮方式叫做 Frame Of Reference 編碼。示例如下：
考慮到頻繁出現(xiàn)的 term（所謂 low cardinality 的值）颓哮，比如 gender 里的男或者女家妆。如果有 1 百萬個文檔，那么性別為男的 posting list 里就會有 50 萬個 int 值冕茅。用 Frame of Reference 編碼進(jìn)行壓縮可以極大減少磁盤占用伤极。這個優(yōu)化對于減少索引尺寸有非常重要的意義。當(dāng)然 mysql b-tree 里也有一個類似的 posting list 的東西姨伤，是未經(jīng)過這樣壓縮的哨坪。
因為這個 Frame of Reference 的編碼是有解壓縮成本的。利用 skip list乍楚，除了跳過了遍歷的成本当编，也跳過了解壓縮這些壓縮過的 block 的過程，從而節(jié)省了 cpu炊豪。
利用 bitset 合并
Bitset 是一種很直觀的數(shù)據(jù)結(jié)構(gòu)凌箕，對應(yīng) posting list 如：
[1,3,4,7,10]
對應(yīng)的 bitset 就是：
[1,0,1,1,0,0,1,0,0,1]
每個文檔按照文檔 id 排序?qū)?yīng)其中的一個 bit。Bitset 自身就有壓縮的特點词渤，其用一個 byte 就可以代表 8 個文檔牵舱。所以 100 萬個文檔只需要 12.5 萬個 byte。但是考慮到文檔可能有數(shù)十億之多缺虐，在內(nèi)存里保存 bitset 仍然是很奢侈的事情芜壁。而且對于個每一個 filter 都要消耗一個 bitset，比如 age=18 緩存起來的話是一個 bitset，18<=age<25 是另外一個 filter 緩存起來也要一個 bitset慧妄。
所以秘訣就在于需要有一個數(shù)據(jù)結(jié)構(gòu)：
- 可以很壓縮地保存上億個 bit 代表對應(yīng)的文檔是否匹配 filter顷牌；
- 這個壓縮的 bitset 仍然可以很快地進(jìn)行 AND 和 OR 的邏輯操作。
Lucene 使用的這個數(shù)據(jù)結(jié)構(gòu)叫做 Roaring Bitmap塞淹。
其壓縮的思路其實很簡單窟蓝。與其保存 100 個 0，占用 100 個 bit饱普。還不如保存 0 一次运挫，然后聲明這個 0 重復(fù)了 100 遍。
這兩種合并使用索引的方式都有其用途套耕。Elasticsearch 對其性能有詳細(xì)的對比（ https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps ）谁帕。簡單的結(jié)論是：因為 Frame of Reference 編碼是如此 高效，對于簡單的相等條件的過濾緩存成純內(nèi)存的 bitset 還不如需要訪問磁盤的 skip list 的方式要快冯袍。
如何減少文檔數(shù)匈挖？
一種常見的壓縮存儲時間序列的方式是把多個數(shù)據(jù)點合并成一行。Opentsdb 支持海量數(shù)據(jù)的一個絕招就是定期把很多行數(shù)據(jù)合并成一行康愤，這個過程叫 compaction儡循。類似的 vivdcortext 使用 mysql 存儲的時候，也把一分鐘的很多數(shù)據(jù)點合并存儲到 mysql 的一行里以減少行數(shù)征冷。
這個過程可以示例如下：
可以看到贮折，行變成了列了。每一列可以代表這一分鐘內(nèi)一秒的數(shù)據(jù)资盅。
Elasticsearch 有一個功能可以實現(xiàn)類似的優(yōu)化效果，那就是 Nested Document踊赠。我們可以把一段時間的很多個數(shù)據(jù)點打包存儲到一個父文檔里呵扛，變成其嵌套的子文檔。示例如下：
{timestamp:12:05:01, idc:sz, value1:10,value2:11}
{timestamp:12:05:02, idc:sz, value1:9,value2:9}
{timestamp:12:05:02, idc:sz, value1:18,value:17}
可以打包成：
{
max_timestamp:12:05:02, min_timestamp: 1205:01, idc:sz,
records: [
{timestamp:12:05:01, value1:10,value2:11}
{timestamp:12:05:02, value1:9,value2:9}
{timestamp:12:05:02, value1:18,value:17}
]
}
這樣可以把數(shù)據(jù)點公共的維度字段上移到父文檔里筐带，而不用在每個子文檔里重復(fù)存儲今穿，從而減少索引的尺寸。
（圖片來源： https://www.youtube.com/watch?v=Su5SHc_uJw8 伦籍，F(xiàn)aceting with Lucene Block Join Query）
在存儲的時候蓝晒，無論父文檔還是子文檔，對于 Lucene 來說都是文檔帖鸦，都會有文檔 Id芝薇。但是對于嵌套文檔來說，可以保存起子文檔和父文檔的文檔 id 是連續(xù)的作儿，而且父文檔總是最后一個洛二。有這樣一個排序性作為保障，那么有一個所有父文檔的 posting list 就可以跟蹤所有的父子關(guān)系。也可以很容易地在父子文檔 id 之間做轉(zhuǎn)換晾嘶。把父子關(guān)系也理解為一個 filter妓雾，那么查詢時檢索的時候不過是又 AND 了另外一個 filter 而已。前面我們已經(jīng)看到了 Elasticsearch 可以非常高效地處理多 filter 的情況垒迂，充分利用底層的索引械姻。
使用了嵌套文檔之后，對于 term 的 posting list 只需要保存父文檔的 doc id 就可以了机断，可以比保存所有的數(shù)據(jù)點的 doc id 要少很多楷拳。如果我們可以在一個父文檔里塞入 50 個嵌套文檔，那么 posting list 可以變成之前的 1/50
