ddia/ch3.md at master · Vonng/ddia

引言

數據庫最基本兩件事：

• 儲存數據
• 檢索數據

本章會討論

• 資料庫如何儲存資料
• 如何找到資料

儲存引擎依據負載進最佳化，分成兩種

• 事務型負載最佳化
  Online Transaction Processing (OLTP) 儲存引擎，用於高併發的交易性應用，需要支援併發的讀取或寫入操作。
• 分析性負載最佳化
  Online Analytical Processing (OLAP) 儲存引擎，用於針對大數據集進行分析查詢，支援複雜的聚集計算和多維分析。

兩大類資料庫引擎

• page-oriented
  頁面導向資料庫被用於儲存表格，其中每個表格被分為好幾個磁碟頁面。磁碟頁面是資料庫系統與磁碟交互的最小單位，通常大小為 4KB 或 8KB。
• log-structured
  日誌導向資料庫最初是由 Google 發明，用於處理 Web 搜索的索引數據。這種資料庫引擎將所有修改操作寫入一個追蹤寫入（write-ahead log, WAL）中，然後將實際數據讀取到記憶體中，並在記憶體中進行修改。當修改完成時，這些修改操作會被追加到 WAL 中，然後再以某種方式寫入磁碟。這種方式允許寫入操作非常快速，並且可以維護良好的寫入吞吐量，從而使其成為許多大型分佈式數據庫的理想選擇。

驅動資料庫的資料結構

最簡單的資料庫

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

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

這個簡單的程式實現鍵值儲存和讀取，每次set 時會在檔案尾巴追加記錄，讀取時會從最後一行往上找直到找到key

$ 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"]}

db_set 有非常好的效能，因為在檔尾追加寫入是非常高效的，許多資料庫的內部使用了log structed，也是用僅追加(append-only)

db_get 的效能則很糟, O(n)，為了改善這個問題，我們需要一個數據結構 Index

Index 是一個「額外」的資料，能改變查詢的效能，但是在寫入時會增加開銷，所以寫入效能很難超過單純的追加寫入檔案

權衡選什麼索引就是DBA的專業

Hash Index

為了簡化，書中假設要儲存的資料是 key-value Data

假如資料要存進檔案，那 Index 最簡單的作法就是 存下每筆資料在檔案的 Offset

查詢資料時，只要從index取得 offset，再去檔案尋找(seek)即可。

感覺很簡單，實際上 Bitcask 就是這麼做的。

這種結構特別適合在很多寫操作的場景，像是貓咪影片的點擊次數

如果檔案太大的話，就開新的檔案，然後有時間再把舊的檔案壓縮

健值更新日誌 (統計貓咪影片的播放次數)

檔案很多的話，可以合併

同時執行壓縮和分段合併

為每個檔案儲存自己的 hash index

其它實現細節：

• 檔案格式
  書中提到，在儲存數據時使用二進制格式會比使用文本格式更快，因為文本格式需要進行解析和序列化，而二進制格式可以直接使用。這是許多資料庫的優化技巧之一。
• 刪除記錄
  當資料被刪除時，為了避免 hash index 中的資料不一致，可以先標記它們為被刪除的狀態，稱為墓碑（tombstone）。當 hash index 查找到被標記為墓碑的資料時，就知道這個資料已經被刪除，並且不會再被回傳。
• 崩潰恢復
  如果資料庫重新啟動，因為記憶體中的雜湊對映表丟失，所以必須重新構建。這可以通過在啟動時重新讀取每個數據檔案並重建對映表來實現。Bitcask 會把 index cache 起來
• 部分寫入記錄
  資料庫隨時可能崩潰，包括在將記錄追加到日誌的過程中。 Bitcask 檔案包含校驗和，允許檢測和忽略日誌中的這些損壞部分。
• 併發控制
  由於寫操作是以嚴格的順序追加到日誌中的，所以常見的實現是隻有一個寫入執行緒。也因為資料檔案段是僅追加的或者說是不可變的，所以它們可以被多個執行緒同時讀取。

僅追加日誌似乎很浪費：為什麼不直接在檔案裡更新，原因如下

• 順序寫入比隨機讀取更快，因為它允許操作系統以更高效的方式編組寫入操作。
• 併發和崩潰恢復容易。
• 合併舊段資料可以防止碎片化問題

hash index 也有其侷限性：

