?1. 什么是數(shù)據(jù)庫的存儲引擎技術(shù)

數(shù)據(jù)庫的存儲引擎是什么？它主要解決什么問題？

很多數(shù)據(jù)庫管理員可能對存儲引擎并不熟悉，因為大多數(shù)常見關(guān)系型數(shù)據(jù)庫基本只有一種存儲引擎，沒有給我們選擇和設(shè)計的機會，例如Oracle、SQL Server。但是如果我們接觸MySQL以及其他一些NoSQL分布式數(shù)據(jù)庫比較多的人可能對存儲引擎就會深有感受。首先，我們認為存儲引擎就是為了實現(xiàn)數(shù)據(jù)存儲以及數(shù)據(jù)檢索而實現(xiàn)的解決方案，如何建立索引，如果實現(xiàn)更新，如何檢索數(shù)據(jù)等都是它的功能實現(xiàn)范疇。常見的存儲引擎有哈希存儲引擎和樹存儲引擎，樹存儲引擎又分為B-Tree、B+Tree、LSM-Tree等若干種。不同的存儲引擎對數(shù)據(jù)的結(jié)構(gòu)、數(shù)據(jù)的存儲方式、數(shù)據(jù)的讀取方式等都有不同的要求和特點。

2. 不同存儲引擎如何建立索引

2.1 B-Tree

B樹數(shù)據(jù)結(jié)構(gòu)其實是在我們大學當中所學數(shù)據(jù)結(jié)構(gòu)課程當中的二叉樹基礎(chǔ)上的一種升級和改進。最早是由德國計算機科學家Rudolf Bayer等人于1972年在論文 《Organization and Maintenance of Large Ordered Indexes》提出。

如圖所示，B樹事實上是一種平衡的多叉查找樹，也就是說最多可以開m個叉（m>=2），我們稱之為m階b樹?？偟膩碚f，m階B樹滿足以下條件：

（1）每個節(jié)點至多可以擁有m棵子樹。

（2）根節(jié)點，只有至少有2個節(jié)點（極端情況，就是一棵樹就一個根節(jié)點)。

（3）非根非葉的節(jié)點至少有Ceil(m/2)個子樹( 圖中5階B樹，每個節(jié)點至少有3個子樹)。

（4）非葉節(jié)點中信息包括[n,A0,K1,…,Kn,An]，其中n表示該節(jié)點保存的關(guān)鍵字個數(shù)，K為關(guān)鍵字且Ki（對應(yīng)到關(guān)系型數(shù)據(jù)庫當中的信息，就是二位表當中記錄的主鍵信息）。

（5）從根到葉子的每一條路徑都有相同的長度，也就是指向這些節(jié)點的指針為空。

2.2 B+Tree

B+樹實際上是B-Tree的升級版，它是基于原有數(shù)據(jù)結(jié)構(gòu)的不足支持進行系列改造之后形成的存儲引擎技術(shù)，如圖所示：

從圖中所示的狀況我們可以很直觀感受到：B+樹與 B樹最大的不同是所有數(shù)據(jù)記錄都保存在葉子節(jié)點中，葉子結(jié)點是有指針將所有數(shù)據(jù)連接起來的。具體來說，B+樹與B樹的主要區(qū)別：

（1） 有n棵子樹的節(jié)點含有n個關(guān)鍵字（也有認為是n-1個關(guān)鍵字）;

（2） 所有的葉子節(jié)點包含了全部的關(guān)鍵字，及指向含這些關(guān)鍵字記錄的指針，且葉子節(jié)點本身根據(jù)關(guān)鍵字自小而大順序連接;

（3） 非葉子節(jié)點可以看成索引部分，節(jié)點中僅含有其子樹中的最大或最小關(guān)鍵字.

由于采用了這樣的結(jié)構(gòu)，B+樹對比B樹有以下兩方面優(yōu)點：

