作為一名應用系統開發人員，為什麼要關註數據內部的存儲和檢索呢？首先，你不太可能從頭開始實現一套自己的存儲引擎，往往需要從眾多現有的存儲引擎中選擇一個適合自己應用的存儲引擎。因此，為了針對你特定的工作負載而對資料庫調優時，最好對存儲引擎的底層機制有一個大概的瞭解。 今天我們就先來瞭解下關係型資料庫My ...
作為一名應用系統開發人員，為什麼要關註數據內部的存儲和檢索呢？首先，你不太可能從頭開始實現一套自己的存儲引擎，往往需要從眾多現有的存儲引擎中選擇一個適合自己應用的存儲引擎。因此，為了針對你特定的工作負載而對資料庫調優時，最好對存儲引擎的底層機制有一個大概的瞭解。
今天我們就先來瞭解下關係型資料庫MySQL和NoSQL存儲引擎HBase的底層存儲機制。對於一個資料庫的性能來說，其數據的組織方式至關重要。眾所周知，資料庫的數據大多存儲在磁碟上，而磁碟的訪問相對記憶體的訪問來說是一項很耗時的操作，對比如下。因此，提高資料庫數據的查找速度的關鍵點之一便是儘量減少磁碟的訪問次數。
磁碟與記憶體的訪問速度對比
為了加速資料庫數據的訪問，大多傳統的關係型資料庫都會使用特殊的數據結構來幫助查找數據，這種數據結構叫作索引（ Index）。對於傳統的關係型資料庫，考慮到經常需要範圍查找某一批數據，因此其索引一般不使用 Hash演算法，而使用樹（ Tree）結構。然而，樹結構的種類很多，卻不一定都適合用於做資料庫索引。
二叉查找樹與平衡二叉樹
最常見的樹結構是二叉查找樹（ Binary Search Tree），它就是一棵二叉有序樹：保證左子樹上所有節點的值都小於根節點的值，而右子樹上所有節點的值都大於根節點的值。其優點在於實現簡單，並且樹在平衡的狀態下查找效率能達到 O(log n)；缺點是在極端非平衡情況下查找效率會退化到 O(n)，因此很難保證索引的效率。
二叉查找樹的查找效率
針對上述二叉查找樹的缺點，人們很自然就想到是否能用平衡二叉樹（ Balanced Binary Tree）來解決這個問題。但是平衡二叉樹依然有個比較大的問題：它的樹高為 log n——對於索引樹來說，樹的高度越高，意味著查找所要花費的訪問次數越多，查詢效率越低。
況且，主存從磁碟讀數據一般以頁為單位，因此每次訪問磁碟都會讀取多個扇區的數據（比如 4KB大小的數據），遠大於單個二叉樹節點的值（位元組級別），這也是造成二叉樹相對索引樹效率低下的原因。正因如此，人們就想到了通過增加每個樹節點的度來提高訪問效率，而 B+樹（B+-tree）便受到了更多的關註。
B+樹
在傳統的關係型資料庫里， B+樹（ B+-tree）及其衍生樹是被用得比較多的索引樹。
B+樹
B+樹的主要特點如下。
每個樹節點只存放鍵值，不存放數值，而由葉子節點存放數值。這樣會使樹節點的度比較大，而樹的高度就比較低，從而有利於提高查詢效率。
葉子節點存放數值，並按照值大小順序排序，且帶指向相鄰節點的指針，以便高效地進行區間數據查詢；並且所有葉子節點與根節點的距離相同，因此任何查詢的效率都很相似。
與二叉樹不同， B+樹的數據更新操作不從根節點開始，而從葉子節點開始，並且在更新過程中樹能以比較小的代價實現自平衡。
正是由於 B+樹的上述優點，它成了傳統關係型資料庫的寵兒。當然，它也並非無懈可擊，它的主要缺點在於隨著數據插入的不斷發生，葉子節點會慢慢分裂——這可能會導致邏輯上原本連續的數據實際上存放在不同的物理磁碟塊位置上，在做範圍查詢的時候會導致較高的磁碟 IO，以致嚴重影響到性能。
日誌結構合併樹
眾所周知，資料庫的數據大多存儲在磁碟上，而無論是傳統的機械硬碟（ HardDiskDrive, HDD）還是固態硬碟（ Solid State Drive, SSD），對磁碟數據的順序讀寫速度都遠高於隨機讀寫。
磁碟順序與隨機訪問吞吐對比
然而，基於 B+樹的索引結構是違背上述磁碟基本特點的——它會需要較多的磁碟隨機讀寫，於是， 1992年，名為日誌結構（ Log-Structured）的新型索引結構方法便應運而生。日誌結構方法的主要思想是將磁碟看作一個大的日誌，每次都將新的數據及其索引結構添加到日誌的最末端，以實現對磁碟的順序操作，從而提高索引性能。不過，日誌結構方法也有明顯的缺點，隨機讀取數據時效率很低。
1996年，一篇名為 Thelog-structured merge-tree（LSM-tree）的論文創造性地提出了日誌結構合併樹（ Log-Structured Merge-Tree）的概念，該方法既吸收了日誌結構方法的優點，又通過將數據文件預排序剋服了日誌結構方法隨機讀性能較差的問題。儘管當時 LSM-tree新穎且優勢鮮明，但它真正聲名鵲起卻是在 10年之後的 2006年，那年谷歌的一篇使用了 LSM-tree技術的論文 Bigtable: A Distributed Storage System for Structured Data橫空出世，在分散式數據處理領域掀起了一陣旋風，隨後兩個聲名赫赫的大數據開源組件（ 2007年的 HBase與 2008年的 Cassandra，目前兩者同為 Apache頂級項目）直接在其思想基礎上破繭而出，徹底改變了大數據基礎組件的格局，同時也極大地推廣了 LSM-tree技術。
LSM-tree最大的特點是同時使用了兩部分類樹的數據結構來存儲數據，並同時提供查詢。其中一部分數據結構（ C0樹）存在於記憶體緩存（通常叫作 memtable）中，負責接受新的數據插入更新以及讀請求，並直接在記憶體中對數據進行排序；另一部分數據結構（ C1樹）存在於硬碟上 (這部分通常叫作 sstable)，它們是由存在於記憶體緩存中的 C0樹沖寫到磁碟而成的，主要負責提供讀操作，特點是有序且不可被更改。
LSM-tree的 C0與 C1部分
LSM-tree的另一大特點是除了使用兩部分類樹的數據結構外，還會使用日誌文件（通常叫作 commit log）來為數據恢復做保障。這三類數據結構的協作順序一般是：所有的新插入與更新操作都首先被記錄到 commit log中——該操作叫作 WAL（Write Ahead Log），然後再寫到 memtable，最後當達到一定條件時數據會從 memtable沖寫到 sstable，並拋棄相關的 log數據； memtable與 sstable可同時供查詢；當 memtable出問題時，可從 commit log與 sstable中將 memtable的數據恢復。
我們可以參考 HBase的架構來體會其架構中基於 LSM-tree的部分特點。按照 WAL的原則，數據首先會寫到 HBase的 HLog(相當於 commit log)里，然後再寫到 MemStore（相當於 memtable）里，最後會沖寫到磁碟 StoreFile（相當於 sstable）中。這樣 HBase的 HRegionServer就通過 LSM-tree實現了數據文件的生成。HBase LSM-tree架構示意圖如下圖。
HBase LSM-tree架構示意圖
LSM-tree的這種結構非常有利於數據的快速寫入（理論上可以接近磁碟順序寫速度），但是不利於讀——因為理論上讀的時候可能需要同時從 memtable和所有硬碟上的 sstable中查詢數據，這樣顯然會對性能造成較大的影響。為瞭解決這個問題， LSM-tree採取了以下主要的相關措施。
- 定期將硬碟上小的 sstable合併（通常叫作 Merge或 Compaction操作）成大的 sstable，以減少 sstable的數量。而且，平時的數據更新刪除操作並不會更新原有的數據文件，只會將更新刪除操作加到當前的數據文件末端，只有在 sstable合併的時候才會真正將重覆的操作或更新去重、合併。
- 對每個 sstable使用布隆過濾器（ Bloom Filter），以加速對數據在該 sstable的存在性進行判定，從而減少數據的總查詢時間。
總結
LSM樹和B+樹的差異主要在於讀性能和寫性能進行權衡，在犧牲的同時尋找其餘補救方案。
B+樹存儲引擎，不僅支持單條記錄的增、刪、讀、改操作，還支持順序掃描（B+樹的葉子節點之間的指針），對應的存儲系統就是關係資料庫。但隨著寫入操作增多，為了維護B+樹結構，節點分裂，讀磁碟的隨機讀寫概率會變大，性能會逐漸減弱。LSM樹（Log-Structured MergeTree）存儲引擎和B+樹存儲引擎一樣，同樣支持增、刪、讀、改、順序掃描操作。而且通過批量存儲技術規避磁碟隨機寫入問題。當然凡事有利有弊，LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。
訂閱關註微信公眾號《大數據技術進階》，及時獲取更多大數據架構和應用相關技術文章！