• memory 放不下 index 時，hash index 在 disk 上表現很糟
• 範圍查詢效率不高，無法輕鬆掃描 kitty00000 ~ kitty99999

SSTables and LSM tree

在之前的 hash index 結構，寫入檔案的 key 值順序，是照寫入時間先後的

SSTable(Sorted String Table) 則是要求寫入的順序照 key 的順序

用SSTable 的好處是

• 合併檔案可以更高效，同時讀取多個檔案合併
• 可以不用存下所有的 key offset 對應，因為 key 是排序的，只要先找到大概的位置，再掃描檔案即可
• index 的空間節省，IO也節省

具有記憶體索引的 SSTable

構建和維護SSTables

如何讓資料能夠預先排好序呢？畢竟我們接收到的寫入請求是沒有順序的。

雖然在硬碟上維護有序結構也是可能的，但在記憶體內則容易多

方便排序的資料結構

• 紅黑樹
• AVL 樹

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

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

只剩一個問題，資料庫崩潰，則最近的寫入（在記憶體表中，但尚未寫入硬碟）將丟失。

解法：硬碟上儲存一個單獨的日誌檔，在寫入記憶體錢先寫入日誌檔，用於崩潰後回復記憶體

用SSTables製作LSM樹

LSM-Tree（Log Structured-Merge Tree）是一種非常流行的樹型資料結構，用於實現許多現代資料庫系統。LSM-Tree 將數據分為多個層，每層使用不同的資料結構（如 SSTable）來進行儲存和檢索。當資料寫入時，它會先被寫入具有較快寫入速度的記憶體中，然後當記憶體中的資料達到一定閾值時，會將其寫入下一層。這樣可以避免過多的硬碟寫入，同時也可以提高查詢效率。

LSM Read 實作方式

在 LSM-Tree 中，當我們需要查詢資料時，會首先在記憶體中查找，如果找不到，就繼續在下一層的 SSTable 中查找，直到找到該筆資料或者所有的 SSTable 都被查詢過為止。此外，LSM-Tree 通常還會使用 Bloom Filters 來進一步加速查詢。

Bloom Filters 是一種資料結構，常用於判斷某個元素是否存在於一個集合中。它是由 Burton Bloom 於 1970 年提出的。

相較於傳統的B-Tree，LSM-Tree的優點在於：

• 寫入效率高，因為數據先被寫入記憶體中，而不是直接寫入磁碟中，當記憶體中的數據達到一定閾值時，再進行一次性的寫入操作。
• 可以進行批量寫入和刪除操作，因為數據被分為多個層，可以使用批量寫入和刪除操作來進行優化。
• 可以進行崩潰恢復，因為數據被分為多個層，可以在數據崩潰時進行恢復操作。

LSM-Tree 的缺點包括：

• 查詢效率不穩定，因為數據被分為多個層，所以查詢效率可能會隨著層數的增加而下降，尤其是在 SSTable 中有很多墓碑（tombstone）時。
• LSM-Tree 的儲存格式比較複雜，需要將數據分為多個層，每層使用不同的資料結構進行儲存，這導致它比較難以實現。
• 在寫入時，需要先將數據寫入記憶體中，然後再進行一次性的寫入操作。這樣會導致寫入操作的延遲性較高。

總體而言，LSM-Tree 是一種非常有效的數據儲存和檢索方式，但它也有一些缺點，需要在實際使用中加以注意。

效能最佳化

當查詢不存在的鍵時，需要檢查記憶體表和從最近到最早的所有段檔案，那樣很慢。

解決方法：

• 使用布隆過濾器(Bloom Filters)來最佳化查詢不存在的鍵時的訪問
• 考慮使用 size-tiered 和 leveled compaction 來確定 SSTables 被壓縮和合並的順序和時間

LSM 樹的基本思想是將一系列在後臺合併的 SSTables 儲存起來，即使資料集比可用記憶體大得多，它仍能繼續正常工作。資料按排序順序儲存，可高效地執行範圍查詢，並且因為硬碟寫入是連續的，所以 LSM 樹可以支援非常高的寫入吞吐量。

Bloom Filter（布隆過濾器）是用來檢驗一個元素是否存在於特定集合中的概念。它在空間複雜度方面比 hash table 更優秀，但使用它時需要注意偽陽性(false positive)的問題

false positive：沒有就是沒有，有代表有可能有

B樹

