> For the complete documentation index, see [llms.txt](https://vonng.gitbook.io/vonng/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://vonng.gitbook.io/vonng/content/tw/ch3.md).

# 第三章：儲存與檢索

![](https://github.com/Vonng/ddia/blob/master/img/ch3.png)

> 建立秩序，省卻搜尋
>
> —— 德國諺語

一個數據庫在最基礎的層次上需要完成兩件事情：當你把資料交給資料庫時，它應當把資料儲存起來；而後當你向資料庫要資料時，它應當把資料返回給你。

在 [第二章](https://github.com/Vonng/ddia/blob/master/tw/ch2/README.md) 中，我們討論了資料模型和查詢語言，即程式設計師將資料錄入資料庫的格式，以及再次要回資料的機制。在本章中我們會從資料庫的視角來討論同樣的問題：資料庫如何儲存我們提供的資料，以及如何在我們需要時重新找到資料。

作為程式設計師，為什麼要關心資料庫內部儲存與檢索的機理？你可能不會去從頭開始實現自己的儲存引擎，但是你 **確實** 需要從許多可用的儲存引擎中選擇一個合適的。而且為了讓儲存引擎能在你的工作負載型別上執行良好，你也需要大致瞭解儲存引擎在底層究竟做了什麼。

特別需要注意，針對 **事務性** 負載最佳化的和針對 **分析性** 負載最佳化的儲存引擎之間存在巨大差異。稍後我們將在 “[事務處理還是分析？](#事務處理還是分析？)” 一節中探討這一區別，並在 “[列式儲存](#列式儲存)” 中討論一系列針對分析性負載而最佳化的儲存引擎。

但首先，我們將從你可能已經很熟悉的兩大類資料庫（傳統的關係型資料庫和很多所謂的 “NoSQL” 資料庫）中使用的 **儲存引擎** 來開始本章的內容。我們將研究兩大類儲存引擎：**日誌結構（log-structured）** 的儲存引擎，以及 **面向頁面（page-oriented）** 的儲存引擎（例如 B 樹）。

### 驅動資料庫的資料結構

世界上最簡單的資料庫可以用兩個 Bash 函式實現：

```bash
#!/bin/bash
db_set () {
  echo "$1,$2" >> database
}

db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
```

這兩個函式實現了鍵值儲存的功能。執行 `db_set key value` 會將 **鍵（key）** 和 **值（value）** 儲存在資料庫中。鍵和值（幾乎）可以是你喜歡的任何東西，例如，值可以是 JSON 文件。然後呼叫 `db_get key` 會查詢與該鍵關聯的最新值並將其返回。

麻雀雖小，五臟俱全：

```bash
$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'

$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
```

底層的儲存格式非常簡單：一個文字檔案，每行包含一條逗號分隔的鍵值對（忽略轉義問題的話，大致與 CSV 檔案類似）。每次對 `db_set` 的呼叫都會向檔案末尾追加記錄，所以更新鍵的時候舊版本的值不會被覆蓋 —— 因而查詢最新值的時候，需要找到檔案中鍵最後一次出現的位置（因此 `db_get` 中使用了 `tail -n 1` )。

```bash
$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'

$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}

$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}
```

`db_set` 函式對於極其簡單的場景其實有非常好的效能，因為在檔案尾部追加寫入通常是非常高效的。與 `db_set` 做的事情類似，許多資料庫在內部使用了 **日誌（log）**，也就是一個 **僅追加（append-only）** 的資料檔案。真正的資料庫有更多的問題需要處理（如併發控制，回收硬碟空間以避免日誌無限增長，處理錯誤與部分寫入的記錄），但基本原理是一樣的。日誌極其有用，我們還將在本書的其它部分重複見到它好幾次。

> **日誌（log）** 這個詞通常指應用日誌：即應用程式輸出的描述正在發生的事情的文字。本書在更普遍的意義下使用 **日誌** 這一詞：一個僅追加的記錄序列。它可能壓根就不是給人類看的，它可以使用二進位制格式，並僅能由其他程式讀取。

另一方面，如果這個資料庫中有著大量記錄，則這個 `db_get` 函式的效能會非常糟糕。每次你想查詢一個鍵時，`db_get` 必須從頭到尾掃描整個資料庫檔案來查詢鍵的出現。用演算法的語言來說，查詢的開銷是 `O(n)` ：如果資料庫記錄數量 n 翻了一倍，查詢時間也要翻一倍。這就不好了。

為了高效查詢資料庫中特定鍵的值，我們需要一個數據結構：**索引（index）**。本章將介紹一系列的索引結構，並在它們之間進行比較。索引背後的大致思想是透過儲存一些額外的元資料作為路標來幫助你找到想要的資料。如果你想以幾種不同的方式搜尋同一份資料，那麼你也許需要在資料的不同部分上建立多個索引。

索引是從主資料衍生的 **額外的（additional）** 結構。許多資料庫允許新增與刪除索引，這不會影響資料的內容，而只會影響查詢的效能。維護額外的結構會產生開銷，特別是在寫入時。寫入效能很難超過簡單地追加寫入檔案，因為追加寫入是最簡單的寫入操作。任何型別的索引通常都會減慢寫入速度，因為每次寫入資料時都需要更新索引。

這是儲存系統中一個重要的權衡：精心選擇的索引加快了讀查詢的速度，但是每個索引都會拖慢寫入速度。因為這個原因，資料庫預設並不會索引所有的內容，而需要你，也就是程式設計師或資料庫管理員（DBA），基於對應用的典型查詢模式的瞭解來手動選擇索引。你可以選擇那些能為應用帶來最大收益而且又不會引入超出必要開銷的索引。

#### 雜湊索引

讓我們從 **鍵值資料（key-value Data）** 的索引開始。這不是你可以索引的唯一資料型別，但鍵值資料是很常見的。在引入更複雜的索引之前，它是重要的第一步。

鍵值儲存與在大多數程式語言中可以找到的 **字典（dictionary）** 型別非常相似，通常字典都是用 **雜湊對映（hash map）** 或 **散列表（hash table）** 實現的。雜湊對映在許多演算法教科書中都有描述【1,2】，所以這裡我們不會討論它的工作細節。既然我們已經可以用雜湊對映來表示 **記憶體中** 的資料結構，為什麼不使用它來索引 **硬碟上** 的資料呢？

假設我們的資料儲存只是一個追加寫入的檔案，就像前面的例子一樣，那麼最簡單的索引策略就是：保留一個記憶體中的雜湊對映，其中每個鍵都對映到資料檔案中的一個位元組偏移量，指明瞭可以找到對應值的位置，如 [圖 3-1](https://github.com/Vonng/ddia/blob/master/img/fig3-1.png) 所示。當你將新的鍵值對追加寫入檔案中時，還要更新雜湊對映，以反映剛剛寫入的資料的偏移量（這同時適用於插入新鍵與更新現有鍵）。當你想查詢一個值時，使用雜湊對映來查詢資料檔案中的偏移量，**尋找（seek）** 該位置並讀取該值即可。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-1.png)

**圖 3-1 以類 CSV 格式儲存鍵值對的日誌，並使用記憶體雜湊對映進行索引。**

聽上去簡單，但這是一個可行的方法。現實中，Bitcask 實際上就是這麼做的（Riak 中預設的儲存引擎）【3】。Bitcask 提供高效能的讀取和寫入操作，但要求所有的鍵必須能放入可用記憶體中，因為雜湊對映完全保留在記憶體中。而資料值可以使用比可用記憶體更多的空間，因為可以在硬碟上透過一次硬碟查詢操作來載入所需部分，如果資料檔案的那部分已經在檔案系統快取中，則讀取根本不需要任何硬碟 I/O。

像 Bitcask 這樣的儲存引擎非常適合每個鍵的值經常更新的情況。例如，鍵可能是某個貓咪影片的網址（URL），而值可能是該影片被播放的次數（每次有人點選播放按鈕時遞增）。在這種型別的工作負載中，有很多寫操作，但是沒有太多不同的鍵 —— 每個鍵有很多的寫操作，但是將所有鍵儲存在記憶體中是可行的。

到目前為止，我們只是在追加寫入一個檔案 —— 所以如何避免最終用完硬碟空間？一種好的解決方案是，將日誌分為特定大小的 **段（segment）**，當日誌增長到特定尺寸時關閉當前段檔案，並開始寫入一個新的段檔案。然後，我們就可以對這些段進行 **壓縮（compaction）**，如 [圖 3-2](https://github.com/Vonng/ddia/blob/master/img/fig3-2.png) 所示。這裡的壓縮意味著在日誌中丟棄重複的鍵，只保留每個鍵的最近更新。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-2.png)

**圖 3-2 鍵值更新日誌（統計貓咪影片的播放次數）的壓縮，只保留每個鍵的最近值**

而且，由於壓縮經常會使得段變得很小（假設在一個段內鍵被平均重寫了好幾次），我們也可以在執行壓縮的同時將多個段合併在一起，如 [圖 3-3](https://github.com/Vonng/ddia/blob/master/img/fig3-3.png) 所示。段被寫入後永遠不會被修改，所以合併的段被寫入一個新的檔案。凍結段的合併和壓縮可以在後臺執行緒中完成，這個過程進行的同時，我們仍然可以繼續使用舊的段檔案來正常提供讀寫請求。合併過程完成後，我們將讀取請求轉換為使用新合併的段而不是舊的段 —— 然後舊的段檔案就可以簡單地刪除掉了。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-3.png)

**圖 3-3 同時執行壓縮和分段合併**

每個段現在都有自己的記憶體散列表，將鍵對映到檔案偏移量。為了找到一個鍵的值，我們首先檢查最近的段的雜湊對映；如果鍵不存在，我們就檢查第二個最近的段，依此類推。合併過程將保持段的數量足夠小，所以查詢過程不需要檢查太多的雜湊對映。

要讓這個簡單的想法在實際中能工作會涉及到大量的細節。簡單來說，下面幾點都是實現過程中需要認真考慮的問題：

* 檔案格式

  CSV 不是日誌的最佳格式。使用二進位制格式更快，更簡單：首先以位元組為單位對字串的長度進行編碼，然後是原始的字串（不需要轉義）。
* 刪除記錄

  如果要刪除一個鍵及其關聯的值，則必須在資料檔案中追加一個特殊的刪除記錄（邏輯刪除，有時被稱為墓碑，即 tombstone）。當日誌段被合併時，合併過程會透過這個墓碑知道要將被刪除鍵的所有歷史值都丟棄掉。
* 崩潰恢復

  如果資料庫重新啟動，則記憶體雜湊對映將丟失。原則上，你可以透過從頭到尾讀取整個段檔案並記錄下來每個鍵的最近值來恢復每個段的雜湊對映。但是，如果段檔案很大，可能需要很長時間，這會使服務的重啟比較痛苦。Bitcask 透過將每個段的雜湊對映的快照儲存在硬碟上來加速恢復，可以使雜湊對映更快地載入到記憶體中。
* 部分寫入記錄

  資料庫隨時可能崩潰，包括在將記錄追加到日誌的過程中。Bitcask 檔案包含校驗和，允許檢測和忽略日誌中的這些損壞部分。
* 併發控制

  由於寫操作是以嚴格的順序追加到日誌中的，所以常見的實現是隻有一個寫入執行緒。也因為資料檔案段是僅追加的或者說是不可變的，所以它們可以被多個執行緒同時讀取。

乍一看，僅追加日誌似乎很浪費：為什麼不直接在檔案裡更新，用新值覆蓋舊值？僅追加的設計之所以是個好的設計，有如下幾個原因：

* 追加和分段合併都是順序寫入操作，通常比隨機寫入快得多，尤其是在磁性機械硬碟上。在某種程度上，順序寫入在基於快閃記憶體的 **固態硬碟（SSD）** 上也是好的選擇【4】。我們將在“[比較 B 樹和 LSM 樹](#比較b樹和lsm樹)”中進一步討論這個問題。
* 如果段檔案是僅追加的或不可變的，併發和崩潰恢復就簡單多了。例如，當一個數據值被更新的時候發生崩潰，你不用擔心檔案裡將會同時包含舊值和新值各自的一部分。
* 合併舊段的處理也可以避免資料檔案隨著時間的推移而碎片化的問題。

但是，散列表索引也有其侷限性：

* 散列表必須能放進記憶體。如果你有非常多的鍵，那真是倒楣。原則上可以在硬碟上維護一個雜湊對映，不幸的是硬碟雜湊對映很難表現優秀。它需要大量的隨機訪問 I/O，而後者耗盡時想要再擴充是很昂貴的，並且需要很煩瑣的邏輯去解決雜湊衝突【5】。
* 範圍查詢效率不高。例如，你無法輕鬆掃描 kitty00000 和 kitty99999 之間的所有鍵 —— 你必須在雜湊對映中單獨查詢每個鍵。

在下一節中，我們將看到一個沒有這些限制的索引結構。

#### SSTables和LSM樹

在 [圖 3-3](https://github.com/Vonng/ddia/blob/master/img/fig3-3.png) 中，每個日誌結構儲存段都是一系列鍵值對。這些鍵值對按照它們寫入的順序排列，日誌中稍後的值優先於日誌中較早的相同鍵的值。除此之外，檔案中鍵值對的順序並不重要。

現在我們可以對段檔案的格式做一個簡單的改變：要求鍵值對的序列按鍵排序。乍一看，這個要求似乎打破了我們使用順序寫入的能力，我們將稍後再回到這個問題。

我們把這個格式稱為 **排序字串表（Sorted String Table）**，簡稱 SSTable。我們還要求每個鍵只在每個合併的段檔案中出現一次（壓縮過程已經保證）。與使用雜湊索引的日誌段相比，SSTable 有幾個大的優勢：

1. 即使檔案大於可用記憶體，合併段的操作仍然是簡單而高效的。這種方法就像歸併排序演算法中使用的方法一樣，如 [圖 3-4](https://github.com/Vonng/ddia/blob/master/img/fig3-4.png) 所示：你開始並排讀取多個輸入檔案，檢視每個檔案中的第一個鍵，複製最低的鍵（根據排序順序）到輸出檔案，不斷重複此步驟，將產生一個新的合併段檔案，而且它也是也按鍵排序的。

   ![](https://github.com/Vonng/ddia/blob/master/img/fig3-4.png)

   **圖 3-4 合併幾個 SSTable 段，只保留每個鍵的最新值**

   如果在幾個輸入段中出現相同的鍵，該怎麼辦？請記住，每個段都包含在一段時間內寫入資料庫的所有值。這意味著一個輸入段中的所有值一定比另一個段中的所有值都更近（假設我們總是合併相鄰的段）。當多個段包含相同的鍵時，我們可以保留最近段的值，並丟棄舊段中的值。
2. 為了在檔案中找到一個特定的鍵，你不再需要在記憶體中儲存所有鍵的索引。以 [圖 3-5](https://github.com/Vonng/ddia/blob/master/img/fig3-5.png) 為例：假設你正在記憶體中尋找鍵 `handiwork`，但是你不知道這個鍵在段檔案中的確切偏移量。然而，你知道 `handbag` 和 `handsome` 的偏移，而且由於排序特性，你知道 `handiwork` 必須出現在這兩者之間。這意味著你可以跳到 `handbag` 的偏移位置並從那裡掃描，直到你找到 `handiwork`（或沒找到，如果該檔案中沒有該鍵）。

   ![](https://github.com/Vonng/ddia/blob/master/img/fig3-5.png)

   **圖 3-5 具有記憶體索引的 SSTable**

   你仍然需要一個記憶體中的索引來告訴你一些鍵的偏移量，但它可以是稀疏的：每幾千位元組的段檔案有一個鍵就足夠了，因為幾千位元組可以很快地被掃描完 。
3. 由於讀取請求無論如何都需要掃描所請求範圍內的多個鍵值對，因此可以將這些記錄分組為塊（block），並在將其寫入硬碟之前對其進行壓縮（如 [圖 3-5](https://github.com/Vonng/ddia/blob/master/img/fig3-5.png) 中的陰影區域所示） 。稀疏記憶體索引中的每個條目都指向壓縮塊的開始處。除了節省硬碟空間之外，壓縮還可以減少對 I/O 頻寬的使用。

**構建和維護SSTables**

到目前為止還不錯，但是如何讓你的資料能夠預先排好序呢？畢竟我們接收到的寫入請求可能以任何順序發生。

雖然在硬碟上維護有序結構也是可能的（請參閱 “[B 樹](#B樹)”），但在記憶體儲存則要容易得多。有許多可以使用的眾所周知的樹形資料結構，例如紅黑樹或 AVL 樹【2】。使用這些資料結構，你可以按任何順序插入鍵，並按排序順序讀取它們。

現在我們可以讓我們的儲存引擎以如下方式工作：

* 有新寫入時，將其新增到記憶體中的平衡樹資料結構（例如紅黑樹）。這個記憶體樹有時被稱為 **記憶體表（memtable）**。
* 當 **記憶體表** 大於某個閾值（通常為幾兆位元組）時，將其作為 SSTable 檔案寫入硬碟。這可以高效地完成，因為樹已經維護了按鍵排序的鍵值對。新的 SSTable 檔案將成為資料庫中最新的段。當該 SSTable 被寫入硬碟時，新的寫入可以在一個新的記憶體表例項上繼續進行。
* 收到讀取請求時，首先嘗試在記憶體表中找到對應的鍵，如果沒有就在最近的硬碟段中尋找，如果還沒有就在下一個較舊的段中繼續尋找，以此類推。
* 時不時地，在後臺執行一個合併和壓縮過程，以合併段檔案並將已覆蓋或已刪除的值丟棄掉。

這個方案效果很好。它只會遇到一個問題：如果資料庫崩潰，則最近的寫入（在記憶體表中，但尚未寫入硬碟）將丟失。為了避免這個問題，我們可以在硬碟上儲存一個單獨的日誌，每個寫入都會立即被追加到這個日誌上，就像在前面的章節中所描述的那樣。這個日誌沒有按排序順序，但這並不重要，因為它的唯一目的是在崩潰後恢復記憶體表。每當記憶體表寫出到 SSTable 時，相應的日誌都可以被丟棄。

**用SSTables製作LSM樹**

這裡描述的演算法本質上是 LevelDB【6】和 RocksDB【7】這些鍵值儲存引擎庫所使用的技術，這些儲存引擎被設計嵌入到其他應用程式中。除此之外，LevelDB 可以在 Riak 中用作 Bitcask 的替代品。在 Cassandra 和 HBase 中也使用了類似的儲存引擎【8】，而且他們都受到了 Google 的 Bigtable 論文【9】（引入了術語 SSTable 和 memtable ）的啟發。

這種索引結構最早由 Patrick O'Neil 等人發明，且被命名為日誌結構合併樹（或 LSM 樹）【10】，它是基於更早之前的日誌結構檔案系統【11】來構建的。基於這種合併和壓縮排序檔案原理的儲存引擎通常被稱為 LSM 儲存引擎。

Lucene，是一種全文搜尋的索引引擎，在 Elasticsearch 和 Solr 被使用，它使用類似的方法來儲存它的關鍵詞詞典【12,13】。全文索引比鍵值索引複雜得多，但是基於類似的想法：在搜尋查詢中，由一個給定的單詞，找到提及單詞的所有文件（網頁、產品描述等）。這也是透過鍵值結構實現的：其中鍵是 **單詞（term）**，值是所有包含該單詞的文件的 ID 列表（**postings list**）。在 Lucene 中，從詞語到記錄列表的這種對映儲存在類似於 SSTable 的有序檔案中，並根據需要在後臺執行合併【14】。

**效能最佳化**

與往常一樣，要讓儲存引擎在實踐中表現良好涉及到大量設計細節。例如，當查詢資料庫中不存在的鍵時，LSM 樹演算法可能會很慢：你必須先檢查記憶體表，然後檢視從最近的到最舊的所有的段（可能還必須從硬碟讀取每一個段檔案），然後才能確定這個鍵不存在。為了最佳化這種訪問，儲存引擎通常使用額外的布隆過濾器（Bloom filters）【15】。（布隆過濾器是一種節省記憶體的資料結構，用於近似表達集合的內容，它可以告訴你資料庫中是否存在某個鍵，從而為不存在的鍵節省掉許多不必要的硬碟讀取操作。）

還有一些不同的策略來確定 SSTables 被壓縮和合並的順序和時間。最常見的選擇是 size-tiered 和 leveled compaction。LevelDB 和 RocksDB 使用 leveled compaction（LevelDB 因此得名），HBase 使用 size-tiered，Cassandra 同時支援這兩種【16】。對於 sized-tiered，較新和較小的 SSTables 相繼被合併到較舊的和較大的 SSTable 中。對於 leveled compaction，key （按照分佈範圍）被拆分到較小的 SSTables，而較舊的資料被移動到單獨的層級（level），這使得壓縮（compaction）能夠更加增量地進行，並且使用較少的硬碟空間。

即使有許多微妙的東西，LSM 樹的基本思想 —— 儲存一系列在後臺合併的 SSTables —— 簡單而有效。即使資料集比可用記憶體大得多，它仍能繼續正常工作。由於資料按排序順序儲存，你可以高效地執行範圍查詢（掃描所有從某個最小值到某個最大值之間的所有鍵），並且因為硬碟寫入是連續的，所以 LSM 樹可以支援非常高的寫入吞吐量。

#### B樹

前面討論的日誌結構索引看起來已經相當可用了，但它們卻不是最常見的索引型別。使用最廣泛的索引結構和日誌結構索引相當不同，它就是我們接下來要討論的 B 樹。

從 1970 年被引入【17】，僅不到 10 年後就變得 “無處不在”【18】，B 樹很好地經受了時間的考驗。在幾乎所有的關係資料庫中，它們仍然是標準的索引實現，許多非關係資料庫也會使用到 B 樹。

像 SSTables 一樣，B 樹保持按鍵排序的鍵值對，這允許高效的鍵值查詢和範圍查詢。但這也就是僅有的相似之處了：B 樹有著非常不同的設計理念。

我們前面看到的日誌結構索引將資料庫分解為可變大小的段，通常是幾兆位元組或更大的大小，並且總是按順序寫入段。相比之下，B 樹將資料庫分解成固定大小的 **塊（block）** 或 **分頁（page）**，傳統上大小為 4KB（有時會更大），並且一次只能讀取或寫入一個頁面。這種設計更接近於底層硬體，因為硬碟空間也是按固定大小的塊來組織的。

每個頁面都可以使用地址或位置來標識，這允許一個頁面引用另一個頁面 —— 類似於指標，但在硬碟而不是在記憶體中。我們可以使用這些頁面引用來構建一個頁面樹，如 [圖 3-6](https://github.com/Vonng/ddia/blob/master/img/fig3-6.png) 所示。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-6.png)

**圖 3-6 使用 B 樹索引查詢一個鍵**

一個頁面會被指定為 B 樹的根；在索引中查詢一個鍵時，就從這裡開始。該頁面包含幾個鍵和對子頁面的引用。每個子頁面負責一段連續範圍的鍵，根頁面上每兩個引用之間的鍵，表示相鄰子頁面管理的鍵的範圍（邊界）。

在 [圖 3-6](https://github.com/Vonng/ddia/blob/master/img/fig3-6.png) 的例子中，我們正在尋找鍵 251 ，所以我們知道我們需要跟蹤邊界 200 和 300 之間的頁面引用。這將我們帶到一個類似的頁面，進一步將 200 到 300 的範圍拆分到子範圍。

最終，我們將到達某個包含單個鍵的頁面（葉子頁面，leaf page），該頁面或者直接包含每個鍵的值，或者包含了對可以找到值的頁面的引用。

在 B 樹的一個頁面中對子頁面的引用的數量稱為 **分支因子（branching factor）**。例如，在 [圖 3-6](https://github.com/Vonng/ddia/blob/master/img/fig3-6.png) 中，分支因子是 6。在實踐中，分支因子的大小取決於儲存頁面引用和範圍邊界所需的空間，但這個值通常是幾百。

如果要更新 B 樹中現有鍵的值，需要搜尋包含該鍵的葉子頁面，更改該頁面中的值，並將該頁面寫回到硬碟（對該頁面的任何引用都將保持有效）。如果你想新增一個新的鍵，你需要找到其範圍能包含新鍵的頁面，並將其新增到該頁面。如果頁面中沒有足夠的可用空間容納新鍵，則將其分成兩個半滿頁面，並更新父頁面以反映新的鍵範圍分割槽，如 [圖 3-7](https://github.com/Vonng/ddia/blob/master/img/fig3-7.png) 所示 。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-7.png)

**圖 3-7 透過分割頁面來生長 B 樹**

這個演算法可以確保樹保持平衡：具有 n 個鍵的 B 樹總是具有 $O (log n)$ 的深度。大多數資料庫可以放入一個三到四層的 B 樹，所以你不需要追蹤多個頁面引用來找到你正在查詢的頁面（分支因子為 500 的 4KB 頁面的四層樹可以儲存多達 256TB 的資料）。

**讓B樹更可靠**

B 樹的基本底層寫操作是用新資料覆寫硬碟上的頁面，並假定覆寫不改變頁面的位置：即，當頁面被覆寫時，對該頁面的所有引用保持完整。這與日誌結構索引（如 LSM 樹）形成鮮明對比，後者只追加到檔案（並最終刪除過時的檔案），但從不修改檔案中已有的內容。

你可以把覆寫硬碟上的頁面對應為實際的硬體操作。在磁性硬碟驅動器上，這意味著將磁頭移動到正確的位置，等待旋轉盤上的正確位置出現，然後用新的資料覆寫適當的扇區。在固態硬碟上，由於 SSD 必須一次擦除和重寫相當大的儲存晶片塊，所以會發生更複雜的事情【19】。

而且，一些操作需要覆寫幾個不同的頁面。例如，如果因為插入導致頁面過滿而拆分頁面，則需要寫入新拆分的兩個頁面，並覆寫其父頁面以更新對兩個子頁面的引用。這是一個危險的操作，因為如果資料庫在系列操作進行到一半時崩潰，那麼最終將導致一個損壞的索引（例如，可能有一個孤兒頁面沒有被任何頁面引用） 。

為了使資料庫能處理異常崩潰的場景，B 樹實現通常會帶有一個額外的硬碟資料結構：**預寫式日誌**（WAL，即 write-ahead log，也稱為 **重做日誌**，即 redo log）。這是一個僅追加的檔案，每個 B 樹的修改在其能被應用到樹本身的頁面之前都必須先寫入到該檔案。當資料庫在崩潰後恢復時，這個日誌將被用來使 B 樹恢復到一致的狀態【5,20】。

另外還有一個更新頁面的複雜情況是，如果多個執行緒要同時訪問 B 樹，則需要仔細的併發控制 —— 否則執行緒可能會看到樹處於不一致的狀態。這通常是透過使用 **鎖存器**（latches，輕量級鎖）保護樹的資料結構來完成。日誌結構化的方法在這方面更簡單，因為它們在後臺進行所有的合併，而不會干擾新接收到的查詢，並且能夠時不時地將段檔案切換為新的（該切換是原子操作）。

**B樹的最佳化**

由於 B 樹已經存在了很久，所以並不奇怪這麼多年下來有很多最佳化的設計被開發出來，僅舉幾例：

* 不同於覆寫頁面並維護 WAL 以支援崩潰恢復，一些資料庫（如 LMDB）使用寫時複製方案【21】。經過修改的頁面被寫入到不同的位置，並且還在樹中建立了父頁面的新版本，以指向新的位置。這種方法對於併發控制也很有用，我們將在 “[快照隔離和可重複讀](https://github.com/Vonng/ddia/blob/master/tw/ch7/README.md#快照隔離和可重複讀)” 中看到。
* 我們可以透過不儲存整個鍵，而是縮短其大小，來節省頁面空間。特別是在樹內部的頁面上，鍵只需要提供足夠的資訊來充當鍵範圍之間的邊界。在頁面中包含更多的鍵允許樹具有更高的分支因子，因此也就允許更少的層級 。
* 通常，頁面可以放置在硬碟上的任何位置；沒有什麼要求相鄰鍵範圍的頁面也放在硬碟上相鄰的區域。如果某個查詢需要按照排序順序掃描大部分的鍵範圍，那麼這種按頁面儲存的佈局可能會效率低下，因為每個頁面的讀取都需要執行一次硬碟查詢。因此，許多 B 樹的實現在佈局樹時會盡量使葉子頁面按順序出現在硬碟上。但是，隨著樹的增長，要維持這個順序是很困難的。相比之下，由於 LSM 樹在合併過程中一次性重寫一大段儲存，所以它們更容易使順序鍵在硬碟上連續儲存。
* 額外的指標被新增到樹中。例如，每個葉子頁面可以引用其左邊和右邊的兄弟頁面，使得不用跳回父頁面就能按順序對鍵進行掃描。
* B 樹的變體如 **分形樹（fractal trees）**【22】借用了一些日誌結構的思想來減少硬碟查詢（而且它們與分形無關）。

#### 比較B樹和LSM樹

儘管 B 樹實現通常比 LSM 樹實現更成熟，LSM 樹由於其效能特徵的關係，仍然引起了不少關注。根據經驗，通常 LSM 樹的寫入速度更快，而 B 樹的讀取速度更快【23】。LSM 樹上的讀取通常比較慢，因為它們必須檢查幾種不同的資料結構和不同壓縮（Compaction）層級的 SSTables。

然而，基準測試的結果通常和工作負載的細節相關。你需要用你特有的工作負載來測試系統，以便進行有效的比較。在本節中，我們將簡要討論一些在衡量儲存引擎效能時值得考慮的事情。

**LSM樹的優點**

B 樹索引中的每塊資料都必須至少寫入兩次：一次寫入預先寫入日誌（WAL），一次寫入樹頁面本身（如果有分頁還需要再寫入一次）。即使在該頁面中只有幾個位元組發生了變化，也需要接受寫入整個頁面的開銷。有些儲存引擎甚至會覆寫同一個頁面兩次，以免在電源故障的情況下頁面未完整更新【24,25】。

由於反覆壓縮和合並 SSTables，日誌結構索引也會多次重寫資料。這種影響 —— 在資料庫的生命週期中每筆資料導致對硬碟的多次寫入 —— 被稱為 **寫入放大（write amplification）**。使用固態硬碟的機器需要額外關注這點，固態硬碟的快閃記憶體壽命在覆寫有限次數後就會耗盡。

在寫入繁重的應用程式中，效能瓶頸可能是資料庫可以寫入硬碟的速度。在這種情況下，寫放大會導致直接的效能代價：儲存引擎寫入硬碟的次數越多，可用硬碟頻寬內它能處理的每秒寫入次數就越少。

進而，LSM 樹通常能夠比 B 樹支援更高的寫入吞吐量，部分原因是它們有時具有較低的寫放大（儘管這取決於儲存引擎的配置和工作負載），部分是因為它們順序地寫入緊湊的 SSTable 檔案而不是必須覆寫樹中的幾個頁面【26】。這種差異在機械硬碟上尤其重要，其順序寫入比隨機寫入要快得多。

LSM 樹可以被壓縮得更好，因此通常能比 B 樹在硬碟上產生更小的檔案。B 樹儲存引擎會由於碎片化（fragmentation）而留下一些未使用的硬碟空間：當頁面被拆分或某行不能放入現有頁面時，頁面中的某些空間仍未被使用。由於 LSM 樹不是面向頁面的，並且會透過定期重寫 SSTables 以去除碎片，所以它們具有較低的儲存開銷，特別是當使用分層壓縮（leveled compaction）時【27】。

在許多固態硬碟上，韌體內部使用了日誌結構化演算法，以將隨機寫入轉變為順序寫入底層儲存晶片，因此儲存引擎寫入模式的影響不太明顯【19】。但是，較低的寫入放大率和減少的碎片仍然對固態硬碟更有利：更緊湊地表示資料允許在可用的 I/O 頻寬內處理更多的讀取和寫入請求。

**LSM樹的缺點**

日誌結構儲存的缺點是壓縮過程有時會干擾正在進行的讀寫操作。儘管儲存引擎嘗試增量地執行壓縮以儘量不影響併發訪問，但是硬碟資源有限，所以很容易發生某個請求需要等待硬碟先完成昂貴的壓縮操作。對吞吐量和平均響應時間的影響通常很小，但是日誌結構化儲存引擎在更高百分位的響應時間（請參閱 “[描述效能](https://github.com/Vonng/ddia/blob/master/tw/ch1/README.md#描述效能)”）有時會相當長，而 B 樹的行為則相對更具有可預測性【28】。

壓縮的另一個問題出現在高寫入吞吐量時：硬碟的有限寫入頻寬需要在初始寫入（記錄日誌和重新整理記憶體表到硬碟）和在後臺執行的壓縮執行緒之間共享。寫入空資料庫時，可以使用全硬碟頻寬進行初始寫入，但資料庫越大，壓縮所需的硬碟頻寬就越多。

如果寫入吞吐量很高，並且壓縮沒有仔細配置好，有可能導致壓縮跟不上寫入速率。在這種情況下，硬碟上未合併段的數量不斷增加，直到硬碟空間用完，讀取速度也會減慢，因為它們需要檢查更多的段檔案。通常情況下，即使壓縮無法跟上，基於 SSTable 的儲存引擎也不會限制傳入寫入的速率，所以你需要進行明確的監控來檢測這種情況【29,30】。

B 樹的一個優點是每個鍵只存在於索引中的一個位置，而日誌結構化的儲存引擎可能在不同的段中有相同鍵的多個副本。這個方面使得 B 樹在想要提供強大的事務語義的資料庫中很有吸引力：在許多關係資料庫中，事務隔離是透過在鍵範圍上使用鎖來實現的，在 B 樹索引中，這些鎖可以直接附加到樹上【5】。在 [第七章](https://github.com/Vonng/ddia/blob/master/tw/ch7/README.md) 中，我們將更詳細地討論這一點。

B 樹在資料庫架構中是非常根深蒂固的，為許多工作負載都提供了始終如一的良好效能，所以它們不可能在短期內消失。在新的資料庫中，日誌結構化索引變得越來越流行。沒有簡單易行的辦法來判斷哪種型別的儲存引擎對你的使用場景更好，所以需要透過一些測試來得到相關經驗。

#### 其他索引結構

到目前為止，我們只討論了鍵值索引，它們就像關係模型中的 **主鍵（primary key）** 索引。主鍵唯一標識關係表中的一行，或文件資料庫中的一個文件或圖形資料庫中的一個頂點。資料庫中的其他記錄可以透過其主鍵（或 ID）引用該行 / 文件 / 頂點，索引就被用於解析這樣的引用。

次級索引（secondary indexes）也很常見。在關係資料庫中，你可以使用 `CREATE INDEX` 命令在同一個表上建立多個次級索引，而且這些索引通常對於有效地執行聯接（join）而言至關重要。例如，在 [第二章](https://github.com/Vonng/ddia/blob/master/tw/ch2/README.md) 中的 [圖 2-1](https://github.com/Vonng/ddia/blob/master/img/fig2-1.png) 中，很可能在 `user_id` 列上有一個次級索引，以便你可以在每個表中找到屬於同一使用者的所有行。

次級索引可以很容易地從鍵值索引構建。次級索引主要的不同是鍵不是唯一的，即可能有許多行（文件，頂點）具有相同的鍵。這可以透過兩種方式來解決：將匹配行識別符號的列表作為索引裡的值（就像全文索引中的記錄列表），或者透過向每個鍵新增行識別符號來使鍵唯一。無論哪種方式，B 樹和日誌結構索引都可以用作次級索引。

**將值儲存在索引中**

索引中的鍵是查詢要搜尋的內容，而其值可以是以下兩種情況之一：它可以是實際的行（文件，頂點），也可以是對儲存在別處的行的引用。在後一種情況下，行被儲存的地方被稱為 **堆檔案（heap file）**，並且儲存的資料沒有特定的順序（它可以是僅追加的，或者它可以跟蹤被刪除的行以便後續可以用新的資料進行覆蓋）。堆檔案方法很常見，因為它避免了在存在多個次級索引時對資料的複製：每個索引只引用堆檔案中的一個位置，實際的資料都儲存在一個地方。

在不更改鍵的情況下更新值時，堆檔案方法可以非常高效：只要新值的位元組數不大於舊值，就可以覆蓋該記錄。如果新值更大，情況會更複雜，因為它可能需要移到堆中有足夠空間的新位置。在這種情況下，要麼所有的索引都需要更新，以指向記錄的新堆位置，或者在舊堆位置留下一個轉發指標【5】。

在某些情況下，從索引到堆檔案的額外跳躍對讀取來說效能損失太大，因此可能希望將被索引的行直接儲存在索引中。這被稱為聚集索引（clustered index）。例如，在 MySQL 的 InnoDB 儲存引擎中，表的主鍵總是一個聚集索引，次級索引則引用主鍵（而不是堆檔案中的位置）【31】。在 SQL Server 中，可以為每個表指定一個聚集索引【32】。

在 **聚集索引**（在索引中儲存所有的行資料）和 **非聚集索引**（僅在索引中儲存對資料的引用）之間的折衷被稱為 **覆蓋索引（covering index）** 或 **包含列的索引（index with included columns）**，其在索引記憶體儲表的一部分列【33】。這允許透過單獨使用索引來處理一些查詢（這種情況下，可以說索引 **覆蓋（cover）** 了查詢）【32】。

與任何型別的資料重複一樣，聚集索引和覆蓋索引可以加快讀取速度，但是它們需要額外的儲存空間，並且會增加寫入開銷。資料庫還需要額外的努力來執行事務保證，因為應用程式不應看到任何因為使用副本而導致的不一致。

**多列索引**

至今討論的索引只是將一個鍵對映到一個值。如果我們需要同時查詢一個表中的多個列（或文件中的多個欄位），這顯然是不夠的。

最常見的多列索引被稱為 **連線索引（concatenated index）** ，它透過將一列的值追加到另一列後面，簡單地將多個欄位組合成一個鍵（索引定義中指定了欄位的連線順序）。這就像一個老式的紙質電話簿，它提供了一個從（姓氏，名字）到電話號碼的索引。由於排序順序，索引可以用來查詢所有具有特定姓氏的人，或所有具有特定姓氏 - 名字組合的人。但如果你想找到所有具有特定名字的人，這個索引是沒有用的。

**多維索引（multi-dimensional index）** 是一種查詢多個列的更一般的方法，這對於地理空間資料尤為重要。例如，餐廳搜尋網站可能有一個數據庫，其中包含每個餐廳的經度和緯度。當用戶在地圖上檢視餐館時，網站需要搜尋使用者正在檢視的矩形地圖區域內的所有餐館。這需要一個二維範圍查詢，如下所示：

```sql
SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
                          AND longitude > -0.1162 AND longitude < -0.1004;
```

一個標準的 B 樹或者 LSM 樹索引不能夠高效地處理這種查詢：它可以返回一個緯度範圍內的所有餐館（但經度可能是任意值），或者返回在同一個經度範圍內的所有餐館（但緯度可能是北極和南極之間的任意地方），但不能同時滿足兩個條件。

一種選擇是使用 **空間填充曲線（space-filling curve）** 將二維位置轉換為單個數字，然後使用常規 B 樹索引【34】。更普遍的是，使用特殊化的空間索引，例如 R 樹。例如，PostGIS 使用 PostgreSQL 的通用 GiST 工具【35】將地理空間索引實現為 R 樹。這裡我們沒有足夠的地方來描述 R 樹，但是有大量的文獻可供參考。

有趣的是，多維索引不僅可以用於地理位置。例如，在電子商務網站上可以使用建立在（紅，綠，藍）維度上的三維索引來搜尋特定顏色範圍內的產品，也可以在天氣觀測資料庫中建立（日期，溫度）的二維索引，以便有效地搜尋 2013 年內的溫度在 25 至 30°C 之間的所有觀測資料。如果使用一維索引，你將不得不掃描 2013 年的所有記錄（不管溫度如何），然後透過溫度進行過濾，或者反之亦然。二維索引可以同時透過時間戳和溫度來收窄資料集。這個技術被 HyperDex 所使用【36】。

**全文搜尋和模糊索引**

到目前為止所討論的所有索引都假定你有確切的資料，並允許你查詢鍵的確切值或具有排序順序的鍵的值範圍。他們不允許你做的是搜尋**類似**的鍵，如拼寫錯誤的單詞。這種模糊的查詢需要不同的技術。

例如，全文搜尋引擎通常允許搜尋目標從一個單詞擴充套件為包括該單詞的同義詞，忽略單詞的語法變體，搜尋在相同文件中的近義詞，並且支援各種其他取決於文字的語言分析功能。為了處理文件或查詢中的拼寫錯誤，Lucene 能夠在一定的編輯距離內搜尋文字【37】（編輯距離 1 意味著單詞內發生了 1 個字母的新增、刪除或替換）。

正如 “[用 SSTables 製作 LSM 樹](#用SSTables製作LSM樹)” 中所提到的，Lucene 為其詞典使用了一個類似於 SSTable 的結構。這個結構需要一個小的記憶體索引，告訴查詢需要在排序檔案中哪個偏移量查詢鍵。在 LevelDB 中，這個記憶體中的索引是一些鍵的稀疏集合，但在 Lucene 中，記憶體中的索引是鍵中字元的有限狀態自動機，類似於 trie 【38】。這個自動機可以轉換成 Levenshtein 自動機，它支援在給定的編輯距離內有效地搜尋單詞【39】。

其他的模糊搜尋技術正朝著文件分類和機器學習的方向發展。更多詳細資訊請參閱資訊檢索教科書，例如【40】。

**在記憶體中儲存一切**

本章到目前為止討論的資料結構都是對硬碟限制的應對。與主記憶體相比，硬碟處理起來很麻煩。對於磁性硬碟和固態硬碟，如果要在讀取和寫入時獲得良好效能，則需要仔細地佈置硬碟上的資料。但是，我們能容忍這種麻煩，因為硬碟有兩個顯著的優點：它們是持久的（它們的內容在電源關閉時不會丟失），並且每 GB 的成本比 RAM 低。

隨著 RAM 變得更便宜，每 GB 成本的論據被侵蝕了。許多資料集不是那麼大，所以將它們全部儲存在記憶體中是非常可行的，包括可能分佈在多個機器上。這導致了記憶體資料庫的發展。

某些記憶體中的鍵值儲存（如 Memcached）僅用於快取，在重新啟動計算機時丟失的資料是可以接受的。但其他記憶體資料庫的目標是永續性，可以透過特殊的硬體（例如電池供電的 RAM）來實現，也可以將更改日誌寫入硬碟，還可以將定時快照寫入硬碟或者將記憶體中的狀態複製到其他機器上。

記憶體資料庫重新啟動時，需要從硬碟或透過網路從副本重新載入其狀態（除非使用特殊的硬體）。儘管寫入硬碟，它仍然是一個記憶體資料庫，因為硬碟僅出於永續性目的進行日誌追加，讀取請求完全由記憶體來處理。寫入硬碟同時還有運維上的好處：硬碟上的檔案可以很容易地由外部程式進行備份、檢查和分析。

諸如 VoltDB、MemSQL 和 Oracle TimesTen 等產品是具有關係模型的記憶體資料庫，供應商聲稱，透過消除與管理硬碟上的資料結構相關的所有開銷，他們可以提供巨大的效能改進【41,42】。RAM Cloud 是一個開源的記憶體鍵值儲存器，具有永續性（對記憶體和硬碟上的資料都使用日誌結構化方法）【43】。Redis 和 Couchbase 透過非同步寫入硬碟提供了較弱的永續性。

反直覺的是，記憶體資料庫的效能優勢並不是因為它們不需要從硬碟讀取的事實。只要有足夠的記憶體即使是基於硬碟的儲存引擎也可能永遠不需要從硬碟讀取，因為作業系統在記憶體中快取了最近使用的硬碟塊。相反，它們更快的原因在於省去了將記憶體資料結構編碼為硬碟資料結構的開銷【44】。

除了效能，記憶體資料庫的另一個有趣的地方是提供了難以用基於硬碟的索引實現的資料模型。例如，Redis 為各種資料結構（如優先順序佇列和集合）提供了類似資料庫的介面。因為它將所有資料儲存在記憶體中，所以它的實現相對簡單。

最近的研究表明，記憶體資料庫體系結構可以擴充套件到支援比可用記憶體更大的資料集，而不必重新採用以硬碟為中心的體系結構【45】。所謂的 **反快取（anti-caching）** 方法透過在記憶體不足的情況下將最近最少使用的資料從記憶體轉移到硬碟，並在將來再次訪問時將其重新載入到記憶體中。這與作業系統對虛擬記憶體和交換檔案的操作類似，但資料庫可以比作業系統更有效地管理記憶體，因為它可以按單個記錄的粒度工作，而不是整個記憶體頁面。儘管如此，這種方法仍然需要索引能完全放入記憶體中（就像本章開頭的 Bitcask 例子）。

如果 **非易失性儲存器（non-volatile memory, NVM）** 技術得到更廣泛的應用，可能還需要進一步改變儲存引擎設計【46】。目前這是一個新的研究領域，值得關注。

### 事務處理還是分析？

在早期的業務資料處理過程中，一次典型的資料庫寫入通常與一筆 *商業交易（commercial transaction）* 相對應：賣個貨、向供應商下訂單、支付員工工資等等。但隨著資料庫開始應用到那些不涉及到錢的領域，術語 **交易 / 事務（transaction）** 仍留了下來，用於指代一組讀寫操作構成的邏輯單元。

> 事務不一定具有 ACID（原子性，一致性，隔離性和永續性）屬性。事務處理只是意味著允許客戶端進行低延遲的讀取和寫入 —— 而不是隻能定期執行（例如每天一次）的批處理作業。我們在 [第七章](https://github.com/Vonng/ddia/blob/master/tw/ch7/README.md) 中討論 ACID 屬性，在 [第十章](https://github.com/Vonng/ddia/blob/master/tw/ch10/README.md) 中討論批處理。

即使資料庫開始被用於許多不同型別的資料，比如部落格文章的評論、遊戲中的動作、地址簿中的聯絡人等等，基本的訪問模式仍然類似於處理商業交易。應用程式通常使用索引透過某個鍵找少量記錄。根據使用者的輸入來插入或更新記錄。由於這些應用程式是互動式的，這種訪問模式被稱為 **線上事務處理（OLTP, OnLine Transaction Processing）**。

但是，資料庫也開始越來越多地用於資料分析，這些資料分析具有非常不同的訪問模式。通常，分析查詢需要掃描大量記錄，每個記錄只讀取幾列，並計算彙總統計資訊（如計數、總和或平均值），而不是將原始資料返回給使用者。例如，如果你的資料是一個銷售交易表，那麼分析查詢可能是：

* 一月份每個商店的總收入是多少？
* 在最近的推廣活動中多賣了多少香蕉？
* 哪個牌子的嬰兒食品最常與 X 品牌的尿布同時購買？

這些查詢通常由業務分析師編寫，並提供報告以幫助公司管理層做出更好的決策（商業智慧）。為了將這種使用資料庫的模式和事務處理區分開，它被稱為 **線上分析處理（OLAP, OnLine Analytic Processing）**【47】。OLTP 和 OLAP 之間的區別並不總是清晰的，但是一些典型的特徵在 [表 3-1](/vonng/content/tw/ch3.md) 中列出。

**表 3-1 比較事務處理和分析系統的特點**

|   屬性   |   事務處理系統 OLTP   |    分析系統 OLAP   |
| :----: | :-------------: | :------------: |
| 主要讀取模式 |   查詢少量記錄，按鍵讀取   |    在大批次記錄上聚合   |
| 主要寫入模式 |   隨機訪問，寫入要求低延時  | 批次匯入（ETL）或者事件流 |
|  主要使用者 | 終端使用者，透過 Web 應用 | 內部資料分析師，用於決策支援 |
|  處理的資料 |  資料的最新狀態（當前時間點） |   隨時間推移的歷史事件   |
|  資料集尺寸 |     GB \~ TB    |    TB \~ PB    |

起初，事務處理和分析查詢使用了相同的資料庫。SQL 在這方面已證明是非常靈活的：對於 OLTP 型別的查詢以及 OLAP 型別的查詢來說效果都很好。儘管如此，在二十世紀八十年代末和九十年代初期，企業有停止使用 OLTP 系統進行分析的趨勢，轉而在單獨的資料庫上執行分析。這個單獨的資料庫被稱為 **資料倉庫（data warehouse）**。

#### 資料倉庫

一個企業可能有幾十個不同的交易處理系統：面向終端客戶的網站、控制實體商店的收銀系統、倉庫庫存跟蹤、車輛路線規劃、供應鏈管理、員工管理等。這些系統中每一個都很複雜，需要專人維護，所以最終這些系統互相之間都是獨立執行的。

這些 OLTP 系統往往對業務運作至關重要，因而通常會要求 **高可用** 與 **低延遲**。所以 DBA 會密切關注他們的 OLTP 資料庫，他們通常不願意讓業務分析人員在 OLTP 資料庫上執行臨時的分析查詢，因為這些查詢通常開銷巨大，會掃描大部分資料集，這會損害同時在執行的事務的效能。

相比之下，資料倉庫是一個獨立的資料庫，分析人員可以查詢他們想要的內容而不影響 OLTP 操作【48】。資料倉庫包含公司各種 OLTP 系統中所有的只讀資料副本。從 OLTP 資料庫中提取資料（使用定期的資料轉儲或連續的更新流），轉換成適合分析的模式，清理並載入到資料倉庫中。將資料存入倉庫的過程稱為 “**抽取 - 轉換 - 載入（ETL）**”，如 [圖 3-8](https://github.com/Vonng/ddia/blob/master/img/fig3-8.png) 所示。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-8.png)

**圖 3-8 ETL 至資料倉庫的簡化提綱**

幾乎所有的大型企業都有資料倉庫，但在小型企業中幾乎聞所未聞。這可能是因為大多數小公司沒有這麼多不同的 OLTP 系統，大多數小公司只有少量的資料 —— 可以在傳統的 SQL 資料庫中查詢，甚至可以在電子表格中分析。在一家大公司裡，要做一些在一家小公司很簡單的事情，需要很多繁重的工作。

使用單獨的資料倉庫，而不是直接查詢 OLTP 系統進行分析的一大優勢是資料倉庫可針對分析類的訪問模式進行最佳化。事實證明，本章前半部分討論的索引演算法對於 OLTP 來說工作得很好，但對於處理分析查詢並不是很好。在本章的其餘部分中，我們將研究為分析而最佳化的儲存引擎。

**OLTP資料庫和資料倉庫之間的分歧**

資料倉庫的資料模型通常是關係型的，因為 SQL 通常很適合分析查詢。有許多圖形資料分析工具可以生成 SQL 查詢，視覺化結果，並允許分析人員探索資料（透過下鑽、切片和切塊等操作）。

表面上，一個數據倉庫和一個關係型 OLTP 資料庫看起來很相似，因為它們都有一個 SQL 查詢介面。然而，系統的內部看起來可能完全不同，因為它們針對非常不同的查詢模式進行了最佳化。現在許多資料庫供應商都只是重點支援事務處理負載和分析工作負載這兩者中的一個，而不是都支援。

一些資料庫（例如 Microsoft SQL Server 和 SAP HANA）支援在同一產品中進行事務處理和資料倉庫。但是，它們也正日益發展為兩套獨立的儲存和查詢引擎，只是這些引擎正好可以透過一個通用的 SQL 介面訪問【49,50,51】。

Teradata、Vertica、SAP HANA 和 ParAccel 等資料倉庫供應商通常使用昂貴的商業許可證銷售他們的系統。Amazon RedShift 是 ParAccel 的託管版本。最近，大量的開源 SQL-on-Hadoop 專案已經出現，它們還很年輕，但是正在與商業資料倉庫系統競爭，包括 Apache Hive、Spark SQL、Cloudera Impala、Facebook Presto、Apache Tajo 和 Apache Drill【52,53】。其中一些基於了谷歌 Dremel 的想法【54】。

#### 星型和雪花型：分析的模式

正如 [第二章](https://github.com/Vonng/ddia/blob/master/tw/ch2/README.md) 所探討的，根據應用程式的需要，在事務處理領域中使用了大量不同的資料模型。另一方面，在分析型業務中，資料模型的多樣性則少得多。許多資料倉庫都以相當公式化的方式使用，被稱為星型模式（也稱為維度建模【55】）。

[圖 3-9](https://github.com/Vonng/ddia/blob/master/img/fig3-9.png) 中的示例模式顯示了可能在食品零售商處找到的資料倉庫。在模式的中心是一個所謂的事實表（在這個例子中，它被稱為 `fact_sales`）。事實表的每一行代表在特定時間發生的事件（這裡，每一行代表客戶購買的產品）。如果我們分析的是網站流量而不是零售量，則每行可能代表一個使用者的頁面瀏覽或點選。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-9.png)

**圖 3-9 用於資料倉庫的星型模式的示例**

通常情況下，事實被視為單獨的事件，因為這樣可以在以後分析中獲得最大的靈活性。但是，這意味著事實表可以變得非常大。像蘋果、沃爾瑪或 eBay 這樣的大企業在其資料倉庫中可能有幾十 PB 的交易歷史，其中大部分儲存在事實表中【56】。

事實表中的一些列是屬性，例如產品銷售的價格和從供應商那裡購買的成本（可以用來計算利潤率）。事實表中的其他列是對其他表（稱為維度表）的外部索引鍵引用。由於事實表中的每一行都表示一個事件，因此這些維度代表事件發生的物件、內容、地點、時間、方式和原因。

例如，在 [圖 3-9](https://github.com/Vonng/ddia/blob/master/img/fig3-9.png) 中，其中一個維度是已售出的產品。`dim_product` 表中的每一行代表一種待售產品，包括庫存單位（SKU）、產品描述、品牌名稱、類別、脂肪含量、包裝尺寸等。`fact_sales` 表中的每一行都使用外部索引鍵表明在特定交易中銷售了什麼產品。（簡單起見，如果客戶一次購買了幾種不同的產品，則它們在事實表中被表示為單獨的行）。

甚至日期和時間也通常使用維度表來表示，因為這允許對日期的附加資訊（諸如公共假期）進行編碼，從而允許區分假期和非假期的銷售查詢。

“星型模式” 這個名字來源於這樣一個事實，即當我們對錶之間的關係進行視覺化時，事實表在中間，被維度表包圍；與這些表的連線就像星星的光芒。

這個模板的變體被稱為雪花模式，其中維度被進一步分解為子維度。例如，品牌和產品類別可能有單獨的表格，並且 `dim_product` 表格中的每一行都可以將品牌和類別作為外部索引鍵引用，而不是將它們作為字串儲存在 `dim_product` 表格中。雪花模式比星形模式更規範化，但是星形模式通常是首選，因為分析師使用它更簡單【55】。

在典型的資料倉庫中，表格通常非常寬：事實表通常有 100 列以上，有時甚至有數百列【51】。維度表也可以是非常寬的，因為它們包括了所有可能與分析相關的元資料 —— 例如，`dim_store` 表可以包括在每個商店提供哪些服務的細節、它是否具有店內麵包房、店面面積、商店第一次開張的日期、最近一次改造的時間、離最近的高速公路的距離等等。

### 列式儲存

如果事實表中有萬億行和數 PB 的資料，那麼高效地儲存和查詢它們就成為一個具有挑戰性的問題。維度表通常要小得多（數百萬行），所以在本節中我們將主要關注事實表的儲存。

儘管事實表通常超過 100 列，但典型的資料倉庫查詢一次只會訪問其中 4 個或 5 個列（ “`SELECT *`” 查詢很少用於分析）【51】。以 [例 3-1](/vonng/content/tw/ch3.md) 中的查詢為例：它訪問了大量的行（在 2013 年中所有購買了水果或糖果的記錄），但只需訪問 `fact_sales` 表的三列：`date_key, product_sk, quantity`。該查詢忽略了所有其他的列。

**例 3-1 分析人們是否更傾向於在一週的某一天購買新鮮水果或糖果**

```sql
SELECT
  dim_date.weekday,
  dim_product.category,
  SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
  JOIN dim_date ON fact_sales.date_key = dim_date.date_key
  JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
  dim_date.year = 2013 AND
  dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
  dim_date.weekday, dim_product.category;
```

我們如何有效地執行這個查詢？

在大多數 OLTP 資料庫中，儲存都是以面向行的方式進行佈局的：表格的一行中的所有值都相鄰儲存。文件資料庫也是相似的：整個文件通常儲存為一個連續的位元組序列。你可以在 [圖 3-1](https://github.com/Vonng/ddia/blob/master/img/fig3-1.png) 的 CSV 例子中看到這個。

為了處理像 [例 3-1](/vonng/content/tw/ch3.md) 這樣的查詢，你可能在 `fact_sales.date_key`、`fact_sales.product_sk` 上有索引，它們告訴儲存引擎在哪裡查詢特定日期或特定產品的所有銷售情況。但是，面向行的儲存引擎仍然需要將所有這些行（每個包含超過 100 個屬性）從硬碟載入到記憶體中，解析它們，並過濾掉那些不符合要求的屬性。這可能需要很長時間。

列式儲存背後的想法很簡單：不要將所有來自一行的值儲存在一起，而是將來自每一列的所有值儲存在一起。如果每個列式儲存在一個單獨的檔案中，查詢只需要讀取和解析查詢中使用的那些列，這可以節省大量的工作。這個原理如 [圖 3-10](https://github.com/Vonng/ddia/blob/master/img/fig3-10.png) 所示。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-10.png)

**圖 3-10 按列儲存關係型資料，而不是行**

> 列式儲存在關係資料模型中是最容易理解的，但它同樣適用於非關係資料。例如，Parquet【57】是一種列式儲存格式，支援基於 Google 的 Dremel 的文件資料模型【54】。

列式儲存佈局依賴於每個列檔案包含相同順序的行。因此，如果你需要重新組裝完整的行，你可以從每個單獨的列檔案中獲取第 23 項，並將它們放在一起形成表的第 23 行。

#### 列壓縮

除了僅從硬碟載入查詢所需的列以外，我們還可以透過壓縮資料來進一步降低對硬碟吞吐量的需求。幸運的是，列式儲存通常很適合壓縮。

看看 [圖 3-10](https://github.com/Vonng/ddia/blob/master/img/fig3-10.png) 中每一列的值序列：它們通常看起來是相當重複的，這是壓縮的好兆頭。根據列中的資料，可以使用不同的壓縮技術。在資料倉庫中特別有效的一種技術是點陣圖編碼，如 [圖 3-11](https://github.com/Vonng/ddia/blob/master/img/fig3-11.png) 所示。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-11.png)

**圖 3-11 壓縮的點陣圖索引儲存佈局**

通常情況下，一列中不同值的數量與行數相比要小得多（例如，零售商可能有數十億的銷售交易，但只有 100,000 個不同的產品）。現在我們可以拿一個有 n 個不同值的列，並把它轉換成 n 個獨立的點陣圖：每個不同值對應一個位圖，每行對應一個位元位。如果該行具有該值，則該位為 1，否則為 0。

如果 n 非常小（例如，國家 / 地區列可能有大約 200 個不同的值），則這些點陣圖可以將每行儲存成一個位元位。但是，如果 n 更大，大部分點陣圖中將會有很多的零（我們說它們是稀疏的）。在這種情況下，點陣圖可以另外再進行遊程編碼（run-length encoding，一種無損資料壓縮技術），如 [圖 3-11](https://github.com/Vonng/ddia/blob/master/content/tw/fig3-11.png) 底部所示。這可以使列的編碼非常緊湊。

這些點陣圖索引非常適合資料倉庫中常見的各種查詢。例如：

```sql
WHERE product_sk IN（30，68，69）
```

載入 `product_sk = 30`、`product_sk = 68` 和 `product_sk = 69` 這三個點陣圖，並計算三個點陣圖的按位或（OR），這可以非常有效地完成。

```sql
WHERE product_sk = 31 AND store_sk = 3
```

載入 `product_sk = 31` 和 `store_sk = 3` 的點陣圖，並計算按位與（AND）。這是因為列按照相同的順序包含行，因此一列的點陣圖中的第 k 位和另一列的點陣圖中的第 k 位對應相同的行。

對於不同種類的資料，也有各種不同的壓縮方案，但我們不會詳細討論它們，請參閱【58】的概述。

> **列式儲存和列族**
>
> Cassandra 和 HBase 有一個列族（column families）的概念，他們從 Bigtable 繼承【9】。然而，把它們稱為列式（column-oriented）是非常具有誤導性的：在每個列族中，它們將一行中的所有列與行鍵一起儲存，並且不使用列壓縮。因此，Bigtable 模型仍然主要是面向行的。

**記憶體頻寬和向量化處理**

對於需要掃描數百萬行的資料倉庫查詢來說，一個巨大的瓶頸是從硬盤獲取資料到記憶體的頻寬。但是，這不是唯一的瓶頸。分析型資料庫的開發人員還需要有效地利用記憶體到 CPU 快取的頻寬，避免 CPU 指令處理流水線中的分支預測錯誤和閒置等待，以及在現代 CPU 上使用單指令多資料（SIMD）指令來加速運算【59,60】。

除了減少需要從硬碟載入的資料量以外，列式儲存佈局也可以有效利用 CPU 週期。例如，查詢引擎可以將一整塊壓縮好的列資料放進 CPU 的 L1 快取中，然後在緊密的迴圈（即沒有函式呼叫）中遍歷。相比於每條記錄的處理都需要大量函式呼叫和條件判斷的程式碼，CPU 執行這樣一個迴圈要快得多。列壓縮允許列中的更多行被同時放進容量有限的 L1 快取。前面描述的按位 “與” 和 “或” 運算子可以被設計為直接在這樣的壓縮列資料塊上操作。這種技術被稱為向量化處理（vectorized processing）【58,49】。

#### 列式儲存中的排序順序

在列式儲存中，儲存行的順序並不關鍵。按插入順序儲存它們是最簡單的，因為插入一個新行只需要追加到每個列檔案。但是，我們也可以選擇按某種順序來排列資料，就像我們之前對 SSTables 所做的那樣，並將其用作索引機制。

注意，對每列分別執行排序是沒有意義的，因為那樣就沒法知道不同列中的哪些項屬於同一行。我們只能在明確一列中的第 k 項與另一列中的第 k 項屬於同一行的情況下，才能重建出完整的行。

相反，資料的排序需要對一整行統一操作，即使它們的儲存方式是按列的。資料庫管理員可以根據他們對常用查詢的瞭解，來選擇表格中用來排序的列。例如，如果查詢通常以日期範圍為目標，例如“上個月”，則可以將 `date_key` 作為第一個排序鍵。這樣查詢最佳化器就可以只掃描近1個月範圍的行了，這比掃描所有行要快得多。

對於第一排序列中具有相同值的行，可以用第二排序列來進一步排序。例如，如果 `date_key` 是 [圖 3-10](https://github.com/Vonng/ddia/blob/master/img/fig3-10.png) 中的第一個排序關鍵字，那麼 `product_sk` 可能是第二個排序關鍵字，以便同一天的同一產品的所有銷售資料都被儲存在相鄰位置。這將有助於需要在特定日期範圍內按產品對銷售進行分組或過濾的查詢。

按順序排序的另一個好處是它可以幫助壓縮列。如果主要排序列沒有太多個不同的值，那麼在排序之後，將會得到一個相同的值連續重複多次的序列。一個簡單的遊程編碼（就像我們用於 [圖 3-11](https://github.com/Vonng/ddia/blob/master/img/fig3-11.png) 中的點陣圖一樣）可以將該列壓縮到幾 KB —— 即使表中有數十億行。

第一個排序鍵的壓縮效果最強。第二和第三個排序鍵會更混亂，因此不會有這麼長的連續的重複值。排序優先順序更低的列以幾乎隨機的順序出現，所以可能不會被壓縮。但對前幾列做排序在整體上仍然是有好處的。

**幾個不同的排序順序**

對這個想法，有一個巧妙的擴充套件被 C-Store 發現，並在商業資料倉庫 Vertica 中被採用【61,62】：既然不同的查詢受益於不同的排序順序，為什麼不以幾種不同的方式來儲存相同的資料呢？反正資料都需要做備份，以防單點故障時丟失資料。因此你可以用不同排序方式來儲存冗餘資料，以便在處理查詢時，呼叫最適合查詢模式的版本。

在一個列式儲存中有多個排序順序有點類似於在一個面向行的儲存中有多個次級索引。但最大的區別在於面向行的儲存將每一行儲存在一個地方（在堆檔案或聚集索引中），次級索引只包含指向匹配行的指標。在列式儲存中，通常在其他地方沒有任何指向資料的指標，只有包含值的列。

#### 寫入列式儲存

這些最佳化在資料倉庫中是有意義的，因為其負載主要由分析人員執行的大型只讀查詢組成。列式儲存、壓縮和排序都有助於更快地讀取這些查詢。然而，他們的缺點是寫入更加困難。

使用 B 樹的就地更新方法對於壓縮的列是不可能的。如果你想在排序表的中間插入一行，你很可能不得不重寫所有的列檔案。由於行由列中的位置標識，因此插入必須對所有列進行一致地更新。

幸運的是，本章前面已經看到了一個很好的解決方案：LSM 樹。所有的寫操作首先進入一個記憶體中的儲存，在這裡它們被新增到一個已排序的結構中，並準備寫入硬碟。記憶體中的儲存是面向行還是列的並不重要。當已經積累了足夠的寫入資料時，它們將與硬碟上的列檔案合併，並批次寫入新檔案。這基本上是 Vertica 所做的【62】。

查詢操作需要檢查硬碟上的列資料和記憶體中的最近寫入，並將兩者的結果合併起來。但是，查詢最佳化器對使用者隱藏了這個細節。從分析師的角度來看，透過插入、更新或刪除操作進行修改的資料會立即反映在後續的查詢中。

#### 聚合：資料立方體和物化檢視

並非所有資料倉庫都需要採用列式儲存：傳統的面向行的資料庫和其他一些架構也被使用。然而，列式儲存可以顯著加快專門的分析查詢，所以它正在迅速變得流行起來【51,63】。

資料倉庫的另一個值得一提的方面是物化聚合（materialized aggregates）。如前所述，資料倉庫查詢通常涉及一個聚合函式，如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果相同的聚合被許多不同的查詢使用，那麼每次都透過原始資料來處理可能太浪費了。為什麼不將一些查詢使用最頻繁的計數或總和快取起來？

建立這種快取的一種方式是物化檢視（Materialized View）。在關係資料模型中，它通常被定義為一個標準（虛擬）檢視：一個類似於表的物件，其內容是一些查詢的結果。不同的是，物化檢視是查詢結果的實際副本，會被寫入硬碟，而虛擬檢視只是編寫查詢的一個捷徑。從虛擬檢視讀取時，SQL 引擎會將其展開到檢視的底層查詢中，然後再處理展開的查詢。

當底層資料發生變化時，物化檢視需要更新，因為它是資料的非規範化副本。資料庫可以自動完成該操作，但是這樣的更新使得寫入成本更高，這就是在 OLTP 資料庫中不經常使用物化檢視的原因。在讀取繁重的資料倉庫中，它們可能更有意義（它們是否實際上改善了讀取效能取決於使用場景）。

物化檢視的常見特例稱為資料立方體或 OLAP 立方【64】。它是按不同維度分組的聚合網格。[圖 3-12](https://github.com/Vonng/ddia/blob/master/img/fig3-12.png) 顯示了一個例子。

![](https://github.com/Vonng/ddia/blob/master/img/fig3-12.png)

**圖 3-12 資料立方的兩個維度，透過求和聚合**

想象一下，現在每個事實都只有兩個維度表的外部索引鍵 —— 在 [圖 3-12](https://github.com/Vonng/ddia/blob/master/img/fig3-12.png) 中分別是日期和產品。你現在可以繪製一個二維表格，一個軸線上是日期，另一個軸線上是產品。每個單元格包含具有該日期 - 產品組合的所有事實的屬性（例如 `net_price`）的聚合（例如 `SUM`）。然後，你可以沿著每行或每列應用相同的彙總，並獲得減少了一個維度的彙總（按產品的銷售額，無論日期，或者按日期的銷售額，無論產品）。

一般來說，事實往往有兩個以上的維度。在圖 3-9 中有五個維度：日期、產品、商店、促銷和客戶。要想象一個五維超立方體是什麼樣子是很困難的，但是原理是一樣的：每個單元格都包含特定日期 - 產品 - 商店 - 促銷 - 客戶組合的銷售額。這些值可以在每個維度上求和彙總。

物化資料立方體的優點是可以讓某些查詢變得非常快，因為它們已經被有效地預先計算了。例如，如果你想知道每個商店的總銷售額，則只需檢視合適維度的總計，而無需掃描數百萬行的原始資料。

資料立方體的缺點是不具有查詢原始資料的靈活性。例如，沒有辦法計算有多少比例的銷售來自成本超過 100 美元的專案，因為價格不是其中的一個維度。因此，大多數資料倉庫試圖保留儘可能多的原始資料，並將聚合資料（如資料立方體）僅用作某些查詢的效能提升手段。

### 本章小結

在本章中，我們試圖深入瞭解資料庫是如何處理儲存和檢索的。將資料儲存在資料庫中會發生什麼？稍後再次查詢資料時資料庫會做什麼？

在高層次上，我們看到儲存引擎分為兩大類：針對 **事務處理（OLTP）** 最佳化的儲存引擎和針對 **線上分析（OLAP）** 最佳化的儲存引擎。這兩類使用場景的訪問模式之間有很大的區別：

* OLTP 系統通常面向終端使用者，這意味著系統可能會收到大量的請求。為了處理負載，應用程式在每個查詢中通常只訪問少量的記錄。應用程式使用某種鍵來請求記錄，儲存引擎使用索引來查詢所請求的鍵的資料。硬碟查詢時間往往是這裡的瓶頸。
* 資料倉庫和類似的分析系統會少見一些，因為它們主要由業務分析人員使用，而不是終端使用者。它們的查詢量要比 OLTP 系統少得多，但通常每個查詢開銷高昂，需要在短時間內掃描數百萬條記錄。硬碟頻寬（而不是查詢時間）往往是瓶頸，列式儲存是針對這種工作負載的日益流行的解決方案。

在 OLTP 這一邊，我們能看到兩派主流的儲存引擎：

* 日誌結構學派：只允許追加到檔案和刪除過時的檔案，但不會更新已經寫入的檔案。Bitcask、SSTables、LSM 樹、LevelDB、Cassandra、HBase、Lucene 等都屬於這個類別。
* 就地更新學派：將硬碟視為一組可以覆寫的固定大小的頁面。B 樹是這種理念的典範，用在所有主要的關係資料庫和許多非關係型資料庫中。

日誌結構的儲存引擎是相對較新的技術。他們的主要想法是，透過系統性地將隨機訪問寫入轉換為硬碟上的順序寫入，由於硬碟驅動器和固態硬碟的效能特點，可以實現更高的寫入吞吐量。

關於 OLTP，我們最後還介紹了一些更複雜的索引結構，以及針對所有資料都放在記憶體裡而最佳化的資料庫。

然後，我們暫時放下了儲存引擎的內部細節，查看了典型資料倉庫的高階架構，並說明了為什麼分析工作負載與 OLTP 差別很大：當你的查詢需要在大量行中順序掃描時，索引的重要性就會降低很多。相反，非常緊湊地編碼資料變得非常重要，以最大限度地減少查詢需要從硬碟讀取的資料量。我們討論了列式儲存如何幫助實現這一目標。

作為一名應用程式開發人員，如果你掌握了有關儲存引擎內部的知識，那麼你就能更好地瞭解哪種工具最適合你的特定應用程式。當你調整資料庫的最佳化引數時，這種理解讓你能夠設想增減某個值會產生怎樣的效果。

儘管本章不能讓你成為一個特定儲存引擎的調參專家，但它至少大機率使你有了足夠的概念與詞彙儲備去讀懂你所選擇的資料庫的文件。

### 參考文獻

1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman: *Data Structures and Algorithms*. Addison-Wesley, 1983. ISBN: 978-0-201-00023-8
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: *Introduction to Algorithms*, 3rd edition. MIT Press, 2009. ISBN: 978-0-262-53305-8
3. Justin Sheehy and David Smith: “[Bitcask: A Log-Structured Hash Table for Fast Key/Value Data](https://riak.com/assets/bitcask-intro.pdf),” Basho Technologies, April 2010.
4. Yinan Li, Bingsheng He, Robin Jun Yang, et al.: “[Tree Indexing on Solid State Drives](http://pages.cs.wisc.edu/~yinan/paper/fdtree_pvldb.pdf),” *Proceedings of the VLDB Endowment*, volume 3, number 1, pages 1195–1206, September 2010.
5. Goetz Graefe: “[Modern B-Tree Techniques](https://citeseerx.ist.psu.edu/document?repid=rep1\&type=pdf\&doi=0b19f413ffb5bc68b43f3bd05a97c282a7c6d6ab),” *Foundations and Trends in Databases*, volume 3, number 4, pages 203–402, August 2011. [doi:10.1561/1900000028](http://dx.doi.org/10.1561/1900000028)
6. Jeffrey Dean and Sanjay Ghemawat: “[LevelDB Implementation Notes](https://github.com/google/leveldb/blob/master/doc/impl.md),” *github.com*.
7. Dhruba Borthakur: “[The History of RocksDB](https://rocksdb.blogspot.com/2013/11/the-history-of-rocksdb.html),” *rocksdb.blogspot.com*, November 24, 2013.
8. Matteo Bertozzi: “[Apache HBase I/O – HFile](https://blog.cloudera.com/apache-hbase-i-o-hfile/),” *blog.cloudera.com*, June 29, 2012.
9. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, et al.: “[Bigtable: A Distributed Storage System for Structured Data](https://research.google/pubs/pub27898/),” at *7th USENIX Symposium on Operating System Design and Implementation* (OSDI), November 2006.
10. Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil: “[The Log-Structured Merge-Tree (LSM-Tree)](http://www.cs.umb.edu/~poneil/lsmtree.pdf),” *Acta Informatica*, volume 33, number 4, pages 351–385, June 1996. [doi:10.1007/s002360050048](http://dx.doi.org/10.1007/s002360050048)
11. Mendel Rosenblum and John K. Ousterhout: “[The Design and Implementation of a Log-Structured File System](http://research.cs.wisc.edu/areas/os/Qual/papers/lfs.pdf),” *ACM Transactions on Computer Systems*, volume 10, number 1, pages 26–52, February 1992. [doi:10.1145/146941.146943](http://dx.doi.org/10.1145/146941.146943)
12. Adrien Grand: “[What Is in a Lucene Index?](http://www.slideshare.net/lucenerevolution/what-is-inaluceneagrandfinal),” at *Lucene/Solr Revolution*, November 14, 2013.
13. Deepak Kandepet: “[Hacking Lucene—The Index Format](https://web.archive.org/web/20160316190830/http://hackerlabs.github.io/blog/2011/10/01/hacking-lucene-the-index-format/index.html),” *hackerlabs.github.io*, October 1, 2011.
14. Michael McCandless: “[Visualizing Lucene's Segment Merges](http://blog.mikemccandless.com/2011/02/visualizing-lucenes-segment-merges.html),” *blog.mikemccandless.com*, February 11, 2011.
15. Burton H. Bloom: “[Space/Time Trade-offs in Hash Coding with Allowable Errors](https://people.cs.umass.edu/~emery/classes/cmpsci691st/readings/Misc/p422-bloom.pdf),” *Communications of the ACM*, volume 13, number 7, pages 422–426, July 1970. [doi:10.1145/362686.362692](http://dx.doi.org/10.1145/362686.362692)
16. “[Operating Cassandra: Compaction](https://cassandra.apache.org/doc/latest/operating/compaction/index.html),” Apache Cassandra Documentation v4.0, 2016.
17. Rudolf Bayer and Edward M. McCreight: “[Organization and Maintenance of Large Ordered Indices](https://apps.dtic.mil/sti/citations/AD0712079),” Boeing Scientific Research Laboratories, Mathematical and Information Sciences Laboratory, report no. 20, July 1970.
18. Douglas Comer: “[The Ubiquitous B-Tree](https://carlosproal.com/ir/papers/p121-comer.pdf),” *ACM Computing Surveys*, volume 11, number 2, pages 121–137, June 1979. [doi:10.1145/356770.356776](http://dx.doi.org/10.1145/356770.356776)
19. Emmanuel Goossaert: “[Coding for SSDs](http://codecapsule.com/2014/02/12/coding-for-ssds-part-1-introduction-and-table-of-contents/),” *codecapsule.com*, February 12, 2014.
20. C. Mohan and Frank Levine: “[ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging](http://www.ics.uci.edu/~cs223/papers/p371-mohan.pdf),” at *ACM International Conference on Management of Data* (SIGMOD), June 1992. [doi:10.1145/130283.130338](http://dx.doi.org/10.1145/130283.130338)
21. Howard Chu: “[LDAP at Lightning Speed](https://buildstuff14.sched.com/event/08a1a368e272eb599a52e08b4c3c779d),” at *Build Stuff '14*, November 2014.
22. Bradley C. Kuszmaul: “[A Comparison of Fractal Trees to Log-Structured Merge (LSM) Trees](http://www.pandademo.com/wp-content/uploads/2017/12/A-Comparison-of-Fractal-Trees-to-Log-Structured-Merge-LSM-Trees.pdf),” *tokutek.com*, April 22, 2014.
23. Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, et al.: “[Designing Access Methods: The RUM Conjecture](http://openproceedings.org/2016/conf/edbt/paper-12.pdf),” at *19th International Conference on Extending Database Technology* (EDBT), March 2016. [doi:10.5441/002/edbt.2016.42](http://dx.doi.org/10.5441/002/edbt.2016.42)
24. Peter Zaitsev: “[Innodb Double Write](https://www.percona.com/blog/2006/08/04/innodb-double-write/),” *percona.com*, August 4, 2006.
25. Tomas Vondra: “[On the Impact of Full-Page Writes](https://www.enterprisedb.com/blog/impact-full-page-writes),” *blog.2ndquadrant.com*, November 23, 2016.
26. Mark Callaghan: “[The Advantages of an LSM vs a B-Tree](http://smalldatum.blogspot.co.uk/2016/01/summary-of-advantages-of-lsm-vs-b-tree.html),” *smalldatum.blogspot.co.uk*, January 19, 2016.
27. Mark Callaghan: “[Choosing Between Efficiency and Performance with RocksDB](https://codemesh.io/codemesh2016/mark-callaghan),” at *Code Mesh*, November 4, 2016.
28. Michi Mutsuzaki: “[MySQL vs. LevelDB](https://github.com/m1ch1/mapkeeper/wiki/MySQL-vs.-LevelDB),” *github.com*, August 2011.
29. Benjamin Coverston, Jonathan Ellis, et al.: “[CASSANDRA-1608: Redesigned Compaction](https://issues.apache.org/jira/browse/CASSANDRA-1608), *issues.apache.org*, July 2011.
30. Igor Canadi, Siying Dong, and Mark Callaghan: “[RocksDB Tuning Guide](https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide),” *github.com*, 2016.
31. [*MySQL 5.7 Reference Manual*](http://dev.mysql.com/doc/refman/5.7/en/index.html). Oracle, 2014.
32. [*Books Online for SQL Server 2012*](https://learn.microsoft.com/en-us/previous-versions/sql/sql-server-2012/ms130214\(v=sql.110\)). Microsoft, 2012.
33. Joe Webb: “[Using Covering Indexes to Improve Query Performance](https://www.simple-talk.com/sql/learn-sql-server/using-covering-indexes-to-improve-query-performance/),” *simple-talk.com*, 29 September 2008.
34. Frank Ramsak, Volker Markl, Robert Fenk, et al.: “[Integrating the UB-Tree into a Database System Kernel](http://www.vldb.org/conf/2000/P263.pdf),” at *26th International Conference on Very Large Data Bases* (VLDB), September 2000.
35. The PostGIS Development Group: “[PostGIS 2.1.2dev Manual](http://postgis.net/docs/manual-2.1/),” *postgis.net*, 2014.
36. Robert Escriva, Bernard Wong, and Emin Gün Sirer: “[HyperDex: A Distributed, Searchable Key-Value Store](http://www.cs.princeton.edu/courses/archive/fall13/cos518/papers/hyperdex.pdf),” at *ACM SIGCOMM Conference*, August 2012. [doi:10.1145/2377677.2377681](http://dx.doi.org/10.1145/2377677.2377681)
37. Michael McCandless: “[Lucene's FuzzyQuery Is 100 Times Faster in 4.0](http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html),” *blog.mikemccandless.com*, March 24, 2011.
38. Steffen Heinz, Justin Zobel, and Hugh E. Williams: “[Burst Tries: A Fast, Efficient Data Structure for String Keys](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.3499),” *ACM Transactions on Information Systems*, volume 20, number 2, pages 192–223, April 2002. [doi:10.1145/506309.506312](http://dx.doi.org/10.1145/506309.506312)
39. Klaus U. Schulz and Stoyan Mihov: “[Fast String Correction with Levenshtein Automata](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652),” *International Journal on Document Analysis and Recognition*, volume 5, number 1, pages 67–85, November 2002. [doi:10.1007/s10032-002-0082-8](http://dx.doi.org/10.1007/s10032-002-0082-8)
40. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze: [*Introduction to Information Retrieval*](http://nlp.stanford.edu/IR-book/). Cambridge University Press, 2008. ISBN: 978-0-521-86571-5, available online at *nlp.stanford.edu/IR-book*
41. Michael Stonebraker, Samuel Madden, Daniel J. Abadi, et al.: “[The End of an Architectural Era (It’s Time for a Complete Rewrite)](http://nms.csail.mit.edu/~stavros/pubs/hstore.pdf),” at *33rd International Conference on Very Large Data Bases* (VLDB), September 2007.
42. “[VoltDB Technical Overview White Paper](https://www.voltdb.com/files/voltdb-technical-overview/),” VoltDB, 2014.
43. Stephen M. Rumble, Ankita Kejriwal, and John K. Ousterhout: “[Log-Structured Memory for DRAM-Based Storage](https://www.usenix.org/system/files/conference/fast14/fast14-paper_rumble.pdf),” at *12th USENIX Conference on File and Storage Technologies* (FAST), February 2014.
44. Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker: “[OLTP Through the Looking Glass, and What We Found There](http://hstore.cs.brown.edu/papers/hstore-lookingglass.pdf),” at *ACM International Conference on Management of Data* (SIGMOD), June 2008. [doi:10.1145/1376616.1376713](http://dx.doi.org/10.1145/1376616.1376713)
45. Justin DeBrabant, Andrew Pavlo, Stephen Tu, et al.: “[Anti-Caching: A New Approach to Database Management System Architecture](http://www.vldb.org/pvldb/vol6/p1942-debrabant.pdf),” *Proceedings of the VLDB Endowment*, volume 6, number 14, pages 1942–1953, September 2013.
46. Joy Arulraj, Andrew Pavlo, and Subramanya R. Dulloor: “[Let's Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems](http://www.pdl.cmu.edu/PDL-FTP/NVM/storage.pdf),” at *ACM International Conference on Management of Data* (SIGMOD), June 2015. [doi:10.1145/2723372.2749441](http://dx.doi.org/10.1145/2723372.2749441)
47. Edgar F. Codd, S. B. Codd, and C. T. Salley: “[Providing OLAP to User-Analysts: An IT Mandate](https://pdfs.semanticscholar.org/a0bd/1491a54a4de428c5eef9b836ef6ee2915fe7.pdf),” E. F. Codd Associates, 1993.
48. Surajit Chaudhuri and Umeshwar Dayal: “[An Overview of Data Warehousing and OLAP Technology](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/sigrecord.pdf),” *ACM SIGMOD Record*, volume 26, number 1, pages 65–74, March 1997. [doi:10.1145/248603.248616](http://dx.doi.org/10.1145/248603.248616)
49. Per-Åke Larson, Cipri Clinciu, Campbell Fraser, et al.: “[Enhancements to SQL Server Column Stores](http://research.microsoft.com/pubs/193599/Apollo3%20-%20Sigmod%202013%20-%20final.pdf),” at *ACM International Conference on Management of Data* (SIGMOD), June 2013.
50. Franz Färber, Norman May, Wolfgang Lehner, et al.: “[The SAP HANA Database – An Architecture Overview](http://sites.computer.org/debull/A12mar/hana.pdf),” *IEEE Data Engineering Bulletin*, volume 35, number 1, pages 28–33, March 2012.
51. Michael Stonebraker: “[The Traditional RDBMS Wisdom Is (Almost Certainly) All Wrong](http://slideshot.epfl.ch/talks/166),” presentation at *EPFL*, May 2013.
52. Daniel J. Abadi: “[Classifying the SQL-on-Hadoop Solutions](https://web.archive.org/web/20150622074951/http://hadapt.com/blog/2013/10/02/classifying-the-sql-on-hadoop-solutions/),” *hadapt.com*, October 2, 2013.
53. Marcel Kornacker, Alexander Behm, Victor Bittorf, et al.: “[Impala: A Modern, Open-Source SQL Engine for Hadoop](http://pandis.net/resources/cidr15impala.pdf),” at *7th Biennial Conference on Innovative Data Systems Research* (CIDR), January 2015.
54. Sergey Melnik, Andrey Gubarev, Jing Jing Long, et al.: “[Dremel: Interactive Analysis of Web-Scale Datasets](https://research.google/pubs/pub36632/),” at *36th International Conference on Very Large Data Bases* (VLDB), pages 330–339, September 2010.
55. Ralph Kimball and Margy Ross: *The Data Warehouse Toolkit: The Definitive Guide to Dimensional Modeling*, 3rd edition. John Wiley & Sons, July 2013. ISBN: 978-1-118-53080-1
56. Derrick Harris: “[Why Apple, eBay, and Walmart Have Some of the Biggest Data Warehouses You’ve Ever Seen](https://web.archive.org/web/20221129085658/https://old.gigaom.com/2013/03/27/why-apple-ebay-and-walmart-have-some-of-the-biggest-data-warehouses-youve-ever-seen/),” *gigaom.com*, March 27, 2013.
57. Julien Le Dem: “[Dremel Made Simple with Parquet](https://blog.twitter.com/engineering/en_us/a/2013/dremel-made-simple-with-parquet.html),” *blog.twitter.com*, September 11, 2013.
58. Daniel J. Abadi, Peter Boncz, Stavros Harizopoulos, et al.: “[The Design and Implementation of Modern Column-Oriented Database Systems](http://cs-www.cs.yale.edu/homes/dna/papers/abadi-column-stores.pdf),” *Foundations and Trends in Databases*, volume 5, number 3, pages 197–280, December 2013. [doi:10.1561/1900000024](http://dx.doi.org/10.1561/1900000024)
59. Peter Boncz, Marcin Zukowski, and Niels Nes: “[MonetDB/X100: Hyper-Pipelining Query Execution](http://cidrdb.org/cidr2005/papers/P19.pdf),” at *2nd Biennial Conference on Innovative Data Systems Research* (CIDR), January 2005.
60. Jingren Zhou and Kenneth A. Ross: “[Implementing Database Operations Using SIMD Instructions](http://www1.cs.columbia.edu/~kar/pubsk/simd.pdf),” at *ACM International Conference on Management of Data* (SIGMOD), pages 145–156, June 2002. [doi:10.1145/564691.564709](http://dx.doi.org/10.1145/564691.564709)
61. Michael Stonebraker, Daniel J. Abadi, Adam Batkin, et al.: “[C-Store: A Column-oriented DBMS](http://www.cs.umd.edu/~abadi/vldb.pdf),” at *31st International Conference on Very Large Data Bases* (VLDB), pages 553–564, September 2005.
62. Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, et al.: “[The Vertica Analytic Database: C-Store 7 Years Later](http://vldb.org/pvldb/vol5/p1790_andrewlamb_vldb2012.pdf),” *Proceedings of the VLDB Endowment*, volume 5, number 12, pages 1790–1801, August 2012.
63. Julien Le Dem and Nong Li: “[Efficient Data Storage for Analytics with Apache Parquet 2.0](http://www.slideshare.net/julienledem/th-210pledem),” at *Hadoop Summit*, San Jose, June 2014.
64. Jim Gray, Surajit Chaudhuri, Adam Bosworth, et al.: “[Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals](http://arxiv.org/pdf/cs/0701155.pdf),” *Data Mining and Knowledge Discovery*, volume 1, number 1, pages 29–53, March 2007. [doi:10.1023/A:1009726021843](http://dx.doi.org/10.1023/A:1009726021843)