隨著應(yīng)用程序處理的數(shù)據(jù)量不斷增長，擴(kuò)展存儲(chǔ)變得愈發(fā)具有挑戰(zhàn)性。每個(gè)數(shù)據(jù)庫系統(tǒng)都有自己的方案。為了從這些方案中做出正確的選擇，了解它們是至關(guān)重要的。

[[279239]]

每個(gè)應(yīng)用程序在讀寫負(fù)載平衡、一致性、延遲和訪問模式方面各不相同。熟悉數(shù)據(jù)庫和底層存儲(chǔ)能幫助你進(jìn)行架構(gòu)決策、解釋系統(tǒng)行為、排除故障以及根據(jù)具體情況調(diào)優(yōu)。

優(yōu)化一個(gè)系統(tǒng)不可能做到面面俱到。我們當(dāng)然希望有一個(gè)數(shù)據(jù)結(jié)構(gòu)既能保證最佳的讀寫性能，又不需要任何存儲(chǔ)開銷，但顯然，這是不存在的。

本文深入討論了大多數(shù)現(xiàn)代數(shù)據(jù)庫中使用的兩種存儲(chǔ)系統(tǒng)設(shè)計(jì) —— 讀優(yōu)化 B-Tree [1] 和寫優(yōu)化 LSM(log-structured merge)-Tree [5] —— 并描述了它們的用例和優(yōu)缺權(quán)衡。

B-Tree

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

在搜索二叉樹中，每個(gè)節(jié)點(diǎn)都有兩個(gè)孩子(稱為左右孩子)。左子樹的節(jié)點(diǎn)值小于當(dāng)前節(jié)點(diǎn)值，右子樹反之。為了保持樹的深度最小，搜索二叉樹必須是平衡的：當(dāng)隨機(jī)順序的值被添加到樹中時(shí)，如果不加調(diào)整，終會(huì)導(dǎo)致樹的傾斜。

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

二叉樹是最有用的內(nèi)存數(shù)據(jù)結(jié)構(gòu)。然而由于平衡(保持所有子樹的深度最小)和低出度(每個(gè)節(jié)點(diǎn)最多兩個(gè)子節(jié)點(diǎn))，它們?cè)诖疟P上水土不服。B-Tree 允許每個(gè)節(jié)點(diǎn)存儲(chǔ)兩個(gè)以上的指針，并通過將節(jié)點(diǎn)大小與頁面大小(例如，4 KB)進(jìn)行匹配來與塊設(shè)備協(xié)同工作。今天的一些實(shí)現(xiàn)將使用更大的節(jié)點(diǎn)大小，跨越多個(gè)頁面。

B-Tree 有以下幾個(gè)性質(zhì)：

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

本文討論的 B+Tree [3] 是一種經(jīng)常用于數(shù)據(jù)庫存儲(chǔ)的 B-Tree 現(xiàn)代變種。B+Tree 與原始 B-Tree [1] 的不同之處在于：(1)它采用額外鏈接的葉節(jié)點(diǎn)存儲(chǔ)值;(2)值不能存儲(chǔ)在內(nèi)部節(jié)點(diǎn)上。

剖析 B-Tree

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

B-Tree 的特性如下：

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

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

查找

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

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

插入、更新、刪除

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

LSM-Tree

結(jié)構(gòu)化日志合并樹是一個(gè)不可變的基于磁盤的寫優(yōu)化數(shù)據(jù)結(jié)構(gòu)。它適用于寫入比查詢操作更頻繁的場景。LSM-Tree 已經(jīng)獲得了更多的關(guān)注，因?yàn)樗梢员苊怆S機(jī)插入，更新和刪除。

剖析 LSM-Tree

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

有序串行表

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

SSTable 是一種基于硬盤的有序不可變的數(shù)據(jù)結(jié)構(gòu)。從結(jié)構(gòu)上來看，SSTable 可以分為兩部分：數(shù)據(jù)塊和索引塊，如圖 6 所示。數(shù)據(jù)塊包含以鍵為順序?qū)懭氲奈ㄒ绘I值對(duì)。索引塊包含映射到數(shù)據(jù)塊指針的鍵，指針指向?qū)嶋H記錄的位置。為了快速搜索，索引一般使用優(yōu)化的結(jié)構(gòu)實(shí)現(xiàn)，例如 B-Tree 或用于點(diǎn)查詢的哈希表。SSTable 中的每一個(gè)值都有一個(gè)時(shí)間戳與之對(duì)應(yīng)。時(shí)間戳記錄了插入、更新(這兩者一般不做區(qū)分)和刪除時(shí)間。 

SSTable 具有以下優(yōu)點(diǎn)：

• 通過查詢主鍵索引可以實(shí)現(xiàn)快速的點(diǎn)查詢(例如，通過鍵尋找值)。
• 只需要順序讀取數(shù)據(jù)塊上的鍵值對(duì)就可以實(shí)現(xiàn)掃描(例如，遍歷制定范圍內(nèi)的鍵值對(duì))。

SSTable 代表一段時(shí)間內(nèi)所有數(shù)據(jù)庫操作的快照，因?yàn)?SSTable 是通過對(duì)內(nèi)存表的刷新操作創(chuàng)建的，該表充當(dāng)此時(shí)段內(nèi)對(duì)數(shù)據(jù)庫狀態(tài)的緩沖區(qū)。