日誌結構索引已經很常見，但它們不是最常用的索引。B 樹是一種最常見的索引結構，從 1970 年被引入以來，僅不到 10 年就變得“無處不在”，被廣泛使用在關係資料庫和非關係資料庫中。

像 SSTables 一樣，B 樹保持按鍵排序的鍵值對，這允許高效的鍵值查詢和範圍查詢。

B 樹將資料庫分解成固定大小的塊或分頁，通常大小為 4KB，並且一次只能讀取或寫入一個頁面。每個頁面都可以使用地址或位置來標識，這允許一個頁面引用另一個頁面，類似於指標，只是是在硬碟而不是在記憶體中。我們可以使用這些頁面引用來構建一個頁面樹，如圖 3-6 所示。

使用 B 樹索引查詢一個鍵

• B樹由根頁面、子頁面和葉子頁面組成
• 子頁面負責連續鍵範圍，根頁面上的鍵表示相鄰子頁面管理的鍵的邊界
• 查找鍵值時，從根頁面開始，按範圍查找子頁面，直到葉子頁面
• 分支因子是每個頁面中對子頁面引用的數量，範例上是6個，通常是幾百

• 更新 B 樹中的鍵值，需搜尋包含該鍵的葉子頁面，更改值，再將該頁面寫回硬碟（引用仍有效）。
• 新增鍵需找到可包含它的頁面，如空間不足，則分成兩半滿頁面，並更新父頁面。
• 演算法確保樹平衡，n 個鍵的 B 樹深度為 O(log n)。多數資料庫可用三到四層樹，分支因子為 500 的 4KB 頁面的四層樹，可儲存 256TB 資料。

讓B樹更可靠

• B 樹的基本寫入操作，
• 如何覆寫硬碟上的頁面以及如何處理拆分頁面等情況。
• 討論了預寫式日誌（WAL）檔案以及併發控制的問題。
• 日誌結構化的方法相對於 B 樹的優勢。

B 樹的基本寫入操作是用新資料覆寫硬碟上的頁面，而不會改變頁面的位置。這表示當頁面被覆寫時，對該頁面的所有引用不會改變。這與日誌結構索引（如 LSM 樹）形成鮮明對比，後者只是追加到檔案，從不修改檔案中已有的內容。

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

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

B 樹實現中通常會有預寫式日誌（WAL，即 write-ahead log，也稱為重做日誌）檔案，以處理異常崩潰的情況。每次對 B 樹的修改都必須先寫入該檔案，然後才能應用到樹本身的頁面。當資料庫在崩潰後恢復時，這個日誌將被用來使 B 樹恢復到一致的狀態。

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

B樹的最佳化

B樹存在已久，多年來已開發出許多優化設計，包括：

• 使用寫時複製方案，例如LMDB，而非覆寫頁面並維護WAL以支援崩潰恢復。經修改的頁面被寫入不同位置，並在樹中建立父頁面的新版本以指向新位置。這種方法對於併發控制也很有用。
• 縮短鍵的大小，而非儲存整個鍵，以節省頁面空間。在樹內部的頁面上，鍵只需提供足夠的資訊來充當鍵範圍之間的邊界。在頁面中包含更多的鍵允許樹具有更高的分支因子，因此也就允許更少的層級。
• 不要求相鄰鍵範圍的頁面也放在硬碟上相鄰的區域，但這樣隨機存取的速度很慢。因此，許多B樹的實現在佈局樹時會盡量使葉子頁面按順序出現在硬碟上，但隨著樹的增長，要維持這個順序是很困難的。
• 新增指標到樹中，例如每個葉子頁面引用其左右兄弟頁面，使得不用跳回父頁面即可按順序掃描鍵。
• B樹的變體如分形樹借用了一些日誌結構的思想來減少硬碟查詢。

比較B樹和LSM樹

• 通常，LSM樹的寫入速度較快，B樹的讀取速度較快。
• LSM樹具有較高的寫入吞吐量，較低的寫放大和碎片，對固態硬碟較為友好。
• LSM樹可能在壓縮過程中干擾讀寫操作，且在高寫入吞吐量下壓縮性能受限
• B樹為許多工作負載提供了始終如一的良好效能，並適用於事務隔離等應用。

B樹和LSM樹的比較中，B樹實現通常較為成熟，但LSM樹在效能特徵方面也很有吸引力。經驗表明，LSM樹的寫入速度通常更快，而B樹的讀取速度更快。LSM樹上的讀取相對較慢，因為需要檢查多個資料結構和SSTables的不同壓縮層級。