首先，索引節(jié)點上由于只有索引而沒有數(shù)據(jù)，所以索引節(jié)點上能存儲比B樹更多的索引，這樣樹的高度就會更矮。那么查詢的時間復雜度就會更低。再有，因為數(shù)據(jù)都集中在葉子節(jié)點了并且葉子節(jié)點增加前后指針，指向同一個父節(jié)點的相鄰兄弟節(jié)點，給范圍查詢提供遍歷。而如果使用B樹結(jié)構(gòu)，由于數(shù)據(jù)既可以存儲在內(nèi)部節(jié)點也可以存儲在葉子節(jié)點，范圍查詢是很繁瑣的。

2.3 Hash

哈希存儲引擎的數(shù)據(jù)庫本身只是一個健值存儲系統(tǒng)，數(shù)據(jù)庫當中存儲的數(shù)據(jù)以文件的物理形式表現(xiàn)，但是每一個物理文件當中存儲的具體數(shù)據(jù)內(nèi)容主要包含兩種：一種是主健，另外一種是具體的數(shù)據(jù)值。用戶通過put(key,value)來寫入數(shù)據(jù)，或者通過get(key)接口來獲取數(shù)據(jù)，每條記錄都是一個健值對。

哈希索引本身有很多種實現(xiàn)方式，有基于靜態(tài)哈希實現(xiàn)的索引結(jié)構(gòu)，也有基于動態(tài)哈希實現(xiàn)的索引結(jié)構(gòu)，其具體的實現(xiàn)方式依賴于不同的數(shù)據(jù)庫。一般來講，哈希索引表的結(jié)構(gòu)如圖所示：

我們知道HashMap< K,V>，可以通過K 來獲取V, 對于以上的哈希索引來說，PrimaryKey就是我們要取得的V值。比如 （PK = key mod 2） 叫做散列函數(shù)或者哈希函數(shù)，那么PK的區(qū)間范圍，我們稱其為散列地址。存儲的時候 通過散列函數(shù)算出散列地址，然后把value的值存入，查找的時候 通過散列函數(shù)算出散列地址 ，然后讀出數(shù)據(jù)。

3. 不同存儲引擎的數(shù)據(jù)檢索

3.1 B-Tree & B+Tree

對于基于二叉樹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之上形成的樹的存儲結(jié)構(gòu)，那么其查詢數(shù)據(jù)最核心的算法就是二分法查找算法，即通過鍵值的比較排除一定比例的可能性，從而縮小數(shù)據(jù)查找的范圍，最終通過幾次比較定位到要查找的數(shù)據(jù)。直觀表現(xiàn)期間，我們還是以圖為例：

按照圖示，我們查找的數(shù)據(jù)是L，首先，將根節(jié)點的數(shù)據(jù)塊從磁盤讀入內(nèi)存，讀出P值，比較發(fā)現(xiàn)小于P；

接著，遍歷根節(jié)點左指針指向數(shù)據(jù)塊，讀出C、F、J、M值，順序比較后，找到J&M之間的指針；

最后，遍歷指針指向數(shù)據(jù)塊，讀出K、L值，定位所查詢的數(shù)據(jù)L。

根據(jù)以上算法，那么本次查找經(jīng)歷了三次磁盤的讀取，三次內(nèi)存數(shù)據(jù)的比較。由此看見，B樹檢索的時間復雜度主要取決于樹的深度以及節(jié)點內(nèi)保存的數(shù)據(jù)數(shù)量的多少。

對于B+樹的檢索，其實算法與B樹非常類似，其主要區(qū)別在于B+樹的所有檢索操作都不會在非葉子節(jié)點結(jié)束，每一個檢索都會經(jīng)歷相同的長度，那就是從根節(jié)點到葉子節(jié)點，途中經(jīng)歷的非葉子節(jié)點只保留索引信息，只有葉子節(jié)點才會保留所有鍵值數(shù)據(jù)。這種算法把所有遍歷的復雜度留在了葉子節(jié)點的掃描上，減少了檢索途中的IO次數(shù)，保證了葉子節(jié)點掃描的局部優(yōu)勢，同時也保障了所有檢索操作的時間復雜度相對的穩(wěn)定性。因此大部分關(guān)系型數(shù)據(jù)庫選擇的是B+樹作為其存儲引擎。

3.2 Hash

對于Hash存儲引擎的數(shù)據(jù)檢索，我們首先要聊到它的增、刪、改操作。

