1.elasticsearch是什么
ElasticSearch是一個(gè)基于Lucene的搜索服務(wù)器旺聚。它提供了一個(gè)分布式多用戶能力的全文搜索引擎轴或，基于RESTful web接口。Elasticsearch是用Java開(kāi)發(fā)的库继，并作為Apache許可條款下的開(kāi)放源碼發(fā)布，是當(dāng)前流行的企業(yè)級(jí)搜索引擎。能夠達(dá)到實(shí)時(shí)搜索辫呻，穩(wěn)定，可靠琼锋，快速放闺，安裝使用方便
應(yīng)用案例
1.Github：GitHub使用ElasticSearch搜索20TB的數(shù)據(jù)，包括13億文件和1300億行代碼缕坎。
2.elasticsearch能做什么
? ??1怖侦、全文搜索（搜索引擎）
? ??????在一組文檔中查找某一單詞所在文檔及位置
? ??2、模糊匹配
? ??????通過(guò)用戶的輸入去匹配詞庫(kù)中符合條件的詞條
? ??3谜叹、商品搜索
? ??????通過(guò)商品的關(guān)鍵字去數(shù)據(jù)源中查找符合條件的商品
3.elasticsearch的優(yōu)勢(shì)
? ??名詞概念
1.天生支持分布式
Elasticsearch天生就是分布式的础钠，它知道如何管理節(jié)點(diǎn)來(lái)提供高擴(kuò)展和高可用。
1.添加索引
2.增加故障轉(zhuǎn)移
3.橫向擴(kuò)展
4.繼續(xù)擴(kuò)展
5.應(yīng)對(duì)故障
2.倒排索引
?可以看到叉谜，倒排索引是per field的旗吁，一個(gè)字段由一個(gè)自己的倒排索引。18,20這些叫做 term停局，而[1,3]就是posting list很钓。Posting list就是一個(gè)int的數(shù)組，存儲(chǔ)了所有符合某個(gè)term的文檔id董栽。
那么什么是term dictionary 和 term index码倦？
? ? ? ? ?假設(shè)我們有很多個(gè)term，找出某個(gè)特定的term一定很慢锭碳，因?yàn)閠erm沒(méi)有排序袁稽，需要全部過(guò)濾一遍才能找出特定的term。排序之后我們可以用二分查找的方式擒抛，比全遍歷更快地找出目標(biāo)的term推汽。這個(gè)就是 term dictionary。有了term dictionary之后歧沪，可以用 logN 次磁盤查找得到目標(biāo)歹撒。
? ? ? ? ? 但是磁盤的隨機(jī)讀操作仍然是非常昂貴的所以盡量少的讀磁盤，有必要把一些數(shù)據(jù)緩存到內(nèi)存里诊胞。但是整個(gè)term dictionary本身又太大了暖夭，無(wú)法完整地放到內(nèi)存里。于是就有了term index。term index有點(diǎn)像一本字典的大的章節(jié)表迈着。比如：A開(kāi)頭的term ……… Xxx頁(yè)竭望；C開(kāi)頭的term ……… Xxx頁(yè)；E開(kāi)頭的term ………Xxx頁(yè)裕菠。
term index壓縮
? ? ? ?例子是一個(gè)包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trem 樹(shù)咬清。這棵樹(shù)不會(huì)包含所有的term，它包含的是term的一些前綴糕韧。通過(guò)term index可以快速地定位到term dictionary的某個(gè)offset枫振，然后從這個(gè)位置再往后順序查找。整體上來(lái)說(shuō)就是這樣的效果萤彩。所以term index不需要存下所有的term粪滤，而僅僅是他們的一些前綴與Term Dictionary的block之間的映射關(guān)系，再結(jié)合FST(Finite State Transducers)的壓縮技術(shù)雀扶，可以使term index緩存到內(nèi)存中杖小。從term index查到對(duì)應(yīng)的term dictionary的block位置之后，再去磁盤上找term愚墓，大大減少了磁盤隨機(jī)讀的次數(shù)予权。
FST是啥
????????假設(shè)我們現(xiàn)在要將mop, moth, pop, star, stop and top(term index里的term前綴)映射到序號(hào)：0，1浪册，2扫腺，3，4村象，5(term dictionary的block位置)笆环。最簡(jiǎn)單的做法就是定義個(gè)Map，大家找到自己的位置對(duì)應(yīng)入座就好了厚者，但從內(nèi)存占用少的角度想想躁劣，有沒(méi)有更優(yōu)的辦法呢？答案就是：FST
關(guān)于FST的博文：https://www.cnblogs.com/jiu0821/p/7688669.html
term dictionary壓縮
Term dictionary在磁盤上是以分block的方式保存的库菲，一個(gè)block內(nèi)部利用公共前綴壓縮账忘，比如都是Ab開(kāi)頭的單詞就可以把Ab省去。這樣term dictionary可以比b-tree更節(jié)約磁盤空間熙宇。
????????現(xiàn)在我們可以回答“為什么Elasticsearch/Lucene檢索可以比mysql快了鳖擒。Mysql只有term dictionary這一層，是以b-tree排序的方式存儲(chǔ)在磁盤上的奇颠。檢索一個(gè)term需要若干次的random access的磁盤操作败去。
為了提高查詢的效率，減少磁盤尋道次數(shù)烈拒，將多個(gè)值作為一個(gè)數(shù)組通過(guò)連續(xù)區(qū)間存放，一次尋道讀取多個(gè)數(shù)據(jù)
而Lucene在term dictionary的基礎(chǔ)上添加了term index來(lái)加速檢索，term index以樹(shù)的形式緩存在內(nèi)存中荆几。從term index查到對(duì)應(yīng)的term dictionary的block位置之后吓妆，再去磁盤上找term，大大減少了磁盤的random access次數(shù)吨铸。
posting list壓縮技巧
Elasticsearch里除了上面說(shuō)到用FST壓縮term index外行拢，對(duì)posting list也有壓縮技巧〉ǎ”posting list不是已經(jīng)只存儲(chǔ)文檔id了嗎舟奠？還需要壓縮？”
嗯房维，我們?cè)倏椿刈铋_(kāi)始的例子沼瘫，如果Elasticsearch需要對(duì)同學(xué)的性別進(jìn)行索引，會(huì)怎樣咙俩？如果有上千萬(wàn)個(gè)同學(xué)耿戚，而世界上只有男/女這樣兩個(gè)性別，每個(gè)posting list都會(huì)有至少百萬(wàn)個(gè)文檔id阿趁。 Elasticsearch是如何有效的對(duì)這些文檔id壓縮的呢膜蛔？
Frame Of Reference
增量編碼壓縮，將大數(shù)變小數(shù)脖阵，按字節(jié)存儲(chǔ)
首先皂股，Elasticsearch要求posting list是有序的(為了提高搜索的性能，再任性的要求也得滿足)命黔，這樣做的一個(gè)好處是方便壓縮呜呐，看下面這個(gè)圖例：
聯(lián)合索引
上面說(shuō)了半天都是單field索引，如果多個(gè)field索引的聯(lián)合查詢纷铣，倒排索引如何滿足快速查詢的要求呢卵史？
利用跳表(Skip list)的數(shù)據(jù)結(jié)構(gòu)快速做“與”運(yùn)算，或者
利用上面提到的bitset按位“與”
先看看跳表的數(shù)據(jù)結(jié)構(gòu)：
將一個(gè)有序鏈表level0搜立，挑出其中幾個(gè)元素到level1及l(fā)evel2以躯，每個(gè)level越往上，選出來(lái)的指針元素越少啄踊，查找時(shí)依次從高level往低查找忧设，比如55，先找到level2的31颠通，再找到level1的47址晕，最后找到55，一共3次查找顿锰，查找效率和2叉樹(shù)的效率相當(dāng)谨垃，但也是用了一定的空間冗余來(lái)?yè)Q取的启搂。
跳表原理：https://www.cnblogs.com/a8457013/p/8251967.html
假設(shè)有下面三個(gè)posting list需要聯(lián)合索引：
如果使用跳表，對(duì)最短的posting list中的每個(gè)id刘陶，逐個(gè)在另外兩個(gè)posting list中查找看是否存在胳赌，最后得到交集的結(jié)果。