然而，基準測試結果通常取決於工作負載細節，所以需要針對特定工作負載進行測試以進行有效比較。在評估儲存引擎效能時，需要考慮幾個因素。

LSM樹具有更高寫入吞吐量、較低的寫入放大和碎片化，並且可以將資料壓縮得更好，因此在硬碟上產生的檔案較小。不過，壓縮過程可能干擾到正在進行的讀寫操作，導致性能波動和較高的響應時間。在高寫入吞吐量下，壓縮性能可能受限，導致硬碟上未合併段的數量不斷增加，從而影響讀取速度。

B樹的優勢在於每個鍵在索引中只存在一個位置，並且通常具有較快的讀取速度。此外，B樹在需要強大事務語義的資料庫中非常適用，因為可以直接在B樹索引中的鍵範圍上應用鎖。然而，B樹可能具有更高的寫入放大和碎片化，導致磁碟空間使用增加和寫入吞吐量降低。

B樹在資料庫架構中具有深厚基礎，而LSM樹在新型資料庫中越來越受歡迎。要確定哪種儲存引擎最適合特定使用場景，需要根據實際工作負載進行測試。

其他索引結構

名詞解釋

1. 主鍵索引：在關聯式資料庫、文件資料庫或圖形資料庫中，主鍵唯一識別一行、一個文檔或一個頂點。其他紀錄可以通過主鍵（或ID）引用該行/文檔/頂點，索引用於解析這些引用。
2. 次級索引：允許在資料庫表格上建立額外的索引，以提高查詢性能。次要索引可以從鍵值索引構建，主要區別在於鍵不是唯一的。這可以通過使索引中的每個值成為匹配行標識符的列表或通過將行標識符附加到鍵上使其唯一來解決。
3. heap file：存儲行數據的無特定順序的文件。堆文件避免了多個次要索引存在時的數據重複問題：每個索引僅引用堆文件中的位置，實際數據存儲在一個地方。
4. Clustered 索引：將索引行直接存儲在索引中的一種方法，可以提高查詢性能。例如，MySQL的InnoDB存儲引擎中，表的主鍵始終是聚簇索引，次要索引引用主鍵（而不是堆文件位置）。
5. 包含列的索引：Clustered and non clustered index 的過渡，只保存部份需要用到的資料
6. 多列索引：同時查詢多個表列或文檔字段的索引。這對於需要根據多個條件查找數據的情況非常有用。
7. 串接索引：將多個字段組合成一個鍵的多列索引。串接索引的鍵是按照指定的順序將字段附加在一起的。它可以用來查找具有特定條件的所有數據，但如果只查詢其中一個字段，它可能無法提供幫助。
8. 多維索引：用於查詢多個列的一般方法，特別適用於地理空間數據。
9. R樹：專門用於地理空間數據的空間索引。
10. 全文搜索：用於模糊查詢的技術，支持對詞彙、語法變化和近義詞等進行搜索。

目前，我們只討論了鍵值索引，它們就像關係模型中的 主鍵索引。

次級索引（secondary indexes）也很常見。在關係資料庫中，你可以使用 CREATE INDEX 命令在同一個表上建立多個次級索引。

儲存Index 中的值

索引的鍵是查詢欄位，而值可以是行本身或是儲存在別處行的參照。後者儲存在 heap file 中

heap file 資料沒有特定順序，這種方法常見，因為可以避免在有多個次級 index 時複製資料。

Clustered Index 將整個資料列的所有資料存入索引中，查詢可直接在索引樹上完成，速度較快，但只能建立在唯一的鍵上。相反地，非聚集式 index 將索引資料存入索引樹中，而將資料列放置在另一個文件中，因此查詢需要先在索引樹上完成，再到文件中查詢資料列。

cover index 介於 clustered index and non clustered index 之間，包含查詢所需的所有欄位，可不必查詢表格本身即可回答查詢，因此可大幅提高查詢性能。

多列 index

又叫複合 index，對查詢有多種條件時，能加速，要注意 key 的順序是重要的，和下 where 欄位的順序一致的話，查詢是最快的。

多維 index

用於加速多維資料的查詢，例如帶有時間和地點兩個維度的天氣資料。它通常使用 R 樹資料結構來實現，具有高效的範圍查詢和空間查詢功能。在設計多維 index 時，必須仔細選擇索引的維度，以便在查詢時獲得最佳效能。