數(shù)據(jù)文件分活躍狀態(tài)和陳舊狀態(tài)兩種。

數(shù)據(jù)的增加操作，用戶寫入的記錄直接追加到活動文件，因此活動文件會越來越大，當?shù)竭_一定大小時，活躍的數(shù)據(jù)文件會被凍結(jié)。引擎重新建立一個活躍文件用于寫入，而之前的活躍文件則變?yōu)殛惻f的數(shù)據(jù)文件。寫入記錄的同時還要在索引哈希表中添加索引記錄。

數(shù)據(jù)的刪除操作，用戶不直接刪除記錄，而是新增一條相同Key的記錄，把Value值設(shè)置一個刪除的標記。原有記錄依然存在于數(shù)據(jù)文件中，然后更新索引哈希表。這樣的話，在處理檢索操作的時候，用戶就會最先讀到哈希索引表里面的空值記錄，原有記錄后續(xù)處理。

數(shù)據(jù)的更新操作，不支持隨機寫入。對于存儲系統(tǒng)的基本功能中更新，實際上和增加數(shù)據(jù)操作都是一樣的，都是直接寫入活動數(shù)據(jù)文件。同時修改索引哈希表中對應(yīng)記錄的值。這個時候，實際上數(shù)據(jù)文件中同一個Key值對應(yīng)了多條記錄，根據(jù)時間戳記錄來判斷，以最新的數(shù)據(jù)為準。

數(shù)據(jù)的讀取操作，讀取時，首先從索引哈希表中定位到記錄在數(shù)據(jù)文件中的具體位置，然后通過讀取出對應(yīng)的記錄。當然在讀取索引表的時候，索引的結(jié)構(gòu)有可能是索引樹結(jié)構(gòu)，在檢索索引的過程當中會有一定的復雜度，具體根據(jù)樹的深度來判斷檢索的復雜度。

4. 不同存儲引擎技術(shù)的選擇設(shè)計

4.1 B&B+樹的優(yōu)劣勢分析

首先，通過對B樹和B+樹的檢索算法特點來看，從使用的角度上來說，B樹索引存儲結(jié)構(gòu)多用于OLTP型的數(shù)據(jù)庫，因為這類數(shù)據(jù)庫主要以事務(wù)，或是行級別的讀取和存儲為主的（比如MYSQL）。換言之，這種類型的數(shù)據(jù)庫更多的操作是小批量或單行級別的隨機讀取和更新，并且還有事務(wù)方面的需求。在此前提條件之下，之所以有B+樹的誕生，取決于以下兩點：a. 磁盤讀寫代價更低。B樹的內(nèi)部結(jié)點并無指向關(guān)鍵字具體信息的指針。所以其內(nèi)部結(jié)點相對B樹更小。若是把全部同一內(nèi)部結(jié)點的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字數(shù)量也越多。一次性讀入內(nèi)存中的須要查找的關(guān)鍵字也就越多。相對來講IO讀寫次數(shù)也就下降了。b. B+樹只要遍歷葉子節(jié)點就能夠?qū)崿F(xiàn)整棵樹的遍歷。并且在數(shù)據(jù)庫中基于范圍的查詢是很是頻繁的，而B樹實現(xiàn)這樣的操作需要的代價非常高，效率非常低。

其次，通過對B樹和B+樹的更新和刪除算法特點來看，雖然算法相對哈希及其他存儲引擎實現(xiàn)的算法來講會顯得非常復雜，代價很高。但是從另外一個側(cè)面來看，正是由于它沒有通過大量的數(shù)據(jù)追加實現(xiàn)更新和刪除，它就無需去管理那些不同時間戳版本的重復數(shù)據(jù)。有效地利用了磁盤空間和內(nèi)存空間，這個也與我們OLTP型關(guān)系型數(shù)據(jù)庫的規(guī)模以及通用服務(wù)器硬件的配置非常匹配。

4.2 Hash的優(yōu)劣勢分析