查詢

檢索數(shù)據(jù)需要搜索硬盤上的所有 SSTable，檢查內(nèi)存表，并且合并它們的內(nèi)容后返回結(jié)果。要搜索的數(shù)據(jù)可以存儲(chǔ)在多個(gè) SSTable 中，因此合并步驟是必須的。

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

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

LSM-Tree 的維護(hù)

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

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

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

原子性與持久性

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

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

在 B-Tree 中，使用 WAL 可以理解為僅在寫入操作被記錄后才將其寫入數(shù)據(jù)文件。通常，B-Tree 存儲(chǔ)系統(tǒng)的日志尺寸相對(duì)較?。褐灰獙⒏膽?yīng)用于持久存儲(chǔ)，它們就可以被棄用。WAL 還可以作為運(yùn)行時(shí)操作的備份：任何未應(yīng)用于數(shù)據(jù)頁的更改都可以根據(jù)日志記錄重做。

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

總結(jié)

B-Tree 和 LSM-Tree 數(shù)據(jù)結(jié)構(gòu)最大的差異之一是它們優(yōu)化的目的以及優(yōu)化的效果。

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

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

LSM-Tree 具有以下特性：

• 它是不可變的。SSTable 一旦被寫入硬盤就不會(huì)再改變。壓縮操作被用于整合占用空間，刪除條目，合并在不同數(shù)據(jù)文件中的同鍵數(shù)據(jù)。作為壓縮操作的一部分，在成功合并后，源 SSTable 將被棄用并刪除。這種不可變性給我們帶來了另一個(gè)有用的特性，刷新后的表可以被并發(fā)訪問。
• 它是寫優(yōu)化的，這意味著寫入操作將進(jìn)入緩沖，隨后順序刷新到硬盤上，可能支持基于硬盤的空間局部性。
• 讀取操作可能需要訪問多個(gè)數(shù)據(jù)源，因?yàn)樵诓煌瑫r(shí)間寫入的同一個(gè)鍵的數(shù)據(jù)有可能位于不同的數(shù)據(jù)文件中。必須經(jīng)過合并過程才能將記錄返回給客戶端。
• 需要維護(hù) / 壓縮，因?yàn)榫彌_中的寫入操作被刷新到硬盤上。

評(píng)估存儲(chǔ)系統(tǒng)

開發(fā)存儲(chǔ)系統(tǒng)總要面對(duì)類似的挑戰(zhàn)，考慮類似的因素。決定優(yōu)化方向會(huì)對(duì)結(jié)果產(chǎn)生很大影響。你可以在寫入過程中花費(fèi)更多時(shí)間來布局結(jié)構(gòu)以實(shí)現(xiàn)更高效的讀取，為就地更新預(yù)留空間，也可以緩沖數(shù)據(jù)確保順序?qū)懭胍蕴岣邔懭胨俣?。但是，一次完成這一切是不可能的。理想中的存儲(chǔ)系統(tǒng)應(yīng)該具有最低的讀取成本，最低的寫入成本，并且沒有額外開銷。但實(shí)際上，數(shù)據(jù)結(jié)構(gòu)只能在多個(gè)因素之間權(quán)衡。理解這些取舍是重要的。

來自哈佛 DASlab(數(shù)據(jù)系統(tǒng)實(shí)驗(yàn)室)的研究人員總結(jié)了數(shù)據(jù)庫系統(tǒng)優(yōu)化方向的關(guān)鍵三點(diǎn)：讀取開銷、更新開銷和內(nèi)存開銷(或簡稱為 RUM)。對(duì)于數(shù)據(jù)結(jié)構(gòu)、訪問方法、甚至適用于某些工作負(fù)載的選擇應(yīng)該了解哪些參數(shù)對(duì)你的用例最為重要，因?yàn)樗惴ㄊ轻槍?duì)特定用例量身定制的。

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

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

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

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

三種可變參數(shù) —— 讀取，更新和內(nèi)存開銷 —— 可以幫助你評(píng)估數(shù)據(jù)庫并深入了解最適合的工作負(fù)載。它們都非常直觀，將存儲(chǔ)系統(tǒng)按其分類很容易，猜測它是如何執(zhí)行的，然后通過大量測試驗(yàn)證你的假設(shè)。

當(dāng)然，評(píng)估存儲(chǔ)系統(tǒng)時(shí)還有一些其他重要因素需要考慮，例如維護(hù)開銷，易用性，系統(tǒng)要求，頻繁增刪的適應(yīng)性，訪問模式等。RUM 假說只是幫助發(fā)展直觀感覺并提供初始方向的一條經(jīng)驗(yàn)法則。了解你的工作部件是構(gòu)建可擴(kuò)展后端的第一步。

一些因素可能因?qū)嵤┒?，甚至兩個(gè)使用類似存儲(chǔ)設(shè)計(jì)原則的數(shù)據(jù)庫可能會(huì)有不同表現(xiàn)。數(shù)據(jù)庫是包含許多可插拔模塊的復(fù)雜系統(tǒng)，是許多應(yīng)用程序的重要組成部分。這些信息將幫助你窺探數(shù)據(jù)庫的底層，并且了解底層數(shù)據(jù)結(jié)構(gòu)和其內(nèi)部行為之間的差異，從而決定哪個(gè)是最適合你的。