B 樹或 LSM 樹索引無法高效處理這種查詢：它可以返回一個經度範圍內的所有餐廳（但緯度可能是任意值），或者返回在同一緯度範圍內的所有餐廳（但經度可能是任意值），但不能同時滿足兩個條件。

全文搜尋和模糊索引

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

模糊索引（fuzzy indexes）類似於全文搜尋，但允許在查詢過程中包含近似匹配，以處理拼寫錯誤、拼音相似性等問題。為實現模糊索引，可以使用像Levenshtein距離、Damerau-Levenshtein距離和Jaro-Winkler距離等編輯距離度量，或使用如三元組或四元組的n-gram方法來度量相似性。

在記憶體中儲存一切

記憶體資料庫在效能、資料模型和擴展性方面具有優勢：

1. 效能：記憶體資料庫通過直接從記憶體讀取和寫入資料，可以提供更高的讀寫速度，從而提高整體效能。這比傳統的基於硬碟的資料庫更快，因為後者需要在硬碟上查找和操作資料，這會消耗更多的時間。
2. 資料模型：記憶體資料庫可以較容易地支援多種資料結構（如優先順序佇列和集合），從而提供更好的應用支援。這使得開發人員可以更靈活地設計和實現資料模型，以滿足不同的應用需求。
3. 擴展性：記憶體資料庫可以通過反快取方法在記憶體不足的情況下將最近最少使用的資料從記憶體轉移到硬碟，並在需要時重新將其載入到記憶體中。這使得記憶體資料庫能夠支援比可用記憶體更大的資料集，同時保持高效能。

隨著 RAM 成本的降低，將資料集完全儲存在記憶體中變得更加可行。此外，非易失性儲存器（NVM）技術的發展有望為未來的資料存儲帶來重大變革，因為它們結合了記憶體和硬碟的特點，並可以在不同的應用場景中提供更好的性能。

總之，記憶體資料庫在資料庫領域具有顯著優勢，特別是在處理較小資料集時。隨著 RAM 成本降低和非易失性儲存器技術的發展，記憶體資料庫將在資料庫領域發揮越來越重要的作用。

事務處理還是分析？

早期資料庫寫入對應商業交易。後來資料庫應用於非金錢相關領域，仍使用"事務"一詞。事務處理允許客戶端低延遲讀寫，稱為線上事務處理（OLTP）。

資料庫越來越多地用於資料分析，這些分析查詢被稱為線上分析處理（OLAP）。OLTP主要是查詢少量記錄，終端使用者操作。OLAP則主要在大批次記錄上聚合，供內部資料分析師使用。

起初，事務處理和分析查詢使用相同資料庫，但企業趨勢是在單獨的資料倉庫上執行分析。

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

資料倉庫

資料倉庫是一個獨立的資料庫，用於儲存企業內所有OLTP（線上事務處理）系統中的只讀資料副本。企業可能擁有多個交易處理系統，如終端客戶網站、實體商店收銀系統、倉庫庫存追踪等。這些OLTP系統對業務運作至關重要，要求高可用和低延遲，所以一般不允許業務分析人員直接在這些資料庫上執行分析查詢。

資料倉庫允許分析人員查詢資料，而不影響OLTP操作。資料倉庫從OLTP資料庫中提取資料，轉換為適合分析的格式，然後載入資料倉庫。這個過程稱為抽取-轉換-載入（ETL）。

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

資料倉庫可針對分析類的訪問模式進行最佳化。雖然資料倉庫和關係型OLTP資料庫都有SQL查詢介面，但它們針對非常不同的查詢模式進行最佳化。許多資料庫供應商專注於支援事務處理負載或分析工作負載，而不是兩者兼顧。

一些資料庫（如Microsoft SQL Server和SAP HANA）在同一產品中支援事務處理和資料倉庫。還有一些資料倉庫供應商，如Teradata、Vertica等，它們的產品通常使用昂貴的商業許可證銷售。開源SQL-on-Hadoop專案正與商業資料倉庫系統競爭，例如Apache Hive、Spark SQL、Cloudera Impala等。

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

