Lucene作為一個索引和存儲引擎，其實現(xiàn)中包含了很多數(shù)據(jù)存儲和檢索方面的算法。這里對其中一部分算法做些簡單的分析，希望能夠?qū)ξ覀冊谄渌I(lǐng)域處理類似問題時提供參考芍锦。
批量順序?qū)懭胨饕龜?shù)據(jù)
和傳統(tǒng)的數(shù)據(jù)庫比較，Lucene由于對檢索的要求更高：全文檢索飞盆、高亮娄琉、相似度等次乓，其索引處理和存儲發(fā)的負擔要遠多于一般的數(shù)據(jù)庫。再加上孽水，Lcuene追求更大的文檔處理吞吐量票腰，所以Lcuene沒有使用大多數(shù)傳統(tǒng)的關(guān)系數(shù)據(jù)庫的索引結(jié)構(gòu)：B+樹，而是使用map這種更利于I/O的結(jié)果存儲索引女气。
map的新增操作只需要在map文件的末尾添加記錄即可杏慰，而在普通的B+樹增加記錄卻可能需要執(zhí)行seek+update操作。對磁盤來說炼鞠，由于需要移動磁頭/尋道的概率較低缘滥，順序?qū)懙男室哂陔S機寫，所以map的寫效率是優(yōu)于B+樹的谒主。
為了保持磁盤的IO效率朝扼，lucene避免對索引文件的直接修改，所有的索引文件一旦生成霎肯，就是只讀擎颖，不能被改變的。其操作過程如下：
- 在內(nèi)存中保存新增的索引;
- 內(nèi)存中的索引數(shù)量達到一定閾值時姿现，觸發(fā)寫操作肠仪，將這部分數(shù)據(jù)批量寫入新文件，我們稱為segment备典；
- 新增的segment生成后，不能被修改意述；
- update操作和delete操作不會立即導(dǎo)致原有的數(shù)據(jù)被修改或者刪除提佣。
上面的過程執(zhí)行一段時間后，最終我們會得到大量的segment荤崇。為了減少資源占用拌屏，也為了提高檢索效率，lcuene會自動定期將這些小的segment合并成大的segment术荤，合并過程中倚喂，由于map中的數(shù)據(jù)都是排好序的，所以也不會有隨機寫操作瓣戚。通過merge端圈，我們還可以把update和delete操作真正生效，刪除多余的數(shù)據(jù)子库，節(jié)省空間舱权。
Lucene使用的索引結(jié)構(gòu)和管理辦法，其出發(fā)點是為了保證寫入性能仑嗅，同時又能支持較高效率的檢索宴倍，這種方法在很多NoSQL數(shù)據(jù)庫中被使用张症，和B+樹對應(yīng)，這類索引方法我們稱為LSM樹（log structured merge tree)鸵贬。LSM在不同的數(shù)據(jù)中有多種具體實現(xiàn)俗他，差異主要表現(xiàn)在segment的內(nèi)容組織，segment的合并時機和算法等方面阔逼。詳細的資料可以參考：log-structured-merge-trees
聯(lián)合檢索
在很多數(shù)據(jù)庫中兆衅，如果檢索涉及到多個字段，通常檢索過程中只會利用其中一個字段的索引颜价。但Lucene能夠保證使用所用相關(guān)字段的索引涯保，其檢索過程如下：
通過各個字段的索引檢索出多組文檔；
這些文檔使用排好序的跳表(skip list)保存周伦；
遍歷這些跳表夕春，找出它們之間的交集。
這里舉個具體的例子(來自：algorithms-and-data-structures-power-lucene-and-elasticsearch)
假定我們根據(jù)三個不同字段檢索得到三組文檔专挪，表示成下面三個列表：
A：[2, 13, 17]
B：[1, 13, 22]
C: [1, 3, 13]
每個列表提供兩個操作：next和advance:
next表示得到將列表指針指向一個位置及志；
advance(m)表示將指針指向下一個值不小于m的位置；
開始遍歷時寨腔，每個列表的指針指向第一個元素速侈，
A.next -> 2
B.next -> 1
由于B的當前值1小于A的當前值2，所以執(zhí)行：B.advance(2),將B的指針跳向第一個不小于2的位置迫卢，這個值就是13倚搬。
而A的當前值為2，小于13乾蛤，所以這次輪到A需要執(zhí)行跳躍：A.advance(13),結(jié)果指針也來到13每界。
A和B的指針都指向13，我們可以對A和C也執(zhí)行上述操作家卖，導(dǎo)致C的指針也指向13眨层，所以13就是符合條件的文檔。
這個過程中上荡，我們利用到了跳表的快速遍歷特性趴樱，提供了檢索效率。
行存儲和列存儲
Lucene在存儲文檔原始數(shù)據(jù)時酪捡，使用行存儲格式叁征，每行大小固定(16k), 在行內(nèi)可存儲多個文檔。這么設(shè)計的用意在于考慮到Lucene面向的文檔大部分較小沛善，可以多個文檔共存于一行航揉，這樣便于減少行數(shù)，相應(yīng)的行索引數(shù)量也減少金刁，提高讀寫效率帅涂。
Lucene為了支持數(shù)據(jù)的排序和聚合需求议薪，還另外提供了列存儲(DocValue)，它用于存儲所有文檔的特定字段媳友，當需要按照該字段進行排序斯议、聚合時，和行存儲比較醇锚，列式的存儲更利于批量獲取多個文檔的字段值哼御。
關(guān)于Lucene的文件存儲格式，請參考lucene的相關(guān)文檔
壓縮
為了節(jié)省空間焊唬，lucene在行存儲和列存儲中存放的都是壓縮數(shù)據(jù)恋昼。對于行存儲，lucene提供了兩種壓縮選項：BEST_SPEED和BEST_COMPRESSION赶促，對應(yīng)速度優(yōu)先和空間優(yōu)先的不同策略液肌。
而在列存儲中，lucene主要通過對數(shù)據(jù)的編解碼實現(xiàn)壓縮鸥滨，這里有些例子：
- Delta Encoding
- 取出字段的最小值嗦哆；
- 其他字段的值表示成和最小值的差異；
- Table Encoding
- 如果字段的取值不超過256個婿滓；將所有的值保存在一個獨立的table中老速；
- 各個字段表示成table的索引
- 在字段值的cardinality不多的情況下適用
Cardinality
Cardinality是指集合中不同值的個數(shù)。按照一般的做法凸主，我們需要遍歷集合橘券，將不同的值保存到一個Map中，完成遍歷后卿吐，map的size就是cardinality约郁。可是這種處理方法不適合大集合但两，會消耗太多內(nèi)存。
Lucene采用了另外的方法來統(tǒng)計cardinality供置，該方法不能夠得到精確計算結(jié)果谨湘，但是能夠得到一個近似值。方法的名稱為:HyperLogLog++芥丧，計算過程如下：
- 計算字段的hash值紧阔；
- 統(tǒng)計hash值末尾開始的連續(xù)0的個數(shù)，記為m续担；
- 記錄m的最大值擅耽；
-
Cardinality = 2m
| 原始值 | hash值 | 末尾連續(xù)0的個數(shù) |
|---|---|---|
| 12345 | 11001011111101011010 | 1 |
| 3456 | 10001101001100111000 | 3 |
| 948 | 01000111110100110100 | 2 |
我們來看個例子：
| 原始值 | hash值 | 末尾連續(xù)0的個數(shù) |
|---|---|---|
| 12345 | 11001011111101011010 | 1 |
| 3456 | 10001101001100111000 | 3 |
| 948 | 01000111110100110100 | 2 |
在上面的3個值中，我們觀察到末尾連續(xù)0的個數(shù)最大為3物遇，根據(jù)公式乖仇，cadinality等于23=8
這個計算過程不需要我們?nèi)ケ闅v和記住所有的不同值憾儒，只需要一個變量(末尾連續(xù)0的個數(shù))就可以了，所以對內(nèi)存資源占用很少乃沙。當然起趾，我們上面的描述是對HyperLogLog的簡化，為了減少結(jié)果偏差警儒，HyperLogLog的實現(xiàn)要比上面的過程稍微復(fù)雜一些训裆，但是其本質(zhì)不變，都是對結(jié)果的近似估算蜀铲。
其實有很多類似的的近似估算方法边琉，它們一般被歸類到data sketch算法，適用于大數(shù)據(jù)環(huán)境中對數(shù)據(jù)的近似統(tǒng)計记劝。更詳細的記錄可以參考：skectching-sclaing
