講LSM樹之前，需要提下三種基本的存儲引擎镣典，這樣才能清楚LSM樹的由來：
哈希存儲引擎 ?是哈希表的持久化實(shí)現(xiàn)兔毙，支持增、刪的猛、改以及隨機(jī)讀取操作艺智，但不支持順序掃描疤苹，對應(yīng)的存儲系統(tǒng)為key-value存儲系統(tǒng)。對于key-value的插入以及查詢哑姚，哈希表的復(fù)雜度都是O(1)，明顯比樹的操作O(n)快,如果不需要有序的遍歷數(shù)據(jù)芜茵，哈希表就是your Mr.Right
B樹存儲引擎是B樹（關(guān)于B樹的由來叙量，數(shù)據(jù)結(jié)構(gòu)以及應(yīng)用場景可以看之前一篇博文）的持久化實(shí)現(xiàn)，不僅支持單條記錄的增夕晓、刪宛乃、讀、改操作蒸辆，還支持順序掃描（B+樹的葉子節(jié)點(diǎn)之間的指針）征炼，對應(yīng)的存儲系統(tǒng)就是關(guān)系數(shù)據(jù)庫（Mysql等）。
LSM樹（Log-Structured Merge Tree）存儲引擎和B樹存儲引擎一樣躬贡，同樣支持增谆奥、刪、讀拂玻、改酸些、順序掃描操作宰译。而且通過批量存儲技術(shù)規(guī)避磁盤隨機(jī)寫入問題。當(dāng)然凡事有利有弊魄懂，LSM樹和B+樹相比沿侈，LSM樹犧牲了部分讀性能，用來大幅提高寫性能市栗。
通過以上的分析缀拭，應(yīng)該知道LSM樹的由來了，LSM樹的設(shè)計(jì)思想非常樸素：將對數(shù)據(jù)的修改增量保持在內(nèi)存中填帽，達(dá)到指定的大小限制后將這些修改操作批量寫入磁盤蛛淋，不過讀取的時(shí)候稍微麻煩，需要合并磁盤中歷史數(shù)據(jù)和內(nèi)存中最近修改操作篡腌，所以寫入性能大大提升褐荷，讀取時(shí)可能需要先看是否命中內(nèi)存，否則需要訪問較多的磁盤文件嘹悼。極端的說叛甫，基于LSM樹實(shí)現(xiàn)的HBase的寫性能比Mysql高了一個(gè)數(shù)量級，讀性能低了一個(gè)數(shù)量級绘迁。
LSM樹原理把一棵大樹拆分成N棵小樹合溺，它首先寫入內(nèi)存中，隨著小樹越來越大缀台，內(nèi)存中的小樹會flush到磁盤中棠赛，磁盤中的樹定期可以做merge操作，合并成一棵大樹膛腐，以優(yōu)化讀性能睛约。
以上這些大概就是HBase存儲的設(shè)計(jì)主要思想，這里分別對應(yīng)說明下：
因?yàn)樾湎葘懙絻?nèi)存中哲身，為了防止內(nèi)存數(shù)據(jù)丟失辩涝，寫內(nèi)存的同時(shí)需要暫時(shí)持久化到磁盤，對應(yīng)了HBase的MemStore和HLog
MemStore上的樹達(dá)到一定大小之后勘天，需要flush到HRegion磁盤中（一般是Hadoop DataNode）怔揩，這樣MemStore就變成了DataNode上的磁盤文件StoreFile，定期HRegionServer對DataNode的數(shù)據(jù)做merge操作脯丝，徹底刪除無效空間商膊，多棵小樹在這個(gè)時(shí)機(jī)合并成大樹，來增強(qiáng)讀性能宠进。
關(guān)于LSM Tree晕拆，對于最簡單的二層LSM Tree而言，內(nèi)存中的數(shù)據(jù)和磁盤你中的數(shù)據(jù)merge操作材蹬，如下圖
圖來自lsm論文
lsm tree实幕，理論上吝镣，可以是內(nèi)存中樹的一部分和磁盤中第一層樹做merge，對于磁盤中的樹直接做update操作有可能會破壞物理block的連續(xù)性昆庇，但是實(shí)際應(yīng)用中末贾，一般lsm有多層，當(dāng)磁盤中的小樹合并成一個(gè)大樹的時(shí)候凰锡，可以重新排好順序未舟，使得block連續(xù)圈暗，優(yōu)化讀性能掂为。
hbase在實(shí)現(xiàn)中，是把整個(gè)內(nèi)存在一定閾值后员串，flush到disk中勇哗，形成一個(gè)file，這個(gè)file的存儲也就是一個(gè)小的B+樹寸齐，因?yàn)閔base一般是部署在hdfs上欲诺，hdfs不支持對文件的update操作，所以hbase這么整體內(nèi)存flush渺鹦，而不是和磁盤中的小樹merge update扰法，這個(gè)設(shè)計(jì)也就能講通了。內(nèi)存flush到磁盤上的小樹毅厚，定期也會合并成一個(gè)大樹塞颁。整體上hbase就是用了lsm tree的思路。
