本文來自twt企業(yè)IT社區(qū)，作者/趙海。
很多數(shù)據(jù)庫管理員可能對(duì)存儲(chǔ)引擎并不熟悉，但接觸MySQL以及其他一些NoSQL分布式數(shù)據(jù)庫比較多的人可能對(duì)存儲(chǔ)引擎就會(huì)深有感受。不同的存儲(chǔ)引擎對(duì)數(shù)據(jù)的結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)方式、數(shù)據(jù)的讀取方式等都有不同的要求和特點(diǎn)。存儲(chǔ)引擎的基本思想是決定具體數(shù)據(jù)庫產(chǎn)品的適用場(chǎng)景的最根本原因，本文希望通過這些原理性的討論和分析展示給大家有一個(gè)宏觀的視圖，從而指導(dǎo)具體的數(shù)據(jù)庫設(shè)計(jì)實(shí)踐。
1.什么是數(shù)據(jù)庫的存儲(chǔ)引擎技術(shù)
數(shù)據(jù)庫的存儲(chǔ)引擎是什么？它主要解決什么問題？
很多數(shù)據(jù)庫管理員可能對(duì)存儲(chǔ)引擎并不熟悉，因?yàn)榇蠖鄶?shù)常見關(guān)系型數(shù)據(jù)庫基本只有一種存儲(chǔ)引擎，沒有給我們選擇和設(shè)計(jì)的機(jī)會(huì)，例如Oracle、SQL Server。但是如果我們接觸MySQL以及其他一些NoSQL分布式數(shù)據(jù)庫比較多的人可能對(duì)存儲(chǔ)引擎就會(huì)深有感受。首先，我們認(rèn)為存儲(chǔ)引擎就是為了實(shí)現(xiàn)數(shù)據(jù)存儲(chǔ)以及數(shù)據(jù)檢索而實(shí)現(xiàn)的解決方案，如何建立索引，如果實(shí)現(xiàn)更新，如何檢索數(shù)據(jù)等都是它的功能實(shí)現(xiàn)范疇。常見的存儲(chǔ)引擎有哈希存儲(chǔ)引擎和樹存儲(chǔ)引擎，樹存儲(chǔ)引擎又分為B-Tree、B+Tree、LSM-Tree等若干種。不同的存儲(chǔ)引擎對(duì)數(shù)據(jù)的結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)方式、數(shù)據(jù)的讀取方式等都有不同的要求和特點(diǎn)。
2.不同存儲(chǔ)引擎如何建立索引
2.1 B-Tree
B樹數(shù)據(jù)結(jié)構(gòu)其實(shí)是在我們大學(xué)當(dāng)中所學(xué)數(shù)據(jù)結(jié)構(gòu)課程當(dāng)中的二叉樹基礎(chǔ)上的一種升級(jí)和改進(jìn)。最早是由德國計(jì)算機(jī)科學(xué)家Rudolf Bayer等人于1972年在論文《Organization and Maintenance of Large Ordered Indexes》提出。
如圖所示，B樹事實(shí)上是一種平衡的多叉查找樹，也就是說最多可以開m個(gè)叉（m>=2），我們稱之為m階b樹?？偟膩碚f，m階B樹滿足以下條件：
（1）每個(gè)節(jié)點(diǎn)至多可以擁有m棵子樹。
（2）根節(jié)點(diǎn)，只有至少有2個(gè)節(jié)點(diǎn)（極端情況，就是一棵樹就一個(gè)根節(jié)點(diǎn))。
（3）非根非葉的節(jié)點(diǎn)至少有Ceil(m/2)個(gè)子樹(圖中5階B樹，每個(gè)節(jié)點(diǎn)至少有3個(gè)子樹)。
（4）非葉節(jié)點(diǎn)中信息包括[n,A0,K1,…,Kn,An]，其中n表示該節(jié)點(diǎn)保存的關(guān)鍵字個(gè)數(shù)，K為關(guān)鍵字且Ki（對(duì)應(yīng)到關(guān)系型數(shù)據(jù)庫當(dāng)中的信息，就是二位表當(dāng)中記錄的主鍵信息）。
（5）從根到葉子的每一條路徑都有相同的長度，也就是指向這些節(jié)點(diǎn)的指針為空。
2.2 B+Tree
B+樹實(shí)際上是B-Tree的升級(jí)版，它是基于原有數(shù)據(jù)結(jié)構(gòu)的不足支持進(jìn)行系列改造之后形成的存儲(chǔ)引擎技術(shù)，如圖所示：
從圖中所示的狀況我們可以很直觀感受到：B+樹與B樹最大的不同是所有數(shù)據(jù)記錄都保存在葉子節(jié)點(diǎn)中，葉子結(jié)點(diǎn)是有指針將所有數(shù)據(jù)連接起來的。具體來說，B+樹與B樹的主要區(qū)別：
（1）有n棵子樹的節(jié)點(diǎn)含有n個(gè)關(guān)鍵字（也有認(rèn)為是n-1個(gè)關(guān)鍵字）;
（2）所有的葉子節(jié)點(diǎn)包含了全部的關(guān)鍵字，及指向含這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身根據(jù)關(guān)鍵字自小而大順序連接;
（3）非葉子節(jié)點(diǎn)可以看成索引部分，節(jié)點(diǎn)中僅含有其子樹中的最大或最小關(guān)鍵字.
由于采用了這樣的結(jié)構(gòu)，B+樹對(duì)比B樹有以下兩方面優(yōu)點(diǎn)：
首先，索引節(jié)點(diǎn)上由于只有索引而沒有數(shù)據(jù)，所以索引節(jié)點(diǎn)上能存儲(chǔ)比B樹更多的索引，這樣樹的高度就會(huì)更矮。那么查詢的時(shí)間復(fù)雜度就會(huì)更低。再有，因?yàn)閿?shù)據(jù)都集中在葉子節(jié)點(diǎn)了并且葉子節(jié)點(diǎn)增加前后指針，指向同一個(gè)父節(jié)點(diǎn)的相鄰兄弟節(jié)點(diǎn)，給范圍查詢提供遍歷。而如果使用B樹結(jié)構(gòu)，由于數(shù)據(jù)既可以存儲(chǔ)在內(nèi)部節(jié)點(diǎn)也可以存儲(chǔ)在葉子節(jié)點(diǎn)，范圍查詢是很繁瑣的。
2.3 Hash
哈希存儲(chǔ)引擎的數(shù)據(jù)庫本身只是一個(gè)健值存儲(chǔ)系統(tǒng)，數(shù)據(jù)庫當(dāng)中存儲(chǔ)的數(shù)據(jù)以文件的物理形式表現(xiàn)，但是每一個(gè)物理文件當(dāng)中存儲(chǔ)的具體數(shù)據(jù)內(nèi)容主要包含兩種：一種是主健，另外一種是具體的數(shù)據(jù)值。用戶通過put(key,value)來寫入數(shù)據(jù)，或者通過get(key)接口來獲取數(shù)據(jù)，每條記錄都是一個(gè)健值對(duì)。
哈希索引本身有很多種實(shí)現(xiàn)方式，有基于靜態(tài)哈希實(shí)現(xiàn)的索引結(jié)構(gòu)，也有基于動(dòng)態(tài)哈希實(shí)現(xiàn)的索引結(jié)構(gòu)，其具體的實(shí)現(xiàn)方式依賴于不同的數(shù)據(jù)庫。一般來講，哈希索引表的結(jié)構(gòu)如圖所示：
我們知道HashMap<K,V>，可以通過K來獲取V,對(duì)于以上的哈希索引來說，PrimaryKey就是我們要取得的V值。比如（PK=key mod 2）叫做散列函數(shù)或者哈希函數(shù)，那么PK的區(qū)間范圍，我們稱其為散列地址。存儲(chǔ)的時(shí)候通過散列函數(shù)算出散列地址，然后把value的值存入，查找的時(shí)候通過散列函數(shù)算出散列地址，然后讀出數(shù)據(jù)。
3.不同存儲(chǔ)引擎的數(shù)據(jù)檢索
3.1 B-Tree&B+Tree
對(duì)于基于二叉樹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之上形成的樹的存儲(chǔ)結(jié)構(gòu)，那么其查詢數(shù)據(jù)最核心的算法就是二分法查找算法，即通過鍵值的比較排除一定比例的可能性，從而縮小數(shù)據(jù)查找的范圍，最終通過幾次比較定位到要查找的數(shù)據(jù)。直觀表現(xiàn)期間，我們還是以圖為例：
按照?qǐng)D示，我們查找的數(shù)據(jù)是L，
首先，將根節(jié)點(diǎn)的數(shù)據(jù)塊從磁盤讀入內(nèi)存，讀出P值，比較發(fā)現(xiàn)小于P；
接著，遍歷根節(jié)點(diǎn)左指針指向數(shù)據(jù)塊，讀出C、F、J、M值，順序比較后，找到J&M之間的指針；
最后，遍歷指針指向數(shù)據(jù)塊，讀出K、L值，定位所查詢的數(shù)據(jù)L。
根據(jù)以上算法，那么本次查找經(jīng)歷了三次磁盤的讀取，三次內(nèi)存數(shù)據(jù)的比較。由此看見，B樹檢索的時(shí)間復(fù)雜度主要取決于樹的深度以及節(jié)點(diǎn)內(nèi)保存的數(shù)據(jù)數(shù)量的多少。
對(duì)于B+樹的檢索，其實(shí)算法與B樹非常類似，其主要區(qū)別在于B+樹的所有檢索操作都不會(huì)在非葉子節(jié)點(diǎn)結(jié)束，每一個(gè)檢索都會(huì)經(jīng)歷相同的長度，那就是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，途中經(jīng)歷的非葉子節(jié)點(diǎn)只保留索引信息，只有葉子節(jié)點(diǎn)才會(huì)保留所有鍵值數(shù)據(jù)。這種算法把所有遍歷的復(fù)雜度留在了葉子節(jié)點(diǎn)的掃描上，減少了檢索途中的IO次數(shù)，保證了葉子節(jié)點(diǎn)掃描的局部優(yōu)勢(shì)，同時(shí)也保障了所有檢索操作的時(shí)間復(fù)雜度相對(duì)的穩(wěn)定性。因此大部分關(guān)系型數(shù)據(jù)庫選擇的是B+樹作為其存儲(chǔ)引擎。
3.2 Hash
對(duì)于Hash存儲(chǔ)引擎的數(shù)據(jù)檢索，我們首先要聊到它的增、刪、改操作。
數(shù)據(jù)文件分活躍狀態(tài)和陳舊狀態(tài)兩種。
數(shù)據(jù)的增加操作，用戶寫入的記錄直接追加到活動(dòng)文件，因此活動(dòng)文件會(huì)越來越大，當(dāng)?shù)竭_(dá)一定大小時(shí)，活躍的數(shù)據(jù)文件會(huì)被凍結(jié)。引擎重新建立一個(gè)活躍文件用于寫入，而之前的活躍文件則變?yōu)殛惻f的數(shù)據(jù)文件。寫入記錄的同時(shí)還要在索引哈希表中添加索引記錄。
數(shù)據(jù)的刪除操作，用戶不直接刪除記錄，而是新增一條相同Key的記錄，把Value值設(shè)置一個(gè)刪除的標(biāo)記。原有記錄依然存在于數(shù)據(jù)文件中，然后更新索引哈希表。這樣的話，在處理檢索操作的時(shí)候，用戶就會(huì)最先讀到哈希索引表里面的空值記錄，原有記錄后續(xù)處理。
數(shù)據(jù)的更新操作，不支持隨機(jī)寫入。對(duì)于存儲(chǔ)系統(tǒng)的基本功能中更新，實(shí)際上和增加數(shù)據(jù)操作都是一樣的，都是直接寫入活動(dòng)數(shù)據(jù)文件。同時(shí)修改索引哈希表中對(duì)應(yīng)記錄的值。這個(gè)時(shí)候，實(shí)際上數(shù)據(jù)文件中同一個(gè)Key值對(duì)應(yīng)了多條記錄，根據(jù)時(shí)間戳記錄來判斷，以最新的數(shù)據(jù)為準(zhǔn)。
數(shù)據(jù)的讀取操作，讀取時(shí)，首先從索引哈希表中定位到記錄在數(shù)據(jù)文件中的具體位置，然后通過讀取出對(duì)應(yīng)的記錄。當(dāng)然在讀取索引表的時(shí)候，索引的結(jié)構(gòu)有可能是索引樹結(jié)構(gòu)，在檢索索引的過程當(dāng)中會(huì)有一定的復(fù)雜度，具體根據(jù)樹的深度來判斷檢索的復(fù)雜度。
4.不同存儲(chǔ)引擎技術(shù)的選擇設(shè)計(jì)
4.1 B&B+樹的優(yōu)劣勢(shì)分析
首先，通過對(duì)B樹和B+樹的檢索算法特點(diǎn)來看，從使用的角度上來說，B樹索引存儲(chǔ)結(jié)構(gòu)多用于OLTP型的數(shù)據(jù)庫，因?yàn)檫@類數(shù)據(jù)庫主要以事務(wù)，或是行級(jí)別的讀取和存儲(chǔ)為主的（比如MYSQL）。換言之，這種類型的數(shù)據(jù)庫更多的操作是小批量或單行級(jí)別的隨機(jī)讀取和更新，并且還有事務(wù)方面的需求。在此前提條件之下，之所以有B+樹的誕生，取決于以下兩點(diǎn)：a.磁盤讀寫代價(jià)更低。B樹的內(nèi)部結(jié)點(diǎn)并無指向關(guān)鍵字具體信息的指針。所以其內(nèi)部結(jié)點(diǎn)相對(duì)B樹更小。若是把全部同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多。一次性讀入內(nèi)存中的須要查找的關(guān)鍵字也就越多。相對(duì)來講IO讀寫次數(shù)也就下降了。b.B+樹只要遍歷葉子節(jié)點(diǎn)就能夠?qū)崿F(xiàn)整棵樹的遍歷。并且在數(shù)據(jù)庫中基于范圍的查詢是很是頻繁的，而B樹實(shí)現(xiàn)這樣的操作需要的代價(jià)非常高，效率非常低。
其次，通過對(duì)B樹和B+樹的更新和刪除算法特點(diǎn)來看，雖然算法相對(duì)哈希及其他存儲(chǔ)引擎實(shí)現(xiàn)的算法來講會(huì)顯得非常復(fù)雜，代價(jià)很高。但是從另外一個(gè)側(cè)面來看，正是由于它沒有通過大量的數(shù)據(jù)追加實(shí)現(xiàn)更新和刪除，它就無需去管理那些不同時(shí)間戳版本的重復(fù)數(shù)據(jù)。有效地利用了磁盤空間和內(nèi)存空間，這個(gè)也與我們OLTP型關(guān)系型數(shù)據(jù)庫的規(guī)模以及通用服務(wù)器硬件的配置非常匹配。
4.2 Hash的優(yōu)劣勢(shì)分析
首先，從數(shù)據(jù)結(jié)構(gòu)特點(diǎn)來看。我們?cè)谇斑吿岬搅怂臄?shù)據(jù)結(jié)構(gòu)以及索引表的結(jié)構(gòu)，我們發(fā)現(xiàn)最大的特點(diǎn)就是在于所有的這些數(shù)據(jù)結(jié)構(gòu)都是以模式為基礎(chǔ)的。所以基于這一點(diǎn)來看，它本身更適合能以鍵值對(duì)的模式表示的數(shù)據(jù)存儲(chǔ)，無論是固定的鍵值，還是變動(dòng)的鍵值。其次，我們來分析哈希存儲(chǔ)引擎索引表檢索算法的特點(diǎn)。如果沖突處理的算法的當(dāng)，它大概率可以通過一次哈希函數(shù)就可以定位到數(shù)據(jù)的基本位置，與B-Tree存儲(chǔ)引擎相比較而言，它少了樹根、樹枝、樹葉節(jié)點(diǎn)的遍歷和多次的讀取操作。從哈希存儲(chǔ)引擎添加、刪除、更新數(shù)據(jù)的算法特點(diǎn)來看，基于除了檢索之外所有的數(shù)據(jù)操作都是通過添加新數(shù)據(jù)來變相實(shí)現(xiàn)。同樣與B-Tree存儲(chǔ)引擎相比較而言，添加一條新的紀(jì)錄遠(yuǎn)比檢索、加鎖、修改、放鎖這個(gè)過程要效率很多。從這個(gè)意義上來講，如果我們能把這些符合鍵值對(duì)要求的索引表數(shù)據(jù)全部引入到內(nèi)存，那么對(duì)于隨機(jī)讀取的并發(fā)能力提升無疑是巨大的質(zhì)變，這也是它能被Redis、Memcache這類內(nèi)存數(shù)據(jù)庫選中的重要原因。最后，所以對(duì)于事務(wù)性要求不是非常強(qiáng)，并且包含大量寫入及更新的數(shù)據(jù)場(chǎng)景就比較有優(yōu)勢(shì)了。
矛盾總是貫穿于事物的發(fā)展過程當(dāng)中，有利就有弊。對(duì)于哈希存儲(chǔ)引擎也是如此，正是因?yàn)樗膬?yōu)勢(shì)而導(dǎo)致了一些不可避免的劣勢(shì)。首先、由于哈希存儲(chǔ)引擎的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，那么對(duì)于一些數(shù)據(jù)內(nèi)部字段之間以及數(shù)據(jù)本身有著相對(duì)復(fù)雜的關(guān)系的數(shù)據(jù)，比如二維表數(shù)據(jù)。哈希存儲(chǔ)引擎就會(huì)束手無策。其次，由于哈希存儲(chǔ)引擎的檢索算法是基于哈希索引表的哈希函數(shù)計(jì)算實(shí)現(xiàn)，那么它就只能實(shí)現(xiàn)一次比較孤立的數(shù)據(jù)定位，對(duì)于范圍的查詢以及檢索過程當(dāng)中的一些排序、分組、過濾等操作就力不從心了。最后，還是從其數(shù)據(jù)增加、刪除、更新的算法來看。它是犧牲了大量的存儲(chǔ)空間來實(shí)現(xiàn)操作的高效性，那么后續(xù)必然會(huì)帶來空間的管理代價(jià)以及數(shù)據(jù)的合并處理代價(jià)，數(shù)據(jù)片越大、哈希樹的高度越高，那么數(shù)據(jù)檢索的效率相應(yīng)會(huì)提高很多，因?yàn)楣：瘮?shù)定位之后必然隨之而來的是對(duì)定位到的數(shù)據(jù)片的全部掃描，數(shù)據(jù)片越大，檢索的平均效率越差。同時(shí)后臺(tái)執(zhí)行的數(shù)據(jù)片合并的時(shí)間越長。因此對(duì)于數(shù)據(jù)粒度比較大，又沒有一個(gè)好的哈希函數(shù)可以使用的場(chǎng)景，也不是哈希存儲(chǔ)引擎使用的最佳場(chǎng)景。
5.總結(jié)與展望
無論是樹還是哈希存儲(chǔ)引擎，它們都是數(shù)據(jù)存取技術(shù)的設(shè)計(jì)思想，很多關(guān)系型數(shù)據(jù)庫大多基于B-Tree家族實(shí)現(xiàn)的，而很多分布式NoSQL數(shù)據(jù)庫都是基于Hash家族實(shí)現(xiàn)的，在每一種產(chǎn)品具體實(shí)現(xiàn)的過程中可能會(huì)改進(jìn)其中的一些算法細(xì)節(jié)從而實(shí)現(xiàn)部分缺陷的優(yōu)化，尤其是一些開源的數(shù)據(jù)庫。但是這種存儲(chǔ)引擎的基本思想是決定具體數(shù)據(jù)庫產(chǎn)品的適用場(chǎng)景的最根本原因，本文希望通過這些原理性的討論和分析展示給大家有一個(gè)宏觀的視圖，從而指導(dǎo)具體的數(shù)據(jù)庫設(shè)計(jì)實(shí)踐。當(dāng)然也希望更多同業(yè)能從更多維度繼續(xù)分析討論并分享。
