隨著應用程序處理的數據量不斷增長，擴展存儲變得愈發具有挑戰性。每個數據庫系統都有自己的方案。為了從這些方案中做出正確的選擇，了解它們是至關重要的。

[[279239]]

每個應用程序在讀寫負載平衡、一致性、延遲和訪問模式方面各不相同。熟悉數據庫和底層存儲能幫助你進行架構決策、解釋系統行為、排除故障以及根據具體情況調優。

優化一個系統不可能做到面面俱到。我們當然希望有一個數據結構既能保證最佳的讀寫性能，又不需要任何存儲開銷，但顯然，這是不存在的。

本文深入討論了大多數現代數據庫中使用的兩種存儲系統設計 —— 讀優化 B-Tree [1] 和寫優化 LSM(log-structured merge)-Tree [5] —— 并描述了它們的用例和優缺權衡。

B-Tree

B-Tree 是一種流行的讀優化索引數據結構，是二叉樹的泛化。它有許多變種，并且被用于多種數據庫(包括 MySQL InnoDB [4]、PostgreSQL [7])甚至文件系統(HFS+ [8]、HTrees ext4 [9])。B-Tree 中的 B 代表原始數據結構的作者 Bayer，或是他當時就職的公司 Boeing。

在搜索二叉樹中，每個節點都有兩個孩子(稱為左右孩子)。左子樹的節點值小于當前節點值，右子樹反之。為了保持樹的深度最小，搜索二叉樹必須是平衡的：當隨機順序的值被添加到樹中時，如果不加調整，終會導致樹的傾斜。

一種平衡二叉樹的方法是所謂的旋轉：重新排列節點，將較深子樹的父節點向下推到其子節點下方，并將該子節點拉上來，將其放在原父節點的位置。圖 1 是平衡二叉樹中的旋轉示例。在左側添加節點 2 后，二叉樹失去平衡。為了使該樹平衡，將其以節點 3 為軸旋轉(樹圍繞它旋轉)。然后節點 5(旋轉前是根節點和節點 3 的父節點)成為其子節點。旋轉完成后，左側子樹的深度減少 1，右側子樹的深度增加 1。樹的最大深度已經減小。 

二叉樹是最有用的內存數據結構。然而由于平衡(保持所有子樹的深度最小)和低出度(每個節點最多兩個子節點)，它們在磁盤上水土不服。B-Tree 允許每個節點存儲兩個以上的指針，并通過將節點大小與頁面大小(例如，4 KB)進行匹配來與塊設備協同工作。今天的一些實現將使用更大的節點大小，跨越多個頁面。

B-Tree 有以下幾個性質：

• 有序。這允許順序掃描并簡化查找。
• 自平衡。在插入和刪除時不需要平衡樹：當 B-Tree 節點已滿時，它被分成兩部分，并且當相鄰節點的利用率低于某個閾值時，合并這兩個節點。這也意味著各葉子節點與根節點的距離相等，并且在查找過程中定位的步數是相同的。
• 對數級查找時間復雜度。查找時間是非常重要的，這使得 B-Tree 成為數據庫索引的理想選擇。
• 易變。插入、更新、刪除(包括因此導致的拆分和合并)過程在磁盤上進行。為了使就地更新成為可能，需要一定的空間開銷。B-Tree 可以作為聚集索引，實際數據存儲在葉子節點上，也可以作為非聚集索引，稱為一個堆文件。

本文討論的 B+Tree [3] 是一種經常用于數據庫存儲的 B-Tree 現代變種。B+Tree 與原始 B-Tree [1] 的不同之處在于：(1)它采用額外鏈接的葉節點存儲值;(2)值不能存儲在內部節點上。

剖析 B-Tree

我們先來仔細看看 B-Tree 的結構，如圖 2 所示。B-Tree 的節點有幾種類型：根節點，內部節點和葉子節點。根節點(頂部)是沒有雙親的節點(即，它不是任何節點的子節點)。內部節點(中間)有雙親和孩子節點;他們將根節點和葉子節點連接起來。葉子節點(底部)持有數據并且沒有孩子節點。圖 2 描繪了分支因子為 4(4 個指針，內部節點中有 3 個鍵，葉上有 4 個鍵/值對)的 B-Tree。 

