翻譯《Designing Data-Intensive Applications》
作者：Martin Kleppmann
譯者：雨釣（有增改）
B-Tree
目前我們所討論的日志結(jié)構(gòu)的索引已經(jīng)被廣泛認(rèn)可，但是他們卻不是最普遍的索引類型。被用于構(gòu)建索引的最普遍的數(shù)據(jù)結(jié)構(gòu)于此有很大的不同，我們稱之為：B-Tree
在1970年引入，不到10年之后，已經(jīng)發(fā)展到“無所不在”，B-trees經(jīng)受住了時(shí)間的考驗(yàn)。 它們?nèi)匀皇菐缀跛嘘P(guān)系數(shù)據(jù)庫中的標(biāo)準(zhǔn)索引實(shí)現(xiàn)，而且許多非關(guān)系數(shù)據(jù)庫也使用它們。
與SSTables類似，B-Tree將鍵值對(duì)按鍵排序，以便允許高效的鍵值查找和范圍查詢，但二者僅有這一點(diǎn)相似之處，因?yàn)锽-Tree有非常不同的設(shè)計(jì)理念。
我們之前看到的日志結(jié)構(gòu)索引將數(shù)據(jù)庫分解為可變大小的 segments，通常是幾兆字節(jié)或更大的大小，并且總是按順序?qū)憽?與此相反，B-Tree將數(shù)據(jù)庫分解成固定大小的塊或頁面，傳統(tǒng)上是4 KB大小(有時(shí)更大)，并同時(shí)讀取或?qū)懸豁摗?這個(gè)設(shè)計(jì)更接近符合（corresponds ）底層硬件，因?yàn)榇疟P存儲(chǔ)也是采用類似的設(shè)計(jì)，數(shù)據(jù)被安排在固定大小的塊中。
B-Tree中每個(gè)頁面都可以使用一個(gè)地址或位置來標(biāo)識(shí)，這允許一個(gè)頁面轉(zhuǎn)到另一個(gè)頁面（類似于一個(gè)指針），注意這是在磁盤上而不是在內(nèi)存中。 我們可以使用這些頁面引用來構(gòu)建頁面樹，如所示。
一頁被指定為B-Tree的Root；每當(dāng)你想要查找索引中的key時(shí)，就從這里開始。這個(gè)也包含幾個(gè)key和一些指向其子節(jié)點(diǎn)頁的指針。 每個(gè)子元素負(fù)責(zé)一個(gè)連續(xù)的鍵范圍，引用之間的鍵表示這些范圍之間的界限在哪里。
在圖3-6的示例中，我們正在尋找key=251，因此我們知道我們需要遵循在邊界200和300之間的頁面引用。 這就把我們進(jìn)一步引入200-300范圍分解的子范圍。
最終，我們會(huì)找到一個(gè)包含單個(gè)key(葉子頁)的頁面，其中包含每個(gè)key的值，或者包含指向該值的頁面的引用。
在B-Tree的一頁中對(duì)子頁面的引用數(shù)量稱為分支因子（branching factor）。例如，在圖3-6中，分支因子為6。在實(shí)踐中，分支因素取決于存儲(chǔ)頁面所需的空間數(shù)量和范圍邊界，但通常是幾百個(gè)
如果您想要更新B-tree中的現(xiàn)有key的值，則需要搜索包含該key的頁，更改該頁面中的值，并將該頁面寫回磁盤(任何對(duì)該頁面的引用仍然有效)， 如果您想添加一個(gè)新key，您需要找到其范圍包含新key的頁面并將其添加到該頁面中。 如果頁面中沒有足夠的空閑空間來容納新key，那么它切分成兩個(gè)完整的頁面，而父頁面將被更新，如圖3-7（ 將一個(gè)新key插入到B-Tree中是相當(dāng)直觀的，但是刪除一個(gè)key(同時(shí)保持樹的平衡)會(huì)更復(fù)雜一些[2]）。
[圖片上傳失敗...(image-bd0a82-1550122280516)]
這個(gè)算法保證了樹的平衡:一個(gè)b -樹，n個(gè)鍵，alwayshas a depth of O(log n)，大多數(shù)數(shù)據(jù)庫都能適應(yīng)B-tree，它有3到4個(gè)級(jí)別，所以你不需要遵循很多頁面引用來找到你要查找的頁面。(4kb頁的四層樹，其分支系數(shù)為500，可存儲(chǔ)到256 TB(即500^4*4k)。)
Making B-trees reliable
B-Tree底層基本的寫操作是用新的頁面數(shù)據(jù)覆蓋磁盤上的一個(gè)頁面，我們先假定覆蓋寫操作不會(huì)改變頁面的位置，例如; 當(dāng)頁面被覆蓋時(shí)，所有對(duì)該頁面的引用都保持不變。 這與lsm -tree這樣的日志結(jié)構(gòu)索引形成了鮮明的對(duì)比：這些索引只會(huì)附加到文件(最終會(huì)刪除過時(shí)的文件)，但永遠(yuǎn)不會(huì)修改文件。
您可以考慮將磁盤上的頁面重寫看做為實(shí)際的硬件操作。 在磁盤上，這意味著把磁盤頭移到正確的位置，然后用新的數(shù)據(jù)覆蓋適當(dāng)?shù)纳葏^(qū)。 在SSD上，由于SSD必須在一段時(shí)間內(nèi)清除和重寫相當(dāng)大的一段晶體管芯片[19]，所以會(huì)發(fā)生一些更復(fù)雜的情況。
此外，有些操作需要覆蓋多個(gè)不同的頁面。 例如，因?yàn)椴迦胨膬?nèi)容過多導(dǎo)致需要分割一個(gè)頁面 ，那么您需要將兩個(gè)頁面分開，并覆蓋它們的父頁面，同時(shí)更新兩個(gè)子頁面的內(nèi)容。 這是一個(gè)危險(xiǎn)的操作，因?yàn)槿绻麛?shù)據(jù)在僅僅一些頁面被寫入后崩潰了，那么您最終會(huì)得到一個(gè)cor - rupted索引(例如，可能會(huì)有一個(gè)孤兒頁面，而不屬于任何父頁面)。
為了使數(shù)據(jù)庫恢復(fù)到崩潰的狀態(tài)，B-tree的實(shí)現(xiàn)通常包括在磁盤上添加一個(gè)額外的數(shù)據(jù)結(jié)構(gòu):write-ahead log(WAL, also known as a redo log)。 這是一個(gè)附加(append-only)的文件，在更改被應(yīng)用到樹本身的頁面之前，每一個(gè)B-tree修改都必須被寫入到該文件。 當(dāng)數(shù)據(jù)庫在崩潰恢復(fù)時(shí)，這個(gè)日志被用來恢復(fù)B-tree，并將數(shù)據(jù)返回到一個(gè)一致的狀態(tài)[5,20]。
更新頁面的另一個(gè)復(fù)雜之處是，如果多個(gè)線程在同一時(shí)間訪問B-tree，則需要進(jìn)行嚴(yán)密的并發(fā)控制，否則線程可能會(huì)在不一致的狀態(tài)下看到B-tree中的數(shù)據(jù)。 這通常是通過使用鎖 (輕量級(jí)鎖)來保護(hù)樹的數(shù)據(jù)結(jié)構(gòu)的。 在這方面，日志結(jié)構(gòu)的方法比較簡(jiǎn)單，因?yàn)樗鼈冊(cè)诤笈_(tái)進(jìn)行所有合并，而不會(huì)干擾正常的查詢，并且不時(shí)地將新segments與老的segments進(jìn)行原子操作的交換。
B-tree optimizations
由于B-tree已經(jīng)存在了很長時(shí)間，所以許多優(yōu)化技術(shù)在過去的幾年里發(fā)展起來也就不足為奇了。僅舉幾個(gè)例子:
有些數(shù)據(jù)庫(如LMDB)使用了一個(gè)復(fù)制-寫的方案[21]，而不是覆蓋頁面并維護(hù)一個(gè)用于崩潰恢復(fù)的WAL。 一個(gè)修改后的頁面被寫入到一個(gè)不同的位置，并且在樹中創(chuàng)建了一個(gè)新版本的父頁面，指向新的位置。這種方式對(duì)并發(fā)也是有用的
我們可以通過不存儲(chǔ)整個(gè)key來節(jié)省頁面空間，但可以縮寫它。 特別是在樹的內(nèi)部頁面，key只需要提供足夠的信息作為key范圍之間的邊界。將更多的key放入一個(gè)頁面中，可以使樹具有更高的分支系數(shù)，從而使級(jí)別更低（ 這種變體有時(shí)被稱為B+樹，盡管這種優(yōu)化很常見，但它通常與其他B-tree變體沒有區(qū)別。）。
一般來說，頁面可以放置在磁盤的任何位置；key值的范圍相近，并不要求page在磁盤上的位置也要相鄰。 如果一個(gè)查詢需要掃描按順序排列的key范圍內(nèi)的部分，那么頁面逐頁布局就可能是不高效的，因?yàn)槊總€(gè)讀到的頁面都可能需要一個(gè)磁盤查找。 因此，許多B-tree實(shí)現(xiàn)都試圖對(duì)樹進(jìn)行布局優(yōu)化，以便頁面在磁盤上按順序存儲(chǔ)。 然而，當(dāng)樹生長時(shí)，很難維持這種順序。 相比之下，由于lsm -樹在一個(gè)合并過程中重寫了大量segments存儲(chǔ)，因此它們更容易在磁盤上保持?jǐn)?shù)據(jù)按key連續(xù)。
額外的指針被添加到樹中。例如，每個(gè)leaf頁面都可以引用其位于左和右的同級(jí)頁面（sibling pages），這樣可以在不跳轉(zhuǎn)回父頁面的情況下按順序?qū)ζ溥M(jìn)行掃描。
像分形樹這樣的B-tree變體[22]借用了一些邏輯結(jié)構(gòu)的想法來幫助磁盤尋找(它們與分形無關(guān))。
Comparing B-Trees and LSM-Trees
盡管B-Tree實(shí)現(xiàn)通常比LSM-Tree實(shí)現(xiàn)更成熟，但LSM樹的特性也很有用。根據(jù)經(jīng)驗(yàn)LSM-Tree通常對(duì)寫操作支持更友好，寫操作更快，而B-Trees被認(rèn)為讀起來更快[23]，在LSM-Trees上讀取通常要慢一些，因?yàn)樗鼈儽仨殭z查不同的壓縮階段的數(shù)據(jù)結(jié)構(gòu)和SSTables。
但是，基準(zhǔn)測(cè)試通常對(duì)工作負(fù)載的細(xì)節(jié)并不十分不確定。你需要使用你的特定工作負(fù)載來測(cè)試系統(tǒng)，以便獲得更為準(zhǔn)確的測(cè)試結(jié)論。 在本節(jié)中，我們將簡(jiǎn)要討論一些在度量存儲(chǔ)引擎性能時(shí)值得考慮的事情。
Advantages of LSM-trees
B-Tree索引至少需要寫兩次數(shù)據(jù)：一次是寫日志（write-ahead log），一次是樹頁面本身(可能是頁面分割后)。 同時(shí)即使頁面中只有幾個(gè)字節(jié)發(fā)生了變化也需要對(duì)整個(gè)頁面進(jìn)行重寫。 有些存儲(chǔ)引擎甚至?xí)谙嗤捻撁嫔现貙憙纱危员苊庠诔霈F(xiàn)電源故障時(shí)出現(xiàn)部分更新的頁面[24,25].。
由于重復(fù)的壓縮和SSTables的合并，日志結(jié)構(gòu)的索引也需要多次重寫數(shù)據(jù)。 這個(gè)中多次寫入數(shù)據(jù)庫，導(dǎo)致在數(shù)據(jù)庫的生命周期中對(duì)磁盤進(jìn)行多寫操作—稱為write amplification。 當(dāng)使用ssd時(shí)就需要特別注意，SSD是有寫入次數(shù)的，所以在使用SSD時(shí)只能覆寫固定的塊，即這些塊的寫入次數(shù)還沒有被耗盡。
在哪些需要對(duì)數(shù)據(jù)庫進(jìn)行大量寫操作的應(yīng)用程序中，性能瓶頸可能是數(shù)據(jù)庫寫入磁盤的速率。 在這種情況下，write amplification有一個(gè)直接的效率成本：在可用的磁盤帶寬內(nèi)，一個(gè)存儲(chǔ)引擎寫入磁盤的次數(shù)越多，每分鐘內(nèi)處理寫入的將越少 。
此外，LSM-Tree通常能夠比B-Tree保持更高的寫吞吐量，一部分原因是它們有時(shí)具有更低的寫擴(kuò)增(盡管這取決于存儲(chǔ)引擎的配置和工作負(fù)載)，另一部分原因是它們可以順序地寫SSTable文件，而不是在樹中重寫幾個(gè)頁面[26]。 這種差異在磁盤上尤其重要，因?yàn)樵诖疟P上，順序?qū)懭氡入S機(jī)寫入要快得多。
LSM-Tree可以被更好地壓縮，因此他們?cè)诖疟P上生成的文件通常要比B-Tree生成的文件更小。B-tree存儲(chǔ)引擎會(huì)存在磁盤碎片化的問題；當(dāng)一個(gè)頁面被分割，或者當(dāng)一個(gè)行不能存儲(chǔ)在現(xiàn)有的頁面時(shí)，頁面中的一些空間就無法被使用，一致處于空余狀態(tài)。 由于LSM-Tree不是面向頁的，并且周期性地重寫SSTables以清除碎片，所以在使用分層壓縮[27]時(shí)，它們的存儲(chǔ)開銷更低。
在許多SSD中，固件內(nèi)部使用一種日志結(jié)構(gòu)算法來將隨機(jī)寫轉(zhuǎn)化為順序?qū)?，因此存?chǔ)引擎寫入模式對(duì)此影響不那么顯著[19] 。但是，較低的write amplification和較少存儲(chǔ)碎片對(duì)SSD仍然是有利：數(shù)據(jù)的存儲(chǔ)更加緊湊，在可用的I/O 帶寬中可以滿足更多的讀寫請(qǐng)求。
Downsides Of LSM-trees
日志結(jié)構(gòu)存儲(chǔ)的缺點(diǎn)是壓縮過程有時(shí)會(huì)影響（interfere with）正在進(jìn)行的讀和寫的性能。 即使存儲(chǔ)引擎試圖逐步執(zhí)行壓縮操作以便盡量不影響并發(fā)訪問。但是，畢竟磁盤資源有限，仍然很容易發(fā)生這樣的情況：當(dāng)磁盤完成一個(gè)昂貴的壓縮操作時(shí)，請(qǐng)求（讀請(qǐng)求和寫請(qǐng)求）操作需要等待。在進(jìn)行延遲監(jiān)控時(shí)，這種情況雖然對(duì)吞吐量和平均響應(yīng)時(shí)間的影響通常很小，但在較高的占位百分比數(shù)值中，日志結(jié)構(gòu)存儲(chǔ)引擎的查詢響應(yīng)時(shí)間有時(shí)相當(dāng)高，而B-Tree相對(duì)而言則可以更容易預(yù)測(cè)和監(jiān)測(cè)[28]
壓縮的另一個(gè)問題是高寫吞吐量：有限的磁盤寫入帶寬需要在初始寫入(日志數(shù)據(jù)寫入數(shù)據(jù)庫和刷新memtable到磁盤)和后臺(tái)運(yùn)行的壓縮線程之間共享。 當(dāng)寫入一個(gè)空數(shù)據(jù)庫時(shí)，可以使用整個(gè)磁盤帶寬來進(jìn)行初始寫入，但是數(shù)據(jù)庫中數(shù)據(jù)量越大，壓縮所需的磁盤帶寬就越多。如果寫吞吐量高，而壓縮進(jìn)程沒有經(jīng)過優(yōu)化配置，則會(huì)發(fā)生壓縮無法跟上寫入速度的情況。 在這種情況下，磁盤上未合并的segment的數(shù)量一直在增長，直到耗盡磁盤空間，并且讀取速度也會(huì)減慢，因?yàn)樗鼈冃枰獧z查更多的segment文件。 通常，即使后臺(tái)運(yùn)行的壓縮進(jìn)程不能保持較高的壓縮效率，基于SSTable的存儲(chǔ)引擎也不會(huì)限制數(shù)據(jù)寫入的速度，因此需要提供額外的監(jiān)視來檢測(cè)這種情況[29,30]。
B-Tree的一個(gè)優(yōu)點(diǎn)是，每個(gè)key在索引中只存儲(chǔ)在一個(gè)位置，而一個(gè)日志結(jié)構(gòu)的存儲(chǔ)引擎可能有多個(gè)相同的key且這些key在不同的segment中。B-Tree數(shù)據(jù)庫希望提供強(qiáng)大的事務(wù)語義，這就使得它很具有吸引力：在許多關(guān)系數(shù)據(jù)庫中，事務(wù)隔離是在key的范圍內(nèi)使用鎖實(shí)現(xiàn)的，在B-Tree索引中，這些鎖掃描直接連接到樹[5]。在第七章，我們將更詳細(xì)地討論這一點(diǎn)。
B-Tree在數(shù)據(jù)庫體系結(jié)構(gòu)中是根深蒂固的，并且在許多工作負(fù)載中提供良好的一致性，所以它們不可能短時(shí)間內(nèi)消失掉。 在新的數(shù)據(jù)存儲(chǔ)中，日志結(jié)構(gòu)的索引變得越來越流行。并沒有任何快速簡(jiǎn)單的規(guī)則來確定哪種類型的存儲(chǔ)引擎對(duì)您的用例更好，這需要憑借自身經(jīng)驗(yàn)和對(duì)自身業(yè)務(wù)的認(rèn)知進(jìn)行測(cè)試。
未完待續(xù)。。。。