首先，從數(shù)據(jù)結(jié)構(gòu)特點來看。我們在前邊提到了它的數(shù)據(jù)結(jié)構(gòu)以及索引表的結(jié)構(gòu)，我們發(fā)現(xiàn)最大的特點就是在于所有的這些數(shù)據(jù)結(jié)構(gòu)都是以模式為基礎(chǔ)的。所以基于這一點來看，它本身更適合能以鍵值對的模式表示的數(shù)據(jù)存儲，無論是固定的鍵值，還是變動的鍵值。其次，我們來分析哈希存儲引擎索引表檢索算法的特點。如果沖突處理的算法的當，它大概率可以通過一次哈希函數(shù)就可以定位到數(shù)據(jù)的基本位置，與B-Tree存儲引擎相比較而言，它少了樹根、樹枝、樹葉節(jié)點的遍歷和多次的讀取操作。從哈希存儲引擎添加、刪除、更新數(shù)據(jù)的算法特點來看，基于除了檢索之外所有的數(shù)據(jù)操作都是通過添加新數(shù)據(jù)來變相實現(xiàn)。同樣與B-Tree存儲引擎相比較而言，添加一條新的紀錄遠比檢索、加鎖、修改、放鎖這個過程要效率很多。從這個意義上來講，如果我們能把這些符合鍵值對要求的索引表數(shù)據(jù)全部引入到內(nèi)存，那么對于隨機讀取的并發(fā)能力提升無疑是巨大的質(zhì)變，這也是它能被Redis、Memcache這類內(nèi)存數(shù)據(jù)庫選中的重要原因。最后，所以對于事務(wù)性要求不是非常強，并且包含大量寫入及更新的數(shù)據(jù)場景就比較有優(yōu)勢了。

矛盾總是貫穿于事物的發(fā)展過程當中，有利就有弊。對于哈希存儲引擎也是如此，正是因為它的優(yōu)勢而導致了一些不可避免的劣勢。首先、由于哈希存儲引擎的數(shù)據(jù)結(jié)構(gòu)特點，那么對于一些數(shù)據(jù)內(nèi)部字段之間以及數(shù)據(jù)本身有著相對復雜的關(guān)系的數(shù)據(jù)，比如二維表數(shù)據(jù)。哈希存儲引擎就會束手無策。其次，由于哈希存儲引擎的檢索算法是基于哈希索引表的哈希函數(shù)計算實現(xiàn)，那么它就只能實現(xiàn)一次比較孤立的數(shù)據(jù)定位，對于范圍的查詢以及檢索過程當中的一些排序、分組、過濾等操作就力不從心了。最后，還是從其數(shù)據(jù)增加、刪除、更新的算法來看。它是犧牲了大量的存儲空間來實現(xiàn)操作的高效性，那么后續(xù)必然會帶來空間的管理代價以及數(shù)據(jù)的合并處理代價，數(shù)據(jù)片越大、哈希樹的高度越高，那么數(shù)據(jù)檢索的效率相應(yīng)會提高很多，因為哈希函數(shù)定位之后必然隨之而來的是對定位到的數(shù)據(jù)片的全部掃描，數(shù)據(jù)片越大，檢索的平均效率越差。同時后臺執(zhí)行的數(shù)據(jù)片合并的時間越長。因此對于數(shù)據(jù)粒度比較大，又沒有一個好的哈希函數(shù)可以使用的場景，也不是哈希存儲引擎使用的最佳場景。

5. 總結(jié)與展望

無論是樹還是哈希存儲引擎，它們都是數(shù)據(jù)存取技術(shù)的設(shè)計思想，很多關(guān)系型數(shù)據(jù)庫大多基于B-Tree家族實現(xiàn)的，而很多分布式NoSQL數(shù)據(jù)庫都是基于Hash家族實現(xiàn)的，在每一種產(chǎn)品具體實現(xiàn)的過程中可能會改進其中的一些算法細節(jié)從而實現(xiàn)部分缺陷的優(yōu)化，尤其是一些開源的數(shù)據(jù)庫。但是這種存儲引擎的基本思想是決定具體數(shù)據(jù)庫產(chǎn)品的適用場景的最根本原因，本文希望通過這些原理性的討論和分析展示給大家有一個宏觀的視圖，從而指導具體的數(shù)據(jù)庫設(shè)計實踐。當然也希望更多同業(yè)能從更多維?度繼續(xù)分析討論并分享。