B-Tree 的特性如下：

• 分支因子 —— 指向子節點的指針數(N)。除指針外，根節點和內部節點還持有 N-1 個鍵。
• 利用率 —— 節點當前持有的指向子節點的指針數量與可用最大值之比。例如，若某樹分支因子是 N，且其中某節點當前持有 N/2 個指針，則該節點利用率為 50%。
• 高度 —— B-Tree 的數量級，表示在查找過程中必須經過多少指針。

樹中的每個非葉節點最多可持有 N 個鍵(索引條目)，這些鍵將樹分為 N+1 個子樹，這些子樹可以通過相應的指針定位。項 Ki 中的指針 i 指向某子樹，該子樹中包含所有 Ki-1 <= K目標 < Ki(其中 K 是一組鍵)的索引項。首尾指針是特殊的，它們指向的子樹中所有的項都小于等于最左子節點的 K0 或大于最右子節點的 KN-1。葉子節點同時持有其同級前后節點的指針，形成兄弟節點間的雙向鏈表。所有節點中的鍵總是有序的。

查找

進行查找時，將從根節點開始搜索，并經過內部節點遞歸向下到葉子節點層。在每層中，通過指向子節點的指針將搜索范圍縮小到某子樹(包含搜索目標值的子樹)。圖 3 展示了 B-Tree 的一次從根到葉的搜索過程，指針在兩個鍵之間，其中一個大于(或等于)搜索目標，另一個小于搜索目標。進行點查詢時，搜索將在定位到葉子節點后完成。進行范圍掃描時，遍歷所找到的葉子節點的鍵和值，然后遍歷范圍內的兄弟葉子節點。 

在復雜度方面，B-Tree 保證查詢的時間復雜度為 log(n)，因為查找一個節點中的鍵使用二分查找，如圖 4 所示。二進制搜索可以通俗的解釋為在字典中查找以某字母開頭的單詞，字典中所有單詞都按字母順序排序。首先你翻開正好在字典中間的一頁。如果要查找的單詞字母順序小于(在前面)當前頁，你繼續在字典的左半邊查找;否則就繼續在右半邊查找。你繼續像這樣將剩余的頁碼范圍分為一半，選擇一邊，直到找到期望的字母。每一步都將搜索范圍減半，因此查找的時間復雜度為對數級。 B-Tree 節點上的鍵是有序的，且使用二分查找算法進行匹配，因此 B-Tree 的搜索復雜度是對數級的。這也說明了保持樹的高利用率和統一訪問的重要性。 

插入、更新、刪除

進行插入時，第一步是定位目標葉子節點。此過程使用前序搜索算法。在定位目標葉子節點后，鍵和值將被添加至該節點。如果該節點沒有足夠的可用空間，這種情況稱為溢出，則將葉子節點分割成兩部分。這是通過分配一個新的葉子節點，將一半元素移動到新節點并將一個指向這個新節點的指針添加到父節點來完成的。如果父節點沒有足夠的空間，則也會在父節點上進行分割。操作一直持續到根節點為止。當根節點溢出時，其內容在新分配的節點之間被分割，根節點本身被覆蓋以避免重定位。這也意味著樹(及其高度)總是通過分裂根節點而增長。

LSM-Tree

結構化日志合并樹是一個不可變的基于磁盤的寫優化數據結構。它適用于寫入比查詢操作更頻繁的場景。LSM-Tree 已經獲得了更多的關注，因為它可以避免隨機插入，更新和刪除。

剖析 LSM-Tree

為了允許連續寫入，LSM-Tree 在內存中的表(通常使用支持查找的時間復雜度為對數級的數據結構，例如二叉搜索樹或跳躍表)中批量寫入和更新，當其大小達到閾值時將它寫在磁盤上(這個操作稱為刷新)。檢索數據時需要搜索樹所有磁盤中的部分，檢查內存中的表，合并它們的內容，然后再返回結果。圖 5 展示了 LSM-Tree 的結構：用于寫入的基于內存的表。只要內存表體積達到一定程度，內存表就會被寫入磁盤。進行讀取時，同時讀取磁盤和內存表，通過一個合并操作來整合數據。 

