就是：
數(shù)值Trie樹，下面詳細(xì)介紹
上面說了怎么索引，那么Query呢？比如我給你一個Range Query從423-642，怎么找到那6個term呢？
我們首先可以用shift==0找到范圍的起點后終點（有可能沒有相等的，比如搜索422，也會找到423） 。然后一直往上找，直到找到一個共同的祖先（肯定能找到，因為樹根是所有葉子節(jié)點的祖先），對應(yīng)起點，每次往上走的時候, 左邊范圍節(jié)點都要把它右邊的兄弟節(jié)點都加進(jìn)去, 右邊范圍節(jié)點都要把它左邊的兄弟節(jié)點加進(jìn)去, 若已經(jīng)到達(dá)頂點, 則是將左邊范圍節(jié)點和右邊范圍節(jié)點之間的節(jié)點加進(jìn)行去
查找423到642之間的具體的區(qū)間：
- 423-429,640-642
- 43-49,60-63
- 5-5
所以intToPrefixCoded方法會額外用一個char來保存shift：buffer[0] = (char)(SHIFT_START_INT + shift);
比如423分詞的4的shift是2（這里是10進(jìn)制的例子，二進(jìn)制也是同樣的），423分成423的shift是0，4的shift是0，因此前綴肯定比后綴大 。
最后，由于索引在判斷時無需感知是否是數(shù)字，可以把所有的數(shù)字當(dāng)成二進(jìn)制處理，這樣在存儲和效率上更高 。
三、搜索引擎的極致優(yōu)化LSM思想
LSM (Log Structured Merge Tree)，最早是谷歌的 “BigTable” 提出來的，目標(biāo)是保證寫入性能，同時又能支持較高效率的檢索，在很多 NoSQL 中都有使用，Lucene 也是使用 LSM 思想來寫入 。
普通的B+樹增加記錄可能需要執(zhí)行 seek+update 操作，這需要大量磁盤尋道移動磁頭 。而 LSM 采用記錄在文件末尾，順序?qū)懭霚p少移動磁頭/尋道，執(zhí)行效率高于 B+樹 。具體 LSM 的原理是什么呢？
為了保持磁盤的IO效率，lucene避免對索引文件的直接修改，所有的索引文件一旦生成，就是只讀，不能被改變的 。其操作過程如下：
- 在內(nèi)存中保存新增的索引, 內(nèi)存緩存（也就是memtable）;
- 內(nèi)存中的索引數(shù)量達(dá)到一定閾值時，觸發(fā)寫操作，將這部分?jǐn)?shù)據(jù)批量寫入新文件，我們稱為segment；也就是 sstable文件
- 新增的segment生成后，不能被修改；
- update操作和delete操作不會立即導(dǎo)致原有的數(shù)據(jù)被修改或者刪除，會以append的方式存儲update和delete標(biāo)記;
- 最終得到大量的 segment，為了減少資源占用，也提高檢索效率，會定期的將這些小的 segment 合并成大的 segment，由于map中的數(shù)據(jù)都是排好序的，所以合并也不會有隨機(jī)寫操作；
- 通過merge，還可以把update和delete操作真正生效，刪除多余的數(shù)據(jù)，節(jié)省空間 。
Basic Compaction
每個文件固定N個數(shù)量，超過N，則新建一個sstable；當(dāng)sstable數(shù)大于M，則合并一個大sstable；當(dāng)大sstable的數(shù)量大于M，則合并一個更大的sstable文件，依次類推 。
但是，這會出現(xiàn)一個問題，就是大量的文件被創(chuàng)建，在最壞的情況下，所有的文件都要搜索 。
Levelled Compaction
像 LevelDB 和 Cassandra解決這個問題的方法是：實現(xiàn)了一個分層的，而不是根據(jù)文件大小來執(zhí)行合并操作 。
- 每層維護(hù)指定數(shù)量的文件，保證不讓 key 重疊，查找一個 key 只會查找一個 key；
推薦閱讀
- 網(wǎng)絡(luò)電話的原理是什么
- 網(wǎng)絡(luò)爬蟲的原理
- 網(wǎng)橋的工作原理
- 網(wǎng)絡(luò)傳輸?shù)脑?
- 太陽能熱水器工作原理 太陽能熱水器的基本參數(shù)
- 軟件無線電原理與應(yīng)用 5g網(wǎng)絡(luò)架構(gòu)及關(guān)鍵技術(shù)分析
- 入射面和折射面的定義及其物理原理 入射面和折射面的定義是什么
- 機(jī)械原理關(guān)于斜齒輪重合度的問題
- 機(jī)械千斤頂?shù)脑砑?
- 機(jī)械制冷的原理
-