星型和雪花型模式是分析型資料庫中常見的資料模型。在星型模式中，資料庫中心是一個事實表，它記錄了特定事件（例如客戶購買的產品）。事實表的每一行都包含一個事件，並通過外部鍵引用其他表（稱為維度表）。這些維度表包含了事件發生的物件、內容、地點、時間、方式和原因等資訊。星型模式之所以被稱為星型，是因為當我們將表之間的關係視覺化時，事實表位於中心，被維度表包圍，連線就像星星的光芒。

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

雪花模式是星型模式的一個變體，其中維度被進一步分解成子維度。這意味著維度表可以再引用其他表，將資料進一步細分。雖然雪花模式比星型模式更規範化，但分析師通常更喜歡使用星型模式，因為它更簡單。

列式儲存

列式存儲是一種在資料庫中儲存資料的方式，它將表中的每一列資料存儲在一起，而不是將同一行的所有值相鄰存儲。這與常見的行式存儲方式不同，行式存儲方式會將表中同一行的所有值相鄰存儲。

在資料倉庫和大規模分析查詢中，列式存儲具有明顯優勢。當查詢只涉及表中少數幾列時，列式存儲可以有效地減少IO操作，提高查詢性能。這是因為查詢引擎只需要讀取和解析查詢中涉及的列，而不是整行數據。這在大型事實表（可能包含數百列）的資料倉庫查詢中特別有用。

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

列壓縮

透過壓縮資料，降低對硬碟吞吐量的需求。列式儲存通常適合壓縮，因為在列式儲存中，每一列的值序列通常具有重複性，這有利於壓縮。根據列中的資料，可以使用不同的壓縮技術。

點陣圖編碼：在資料倉庫中特別有效的壓縮技術。點陣圖編碼將具有 n 個不同值的列轉換為 n 個獨立的點陣圖，每個不同值對應一個位圖，每行對應一個位元位。如果該行具有該值，則該位為 1，否則為 0。

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

對於稀疏的點陣圖（其中包含許多零），可以使用遊程編碼（一種無損資料壓縮技術）進一步壓縮。這可以使列的編碼非常緊湊。

記憶體頻寬和向量化處理

資料倉庫查詢中，兩個主要性能瓶頸為

• 硬碟到記憶體頻寬
• 記憶體到CPU的頻寬

解決方法：

• 列式儲存佈局可以降低從硬碟載入的資料量，從而提高效率。
• 查詢引擎可以將壓縮後的列資料放入CPU的L1快取，然後在緊密的迴圈中遍歷。這樣的迴圈相對於包含大量函式呼叫和條件判斷的程式碼執行速度更快。
• 列壓縮允許更多的行同時放入有限的L1快取。
• 向量化處理是一種可以直接在壓縮列資料塊上操作的技術。例如，按位 "與" 和 "或" 運算子可以被設計成在壓縮列資料塊上執行。

列式儲存中的排序順序

列式儲存中資料排序順序的概念和其對查詢效率的影響。

1. 在列式儲存中，資料的行順序不是非常重要。可以按插入順序儲存，但也可以根據某種排序順序排列資料以作為索引機制。
2. 對每一列分別進行排序是沒有意義的，因為這樣就無法重建出完整的行。所以需要對整行資料進行統一操作，即使實際儲存方式是按列的。
3. 資料庫管理員可以根據常用查詢的需求來選擇用於排序的列。例如，如果查詢通常涉及日期範圍，則可以使用日期作為第一個排序鍵，這樣查詢引擎只需掃描特定日期範圍的行，而不需要掃描所有行。
4. 對資料進行排序還有助於壓縮列。如果主要排序列的值重複程度較高，則排序後可以用簡單的運行長度編碼來進行壓縮。
5. C-Store 和 Vertica 等資料庫系統中的一個擴充套件是，既然不同查詢受益於不同的排序順序，為什麼不以多種不同方式儲存相同資料？這樣可以在處理查詢時，選擇最適合查詢模式的排序版本。

總之，列式儲存中的排序順序對於查詢效率和資料壓縮具有重要影響。不同的排序順序可以優化查詢性能並提高資料壓縮率。

寫入列式儲存

在資料倉庫中，列式儲存、壓縮和排序對於大型只讀查詢有幫助。但是，寫入列式儲存比較困難。由於行由列中的位置標識，插入新行可能需要重寫所有列檔案。

一個解決方案是使用LSM樹。寫操作先進入記憶體中的儲存，被加入已排序結構，然後批次寫入硬碟上的列檔案。查詢操作需要檢查硬碟上的列資料和記憶體中的最近寫入，將兩者合併。查詢最佳化器會隱藏這些細節，使得修改後的資料能立即反映在查詢中。

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

