倒排索引是搜索引擎的核心鲜屏，本篇文章介紹了ES中倒排索引是如何實(shí)現(xiàn)的。
ES默認(rèn)為字符串會(huì)創(chuàng)建倒排索引守呜，具體的實(shí)現(xiàn)功能在lucene相關(guān)代碼中粱玲。
倒排索引主要分成兩個(gè)部分:
- term->posting(倒排鏈，docId list)的映射
- posting昧旨。
term->posting的映射
lucene使用FST tree實(shí)現(xiàn)term的查找拾给。
term查找分成2個(gè)文件（8.7的lucene把metadata分開祥得，多了一個(gè)文件）。
term存儲(chǔ)時(shí)會(huì)將一批term存儲(chǔ)在一個(gè)block中蒋得，最少25個(gè)级及，最多48個(gè)，這批term的共同前綴作為FST Tree的一個(gè)item额衙。
term的索引文件后綴是tip饮焦，用來保存FST Tree。
term的數(shù)據(jù)文件后綴是tim窍侧，用來保存term block县踢。
tip文件和tim文件內(nèi)容見：
https://www.amazingkoala.com.cn/Lucene/suoyinwenjian/2019/0401/43.html
term查找流程如下：
1、根據(jù)FST Tree找到termPrefix對應(yīng)在tim文件中position伟件。FST之前是全內(nèi)存的硼啤，現(xiàn)在是off-heap存儲(chǔ)，使用MMap映射斧账。
FST原理介紹：https://www.amazingkoala.com.cn/Lucene/yasuocunchu/2019/0220/35.html
FST tree構(gòu)建出上面的樹形結(jié)構(gòu)谴返，記錄在一個(gè)bytes array中，以前l(fā)ucene是全內(nèi)存的存儲(chǔ)這個(gè)bytes array咧织，現(xiàn)在是off-heap存儲(chǔ)嗓袱，使用MMap映射。
2习绢、根據(jù)termPrefix位置加載term block索抓，然后遍歷每個(gè)termSuffix，檢查term是否存在毯炮。存在的話就能獲取到term對應(yīng)的posting信息逼肯。
posting結(jié)構(gòu)
Lucene使用skipList實(shí)現(xiàn)posting的快速查找。
posting包括了doc桃煎、pos篮幢、pay后綴的三個(gè)文件，docId list主要是實(shí)現(xiàn)在doc文件中为迈，pos存儲(chǔ)了一些全文檢索的position信息三椿，pay存儲(chǔ)了一些附加信息。
doc葫辐、pos搜锰、pay文件內(nèi)容見：
https://www.amazingkoala.com.cn/Lucene/suoyinwenjian/2019/0324/42.html
https://www.amazingkoala.com.cn/Lucene/suoyinwenjian/2019/0324/41.html
docId list在doc文件存儲(chǔ)兩部分內(nèi)容：
- docId鏈表結(jié)構(gòu)，可用來順序遍歷整個(gè)docId list耿战。
- skipList信息蛋叼。
docId鏈表結(jié)構(gòu)存儲(chǔ)方式：每BLOCK_SIZE（默認(rèn)為128）個(gè)doc壓縮存儲(chǔ)為一個(gè)block，最后一個(gè)小于128個(gè)doc的block使用vint方式。
skipList最多存儲(chǔ)MAX_SKIP_LEVELS層(默認(rèn)為10)狈涮，每一層記錄若干個(gè)docId的postion狐胎。第0層記錄的是每個(gè)docId block的postion。每一層創(chuàng)建了skipMultiplier（默認(rèn)為8）個(gè)doc pos歌馍，就在下一層創(chuàng)建一個(gè)doc pos握巢。
上圖實(shí)例的skipList中，一個(gè)block存儲(chǔ)3條記錄松却，skipList每3個(gè)doc創(chuàng)建下一層的item暴浦。
posting查找docId主要有兩個(gè)方法：
nextDoc：查找下一個(gè)docId，這個(gè)只要往下遍歷docId list即可晓锻。
advance：查找某個(gè)docId指定的位置肉渴。在取交、取差時(shí)带射，需要跳著查docId同规，這時(shí)候要用到skipList，加快docId的查找窟社。
倒排索引查詢產(chǎn)生IO的地方：
- FST tree現(xiàn)在是offHeap存儲(chǔ)券勺，如果查到了不在內(nèi)存的塊，則會(huì)產(chǎn)生IO灿里。
- 一個(gè)term查詢关炼，如果前綴沒命中，則不產(chǎn)生IO匣吊，前綴命中則只會(huì)產(chǎn)生一次IO儒拂，加載term block，在term block中查找term是否匹配色鸳。
- 找到的term接下來會(huì)去獲取posting社痛，如果是一個(gè)term，則直接在doc文件中獲取docId列表命雀，此時(shí)是順序IO獲取數(shù)據(jù)蒜哀。如果有多個(gè)term要做and、not query吏砂，則會(huì)有skipList的IO撵儿。
