HBase的列族本質(zhì)上就是一棵LSM樹（Log-Structured Merge-Tree）。
LSM樹分為內(nèi)存部分和磁盤部分。內(nèi)存部分是一個維護有序數(shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)（跳躍表）；磁盤部分由一個個獨立文件組成（每個文件又是由一個個數(shù)據(jù)塊組成）。
內(nèi)存數(shù)據(jù)結(jié)構(gòu)可以選擇：平衡二叉樹、紅黑樹、跳躍表等維護有序集的數(shù)據(jù)結(jié)構(gòu)，由于考慮并發(fā)性能，HBase選擇了表現(xiàn)更優(yōu)秀的跳躍表。
數(shù)據(jù)存儲在磁盤上的數(shù)據(jù)庫系統(tǒng)，磁盤尋道和數(shù)據(jù)讀取都很耗IO，為了避免不必要的IO耗時，可以在磁盤中存儲一些額外的二進制數(shù)據(jù)，這些數(shù)據(jù)用來判斷對于給定的key是否又可能存儲在這個數(shù)據(jù)塊中，這個數(shù)據(jù)結(jié)構(gòu)稱為布隆過濾器（BloomFilter）
一、跳躍表（SkipList）
跳躍表是一種能高效實現(xiàn)插入、刪除、查找的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，這些操作的期望復雜度都是O(logN)（N是元素的個數(shù)）。與紅黑樹、二叉樹相比的優(yōu)勢在于：實現(xiàn)簡單、并發(fā)場景下加鎖粒度更小，從而可以實現(xiàn)更高的并發(fā)性。
跳躍表廣泛使用于KV數(shù)據(jù)庫中，例如Redis、HBase等都把跳躍表作為一種維護有序數(shù)據(jù)集合的基礎數(shù)據(jù)結(jié)構(gòu)。
1、跳躍表的定義
- 跳躍表由多條分層的鏈表組成（設為S0，S1，...），例如圖中有4條鏈表。
- 每條鏈表都有兩個元素：（正無窮大）和（負無窮大），分表表示鏈表的頭部和尾部。
- 從上到小，上層鏈表元素集合是下層鏈表元素集合的子集，即S1是S0的子集，S2是S1的子集。
- 跳躍表的高度定義為水平鏈表的層數(shù)。
2、跳躍表的查找
如上圖，以左上角元素（設為currentNode）作為起點：
- 如果currentNode后繼節(jié)點的值 <= 待查詢值，則沿著這條鏈表向后查詢，否則切換到currentNode的下一層鏈表；
- 繼續(xù)查詢，直到找到待查詢值為止，或者currentNode為空節(jié)點為止。
3、跳躍表的插入
- 先按上述流程找到待插入元素的前驅(qū)和后繼，然后按隨機算法生成一個高度值；
// p是一個(0,1)之間的常數(shù)，一般取p=1/4或1/2
public void randomHeight(double p){
int height = 0;
while(random.nexDouble() < p) height ++;
return height +1
}
- 將帶插入節(jié)點按照高度值生成一個垂直節(jié)點（該節(jié)點的層數(shù)正好等于高度值）。
- 插入到跳躍表的多條鏈表中去。假設height=randomHeight(p)，這里需要分情況討論：
（1）若height大于跳躍表的高度，則跳躍表的高度被提升為height，同時需要更新頭部節(jié)點和尾部節(jié)點的指針指向。
（2）若height小于等于跳躍表的高度，則需要更新待插入元素前驅(qū)和后繼的指針指向。
4、跳躍表的刪除
暫略
關(guān)于跳躍表的理解，可以參考：https://www.sohu.com/a/293236470_298038，這里不做筆記整理了
二、LSM樹（Log-Structured Merge-Tree）
LSM樹（日志結(jié)構(gòu)合并樹），本質(zhì)上和B+樹一樣，是一種磁盤數(shù)據(jù)的索引結(jié)構(gòu)，但是，LSM樹的索引對寫入請求更友好，因為無論是何種寫入請求，LSM樹都會將寫入操作處理為一次順序?qū)?，而HDFS擅長順序?qū)懬也恢С蛛S機寫。因為基于HDFS實現(xiàn)的HBase采用LSM樹作為索引是一種很合適的選擇。
LSM樹的索引一般由兩部分組成：
- 內(nèi)存部分：采用跳躍表（ConcurrentSkipListMap）來維護一個有序的KV（KeyValue）集合；
- 磁盤部分：由多個內(nèi)部KV（KeyValue）有序的文件組成；
1、KV存儲格式
LSM中存儲的是多個KV組成的集合，每一個KV一般都會用一個字節(jié)數(shù)組來表示。
理解字節(jié)數(shù)組的設計：
- keyLen：占4字節(jié)，存儲KV結(jié)構(gòu)中key所占用的字節(jié)長度；
- valueLen：占4字節(jié)，存儲KV結(jié)構(gòu)中value所占用的字節(jié)長度；
- rowkeyLen：占2字節(jié)，存儲rowkey占用的字節(jié)長度；
- rowkeyBytes：占用rowkeyLen個字節(jié)，用來存儲rowkey的二進制內(nèi)容；
- familyLen：占1字節(jié)，用來存儲family占用的字節(jié)長度；
- familyBytes：占familyLen字節(jié)，用來存儲family的二進制內(nèi)容；
- qualifierBytes：占qualifierLen個字節(jié)，用來存儲qualifier的二進制內(nèi)容。
并沒有單點分配字節(jié)來存儲qualifierLen，是因為可以通過keyLen和其他字段的長度，計算出qualifierLen：
qualifierLen = keyLen - 2B - rowkeyLen - 1B - familyLen - 8B - 1B
- timestamp：占8字節(jié)，表示timestamp對應的long值；
- type：占1字節(jié)，表示這個KV 操作的類型，比如：Put、Delete、DeleteColumn、DeleteFamily等;
type字段是一個關(guān)鍵字段，表明LSM樹內(nèi)存儲的不只是數(shù)據(jù)，而是每次操作記錄，這對應來LSM樹（Log-Structured Merge-Tree）中Log的含義，即操作日志。
value部分直接存儲這個KV中value的二進制內(nèi)容，所以字節(jié)數(shù)組串主要是key部分的設計。
2、多路歸并
多路歸并算法：
（1）假設有K路數(shù)據(jù)流，流內(nèi)部是有序的，且流間同為升序或降序；
（2）首先讀取每個流的第一個數(shù)，如果已經(jīng)EOF，pass；
（3）將有效的k(k可能小于K)個數(shù)比較，選出最小的那路mink，輸出，讀取mink的下一個；
（4）直到所有K路都EOF。
其他的，參考網(wǎng)絡資料：http://blog.itpub.net/31561269/viewspace-2564096/
3、LSM樹的索引結(jié)構(gòu)
一個LSM樹的索引主要由兩部分構(gòu)成：
- 內(nèi)存部分：采用跳躍表（ConcurrentSkipListMap）來維護一個有序的KV（KeyValue）集合，KV結(jié)構(gòu)就是前面所說的字節(jié)數(shù)組；
- 磁盤部分：由多個內(nèi)部KV（KeyValue）有序的文件組成；
數(shù)據(jù)寫入時直接寫入MemStore中，隨著不斷寫入，一旦內(nèi)存占用超過一定閥值，就把內(nèi)存部分的數(shù)據(jù)導出，形成一個有序的數(shù)據(jù)文件，存儲在磁盤上。
內(nèi)部導出形成一個有序數(shù)據(jù)文件的過程稱為flush。為避免flush影響寫入性能，會把當前寫入的MemStore設為Snapshot，不允許新的寫入操作寫入這個Snapshot的MemStore，另開一個內(nèi)存空間作為MemStore，讓后面的數(shù)據(jù)寫入。一旦Snapshot的MemStore寫入完畢，對應內(nèi)存空間就可以釋放，這樣就可以通過兩個MemStore來實現(xiàn)穩(wěn)定的寫入性能。
在整個數(shù)據(jù)寫入過程中，LSM樹全部使用append操作（即，磁盤順序?qū)懀瑳]有任何隨機寫操作。
因此LSM樹是一種寫入友好的索引結(jié)構(gòu)，將磁盤的寫入帶寬利用到極致。
隨著寫入增加，內(nèi)存數(shù)據(jù)會不斷刷新到磁盤上，最終磁盤上的數(shù)據(jù)文件越來越多。如果數(shù)據(jù)沒有任何讀取操作，磁盤上產(chǎn)生很多的數(shù)據(jù)文件對寫入并無影響，而且這時寫入速度是最快的，因為所有IO都是順序IO。但是一旦有用戶讀請求，則需要將大量的磁盤文件進行多路歸并，之后才能讀取到所需的數(shù)據(jù)。因為需要將那些key相同的數(shù)據(jù)全局綜合起來，最終選擇出合適的版本返回給用戶。
所以，磁盤文件數(shù)量越多，在讀取時隨機讀取的次數(shù)也會越多，從而影響讀取操作的性能。
為了優(yōu)化讀操作性能，設置了一定策略將選中的多個hfile進行多路歸并，合并成一個文件（即，compact操作），文件的個數(shù)越少，則讀取數(shù)據(jù)時需要隨機操作的次數(shù)越少，讀操作性能則越好。
按選中的文件個數(shù)，將compact操作分為兩種類型：
- minor compact：選中少數(shù)幾個hfile多路歸并成一個文件。
好處：可以進行局部compact，適合較高頻率的跑；
壞處：只合并局部數(shù)據(jù)，對于全局刪除操作無法在合并過程中完全刪除。
- major compact：將所有的hfile一次性多路歸并成一個文件。
好處：合并后只有一個文件，這樣讀取的性能肯定最高；
壞處：合并所有文件需要很長時間且消耗大量IO帶寬。因此major compact不宜太頻繁，適合周期性跑。
總結(jié)：minor compact雖然能減少文件，但是無法徹底清除那些delete操作；而major compact能完全清理那些delete操作，保證數(shù)據(jù)的最小化。
LSM樹的索引結(jié)構(gòu)本質(zhì)上是將寫入操作全部轉(zhuǎn)化為磁盤的順序?qū)懭?，極大提高寫入操作的性能，但是這種設計對讀操作非常不利，因為需要在讀取過程中，通過歸并所有文件來讀取所對應的KV，非常消耗IO資源。
因此HBase中設計來異步的compaction來降低文件個數(shù)，達到提高讀取性能的目的。
由于HDFS只支持文件的順序?qū)?，不支持文件的隨機寫，而且HDFS擅長的場景是大文件存儲而非小文件，所以上層HBase選擇LSM樹這種索引結(jié)構(gòu)是最合適的。
三、布隆過濾器（BloomFilter）
布隆過濾器的理解，網(wǎng)絡資源參考：http://www.itdecent.cn/p/2104d11ee0a2
布隆過濾器只需占用極小的空間，便可給出“可能存在”和“肯定不存在”的存在下判斷，因此可以提前過濾掉很多不必要的數(shù)據(jù)塊，從而節(jié)省了大量的磁盤IO。
HBase的Get操作就是通過運用低成本高效率的布隆過濾器來過濾大量無效的數(shù)據(jù)塊的，從而節(jié)省大量磁盤IO。
在HBase 1.x版本中，用戶可以對某些列設置不同類型的布隆過濾器，共有3種類型：
- NONE：關(guān)閉布隆過濾器功能；
- ROW：按照rowkey來設計布隆過濾器的二進制串并存儲。
Get查詢的時候，必須帶rowkey，所以用戶可以建表時默認把布隆過濾器設置為ROW類型。
- ROWCOL：按照rowkey+family+qualifier這3個字段頻出byte[]來計算布隆過濾器并存儲。
Get查詢的時候，若能指出rowkey、family、qualifier這3個字段，則肯定可以通過布隆過濾器提升性能；若缺少3個字段中任何一個，則無法通過布隆過濾器提升性能（因為計算布隆過濾器的key不確定）。
需要注意！一般意義上的Scan操作，HBase都無法使用布隆過濾器來提升掃描數(shù)據(jù)性能，因為布隆過濾器的key值不確定，所以無法計算出哈希值對比。但是在某些特定場景下，Scan操作可以借助布隆過濾器提升性能。
