答: 因?yàn)镋S的倒排索引還做了 Term Index屠缭。
什么是Term Index颓遏?
答: 將分詞后的term進(jìn)行排序索引溉潭,類似的mysql對(duì)于"term"(即主鍵悄窃,或者索引鍵)只是做了排序, 并且是大部分是放在磁盤上的梧兼,只有B+樹(shù)的上層才是放在內(nèi)存中的萝挤,查詢?nèi)匀恍枰猯ogN的訪問(wèn)磁盤御毅,而ES將term分詞排序后還做了一次索引,term index怜珍,即將term的通用前綴取出端蛆,構(gòu)建成Trie樹(shù)
trie樹(shù) :https://zh.wikipedia.org/wiki/Trie
這個(gè)樹(shù)的缺點(diǎn):存在大量字符串且這些字符串基本沒(méi)有公共前綴,則相應(yīng)的trie樹(shù)將非常消耗內(nèi)存
通過(guò)這個(gè)樹(shù)可以快速的定位到Term dictionary的本term的offset酥泛,再經(jīng)過(guò)順序查找今豆,便可以很快找到本term的posting list。
什么是FST柔袁?
答: Finite State Transducer
FST有兩個(gè)優(yōu)點(diǎn):1)空間占用小呆躲。通過(guò)對(duì)詞典中單詞前綴和后綴的重復(fù)利用,壓縮了存儲(chǔ)空間捶索;2)查詢速度快歼秽。O(len(str))的查詢時(shí)間復(fù)雜度。
Term Dictionary為什么節(jié)約空間?
Term dictionary 在磁盤上是以分 block 的方式保存的情组,一個(gè) block 內(nèi)部利用公共前綴壓縮燥筷,比如都是 Ab 開(kāi)頭的單詞就可以把 Ab 省去箩祥。這樣 term dictionary 可以比 b-tree 更節(jié)約磁盤空間。
上個(gè)問(wèn)題中的block和ES集成測(cè)試類ESIntegTestCase中的disableIndexBlock(String index, String block) 有關(guān)嗎?
/** Disables an index block for the specified index */
public static void disableIndexBlock(String index, String block) {
Settings settings = Settings.builder().put(block, false).build();
client().admin().indices().prepareUpdateSettings(index).setSettings(settings).get();
}
答 : 不知道
skip list 的原理是什么?
答 : 跳躍表