為了提高資料倉庫的查詢性能，可以利用資料立方體和物化檢視進行數據聚合。這兩種技術具有不同的特點和用途：

1. 物化檢視：
   • 將查詢結果的實際副本儲存起來，加速常用聚合函式，如 COUNT、SUM、AVG 等。
   • 與虛擬檢視不同，虛擬檢視只是查詢的捷徑，不儲存任何實際數據。
   • 需要在底層數據變化時進行更新，這會增加寫入成本，在 OLTP 資料庫中不太常用。
2. 資料立方體：
   • 物化檢視的一個特例，按照不同維度分組的聚合網格，也被稱為 OLAP 立方。
   • 允許根據不同維度對數據進行彙總，例如根據日期和產品對銷售額進行彙總。
   • 當事實具有多個維度時，可以擴展到多維超立方體，例如日期、產品、商店、促銷和客戶等五個維度。
   • 優點：讓某些查詢變得非常快，因為這些查詢已經被有效地預先計算了。
   • 缺點：缺乏查詢原始數據的靈活性，因為價格等某些範圍條件不是立方體的維度。

資料倉庫通常會保留儘可能多的原始數據，並將聚合數據（如資料立方體）僅作為某些查詢的效能提升手段。

本章小結

在本章中，我們詳細討論了資料庫如何處理資料的儲存和檢索。資料儲存在資料庫後，查詢時資料庫會進行檢索。我們了解了針對事務處理（OLTP）和線上分析（OLAP）兩種不同使用場景的儲存引擎，以及他們之間的區別。

1. OLTP系統： a. 面向終端使用者，處理大量請求。 b. 每個查詢通常只訪問少量記錄，使用索引進行查詢。 c. 硬碟查詢時間是瓶頸。
2. OLAP系統： a. 面向業務分析人員，查詢量較少。 b. 每個查詢開銷高，需要短時間內掃描大量記錄。 c. 硬碟頻寬是瓶頸，列式儲存有助於提高效能。
3. 兩派主流的儲存引擎： a. 日誌結構學派：例如Bitcask、SSTables、LSM樹、LevelDB、Cassandra、HBase、Lucene等。這些技術通過將隨機訪問寫入轉換為硬碟上的順序寫入，提高寫入吞吐量。 b. 就地更新學派：例如B樹，用於關係資料庫和非關係型資料庫。將硬碟視為一組可覆寫的固定大小的頁面。
4. 複雜的索引結構與記憶體內資料庫：介紹了一些更複雜的索引結構，以及針對所有資料都放在記憶體裡而最佳化的資料庫。
5. 資料倉庫的高階架構： a. 當查詢需要在大量行中順序掃描時，索引的重要性降低。 b. 非常緊湊地編碼資料變得非常重要，以減少查詢需要從硬碟讀取的資料量。 c. 列式儲存有助於實現這一目標，提高查詢效能。

作為一名應用程式開發人員，了解儲存引擎內部的知識將有助於您更好地了解哪種工具最適合特定應用程式。在調整資料庫最佳化引數時，這種理解讓您能夠預測增減某個值所產生的效果。

了解資料庫儲存引擎的內部運作對於選擇最適合您需求的資料庫系統至關重要。以下是一些建議幫助您選擇資料庫：

1. 評估您的工作負載類型：確定您的應用程式是否更偏向OLTP或OLAP，以選擇針對特定需求最佳化的資料庫。
2. 考慮資料庫的可擴展性：根據您的應用程式的未來需求和成長，確保資料庫可以滿足這些需求。
3. 評估資料庫的性能：根據您的應用程式需求，選擇性能最佳的資料庫，特別是在讀取和寫入操作方面。
4. 瞭解資料庫的安全性和完整性：選擇具有內建安全性和完整性機制的資料庫，以確保您的數據安全無虞。
5. 考慮資料庫的支持和社區：選擇具有良好支持和活躍開發者社區的資料庫，這將有助於您解決問題和獲取技術支援。

儘管本章無法使您成為特定儲存引擎的調參專家，但至少能讓您獲得足夠的概念和詞彙，以便您能夠閱讀和理解所選資料庫的文檔。掌握資料庫儲存引擎的基本知識對於您作為應用程式開發人員來說是非常有價值的。