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

[[283718]]

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

磁盤與內(nèi)存的訪問速度對比

為了加速數(shù)據(jù)庫數(shù)據(jù)的訪問，大多傳統(tǒng)的關(guān)系型數(shù)據(jù)庫都會使用特殊的數(shù)據(jù)結(jié)構(gòu)來幫助查找數(shù)據(jù)，這種數(shù)據(jù)結(jié)構(gòu)叫作索引( Index)。對于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫，考慮到經(jīng)常需要范圍查找某一批數(shù)據(jù)，因此其索引一般不使用 Hash算法，而使用樹( Tree)結(jié)構(gòu)。然而，樹結(jié)構(gòu)的種類很多，卻不一定都適合用于做數(shù)據(jù)庫索引。

二叉查找樹與平衡二叉樹

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

二叉查找樹的查找效率

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

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

B+樹

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

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)關(guān)系型數(shù)據(jù)庫的寵兒。當(dāng)然，它也并非無懈可擊，它的主要缺點在于隨著數(shù)據(jù)插入的不斷發(fā)生，葉子節(jié)點會慢慢分裂——這可能會導(dǎo)致邏輯上原本連續(xù)的數(shù)據(jù)實際上存放在不同的物理磁盤塊位置上，在做范圍查詢的時候會導(dǎo)致較高的磁盤 IO，以致嚴(yán)重影響到性能。

日志結(jié)構(gòu)合并樹

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

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

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

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

LSM-tree最大的特點是同時使用了兩部分類樹的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)，并同時提供查詢。其中一部分?jǐn)?shù)據(jù)結(jié)構(gòu)( C0樹)存在于內(nèi)存緩存(通常叫作 memtable)中，負責(zé)接受新的數(shù)據(jù)插入更新以及讀請求，并直接在內(nèi)存中對數(shù)據(jù)進行排序;另一部分?jǐn)?shù)據(jù)結(jié)構(gòu)( C1樹)存在于硬盤上 (這部分通常叫作 sstable)，它們是由存在于內(nèi)存緩存中的 C0樹沖寫到磁盤而成的，主要負責(zé)提供讀操作，特點是有序且不可被更改。

LSM-tree的 C0與 C1部分

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

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

HBase LSM-tree架構(gòu)示意圖

LSM-tree的這種結(jié)構(gòu)非常有利于數(shù)據(jù)的快速寫入(理論上可以接近磁盤順序?qū)懰俣?，但是不利于讀——因為理論上讀的時候可能需要同時從 memtable和所有硬盤上的 sstable中查詢數(shù)據(jù)，這樣顯然會對性能造成較大的影響。為了解決這個問題， LSM-tree采取了以下主要的相關(guān)措施。

定期將硬盤上小的 sstable合并(通常叫作 Merge或 Compaction操作)成大的 sstable，以減少 sstable的數(shù)量。而且，平時的數(shù)據(jù)更新刪除操作并不會更新原有的數(shù)據(jù)文件，只會將更新刪除操作加到當(dāng)前的數(shù)據(jù)文件末端，只有在 sstable合并的時候才會真正將重復(fù)的操作或更新去重、合并。

對每個 sstable使用布隆過濾器( Bloom Filter)，以加速對數(shù)據(jù)在該 sstable的存在性進行判定，從而減少數(shù)據(jù)的總查詢時間。

總結(jié)

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

B+樹存儲引擎，不僅支持單條記錄的增、刪、讀、改操作，還支持順序掃描(B+樹的葉子節(jié)點之間的指針)，對應(yīng)的存儲系統(tǒng)就是關(guān)系數(shù)據(jù)庫。但隨著寫入操作增多，為了維護B+樹結(jié)構(gòu)，節(jié)點分裂，讀磁盤的隨機讀寫概率會變大，性能會逐漸減弱。LSM樹(Log-Structured MergeTree)存儲引擎和B+樹存儲引擎一樣，同樣支持增、刪、讀、改、順序掃描操作。而且通過批量存儲技術(shù)規(guī)避磁盤隨機寫入問題。當(dāng)然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。