什么是LSM樹？
三種基本的存儲引擎——LSM樹的由來
- 哈希存儲引擎 是哈希表的持久化實現(xiàn)，支持增铺敌、刪、改以及隨機讀取操作屁擅，但不支持順序掃描偿凭，對應的存儲系統(tǒng)為key-value存儲系統(tǒng)。對于key-value的插入以及查詢派歌，哈希表的復雜度都是O(1)弯囊，明顯比樹的操作O(n)快，如果不需要有序的遍歷數(shù)據(jù)胶果，哈希表就是最佳選擇匾嘱。
- B樹存儲引擎 是B樹（關(guān)于B樹的由來）的持久化實現(xiàn)，不僅支持單條記錄的增早抠、刪霎烙、讀、改操作蕊连，還支持順序掃描（B+樹的葉子節(jié)點之間的指針）悬垃，對應的存儲系統(tǒng)就是關(guān)系數(shù)據(jù)庫（Mysql等）。
- LSM樹（Log-Structured Merge Tree）存儲引擎 和B樹存儲引擎一樣甘苍，同樣支持增尝蠕、刪、讀载庭、改看彼、順序掃描操作廊佩。而且通過批量存儲技術(shù)規(guī)避磁盤隨機寫入問題。當然凡事有利有弊靖榕，LSM樹和B+樹相比标锄，LSM樹犧牲了部分讀性能，用來大幅提高寫性能序矩。
LSM樹設(shè)計思想
將對數(shù)據(jù)的修改增量保持在內(nèi)存中鸯绿，達到指定的大小限制后將這些修改操作批量寫入磁盤，不過讀取的時候稍微麻煩簸淀，需要合并磁盤中歷史數(shù)據(jù)和內(nèi)存中最近修改操作瓶蝴，所以寫入性能大大提升，讀取時可能需要先看是否命中內(nèi)存租幕，否則需要訪問較多的磁盤文件舷手。極端的說，基于LSM樹實現(xiàn)的HBase的寫性能比Mysql高了一個數(shù)量級劲绪，讀性能低了一個數(shù)量級男窟。
image.png
LSM樹原理把一棵大樹拆分成N棵小樹，它首先寫入內(nèi)存中贾富，隨著小樹越來越大歉眷，內(nèi)存中的小樹會flush到磁盤中，磁盤中的樹定期可以做merge操作颤枪，合并成一棵大樹汗捡，以優(yōu)化讀性能。
HBase的LSM樹的簡易模型描述
image.png
HBase中的LSM存儲實現(xiàn)
image.png