有序串行表

因為 SSTable(有序串行表)的簡單性(易于寫入，搜索和讀取)與合并性能(合并期間，掃描源 SSTable，合并結果的寫入是順序的)，多數現代的 LSM-Tree 實現(例如 RocksDB 和 Apache Cassandra)都選用 SSTable 作為硬盤表。

SSTable 是一種基于硬盤的有序不可變的數據結構。從結構上來看，SSTable 可以分為兩部分：數據塊和索引塊，如圖 6 所示。數據塊包含以鍵為順序寫入的唯一鍵值對。索引塊包含映射到數據塊指針的鍵，指針指向實際記錄的位置。為了快速搜索，索引一般使用優化的結構實現，例如 B-Tree 或用于點查詢的哈希表。SSTable 中的每一個值都有一個時間戳與之對應。時間戳記錄了插入、更新(這兩者一般不做區分)和刪除時間。 

SSTable 具有以下優點：

• 通過查詢主鍵索引可以實現快速的點查詢(例如，通過鍵尋找值)。
• 只需要順序讀取數據塊上的鍵值對就可以實現掃描(例如，遍歷制定范圍內的鍵值對)。

SSTable 代表一段時間內所有數據庫操作的快照，因為 SSTable 是通過對內存表的刷新操作創建的，該表充當此時段內對數據庫狀態的緩沖區。

查詢

檢索數據需要搜索硬盤上的所有 SSTable，檢查內存表，并且合并它們的內容后返回結果。要搜索的數據可以存儲在多個 SSTable 中，因此合并步驟是必須的。

合并步驟也是確保刪除和更新正常工作所必需的。在 LSM-Tree 中，通過插入占位符(通常稱為墓碑)來指定哪個鍵被標記為刪除。同樣的，更新操作只是提交一個帶較晚時間戳的記錄。在讀取期間，被標記刪除的記錄被跳過，不會返回給客戶端。更新操作與之類似：在具有相同鍵的兩個記錄中，只返回具有較晚時間戳的記錄。圖 7 展示了一次合并操作，用于對在不同表中存儲的同一個鍵的數據進行整合：如圖，Alex 記錄中時間戳是 100，隨后更新了新的電話，時間戳為 200;John 記錄被刪除。另外兩項沒有改變，因為它們沒有被覆蓋。 

為了減少搜索 SSTable ，防止為了查找某個鍵而搜索每個 SSTable，許多存儲系統采用一個被稱為布隆過濾器 [10] 的數據結構。這是一個概率數據結構，可用于測試某個元素是否屬于某集合。它有可能產生錯誤的肯定(即，判斷元素是集合的成員，但實際上并不是)，但不能產生錯誤的否定(即，如果返回否定結果，則元素一定不是集合的成員)。換句話說，布隆過濾器用于判斷鍵“可能在 SSTable 中”或“絕對不在 SSTable 中”。在搜索過程中，將會跳過布隆過濾器返回否定結果的 SSTable。

LSM-Tree 的維護

由于 SSTable 是不可變的，因此它們會按順序寫入，并且不存在用于修改的預留空白空間。這就意味著插入、更新或刪除操作將需要重寫整個文件。所有修改數據庫狀態的操作都在內存表中“批處理”。隨著時間的推移，磁盤表的數量將增加(同一個鍵的數據位于幾個不同文件，同一記錄有多個不同的版本，被刪除的冗余記錄)，讀取操作的開銷將變得越來越大。

為了降低讀取開銷，整合被刪除記錄占用的空間并減少磁盤表的數量，LSM-Tree 需要一個壓縮操作，從磁盤讀取完整的 SSTable 并合并它們。由于 SSTable 是以鍵排序的，因此其壓縮工作和歸并排序類似，是非常高效的操作：從多個源有序序列中讀取記錄，進行合并后的輸出馬上追加到結果文件中，則結果文件也是有序的。歸并排序的一個優點是，即使合并內存吃不消的大文件，它依舊可以高效地工作。結果表保留了原始 SSTable 的順序。

