作為一名應用系統(tǒng)開發(fā)人員，為什么要關注數(shù)據(jù)內部的存儲和檢索呢计露？首先尊惰，你不太可能從頭開始實現(xiàn)一套自己的存儲引擎郁轻，往往需要從眾多現(xiàn)有的存儲引擎中選擇一個適合自己應用的存儲引擎。因此笑旺，為了針對你特定的工作負載而對數(shù)據(jù)庫調優(yōu)時昼浦，最好對存儲引擎的底層機制有一個大概的了解。

今天我們就先來了解下關系型數(shù)據(jù)庫MySQL和NoSQL存儲引擎HBase的底層存儲機制筒主。對于一個數(shù)據(jù)庫的性能來說关噪，其數(shù)據(jù)的組織方式至關重要鸟蟹。眾所周知，數(shù)據(jù)庫的數(shù)據(jù)大多存儲在磁盤上使兔，而磁盤的訪問相對內存的訪問來說是一項很耗時的操作建钥，對比如下。因此虐沥，提高數(shù)據(jù)庫數(shù)據(jù)的查找速度的關鍵點之一便是盡量減少磁盤的訪問次數(shù)熊经。

1.jpg

磁盤與內存的訪問速度對比

為了加速數(shù)據(jù)庫數(shù)據(jù)的訪問，大多傳統(tǒng)的關系型數(shù)據(jù)庫都會使用特殊的數(shù)據(jù)結構來幫助查找數(shù)據(jù)欲险，這種數(shù)據(jù)結構叫作索引（ Index）奈搜。對于傳統(tǒng)的關系型數(shù)據(jù)庫，考慮到經常需要范圍查找某一批數(shù)據(jù)盯荤，因此其索引一般不使用 Hash算法，而使用樹（ Tree）結構焕盟。然而秋秤，樹結構的種類很多，卻不一定都適合用于做數(shù)據(jù)庫索引脚翘。

二叉查找樹與平衡二叉樹

最常見的樹結構是二叉查找樹（ Binary Search Tree）灼卢，它就是一棵二叉有序樹：保證左子樹上所有節(jié)點的值都小于根節(jié)點的值，而右子樹上所有節(jié)點的值都大于根節(jié)點的值来农。其優(yōu)點在于實現(xiàn)簡單鞋真，并且樹在平衡的狀態(tài)下查找效率能達到 O(log n)；缺點是在極端非平衡情況下查找效率會退化到 O(n)沃于，因此很難保證索引的效率涩咖。

image

二叉查找樹的查找效率

針對上述二叉查找樹的缺點，人們很自然就想到是否能用平衡二叉樹（ Balanced Binary Tree）來解決這個問題繁莹。但是平衡二叉樹依然有個比較大的問題：它的樹高為 log n——對于索引樹來說檩互，樹的高度越高，意味著查找所要花費的訪問次數(shù)越多咨演，查詢效率越低闸昨。

況且，主存從磁盤讀數(shù)據(jù)一般以頁為單位薄风，因此每次訪問磁盤都會讀取多個扇區(qū)的數(shù)據(jù)（比如 4KB大小的數(shù)據(jù)）饵较，遠大于單個二叉樹節(jié)點的值（字節(jié)級別），這也是造成二叉樹相對索引樹效率低下的原因遭赂。正因如此循诉，人們就想到了通過增加每個樹節(jié)點的度來提高訪問效率，而 B+樹（B+-tree）便受到了更多的關注嵌牺。

B+樹

在傳統(tǒng)的關系型數(shù)據(jù)庫里打洼， B+樹（ B+-tree）及其衍生樹是被用得比較多的索引樹龄糊。

image

B+樹

B+樹的主要特點如下。

每個樹節(jié)點只存放鍵值募疮，不存放數(shù)值炫惩，而由葉子節(jié)點存放數(shù)值。這樣會使樹節(jié)點的度比較大阿浓，而樹的高度就比較低他嚷，從而有利于提高查詢效率。

葉子節(jié)點存放數(shù)值芭毙，并按照值大小順序排序筋蓖，且?guī)е赶蛳噜徆?jié)點的指針，以便高效地進行區(qū)間數(shù)據(jù)查詢退敦；并且所有葉子節(jié)點與根節(jié)點的距離相同粘咖，因此任何查詢的效率都很相似。

與二叉樹不同侈百， B+樹的數(shù)據(jù)更新操作不從根節(jié)點開始瓮下，而從葉子節(jié)點開始，并且在更新過程中樹能以比較小的代價實現(xiàn)自平衡钝域。

正是由于 B+樹的上述優(yōu)點讽坏，它成了傳統(tǒng)關系型數(shù)據(jù)庫的寵兒。當然例证，它也并非無懈可擊路呜，它的主要缺點在于隨著數(shù)據(jù)插入的不斷發(fā)生，葉子節(jié)點會慢慢分裂——這可能會導致邏輯上原本連續(xù)的數(shù)據(jù)實際上存放在不同的物理磁盤塊位置上织咧，在做范圍查詢的時候會導致較高的磁盤 IO胀葱，以致嚴重影響到性能。

日志結構合并樹

眾所周知笙蒙，數(shù)據(jù)庫的數(shù)據(jù)大多存儲在磁盤上巡社，而無論是傳統(tǒng)的機械硬盤（ HardDiskDrive, HDD）還是固態(tài)硬盤（ Solid State Drive, SSD），對磁盤數(shù)據(jù)的順序讀寫速度都遠高于隨機讀寫手趣。

4.jpg

磁盤順序與隨機訪問吞吐對比