在此過程中，被合并的 SSTable 被丟棄并替換為其“壓縮”后的版本，如圖 8 所示。壓縮多個 SSTable 并將它們合并為一個。某些數據庫系統在邏輯層面上按大小把不同的表分為不同級別，分組到相同的“級別”，并在特定級別的表足夠多時開始合并操作。壓縮后，SSTable 的數量減少，提高查詢效率。 

原子性與持久性

為了減少 I/O 操作并使它們順序執行，無論是 B-Tree 還是 LSM-Tree 都在實際更新之前，先在內存中進行批量操作。這意味著，在故障情況時，數據完整性、原子性(將一系列操作賦予原子性，將它們視為一個操作，要么全部執行要么全不執行)、持久性(當進程崩潰或電源失效時，可以確保數據已經到達持久性存儲設備)得不到保證。

為了解決這個問題，大多數現代存儲系統采用 WAL(預寫日志)。WAL 的核心思想是，所有數據庫狀態改變都先持久化進硬盤中的只追加日志中。如果進程在工作中崩潰，將會重映日志以確保沒有數據丟失且所有更改都滿足原子性。

在 B-Tree 中，使用 WAL 可以理解為僅在寫入操作被記錄后才將其寫入數據文件。通常，B-Tree 存儲系統的日志尺寸相對較小：只要將更改應用于持久存儲，它們就可以被棄用。WAL 還可以作為運行時操作的備份：任何未應用于數據頁的更改都可以根據日志記錄重做。

在 LSM-Tree 中，WAL 用于保存處于內存表但尚未完全刷新到磁盤上的更改。只要內存表被刷新完畢并置換，便可以在新創建的 SSTable 中進行讀取操作，則 WAL 中從內存表刷新到硬盤上的那部分更改就可以丟棄了。

總結

B-Tree 和 LSM-Tree 數據結構最大的差異之一是它們優化的目的以及優化的效果。

我們來對比一下 B-Tree 和 LSM-Tree 之間的特性。總的來說，B-Tree 具有以下特性：

• 它是可變的，它允許通過一些空間開銷和更多的寫入路徑來進行就地更新，因而它不需要文件重寫或多源合并。
• 它是讀優化的，這意味著它不需要從多個源數據中讀取(也不需要合并)，因而簡化了讀取路徑。
• 寫操作可能引起級聯節點分裂，這使得寫操作開銷較高。
• 它針對分頁環境(塊存儲)進行了優化，杜絕了字節定位操作。
• 碎片化, 由頻繁更新造成的碎片化可能需要額外的維護和塊重寫。然而對 B-Tree 的維護一般要比 LSM-Tree 要少。
• 并發訪問讀寫隔離，這涉及鎖存器與鎖鏈。

LSM-Tree 具有以下特性：

• 它是不可變的。SSTable 一旦被寫入硬盤就不會再改變。壓縮操作被用于整合占用空間，刪除條目，合并在不同數據文件中的同鍵數據。作為壓縮操作的一部分，在成功合并后，源 SSTable 將被棄用并刪除。這種不可變性給我們帶來了另一個有用的特性，刷新后的表可以被并發訪問。
• 它是寫優化的，這意味著寫入操作將進入緩沖，隨后順序刷新到硬盤上，可能支持基于硬盤的空間局部性。
• 讀取操作可能需要訪問多個數據源，因為在不同時間寫入的同一個鍵的數據有可能位于不同的數據文件中。必須經過合并過程才能將記錄返回給客戶端。
• 需要維護 / 壓縮，因為緩沖中的寫入操作被刷新到硬盤上。

評估存儲系統

開發存儲系統總要面對類似的挑戰，考慮類似的因素。決定優化方向會對結果產生很大影響。你可以在寫入過程中花費更多時間來布局結構以實現更高效的讀取，為就地更新預留空間，也可以緩沖數據確保順序寫入以提高寫入速度。但是，一次完成這一切是不可能的。理想中的存儲系統應該具有最低的讀取成本，最低的寫入成本，并且沒有額外開銷。但實際上，數據結構只能在多個因素之間權衡。理解這些取舍是重要的。