然而晌该，基于 B+樹的索引結構是違背上述磁盤基本特點的——它會需要較多的磁盤隨機讀寫，于是绿渣， 1992年朝群，名為日志結構（ Log-Structured）的新型索引結構方法便應運而生。日志結構方法的主要思想是將磁盤看作一個大的日志中符，每次都將新的數(shù)據(jù)及其索引結構添加到日志的最末端姜胖，以實現(xiàn)對磁盤的順序操作，從而提高索引性能淀散。不過右莱，日志結構方法也有明顯的缺點蚜锨，隨機讀取數(shù)據(jù)時效率很低。

1996年慢蜓，一篇名為 Thelog-structured merge-tree（LSM-tree）的論文創(chuàng)造性地提出了日志結構合并樹（ Log-Structured Merge-Tree）的概念亚再，該方法既吸收了日志結構方法的優(yōu)點，又通過將數(shù)據(jù)文件預排序克服了日志結構方法隨機讀性能較差的問題晨抡。盡管當時 LSM-tree新穎且優(yōu)勢鮮明氛悬，但它真正聲名鵲起卻是在 10年之后的 2006年，那年谷歌的一篇使用了 LSM-tree技術的論文 Bigtable: A Distributed Storage System for Structured Data橫空出世耘柱，在分布式數(shù)據(jù)處理領域掀起了一陣旋風如捅，隨后兩個聲名赫赫的大數(shù)據(jù)開源組件（ 2007年的 HBase與 2008年的 Cassandra，目前兩者同為 Apache頂級項目）直接在其思想基礎上破繭而出调煎，徹底改變了大數(shù)據(jù)基礎組件的格局镜遣，同時也極大地推廣了 LSM-tree技術。

LSM-tree最大的特點是同時使用了兩部分類樹的數(shù)據(jù)結構來存儲數(shù)據(jù)士袄，并同時提供查詢烈涮。其中一部分數(shù)據(jù)結構（ C0樹）存在于內存緩存（通常叫作 memtable）中，負責接受新的數(shù)據(jù)插入更新以及讀請求窖剑，并直接在內存中對數(shù)據(jù)進行排序；另一部分數(shù)據(jù)結構（ C1樹）存在于硬盤上 (這部分通常叫作 sstable)戈稿，它們是由存在于內存緩存中的 C0樹沖寫到磁盤而成的西土，主要負責提供讀操作，特點是有序且不可被更改鞍盗。

image

LSM-tree的 C0與 C1部分

LSM-tree的另一大特點是除了使用兩部分類樹的數(shù)據(jù)結構外需了，還會使用日志文件（通常叫作 commit log）來為數(shù)據(jù)恢復做保障。這三類數(shù)據(jù)結構的協(xié)作順序一般是：所有的新插入與更新操作都首先被記錄到 commit log中——該操作叫作 WAL（Write Ahead Log）般甲，然后再寫到 memtable肋乍，最后當達到一定條件時數(shù)據(jù)會從 memtable沖寫到 sstable，并拋棄相關的 log數(shù)據(jù)敷存； memtable與 sstable可同時供查詢墓造；當 memtable出問題時，可從 commit log與 sstable中將 memtable的數(shù)據(jù)恢復锚烦。

我們可以參考 HBase的架構來體會其架構中基于 LSM-tree的部分特點觅闽。按照 WAL的原則，數(shù)據(jù)首先會寫到 HBase的 HLog(相當于 commit log)里涮俄，然后再寫到 MemStore（相當于 memtable）里蛉拙，最后會沖寫到磁盤 StoreFile（相當于 sstable）中。這樣 HBase的 HRegionServer就通過 LSM-tree實現(xiàn)了數(shù)據(jù)文件的生成彻亲。HBase LSM-tree架構示意圖如下圖孕锄。

image

HBase LSM-tree架構示意圖

LSM-tree的這種結構非常有利于數(shù)據(jù)的快速寫入（理論上可以接近磁盤順序寫速度）吮廉，但是不利于讀——因為理論上讀的時候可能需要同時從 memtable和所有硬盤上的 sstable中查詢數(shù)據(jù)，這樣顯然會對性能造成較大的影響畸肆。為了解決這個問題宦芦， LSM-tree采取了以下主要的相關措施。

• 定期將硬盤上小的 sstable合并（通常叫作 Merge或 Compaction操作）成大的 sstable恼除，以減少 sstable的數(shù)量踪旷。而且，平時的數(shù)據(jù)更新刪除操作并不會更新原有的數(shù)據(jù)文件豁辉，只會將更新刪除操作加到當前的數(shù)據(jù)文件末端令野，只有在 sstable合并的時候才會真正將重復的操作或更新去重、合并徽级。
• 對每個 sstable使用布隆過濾器（ Bloom Filter）气破，以加速對數(shù)據(jù)在該 sstable的存在性進行判定，從而減少數(shù)據(jù)的總查詢時間餐抢。

總結

LSM樹和B+樹的差異主要在于讀性能和寫性能進行權衡现使，在犧牲的同時尋找其余補救方案。

B+樹存儲引擎旷痕，不僅支持單條記錄的增碳锈、刪、讀欺抗、改操作售碳，還支持順序掃描（B+樹的葉子節(jié)點之間的指針），對應的存儲系統(tǒng)就是關系數(shù)據(jù)庫绞呈。但隨著寫入操作增多贸人，為了維護B+樹結構，節(jié)點分裂佃声，讀磁盤的隨機讀寫概率會變大艺智，性能會逐漸減弱。LSM樹（Log-Structured MergeTree）存儲引擎和B+樹存儲引擎一樣圾亏，同樣支持增十拣、刪、讀志鹃、改父晶、順序掃描操作。而且通過批量存儲技術規(guī)避磁盤隨機寫入問題弄跌。當然凡事有利有弊甲喝，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能铛只，用來大幅提高寫性能埠胖。