來自哈佛 DASlab(數據系統實驗室)的研究人員總結了數據庫系統優化方向的關鍵三點：讀取開銷、更新開銷和內存開銷(或簡稱為 RUM)。對于數據結構、訪問方法、甚至適用于某些工作負載的選擇應該了解哪些參數對你的用例最為重要，因為算法是針對特定用例量身定制的。

RUM 假說 [2] 為上述的兩種開銷設置了上限，同時為第三種設置了下限。例如，B-Tree 以提高寫入開銷、預留空間(同時也造成了內存開銷)為代價進行讀優化。LSM-Tree 以讀取時必須進行多硬盤表訪問的高讀取開銷換取低寫入開銷。在處于競爭三角形的三個參數中，一方面的改進可能就意味著另一方面的讓步。圖 9 對 RUM 假說進行了說明。 

B-Tree 優化讀取性能：索引的布局方式可以最小化遍歷樹的磁盤訪問需求。通過訪問一個索引文件就可以定位數據。這是通過持續更新索引文件來實現的，但這也增加了由于節點拆分和合并，重定位以及碎片、不平衡相關的維護造成的額外寫入開銷。為了平穩更新成本并減少分割次數，B-Tree 在所有級別的節點上都預留有額外的空間。這有助于在節點飽和之前延遲寫入開銷的增長。簡而言之，B-Tree 犧牲更新和內存性能以獲得更好的讀取性能。

LSM-Tree 優化寫入性能。無論是更新還是刪除都需要在磁盤上定位數據(B-Tree 也一樣)，并且它通過在內存表中緩存所有插入，更新和刪除操作來保證順序寫入。這是以較高的維護成本和壓縮需求(這是唯一的緩解不斷增長的讀取開銷和減少磁盤表的數量的方式)和更高的讀取成本(因為數據必須從多個源讀取并合并)為代價的。同時，LSM-Tree 通過不保留任何預留空間來減少內存開銷(不同于 B-Tree 節點，其平均利用率為 70%，包含就地更新所需的開銷)，因為更高的利用率和最終文件的不變性，LSM-Tree 支持塊壓縮。簡而言之，LSM-Tree 犧牲讀取性能，提高維護成本來獲得更好的寫入性能和更低的內存占用。

有的數據結構可針對每個期望的屬性進行優化。使用自適應數據結構可以以更高維護成本獲得更好的讀取性能。添加有助于遍歷的元數據(如分散層疊)將會影響寫入時間并占用更多空間，但可以提高讀取性能。使用壓縮優化內存使用率(例如，Gorilla 壓縮 [6] 、delta 編碼等諸多算法)會增加一些開銷，用于在寫入時壓縮數據并在讀取時解壓縮數據。有時候，你可以犧牲功能來提高效率。例如，堆文件和散列索引由于文件格式簡單，可以保證很好的性能和較小的空間開銷，而作為代價，它們不支持除點查詢以外的其他功能。你還可以通過使用近似數據結構(如布隆過濾器、HyperLogLog、Count-Min sketch 等)來為了空間與效率犧牲精度。

三種可變參數 —— 讀取，更新和內存開銷 —— 可以幫助你評估數據庫并深入了解最適合的工作負載。它們都非常直觀，將存儲系統按其分類很容易，猜測它是如何執行的，然后通過大量測試驗證你的假設。

當然，評估存儲系統時還有一些其他重要因素需要考慮，例如維護開銷，易用性，系統要求，頻繁增刪的適應性，訪問模式等。RUM 假說只是幫助發展直觀感覺并提供初始方向的一條經驗法則。了解你的工作部件是構建可擴展后端的第一步。

一些因素可能因實施而異，甚至兩個使用類似存儲設計原則的數據庫可能會有不同表現。數據庫是包含許多可插拔模塊的復雜系統，是許多應用程序的重要組成部分。這些信息將幫助你窺探數據庫的底層，并且了解底層數據結構和其內部行為之間的差異，從而決定哪個是最適合你的。