4. 儲存與檢索

生活的苦惱之一是，每個人對事物的命名都有些偏差。這讓我們理解世界變得比本該有的樣子困難一些，要是命名方式不同就好了。計算機的主要功能並不是傳統意義上的計算，比如算術運算。[……] 它們主要是歸檔系統。

理查德·費曼， 特立獨行的思考 研討會（1985）

在最基礎的層面上，資料庫需要做兩件事：當你給它一些資料時，它應該儲存這些資料；當你之後再詢問時，它應該把資料返回給你。

在 第 3 章 中，我們討論了資料模型和查詢語言 —— 即你向資料庫提供資料的格式，以及之後再次請求資料的介面。在本章中，我們從資料庫的角度討論同樣的問題：資料庫如何儲存你提供的資料，以及當你請求時如何再次找到這些資料。

作為應用開發者，你為什麼要關心資料庫內部如何處理儲存和檢索？你可能不會從頭開始實現自己的儲存引擎，但你 確實 需要從眾多可用的儲存引擎中選擇一個適合你應用的。為了讓儲存引擎在你的工作負載型別上表現良好，你需要對儲存引擎在底層做了什麼有個大致的瞭解。

特別是，針對事務型工作負載（OLTP）最佳化的儲存引擎和針對分析型工作負載最佳化的儲存引擎之間存在巨大差異（我們在 “分析型與事務型系統” 中介紹了這種區別）。本章首先研究兩種用於 OLTP 的儲存引擎家族：寫入不可變資料檔案的 日誌結構 儲存引擎，以及像 B 樹 這樣就地更新資料的儲存引擎。這些結構既用於鍵值儲存，也用於二級索引。

隨後在 “分析型資料儲存” 中，我們將討論一系列針對分析最佳化的儲存引擎；在 “多維索引與全文索引” 中，我們將簡要介紹用於更高階查詢（如文字檢索）的索引。

OLTP 系統的儲存與索引

考慮世界上最簡單的資料庫，用兩個 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，它會查詢與該特定鍵關聯的最新值並返回它。

它確實能工作：

$ db_set 12 '{"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）：

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

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

$ cat database
12,{"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 所做的類似，許多資料庫內部使用 日誌，這是一個僅追加的資料檔案。真正的資料庫有更多問題要處理（如處理併發寫入、回收磁碟空間以防日誌無限增長，以及從崩潰中恢復時處理部分寫入的記錄），但基本原理是相同的。日誌非常有用，我們將在本書中多次遇到它們。

Note

日誌 這個詞通常用於指應用程式日誌，應用程式輸出描述正在發生什麼的文字。在本書中，日誌 用於更一般的含義：磁碟上僅追加的記錄序列。它不一定是人類可讀的；它可能是二進位制的，僅供資料庫系統內部使用。

另一方面，如果你的資料庫中有大量記錄，db_get 函式的效能會很糟糕。每次你想查詢一個鍵時，db_get 必須從頭到尾掃描整個資料庫檔案，尋找該鍵的出現。用算法術語來說，查詢的成本是 O(n)：如果你的資料庫中的記錄數 n 翻倍，查詢時間也會翻倍。這並不好。

為了高效地找到資料庫中特定鍵的值，我們需要一個不同的資料結構：索引。在本章中，我們將研究一系列索引結構並瞭解它們的比較；一般思想是以特定方式（例如，按某個鍵排序）構建資料，使定位所需資料更快。如果你想以幾種不同的方式搜尋相同的資料，你可能需要在資料的不同部分上建立幾個不同的索引。

索引是從主資料派生出的 額外 結構。許多資料庫允許你新增和刪除索引，這不會影響資料庫的內容；它隻影響查詢的效能。維護額外的結構會產生開銷，特別是在寫入時。對於寫入，很難超越簡單地追加到檔案的效能，因為這是最簡單的寫入操作。任何型別的索引通常都會減慢寫入速度，因為每次寫入資料時也需要更新索引。

這是儲存系統中的一個重要權衡：精心選擇的索引加快了讀查詢速度，但每個索引都會消耗額外的磁碟空間並減慢寫入速度，有時會大幅減慢 1。因此，資料庫通常不會預設為所有內容建立索引，而是要求你 —— 編寫應用程式或管理資料庫的人 —— 使用你對應用程式典型查詢模式的瞭解來手動選擇索引。然後你可以選擇為你的應用程式帶來最大收益的索引，而不會引入超過必要的寫入開銷。

日誌結構儲存

首先，讓我們假設你想繼續將資料儲存在 db_set 寫入的僅追加檔案中，你只是想加快讀取速度。一種方法是在記憶體中保留一個雜湊對映，其中每個鍵都對映到檔案中可以找到該鍵最新值的位元組偏移量，如 圖 4-1 所示。

圖 4-1. 以類似 CSV 格式儲存鍵值對日誌，使用記憶體雜湊對映建立索引。

每當你向檔案追加新的鍵值對時，你也會更新雜湊對映以反映剛剛寫入資料的偏移量。當你想查詢一個值時，你使用雜湊對映找到日誌檔案中的偏移量，尋找到該位置，然後讀取值。如果資料檔案的那部分已經在檔案系統快取中，讀取根本不需要任何磁碟 I/O。

這種方法速度更快，但仍然存在幾個問題：

  • 你永遠不會釋放被覆蓋的舊日誌條目佔用的磁碟空間；如果你不斷寫入資料庫，可能會耗盡磁碟空間。
  • 雜湊對映不是持久化的，所以當你重啟資料庫時必須重建它 —— 例如，透過掃描整個日誌檔案來找到每個鍵的最新位元組偏移量。如果你有大量資料，這會使重啟變慢。
  • 雜湊表必須適合記憶體。原則上，你可以在磁碟上維護雜湊表，但不幸的是，很難讓磁碟上的雜湊對映表現良好。它需要大量的隨機訪問 I/O，當它變滿時擴充套件成本高昂，雜湊衝突需要複雜的邏輯 2。
  • 範圍查詢效率不高。例如，你不能輕鬆掃描 10000 和 19999 之間的所有鍵 —— 你必須在雜湊對映中單獨查詢每個鍵。

SSTable 檔案格式

實際上，雜湊表很少用於資料庫索引，相反，保持資料 按鍵排序 的結構更為常見 3。這種結構的一個例子是 排序字串表（Sorted String Table），簡稱 SSTable，如 圖 4-2 所示。這種檔案格式也儲存鍵值對，但它確保它們按鍵排序，每個鍵在檔案中只出現一次。

圖 4-2. 帶有稀疏索引的 SSTable，允許查詢跳轉到正確的塊。

現在你不需要在記憶體中保留所有鍵：你可以將 SSTable 中的鍵值對分組為幾千位元組的 塊，然後在索引中儲存每個塊的第一個鍵。這種只儲存部分鍵的索引稱為 稀疏 索引。這個索引儲存在 SSTable 的單獨部分，例如使用不可變 B 樹、字典樹或其他允許查詢快速查詢特定鍵的資料結構 4。

例如，在 圖 4-2 中，一個塊的第一個鍵是 handbag，下一個塊的第一個鍵是 handsome。現在假設你要查詢鍵 handiwork，它沒有出現在稀疏索引中。由於排序，你知道 handiwork 必須出現在 handbag 和 handsome 之間。這意味著你可以尋找到 handbag 的偏移量，然後從那裡掃描檔案，直到找到 handiwork（或沒有，如果該鍵不在檔案中）。幾千位元組的塊可以非常快速地掃描。

此外，每個記錄塊都可以壓縮（在 圖 4-2 中用陰影區域表示）。除了節省磁碟空間外，壓縮還減少了 I/O 頻寬使用，代價是使用更多一點的 CPU 時間。

構建和合並 SSTable

SSTable 檔案格式在讀取方面比僅追加日誌更好，但它使寫入更加困難。我們不能簡單地追加到末尾，因為那樣檔案就不再排序了（除非鍵恰好按升序寫入）。如果我們每次在中間某處插入鍵時都必須重寫整個 SSTable，寫入將變得太昂貴。

我們可以用 日誌結構 方法解決這個問題，這是僅追加日誌和排序檔案之間的混合：

  1. 當寫入操作到來時，將其新增到記憶體中的有序對映資料結構中，例如紅黑樹、跳錶 5 或字典樹 6。使用這些資料結構，你可以按任意順序插入鍵，高效地查詢它們，並按排序順序讀回它們。這個記憶體資料結構稱為 記憶體表（memtable）。
  2. 當記憶體表變得大於某個閾值（通常是幾兆位元組）時，將其按排序順序作為 SSTable 檔案寫入磁碟。我們將這個新的 SSTable 檔案稱為資料庫的最新 段，它與舊段一起作為單獨的檔案儲存。每個段都有自己內容的單獨索引。當新段被寫入磁碟時，資料庫可以繼續寫入新的記憶體表例項，當 SSTable 寫入完成時，舊記憶體表的記憶體被釋放。
  3. 為了讀取某個鍵的值，首先嘗試在記憶體表和最新的磁碟段中找到該鍵。如果沒有找到，就在下一個較舊的段中查詢，依此類推，直到找到鍵或到達最舊的段。如果鍵沒有出現在任何段中，則它不存在於資料庫中。
  4. 不時地在後臺執行合併和壓實過程，以合併段檔案並丟棄被覆蓋或刪除的值。

合併段的工作方式類似於 歸併排序 演算法 5。該過程如 圖 4-3 所示：並排開始讀取輸入檔案，檢視每個檔案中的第一個鍵，將最低的鍵（根據排序順序）複製到輸出檔案，然後重複。如果同一個鍵出現在多個輸入檔案中，只保留較新的值。這會產生一個新的合併段檔案，也按鍵排序，每個鍵只有一個值，並且它使用最少的記憶體，因為我們可以一次遍歷一個鍵的 SSTable。

圖 4-3. 合併多個 SSTable 段，僅保留每個鍵的最新值。

為了確保資料庫崩潰時記憶體表中的資料不會丟失，儲存引擎在磁碟上保留一個單獨的日誌，每次寫入都會立即追加到該日誌中。此日誌不按鍵排序，但這無關緊要，因為它的唯一目的是在崩潰後恢復記憶體表。每次記憶體表被寫出到 SSTable 後，日誌的相應部分就可以丟棄。

如果你想刪除一個鍵及其關聯的值，你必須向資料檔案追加一個稱為 墓碑（tombstone）的特殊刪除記錄。當日誌段合併時，墓碑告訴合併過程丟棄已刪除鍵的任何先前值。一旦墓碑合併到最舊的段中，它就可以被丟棄。

這裡描述的演算法本質上就是 RocksDB 7、Cassandra、Scylla 和 HBase 8 中使用的演算法，它們都受到 Google 的 Bigtable 論文 9 的啟發（該論文引入了 SSTable 和 memtable 這兩個術語）。

該演算法最初於 1996 年以 日誌結構合併樹（Log-Structured Merge-Tree）或 LSM 樹（LSM-Tree）10 的名稱釋出，建立在早期日誌結構檔案系統工作的基礎上 11。因此，基於合併和壓實排序檔案原理的儲存引擎通常被稱為 LSM 儲存引擎。

在 LSM 儲存引擎中，段檔案是一次性寫入的（透過寫出記憶體表或合併一些現有段），此後它是不可變的。段的合併和壓實可以在後臺執行緒中完成，當它進行時，我們仍然可以使用舊的段檔案繼續提供讀取服務。當合並過程完成時，我們將讀取請求切換到使用新的合併段而不是舊段，然後可以刪除舊的段檔案。

段檔案不一定必須儲存在本地磁碟上：它們也非常適合寫入物件儲存。例如，SlateDB 和 Delta Lake 12 採用了這種方法。

具有不可變段檔案也簡化了崩潰恢復：如果在寫出記憶體表或合併段時發生崩潰，資料庫可以刪除未完成的 SSTable 並重新開始。將寫入持久化到記憶體表的日誌如果在寫入記錄的過程中發生崩潰，或者磁碟已滿，可能包含不完整的記錄；這些通常透過在日誌中包含校驗和來檢測，並丟棄損壞或不完整的日誌條目。我們將在 第 8 章 中更多地討論永續性和崩潰恢復。

布隆過濾器

使用 LSM 儲存，讀取很久以前更新的鍵或不存在的鍵可能會很慢，因為儲存引擎需要檢查多個段檔案。為了加快此類讀取，LSM 儲存引擎通常在每個段中包含一個 布隆過濾器（Bloom filter）13，它提供了一種快速但近似的方法來檢查特定鍵是否出現在特定 SSTable 中。

圖 4-4 顯示了一個包含兩個鍵和 16 位的布隆過濾器示例（實際上，它會包含更多的鍵和更多的位）。對於 SSTable 中的每個鍵，我們計算一個雜湊函式，產生一組數字，然後將其解釋為位陣列的索引 14。我們將對應於這些索引的位設定為 1，其餘保持為 0。例如，鍵 handbag 雜湊為數字 (2, 9, 4)，所以我們將第 2、9 和 4 位設定為 1。然後將點陣圖與鍵的稀疏索引一起儲存為 SSTable 的一部分。這需要一點額外的空間，但與 SSTable 的其餘部分相比，布隆過濾器通常很小。

圖 4-4. 布隆過濾器提供了一種快速的機率檢查，用於判斷特定鍵是否存在於特定 SSTable 中。

當我們想知道一個鍵是否出現在 SSTable 中時，我們像以前一樣計算該鍵的相同雜湊，並檢查這些索引處的位。例如，在 圖 4-4 中，我們查詢鍵 handheld，它雜湊為 (6, 11, 2)。其中一個位是 1（即第 2 位），而另外兩個是 0。這些檢查可以使用所有 CPU 都支援的位運算非常快速地進行。

如果至少有一個位是 0，我們知道該鍵肯定不在 SSTable 中。如果查詢中的位都是 1，那麼該鍵很可能在 SSTable 中，但也有可能是巧合，所有這些位都被其他鍵設定為 1。這種看起來鍵存在但實際上不存在的情況稱為 假陽性（false positive）。

假陽性的機率取決於鍵的數量、每個鍵設定的位數和布隆過濾器中的總位數。你可以使用線上計算器工具為你的應用計算出正確的引數 15。作為經驗法則，你需要為 SSTable 中的每個鍵分配 10 位布隆過濾器空間以獲得 1% 的假陽性機率，每為每個鍵分配額外的 5 位，機率就會降低十倍。

在 LSM 儲存引擎的上下文中，假陽性沒有問題：

  • 如果布隆過濾器說鍵 不 存在，我們可以安全地跳過該 SSTable，因為我們可以確定它不包含該鍵。
  • 如果布隆過濾器說鍵 存在，我們必須查詢稀疏索引並解碼鍵值對塊以檢查鍵是否真的在那裡。如果是假陽性，我們做了一些不必要的工作，但除此之外沒有害處 —— 我們只是繼續使用下一個最舊的段進行搜尋。

壓實策略

一個重要的細節是 LSM 儲存如何選擇何時執行壓實，以及在壓實中包括哪些 SSTable。許多基於 LSM 的儲存系統允許你配置使用哪種壓實策略，一些常見的選擇是 16 17：

分層壓實（Size-tiered compaction）
較新和較小的 SSTable 依次合併到較舊和較大的 SSTable 中。包含較舊資料的 SSTable 可能變得非常大，合併它們需要大量的臨時磁碟空間。這種策略的優點是它可以處理非常高的寫入吞吐量。
分級壓實（Leveled compaction）
鍵範圍被分成較小的 SSTable，較舊的資料被移動到單獨的"級別"中，這允許壓實更增量地進行，並且比分層策略使用更少的磁碟空間。這種策略對於讀取比分層壓實更有效，因為儲存引擎需要讀取更少的 SSTable 來檢查它們是否包含該鍵。

作為經驗法則，如果你主要有寫入而讀取很少，分層壓實表現更好，而如果你的工作負載以讀取為主，分級壓實表現更好。如果你頻繁寫入少量鍵，而很少寫入大量鍵，那麼分級壓實也可能有優勢 18。

儘管有許多細微之處，但 LSM 樹的基本思想 —— 保持在後臺合併的 SSTable 級聯 —— 簡單而有效。我們將在 “比較 B 樹與 LSM 樹” 中更詳細地討論它們的效能特徵。

嵌入式儲存引擎

許多資料庫作為接受網路查詢的服務執行，但也有 嵌入式 資料庫不公開網路 API。相反，它們是在與應用程式程式碼相同的程序中執行的庫，通常讀取和寫入本地磁碟上的檔案，你透過正常的函式呼叫與它們互動。嵌入式儲存引擎的例子包括 RocksDB、SQLite、LMDB、DuckDB 和 KùzuDB 19。

嵌入式資料庫在移動應用中非常常用，用於儲存本地使用者的資料。在後端，如果資料足夠小以適合單臺機器，並且沒有太多併發事務，它們可能是一個合適的選擇。例如，在多租戶系統中，如果每個租戶足夠小且完全與其他租戶分離（即，你不需要執行合併多個租戶資料的查詢），你可能可以為每個租戶使用單獨的嵌入式資料庫例項 20。

我們在本章討論的儲存和檢索方法既用於嵌入式資料庫，也用於客戶端-伺服器資料庫。在 第 6 章 和 第 7 章 中，我們將討論跨多臺機器擴充套件資料庫的技術。

B 樹

日誌結構方法很流行，但它不是鍵值儲存的唯一形式。按鍵讀取和寫入資料庫記錄最廣泛使用的結構是 B 樹。

B 樹於 1970 年引入 21，不到 10 年後就被稱為"無處不在"22，它們經受住了時間的考驗。它們仍然是幾乎所有關係資料庫中的標準索引實現，許多非關係資料庫也使用它們。

像 SSTable 一樣，B 樹按鍵保持鍵值對排序，這允許高效的鍵值查詢和範圍查詢。但相似之處到此為止：B 樹有著非常不同的設計理念。

我們之前看到的日誌結構索引將資料庫分解為可變大小的 段，通常為幾兆位元組或更大，寫入一次後就不可變。相比之下，B 樹將資料庫分解為固定大小的 塊 或 頁，並可能就地覆蓋頁。頁傳統上大小為 4 KiB，但 PostgreSQL 現在預設使用 8 KiB，MySQL 預設使用 16 KiB。

每個頁都可以使用頁號來標識，這允許一個頁引用另一個頁 —— 類似於指標，但在磁碟上而不是在記憶體中。如果所有頁都儲存在同一個檔案中，將頁號乘以頁大小就給我們檔案中頁所在位置的位元組偏移量。我們可以使用這些頁引用來構建頁樹，如 圖 4-5 所示。

圖 4-5. 使用 B 樹索引查詢鍵 251。從根頁開始，我們首先跟隨引用到鍵 200–300 的頁，然後是鍵 250–270 的頁。

一個頁被指定為 B 樹的 根；每當你想在索引中查詢一個鍵時，你就從這裡開始。該頁包含幾個鍵和對子頁的引用。每個子負責一個連續的鍵範圍，引用之間的鍵指示這些範圍之間的邊界在哪裡。（這種結構有時稱為 B+ 樹，但我們不需要將其與其他 B 樹變體區分開來。）

在 圖 4-5 的例子中，我們正在查詢鍵 251，所以我們知道我們需要跟隨邊界 200 和 300 之間的頁引用。這將我們帶到一個看起來相似的頁，該頁進一步將 200–300 範圍分解為子範圍。最終我們到達包含單個鍵的頁（葉頁），該頁要麼內聯包含每個鍵的值，要麼包含對可以找到值的頁的引用。

B 樹的一個頁中對子頁的引用數稱為 分支因子。例如，在 圖 4-5 中，分支因子為六。實際上，分支因子取決於儲存頁引用和範圍邊界所需的空間量，但通常為幾百。

如果你想更新 B 樹中現有鍵的值，你搜索包含該鍵的葉頁，並用包含新值的版本覆蓋磁碟上的該頁。如果你想新增一個新鍵，你需要找到其範圍包含新鍵的頁並將其新增到該頁。如果頁中沒有足夠的空閒空間來容納新鍵，則頁被分成兩個半滿的頁，並更新父頁以說明鍵範圍的新細分。

圖 4-6. 透過在邊界鍵 337 上分割頁來增長 B 樹。父頁被更新以引用兩個子頁。

在 圖 4-6 的例子中，我們想插入鍵 334，但範圍 333–345 的頁已經滿了。因此，我們將其分成範圍 333–337（包括新鍵）的頁和 337–344 的頁。我們還必須更新父頁以引用兩個子頁，它們之間的邊界值為 337。如果父頁沒有足夠的空間容納新引用，它也可能需要被分割，分割可以一直持續到樹的根。當根被分割時，我們在它上面建立一個新根。刪除鍵（可能需要合併節點）更複雜 5。

這個演算法確保樹保持 平衡：具有 n 個鍵的 B 樹始終具有 O(log n) 的深度。大多數資料庫可以適合三或四層深的 B 樹，所以你不需要跟隨許多頁引用來找到你要查詢的頁。（具有 500 分支因子的 4 KiB 頁的四層樹可以儲存多達 250 TB。）

使 B 樹可靠

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

一次覆蓋多個頁，如在頁分割中，是一個危險的操作：如果資料庫在只寫入了部分頁後崩潰，你最終會得到一個損壞的樹（例如，可能有一個 孤立 頁，它不是任何父頁的子頁）。如果硬體不能原子地寫入整個頁，你也可能最終得到部分寫入的頁（這稱為 撕裂頁（torn page）23）。

為了使資料庫對崩潰具有彈性，B 樹實現通常包括磁碟上的額外資料結構：預寫日誌（write-ahead log，WAL）。這是一個僅追加檔案，每個 B 樹修改必須在應用於樹本身的頁之前寫入其中。當資料庫在崩潰後恢復時，此日誌用於將 B 樹恢復到一致狀態 2 24。在檔案系統中，等效機制稱為 日誌記錄（journaling）。

為了提高效能，B 樹實現通常不會立即將每個修改的頁寫入磁碟，而是首先將 B 樹頁緩衝在記憶體中一段時間。預寫日誌還確保在崩潰的情況下資料不會丟失：只要資料已寫入 WAL，並使用 fsync() 系統呼叫重新整理到磁碟，資料就是持久的，因為資料庫將能夠在崩潰後恢復它 25。

B 樹變體

由於 B 樹已經存在了很長時間，多年來已經開發了許多變體。僅舉幾個例子：

  • 一些資料庫（如 LMDB）使用寫時複製方案 26，而不是覆蓋頁並維護 WAL 以進行崩潰恢復。修改的頁被寫入不同的位置，並建立樹中父頁的新版本，指向新位置。這種方法對於併發控制也很有用，我們將在 “快照隔離和可重複讀” 中看到。
  • 我們可以透過不儲存整個鍵而是縮寫它來節省頁中的空間。特別是在樹內部的頁中，鍵只需要提供足夠的資訊來充當鍵範圍之間的邊界。在頁中打包更多鍵允許樹具有更高的分支因子，從而減少層數。
  • 為了加快按排序順序掃描鍵範圍，一些 B 樹實現嘗試佈局樹，使葉頁按順序出現在磁碟上，減少磁碟尋道次數。然而，隨著樹的增長，很難維持這種順序。
  • 已向樹添加了其他指標。例如，每個葉頁可能有對其左右兄弟頁的引用，這允許按順序掃描鍵而無需跳回父頁。

比較 B 樹與 LSM 樹

作為經驗法則，LSM 樹更適合寫入密集型應用，而 B 樹對讀取更快 27 28。然而，基準測試通常對工作負載的細節很敏感。你需要使用特定的工作負載測試系統，以便進行有效的比較。此外，這不是 LSM 和 B 樹之間的嚴格二選一選擇：儲存引擎有時會混合兩種方法的特徵，例如具有多個 B 樹並以 LSM 風格合併它們。在本節中，我們將簡要討論在衡量儲存引擎效能時值得考慮的幾件事。

讀取效能

在 B 樹中，查詢鍵涉及在 B 樹的每個級別讀取一個頁。由於級別數通常很小，這意味著從 B 樹讀取通常很快並且具有可預測的效能。在 LSM 儲存引擎中，讀取通常必須檢查處於不同壓實階段的幾個不同 SSTable，但布隆過濾器有助於減少所需的實際磁碟 I/O 運算元。兩種方法都可以表現良好，哪個更快取決於儲存引擎的細節和工作負載。

範圍查詢在 B 樹上簡單而快速，因為它們可以使用樹的排序結構。在 LSM 儲存上，範圍查詢也可以利用 SSTable 排序，但它們需要並行掃描所有段並組合結果。布隆過濾器對範圍查詢沒有幫助（因為你需要計算範圍內每個可能鍵的雜湊，這是不切實際的），使得範圍查詢在 LSM 方法中比點查詢更昂貴 29。

如果記憶體表填滿，高寫入吞吐量可能會導致日誌結構儲存引擎中的延遲峰值。如果資料無法足夠快地寫入磁碟，可能是因為壓實過程無法跟上傳入的寫入，就會發生這種情況。許多儲存引擎，包括 RocksDB，在這種情況下執行 背壓：它們暫停所有讀取和寫入，直到記憶體表被寫入磁碟 30 31。

關於讀取吞吐量，現代 SSD（特別是 NVMe）可以並行執行許多獨立的讀請求。LSM 樹和 B 樹都能夠提供高讀取吞吐量，但儲存引擎需要仔細設計以利用這種並行性 32。

順序與隨機寫入

使用 B 樹時，如果應用程式寫入的鍵分散在整個鍵空間中，生成的磁碟操作也會隨機分散，因為儲存引擎需要覆蓋的頁可能位於磁碟的任何位置。另一方面，日誌結構儲存引擎一次寫入整個段檔案（無論是寫出記憶體表還是壓實現有段），這比 B 樹中的頁大得多。

許多小的、分散的寫入模式（如 B 樹中的）稱為 隨機寫入，而較少的大寫入模式（如 LSM 樹中的）稱為 順序寫入。磁碟通常具有比隨機寫入更高的順序寫入吞吐量，這意味著日誌結構儲存引擎通常可以在相同硬體上處理比 B 樹更高的寫入吞吐量。這種差異在旋轉磁碟硬碟（HDD）上特別大；在今天大多數資料庫使用的固態硬碟（SSD）上，差異較小，但仍然明顯（參見 “SSD 上的順序與隨機寫入”）。

SSD 上的順序與隨機寫入

在旋轉磁碟硬碟（HDD）上，順序寫入比隨機寫入快得多：隨機寫入必須機械地將磁頭移動到新位置，並等待碟片的正確部分經過磁頭下方，這需要幾毫秒 —— 在計算時間尺度上是永恆的。然而，SSD（固態硬碟）包括 NVMe（非易失性記憶體快速，即連線到 PCI Express 匯流排的快閃記憶體）現在已經在許多用例中超越了 HDD，它們不受這種機械限制。

儘管如此，SSD 對順序寫入的吞吐量也高於隨機寫入。原因是快閃記憶體可以一次讀取或寫入一頁（通常為 4 KiB），但只能一次擦除一個塊（通常為 512 KiB）。塊中的某些頁可能包含有效資料，而其他頁可能包含不再需要的資料。在擦除塊之前，控制器必須首先將包含有效資料的頁移動到其他塊中；這個過程稱為 垃圾回收（GC）33。

順序寫入工作負載一次寫入更大的資料塊，因此整個 512 KiB 塊很可能屬於單個檔案；當該檔案稍後再次被刪除時，整個塊可以被擦除而無需執行任何 GC。另一方面，對於隨機寫入工作負載，塊更可能包含有效和無效資料頁的混合，因此 GC 必須在塊可以擦除之前執行更多工作 34 35 36。

GC 消耗的寫入頻寬就不能用於應用程式。此外，GC 執行的額外寫入會導致快閃記憶體磨損；因此，隨機寫入比順序寫入更快地磨損驅動器。

寫放大

對於任何型別的儲存引擎，來自應用程式的一次寫請求都會轉換為底層磁碟上的多個 I/O 操作。對於 LSM 樹，一個值首先被寫入日誌以保證永續性，然後在記憶體表寫入磁碟時再次寫入，並且每次鍵值對參與壓即時再次寫入。（如果值明顯大於鍵，可以透過將值與鍵分開儲存，並僅對包含鍵和值引用的 SSTable 執行壓實來減少這種開銷 37。）

B 樹索引必須至少寫入每條資料兩次：一次寫入預寫日誌，一次寫入樹頁本身。此外，它們有時需要寫出整個頁，即使該頁中只有幾個位元組發生了變化，以確保 B 樹在崩潰或斷電後可以正確恢復 38 39。

如果你獲取在某個工作負載中寫入磁碟的總位元組數，然後除以如果你只是寫入沒有索引的僅追加日誌需要寫入的位元組數，你就得到了 寫放大。（有時寫放大是根據 I/O 操作而不是位元組來定義的。）在寫入密集型應用程式中，瓶頸可能是資料庫可以寫入磁碟的速率。在這種情況下，寫放大越高，它在可用磁碟頻寬內可以處理的每秒寫入次數就越少。

寫放大是 LSM 樹和 B 樹中的問題。哪個更好取決於各種因素，例如鍵和值的長度，以及你覆蓋現有鍵與插入新鍵的頻率。對於典型的工作負載，LSM 樹往往具有較低的寫放大，因為它們不必寫入整個頁，並且可以壓縮 SSTable 的塊 40。這是使 LSM 儲存引擎非常適合寫入密集型工作負載的另一個因素。

除了影響吞吐量，寫放大也與 SSD 的磨損有關：寫放大較低的儲存引擎將更慢地磨損 SSD。

在測量儲存引擎的寫入吞吐量時，重要的是要執行足夠長的實驗，以便寫放大的影響變得清晰。當寫入空的 LSM 樹時，還沒有進行壓實，因此所有磁碟頻寬都可用於新寫入。隨著資料庫的增長，新寫入需要與壓實共享磁碟頻寬。

磁碟空間使用

B 樹可能會隨著時間的推移變得 碎片化：例如，如果刪除了大量鍵，資料庫檔案可能包含許多 B 樹不再使用的頁。對 B 樹的後續新增可以使用這些空閒頁，但它們不能輕易地返回給作業系統，因為它們在檔案的中間，所以它們仍然佔用檔案系統上的空間。因此，資料庫需要一個後臺過程來移動頁以更好地放置它們，例如 PostgreSQL 中的真空過程 25。

碎片化在 LSM 樹中不太成問題，因為壓實過程無論如何都會定期重寫資料檔案，而且 SSTable 沒有未使用空間的頁。此外，SSTable 中的鍵值對塊可以更好地壓縮，因此通常比 B 樹在磁碟上產生更小的檔案。被覆蓋的鍵和值繼續消耗空間，直到它們被壓實刪除，但使用分級壓即時，這種開銷相當低 40 41。分層壓實（參見 “壓實策略”）使用更多的磁碟空間，特別是在壓實期間臨時使用。

在磁碟上有一些資料的多個副本也可能是一個問題，當你需要刪除一些資料，並確信它真的已被刪除（也許是為了遵守資料保護法規）。例如，在大多數 LSM 儲存引擎中，已刪除的記錄可能仍然存在於較高級別中，直到代表刪除的墓碑透過所有壓實級別傳播，這可能需要很長時間。專門的儲存引擎設計可以更快地傳播刪除 42。

另一方面，SSTable 段檔案的不可變性質在你想在某個時間點對資料庫進行快照時很有用（例如，用於備份或建立資料庫副本以進行測試）：你可以寫出記憶體表並記錄該時間點存在的段檔案。只要你不刪除快照的一部分的檔案，你就不需要實際複製它們。在其頁被覆蓋的 B 樹中，有效地進行這樣的快照更困難。

多列索引與二級索引

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

擁有 二級索引 也非常常見。在關係資料庫中，你可以使用 CREATE INDEX 命令在同一個表上建立多個二級索引，允許你按主鍵以外的列進行搜尋。例如，在 第 3 章 的 圖 3-1 中，你很可能在 user_id 列上有一個二級索引，以便你可以在每個表中找到屬於同一使用者的所有行。

二級索引可以很容易地從鍵值索引構建。主要區別在於，在二級索引中，索引值不一定是唯一的；也就是說，同一索引條目下可能有許多行（文件、頂點）。這可以透過兩種方式解決：要麼使索引中的每個值成為匹配行識別符號的列表（如全文索引中的倒排列表），要麼透過向其追加行識別符號使每個條目唯一。具有就地更新的儲存引擎（如 B 樹）和日誌結構儲存都可用於實現索引。

在索引中儲存值

索引中的鍵是查詢搜尋的內容，但值可以是幾種東西之一：

  • 如果實際資料（行、文件、頂點）直接儲存在索引結構中，則稱為 聚簇索引。例如，在 MySQL 的 InnoDB 儲存引擎中，表的主鍵始終是聚簇索引，在 SQL Server 中，你可以為每個表指定一個聚簇索引 43。
  • 或者，值可以是對實際資料的引用：要麼是相關行的主鍵（InnoDB 對二級索引這樣做），要麼是對磁碟上位置的直接引用。在後一種情況下，儲存行的地方稱為 堆檔案，它以無特定順序儲存資料（它可能是僅追加的，或者它可能跟蹤已刪除的行以便稍後用新資料覆蓋它們）。例如，Postgres 使用堆檔案方法 44。
  • 兩者之間的折中是 覆蓋索引 或 包含列的索引，它在索引中儲存表的 某些 列，除了在堆上或主鍵聚簇索引中儲存完整行 45。這允許僅使用索引來回答某些查詢，而無需解析主鍵或檢視堆檔案（在這種情況下，索引被稱為 覆蓋 查詢）。這可以使某些查詢更快，但資料的重複意味著索引使用更多的磁碟空間並減慢寫入速度。

到目前為止討論的索引只將單個鍵對映到值。如果你需要同時查詢表的多個列（或文件中的多個欄位），請參見 “多維索引與全文索引”。

當更新值而不更改鍵時，堆檔案方法可以允許記錄就地覆蓋，前提是新值不大於舊值。如果新值更大，情況會更複雜，因為它可能需要移動到堆中有足夠空間的新位置。在這種情況下，要麼所有索引都需要更新以指向記錄的新堆位置，要麼在舊堆位置留下轉發指標 2。

全記憶體儲存

本章到目前為止討論的資料結構都是對磁碟限制的回應。與主記憶體相比，磁碟很難處理。對於磁碟和 SSD，如果你想在讀取和寫入上獲得良好的效能，磁碟上的資料需要仔細布局。然而，我們容忍這種尷尬，因為磁碟有兩個顯著的優勢：它們是持久的（如果斷電，其內容不會丟失），並且它們每千兆位元組的成本比 RAM 低。

隨著 RAM 變得更便宜，每千兆位元組成本的論點被侵蝕。許多資料集根本不是那麼大，因此將它們完全保留在記憶體中是完全可行的，可能分佈在幾臺機器上。這導致了 記憶體資料庫 的發展。

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

當記憶體資料庫重新啟動時，它需要重新載入其狀態，要麼從磁碟，要麼透過網路從副本（除非使用特殊硬體）。儘管寫入磁碟，它仍然是一個記憶體資料庫，因為磁碟僅用作永續性的僅追加日誌，讀取完全從記憶體提供。寫入磁碟還具有操作優勢：磁碟上的檔案可以輕鬆備份、檢查和由外部實用程式分析。

VoltDB、SingleStore 和 Oracle TimesTen 等產品是具有關係模型的記憶體資料庫，供應商聲稱，透過消除管理磁碟資料結構相關的所有開銷，它們可以提供巨大的效能改進 46 47。RAMCloud 是一個開源的記憶體鍵值儲存，具有永續性（對記憶體中的資料以及磁碟上的資料使用日誌結構方法）48。

Redis 和 Couchbase 透過非同步寫入磁碟提供弱永續性。

反直覺的是，記憶體資料庫的效能優勢不是因為它們不需要從磁碟讀取。即使是基於磁碟的儲存引擎，如果你有足夠的記憶體，也可能永遠不需要從磁碟讀取，因為作業系統無論如何都會在記憶體中快取最近使用的磁碟塊。相反，它們可以更快，因為它們可以避免將記憶體資料結構編碼為可以寫入磁碟的形式的開銷 49。

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

分析型資料儲存

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

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

一些資料庫，如 Microsoft SQL Server、SAP HANA 和 SingleStore，在同一產品中支援事務處理和資料倉庫。然而，這些混合事務和分析處理（HTAP）資料庫（在 “資料倉庫” 中介紹）越來越多地成為兩個獨立的儲存和查詢引擎，它們恰好可以透過通用的 SQL 介面訪問 50 51 52 53。

雲資料倉庫

Teradata、Vertica 和 SAP HANA 等資料倉庫供應商既銷售商業許可下的本地倉庫，也銷售基於雲的解決方案。但隨著他們的許多客戶轉向雲，新的雲資料倉庫（如 Google Cloud BigQuery、Amazon Redshift 和 Snowflake）也變得廣泛採用。與傳統資料倉庫不同，雲資料倉庫利用可擴充套件的雲基礎設施，如物件儲存和無伺服器計算平臺。

雲資料倉庫往往與其他雲服務更好地整合，並且更具彈性。例如，許多雲倉庫支援自動日誌攝取，並提供與資料處理框架（如 Google Cloud 的 Dataflow 或 Amazon Web Services 的 Kinesis）的輕鬆整合。這些倉庫也更具彈性，因為它們將查詢計算與儲存層解耦 54。資料持久儲存在物件儲存而不是本地磁碟上，這使得可以獨立調整儲存容量和查詢的計算資源，正如我們之前在 “雲原生系統架構” 中看到的。

Apache Hive、Trino 和 Apache Spark 等開源資料倉庫也隨著雲的發展而發展。隨著分析資料儲存轉移到物件儲存上的資料湖，開源倉庫已經開始分解 55。以下元件以前整合在單個系統（如 Apache Hive）中，現在通常作為單獨的元件實現：

查詢引擎
Trino、Apache DataFusion 和 Presto 等查詢引擎解析 SQL 查詢，將其最佳化為執行計劃，並針對資料執行它們。執行通常需要並行、分散式資料處理任務。一些查詢引擎提供內建任務執行，而其他選擇使用第三方執行框架，如 Apache Spark 或 Apache Flink。
儲存格式
儲存格式確定表的行如何編碼為檔案中的位元組，然後通常儲存在物件儲存或分散式檔案系統中 12。然後查詢引擎可以訪問這些資料，但使用資料湖的其他應用程式也可以訪問。此類儲存格式的示例包括 Parquet、ORC、Lance 或 Nimble，我們將在下一節中看到更多關於它們的內容。
表格式
以 Apache Parquet 和類似儲存格式編寫的檔案一旦編寫通常是不可變的。為了支援行插入和刪除，使用 Apache Iceberg 或 Databricks 的 Delta 格式等表格式。表格式指定定義哪些檔案構成表以及表模式的檔案格式。此類格式還提供高階功能，例如時間旅行（查詢表在以前時間點的能力）、垃圾回收，甚至事務。
資料目錄
就像表格式定義哪些檔案構成表一樣，資料目錄定義哪些表組成資料庫。目錄用於建立、重新命名和刪除表。與儲存和表格式不同，Snowflake 的 Polaris 和 Databricks 的 Unity Catalog 等資料目錄通常作為可以使用 REST 介面查詢的獨立服務執行。Apache Iceberg 也提供目錄，可以在客戶端內執行或作為單獨的程序執行。查詢引擎在讀取和寫入表時使用目錄資訊。傳統上，目錄和查詢引擎已經整合，但將它們解耦使資料發現和資料治理系統（在 “資料系統、法律和社會” 中討論）也能夠訪問目錄的元資料。

列式儲存

如 “星型和雪花型：分析模式” 中所討論的，資料倉庫按照慣例通常使用帶有大型事實表的關係模式，該表包含對維度表的外部索引鍵引用。如果你的事實表中有數萬億行和數 PB 的資料，有效地儲存和查詢它們就成為一個具有挑戰性的問題。維度表通常要小得多（數百萬行），因此在本節中我們將重點關注事實的儲存。

儘管事實表通常有超過 100 列，但典型的資料倉庫查詢一次只訪問其中的 4 或 5 列（分析很少需要 "SELECT *" 查詢）52。以 示例 4-1 中的查詢為例：它訪問大量行（2024 日曆年期間每次有人購買水果或糖果的情況），但它只需要訪問 fact_sales 表的三列：date_key、product_sk 和 quantity。查詢忽略所有其他列。

示例 4-1. 分析人們是否更傾向於購買新鮮水果或糖果，取決於星期幾

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 = 2024 AND
    dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
    dim_date.weekday, dim_product.category;

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

在大多數 OLTP 資料庫中，儲存是以 面向行 的方式佈局的：表中一行的所有值彼此相鄰儲存。文件資料庫類似：整個文件通常作為一個連續的位元組序列儲存。你可以在 圖 4-1 的 CSV 示例中看到這一點。

為了處理像 示例 4-1 這樣的查詢，你可能在 fact_sales.date_key 和/或 fact_sales.product_sk 上有索引，告訴儲存引擎在哪裡找到特定日期或特定產品的所有銷售。但是，面向行的儲存引擎仍然需要將所有這些行（每行包含超過 100 個屬性）從磁碟載入到記憶體中，解析它們，並過濾掉不符合所需條件的行。這可能需要很長時間。

面向列（或 列式）儲存背後的想法很簡單：不要將一行中的所有值儲存在一起，而是將每 列 中的所有值儲存在一起 56。如果每列單獨儲存，查詢只需要讀取和解析該查詢中使用的那些列，這可以節省大量工作。圖 4-7 使用 圖 3-5 中事實表的擴充套件版本展示了這一原理。

Note

列儲存在關係資料模型中最容易理解，但它同樣適用於非關係資料。例如，Parquet 57 是一種列式儲存格式，它支援基於 Google 的 Dremel 58 的文件資料模型，使用一種稱為 分解（shredding）或 條帶化（striping）的技術 59。

圖 4-7. 按列而不是按行儲存關係資料。

面向列的儲存佈局依賴於每列以相同順序儲存行。因此，如果你需要重新組裝整行，你可以從每個單獨的列中取出第 23 個條目，並將它們組合在一起形成表的第 23 行。

實際上，列式儲存引擎並不真的一次儲存整個列（可能包含數萬億行）。相反，它們將表分解為數千或數百萬行的塊，並且在每個塊內，它們分別儲存每列的值 60。由於許多查詢都限制在特定的日期範圍內，因此通常使每個塊包含特定時間戳範圍的行。然後查詢只需要在與所需日期範圍重疊的那些塊中載入它需要的列。

列式儲存如今幾乎用於所有分析資料庫 60，從大規模雲資料倉庫（如 Snowflake 61）到單節點嵌入式資料庫（如 DuckDB 62），以及產品分析系統（如 Pinot 63 和 Druid 64）。它用於儲存格式，如 Parquet、ORC 65 66、Lance 67 和 Nimble 68，以及記憶體分析格式，如 Apache Arrow 65 69 和 Pandas/NumPy 70。一些時間序列資料庫，如 InfluxDB IOx 71 和 TimescaleDB 72，也基於面向列的儲存。

列壓縮

除了只從磁碟載入查詢所需的那些列之外，我們還可以透過壓縮資料進一步減少對磁碟吞吐量和網路頻寬的需求。幸運的是，面向列的儲存通常非常適合壓縮。

看看 圖 4-7 中每列的值序列：它們看起來經常重複，這是壓縮的良好跡象。根據列中的資料，可以使用不同的壓縮技術。在資料倉庫中特別有效的一種技術是 點陣圖編碼，如 圖 4-8 所示。

圖 4-8. 單列的壓縮、點陣圖索引儲存。

通常，列中不同值的數量與行數相比很小（例如，零售商可能有數十億條銷售交易，但只有 100,000 種不同的產品）。我們現在可以將具有 n 個不同值的列轉換為 n 個單獨的點陣圖：每個不同值一個位圖，每行一位。如果該行具有該值，則該位為 1，否則為 0。

一種選擇是使用每行一位來儲存這些點陣圖。然而，這些點陣圖通常包含大量零（我們說它們是 稀疏 的）。在這種情況下，點陣圖可以另外進行遊程編碼：計算連續零或一的數量並存儲該數字，如 圖 4-8 底部所示。諸如 咆哮點陣圖（roaring bitmaps）之類的技術在兩種位圖表示之間切換，使用最緊湊的表示 73。這可以使列的編碼非常高效。

像這樣的點陣圖索引非常適合資料倉庫中常見的查詢型別。例如：

WHERE product_sk IN (31, 68, 69):
載入 product_sk = 31、product_sk = 68 和 product_sk = 69 的三個點陣圖，並計算三個點陣圖的按位 OR，這可以非常高效地完成。
WHERE product_sk = 30 AND store_sk = 3:
載入 product_sk = 30 和 store_sk = 3 的點陣圖，並計算按位 AND。這有效是因為列以相同的順序包含行，所以一列點陣圖中的第 k 位對應於另一列點陣圖中第 k 位的同一行。

點陣圖也可用於回答圖查詢，例如查詢社交網路中被使用者 X 關注並且也關注使用者 Y 的所有使用者 74。列式資料庫還有各種其他壓縮方案，你可以在參考文獻中找到 75。

Note

不要將面向列的資料庫與 寬列（也稱為 列族）資料模型混淆，在該模型中，一行可以有數千列，並且不需要所有行都有相同的列 9。儘管名稱相似，寬列資料庫是面向行的，因為它們將一行中的所有值儲存在一起。Google 的 Bigtable、Apache Accumulo 和 HBase 是寬列模型的例子。

列儲存中的排序順序

在列儲存中，行的儲存順序並不一定重要。最簡單的是按插入順序儲存它們，因為這樣插入新行只需追加到每列。但是，我們可以選擇強制執行順序，就像我們之前對 SSTable 所做的那樣，並將其用作索引機制。

請注意，獨立排序每列是沒有意義的，因為那樣我們就不再知道列中的哪些項屬於同一行。我們只能重建一行，因為我們知道一列中的第 k 個項與另一列中的第 k 個項屬於同一行。

相反，資料需要一次排序整行，即使它是按列儲存的。資料庫管理員可以使用他們對常見查詢的瞭解來選擇表應按哪些列排序。例如，如果查詢經常針對日期範圍（例如上個月），則將 date_key 作為第一個排序鍵可能是有意義的。然後查詢可以只掃描上個月的行，這將比掃描所有行快得多。

第二列可以確定在第一列中具有相同值的任何行的排序順序。例如，如果 date_key 是 圖 4-7 中的第一個排序鍵，那麼 product_sk 作為第二個排序鍵可能是有意義的，這樣同一天同一產品的所有銷售都在儲存中分組在一起。這將有助於需要在某個日期範圍內按產品分組或過濾銷售的查詢。

排序順序的另一個優點是它可以幫助壓縮列。如果主排序列沒有許多不同的值，那麼排序後，它將有很長的序列，其中相同的值在一行中重複多次。簡單的遊程編碼，就像我們在 圖 4-8 中用於點陣圖的那樣，可以將該列壓縮到幾千位元組 —— 即使表有數十億行。

該壓縮效果在第一個排序鍵上最強。第二和第三個排序鍵將更加混亂，因此不會有如此長的重複值執行。排序優先順序較低的列基本上以隨機順序出現，因此它們可能不會壓縮得那麼好。但是，讓前幾列排序仍然是整體上的勝利。

寫入列式儲存

我們在 “事務處理和分析的特徵” 中看到，資料倉庫中的讀取往往包括大量行的聚合；列式儲存、壓縮和排序都有助於使這些讀取查詢更快。資料倉庫中的寫入往往是資料的批次匯入，通常透過 ETL 過程。

使用列式儲存，在排序表的中間某處寫入單個行將非常低效，因為你必須從插入位置開始重寫所有壓縮列。但是，一次批次寫入許多行會分攤重寫這些列的成本，使其高效。

通常使用日誌結構方法以批次執行寫入。所有寫入首先進入面向行的、排序的記憶體儲存。當積累了足夠的寫入時，它們將與磁碟上的列編碼檔案合併，並批次寫入新檔案。由於舊檔案保持不可變，新檔案一次寫入，物件儲存非常適合儲存這些檔案。

查詢需要檢查磁碟上的列資料和記憶體中的最近寫入，並將兩者結合起來。查詢執行引擎對使用者隱藏了這種區別。從分析師的角度來看，已透過插入、更新或刪除修改的資料會立即反映在後續查詢中。Snowflake、Vertica、Apache Pinot、Apache Druid 和許多其他系統都這樣做 61 63 64 76。

查詢執行：編譯與向量化

用於分析的複雜 SQL 查詢被分解為由多個階段組成的 查詢計劃，稱為 運算元，這些運算元可能分佈在多臺機器上以並行執行。查詢規劃器可以透過選擇使用哪些運算元、以何種順序執行它們以及在哪裡執行每個運算元來執行大量最佳化。

在每個運算元內，查詢引擎需要對列中的值執行各種操作，例如查詢值在特定值集中的所有行（可能作為連線的一部分），或檢查值是否大於 15。它還需要檢視同一行的幾列，例如查詢產品是香蕉且商店是特定感興趣商店的所有銷售交易。

對於需要掃描數百萬行的資料倉庫查詢，我們不僅需要擔心它們需要從磁碟讀取的資料量，還需要擔心執行複雜運算元所需的 CPU 時間。最簡單的運算元型別就像程式語言的直譯器：在遍歷每一行時，它檢查表示查詢的資料結構，以找出需要對哪些列執行哪些比較或計算。不幸的是，這對許多分析目的來說太慢了。高效查詢執行的兩種替代方法已經出現 77：

查詢編譯
查詢引擎獲取 SQL 查詢並生成用於執行它的程式碼。程式碼逐行迭代，檢視感興趣列中的值，執行所需的任何比較或計算，如果滿足所需條件，則將必要的值複製到輸出緩衝區。查詢引擎將生成的程式碼編譯為機器程式碼（通常使用現有編譯器，如 LLVM），然後在已載入到記憶體中的列編碼資料上執行它。這種程式碼生成方法類似於 Java 虛擬機器（JVM）和類似執行時中使用的即時（JIT）編譯方法。
向量化處理
查詢被解釋，而不是編譯，但透過批次處理列中的許多值而不是逐行迭代來提高速度。一組固定的預定義運算元內建在資料庫中；我們可以向它們傳遞引數並獲得一批結果 50 75。

例如，我們可以將 product_sk 列和"香蕉"的 ID 傳遞給相等運算元，並獲得一個位圖（輸入列中每個值一位，如果是香蕉則為 1）；然後我們可以將 store_sk 列和感興趣商店的 ID 傳遞給相同的相等運算元，並獲得另一個位圖；然後我們可以將兩個點陣圖傳遞給"按位 AND"運算元，如 圖 4-9 所示。結果將是一個位圖，包含特定商店中所有香蕉銷售的 1。

圖 4-9. 兩個點陣圖之間的按位 AND 適合向量化。

這兩種方法在實現方面非常不同，但兩者都在實踐中使用 77。兩者都可以透過利用現代 CPU 的特性來實現非常好的效能：

  • 優先選擇順序記憶體訪問而不是隨機訪問以減少快取未命中 78，
  • 在緊密的內部迴圈中完成大部分工作（即，具有少量指令且沒有函式呼叫）以保持 CPU 指令處理管道繁忙併避免分支預測錯誤，
  • 利用並行性，例如多執行緒和單指令多資料（SIMD）指令 79 80，以及
  • 直接對壓縮資料進行操作，而無需將其解碼為單獨的記憶體表示，這可以節省記憶體分配和複製成本。

物化檢視與多維資料集

我們之前在 “物化和更新時間線” 中遇到了 物化檢視：在關係資料模型中，它們是表狀物件，其內容是某些查詢的結果。區別在於物化檢視是查詢結果的實際副本，寫入磁碟，而虛擬檢視只是編寫查詢的快捷方式。當你從虛擬檢視讀取時，SQL 引擎會即時將其擴充套件為檢視的基礎查詢，然後處理擴充套件的查詢。

當基礎資料更改時，物化檢視需要相應更新。一些資料庫可以自動執行此操作，還有像 Materialize 這樣專門從事物化檢視維護的系統 81。執行此類更新意味著寫入時需要更多工作，但物化檢視可以改善在重複需要執行相同查詢的工作負載中的讀取效能。

物化聚合 是一種可以在資料倉庫中有用的物化檢視型別。如前所述，資料倉庫查詢通常涉及聚合函式，例如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果許多不同的查詢使用相同的聚合，每次都處理原始資料可能會很浪費。為什麼不快取查詢最常使用的一些計數或總和？多維資料集 或 OLAP 立方體 透過建立按不同維度分組的聚合網格來做到這一點 82。圖 4-10 顯示了一個示例。

圖 4-10. 多維資料集的兩個維度，透過求和聚合資料。

現在假設每個事實只有兩個維度表的外部索引鍵 —— 在 圖 4-10 中，這些是 date_key 和 product_sk。你現在可以繪製一個二維表，日期沿著一個軸，產品沿著另一個軸。每個單元格包含具有該日期-產品組合的所有事實的屬性（例如 net_price）的聚合（例如 SUM）。然後，你可以沿著每行或列應用相同的聚合，並獲得已減少一個維度的摘要（不管日期的產品銷售，或不管產品的日期銷售）。

一般來說，事實通常有兩個以上的維度。在 圖 3-5 中有五個維度：日期、產品、商店、促銷和客戶。很難想象五維超立方體會是什麼樣子，但原理保持不變：每個單元格包含特定日期-產品-商店-促銷-客戶組合的銷售。然後可以沿著每個維度重複彙總這些值。

物化多維資料集的優點是某些查詢變得非常快，因為它們已經有效地預先計算了。例如，如果你想知道昨天每個商店的總銷售額，你只需要檢視適當維度的總計 —— 不需要掃描數百萬行。

缺點是多維資料集沒有與查詢原始資料相同的靈活性。例如，沒有辦法計算成本超過 100 美元的商品的銷售比例，因為價格不是維度之一。因此，大多數資料倉庫儘可能多地保留原始資料，並僅將聚合（如多維資料集）用作某些查詢的效能提升。

多維索引與全文索引

我們在本章前半部分看到的 B 樹和 LSM 樹允許對單個屬性進行範圍查詢：例如，如果鍵是使用者名稱，你可以使用它們作為索引來高效查詢所有以 L 開頭的名稱。但有時，按單個屬性搜尋是不夠的。

最常見的多列索引型別稱為 聯合索引，它透過將一列追加到另一列來將幾個欄位組合成一個鍵（索引定義指定欄位以何種順序連線）。這就像老式的紙質電話簿，它提供從（姓氏、名字）到電話號碼的索引。由於排序順序，索引可用於查詢具有特定姓氏的所有人，或具有特定 姓氏-名字 組合的所有人。但是，如果你想查詢具有特定名字的所有人，索引是無用的。

另一方面，多維索引 允許你一次查詢多個列。在地理空間資料中這尤其重要。例如，餐廳搜尋網站可能有一個包含每個餐廳的緯度和經度的資料庫。當用戶在地圖上檢視餐廳時，網站需要搜尋使用者當前檢視的矩形地圖區域內的所有餐廳。這需要像以下這樣的二維範圍查詢：

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

緯度和經度列上的聯合索引無法有效地回答這種查詢：它可以為你提供緯度範圍內的所有餐廳（但在任何經度），或經度範圍內的所有餐廳（但在北極和南極之間的任何地方），但不能同時提供兩者。

一種選擇是使用空間填充曲線將二維位置轉換為單個數字，然後使用常規 B 樹索引 83。更常見的是，使用專門的空間索引，如 R 樹或 Bkd 樹 84；它們劃分空間，使附近的資料點傾向於分組在同一子樹中。例如，PostGIS 使用 PostgreSQL 的通用搜索樹索引設施將地理空間索引實現為 R 樹 85。也可以使用規則間隔的三角形、正方形或六邊形網格 86。

多維索引不僅用於地理位置。例如，在電子商務網站上，你可以在維度（紅色、綠色、藍色）上使用三維索引來搜尋某個顏色範圍內的產品，或者在天氣觀測資料庫中，你可以在（日期、溫度）上有一個二維索引，以便有效地搜尋 2013 年期間溫度在 25 到 30°C 之間的所有觀測。使用一維索引，你必須掃描 2013 年的所有記錄（不管溫度），然後按溫度過濾它們，反之亦然。二維索引可以同時按時間戳和溫度縮小範圍 87。

全文檢索

全文檢索允許你透過可能出現在文字中任何位置的關鍵字搜尋文字文件集合（網頁、產品描述等）88。資訊檢索是一個大的專業主題，通常涉及特定於語言的處理：例如，幾種亞洲語言在單詞之間沒有空格或標點符號，因此將文字分割成單詞需要一個指示哪些字元序列構成單詞的模型。全文檢索還經常涉及匹配相似但不相同的單詞（例如拼寫錯誤或單詞的不同語法形式）和同義詞。這些問題超出了本書的範圍。

然而，在其核心，你可以將全文檢索視為另一種多維查詢：在這種情況下，可能出現在文字中的每個單詞（詞項）是一個維度。包含詞項 x 的文件在維度 x 中的值為 1，不包含 x 的文件的值為 0。搜尋提到"紅蘋果"的文件意味著查詢在 紅 維度中查詢 1，同時在 蘋果 維度中查詢 1。維度數量可能因此非常大。

許多搜尋引擎用來回答此類查詢的資料結構稱為 倒排索引。這是一個鍵值結構，其中鍵是詞項，值是包含該詞項的所有文件的 ID 列表（倒排列表）。如果文件 ID 是順序數字，倒排列表也可以表示為稀疏點陣圖，如 圖 4-8：詞項 x 的點陣圖中的第 n 位是 1，如果 ID 為 n 的文件包含詞項 x 89。

查詢包含詞項 x 和 y 的所有文件現在類似於搜尋匹配兩個條件的行的向量化資料倉庫查詢（圖 4-9）：載入詞項 x 和 y 的兩個點陣圖並計算它們的按位 AND。即使點陣圖是遊程編碼的，這也可以非常高效地完成。

例如，Elasticsearch 和 Solr 使用的全文索引引擎 Lucene 就是這樣工作的 90。它將詞項到倒排列表的對映儲存在類似 SSTable 的排序檔案中，這些檔案使用我們在本章前面看到的相同日誌結構方法在後臺合併 91。PostgreSQL 的 GIN 索引型別也使用倒排列表來支援全文檢索和 JSON 文件內的索引 92 93。

除了將文字分解為單詞，另一種選擇是查詢長度為 n 的所有子字串，稱為 n 元語法。例如，字串 "hello" 的三元語法（n = 3）是 "hel"、"ell" 和 "llo"。如果我們為所有三元語法構建倒排索引，我們可以搜尋至少三個字元長的任意子字串的文件。三元語法索引甚至允許在搜尋查詢中使用正則表示式；缺點是它們相當大 94。

為了處理文件或查詢中的拼寫錯誤，Lucene 能夠在一定編輯距離內搜尋文字中的單詞（編輯距離為 1 意味著已新增、刪除或替換了一個字母）95。它透過將詞項集儲存為字元上的有限狀態自動機（類似於 字典樹 96）並將其轉換為 萊文斯坦自動機 來實現，該自動機支援在給定編輯距離內高效搜尋單詞 97。

向量嵌入

語義搜尋超越了同義詞和拼寫錯誤，試圖理解文件概念和使用者意圖。例如，如果你的幫助頁面包含標題為"取消訂閱"的頁面，使用者在搜尋"如何關閉我的帳戶"或"終止合同"時仍應能夠找到該頁面，即使它們使用完全不同的單詞，但在含義上很接近。

為了理解文件的語義 —— 它的含義 —— 語義搜尋索引使用嵌入模型將文件轉換為浮點值向量，稱為 向量嵌入。向量表示多維空間中的一個點，每個浮點值表示文件沿著一個維度軸的位置。嵌入模型生成的向量嵌入在（這個多維空間中）彼此接近，當嵌入的輸入文件在語義上相似時。

Note

我們在 “查詢執行：編譯與向量化” 中看到了術語 向量化處理。語義搜尋中的向量有不同的含義。在向量化處理中，向量指的是可以用特別最佳化的程式碼處理的一批位。在嵌入模型中，向量是表示多維空間中位置的浮點數列表。

例如，關於農業的維基百科頁面的三維向量嵌入可能是 [0.1, 0.22, 0.11]。關於蔬菜的維基百科頁面會非常接近，可能嵌入為 [0.13, 0.19, 0.24]。關於星型模式的頁面可能有 [0.82, 0.39, -0.74] 的嵌入，相對較遠。我們可以透過觀察看出前兩個向量比第三個更接近。

嵌入模型使用更大的向量（通常超過 1,000 個數字），但原理是相同的。我們不試圖理解各個數字的含義；它們只是嵌入模型指向抽象多維空間中位置的一種方式。搜尋引擎使用距離函式（如餘弦相似度或歐幾里得距離）來測量向量之間的距離。餘弦相似度測量兩個向量角度的餘弦以確定它們的接近程度，而歐幾里得距離測量空間中兩點之間的直線距離。

許多早期的嵌入模型，如 Word2Vec 98、BERT 99 和 GPT 100 都處理文字資料。這些模型通常實現為神經網路。研究人員繼續為影片、音訊和影像建立嵌入模型。最近，模型架構已經變成 多模態 的：單個模型可以為多種模態（如文字和影像）生成向量嵌入。

語義搜尋引擎在使用者輸入查詢時使用嵌入模型生成向量嵌入。使用者的查詢和相關上下文（例如使用者的位置）被輸入到嵌入模型中。嵌入模型生成查詢的向量嵌入後，搜尋引擎必須使用向量索引找到具有相似向量嵌入的文件。

向量索引儲存文件集合的向量嵌入。要查詢索引，你傳入查詢的向量嵌入，索引返回其向量最接近查詢向量的文件。由於我們之前看到的 R 樹不適用於多維向量，因此使用專門的向量索引，例如：

平面索引（Flat indexes）
向量按原樣儲存在索引中。查詢必須讀取每個向量並測量其與查詢向量的距離。平面索引是準確的，但測量查詢與每個向量之間的距離很慢。
倒排檔案（IVF）索引
向量空間被聚類為向量的分割槽（稱為 質心），以減少必須比較的向量數量。IVF 索引比平面索引更快，但只能給出近似結果：即使查詢和文件彼此接近，它們也可能落入不同的分割槽。對 IVF 索引的查詢首先定義 探針，這只是要檢查的分割槽數。使用更多探針的查詢將更準確，但會更慢，因為必須比較更多向量。
分層可導航小世界（HNSW）
HNSW 索引維護向量空間的多個層，如 圖 4-11 所示。每一層都表示為一個圖，其中節點表示向量，邊表示與附近向量的接近度。查詢首先在最頂層定位最近的向量，該層具有少量節點。然後查詢移動到下面一層的同一節點，並跟隨該層中的邊，該層連線更密集，尋找更接近查詢向量的向量。該過程繼續直到到達最後一層。與 IVF 索引一樣，HNSW 索引是近似的。
圖 4-11. 在 HNSW 索引中搜索最接近給定查詢向量的資料庫條目。

許多流行的向量資料庫實現了 IVF 和 HNSW 索引。Facebook 的 Faiss 庫有每種的許多變體 101，PostgreSQL 的 pgvector 也支援兩者 102。IVF 和 HNSW 演算法的完整細節超出了本書的範圍，但它們的論文是極好的資源 103 104。

總結

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

“分析型與事務型系統” 介紹了事務處理（OLTP）和分析（OLAP）之間的區別。在本章中，我們看到為 OLTP 最佳化的儲存引擎與為分析最佳化的儲存引擎看起來非常不同：

  • OLTP 系統針對大量請求進行了最佳化，每個請求讀取和寫入少量記錄，並且需要快速響應。記錄通常透過主鍵或二級索引訪問，這些索引通常是從鍵到記錄的有序對映，也支援範圍查詢。
  • 資料倉庫和類似的分析系統針對掃描大量記錄的複雜讀取查詢進行了最佳化。它們通常使用帶有壓縮的列式儲存佈局，以最小化此類查詢需要從磁碟讀取的資料量，並使用查詢的即時編譯或向量化來最小化處理資料所花費的 CPU 時間。

在 OLTP 方面，我們看到了兩個主要思想流派的儲存引擎：

  • 日誌結構方法，只允許追加到檔案和刪除過時檔案，但從不更新已寫入的檔案。SSTable、LSM 樹、RocksDB、Cassandra、HBase、Scylla、Lucene 等屬於這一組。一般來說，日誌結構儲存引擎往往提供高寫入吞吐量。
  • 就地更新方法，將磁碟視為一組可以覆蓋的固定大小頁。B 樹是這種理念的最大例子，用於所有主要的關係型 OLTP 資料庫以及許多非關係型資料庫。作為經驗法則，B 樹往往更適合讀取，提供比日誌結構儲存更高的讀取吞吐量和更低的響應時間。

然後我們查看了可以同時搜尋多個條件的索引：多維索引（如 R 樹）可以同時按緯度和經度搜索地圖上的點，全文檢索索引可以搜尋出現在同一文字中的多個關鍵字。最後，向量資料庫用於文字文件和其他媒體的語義搜尋；它們使用具有大量維度的向量，並透過比較向量相似性來查詢相似文件。

作為應用程式開發人員，如果你掌握了有關儲存引擎內部的這些知識，你就能更好地知道哪種工具最適合你的特定應用程式。如果你需要調整資料庫的調優引數，這種理解使你能夠想象更高或更低的值可能產生什麼影響。

儘管本章不能讓你成為調優任何特定儲存引擎的專家，但它希望為你提供了足夠的詞彙和想法，使你能夠理解你選擇的資料庫的文件。

參考

  1. Nikolay Samokhvalov. How partial, covering, and multicolumn indexes may slow down UPDATEs in PostgreSQL. postgres.ai, October 2021. Archived at perma.cc/PBK3-F4G9 ↩︎

  2. Goetz Graefe. Modern B-Tree Techniques. Foundations and Trends in Databases, volume 3, issue 4, pages 203–402, August 2011. doi:10.1561/1900000028 ↩︎ ↩︎ ↩︎

  3. Evan Jones. Why databases use ordered indexes but programming uses hash tables. evanjones.ca, December 2019. Archived at perma.cc/NJX8-3ZZD ↩︎

  4. Branimir Lambov. CEP-25: Trie-indexed SSTable format. cwiki.apache.org, November 2022. Archived at perma.cc/HD7W-PW8U. Linked Google Doc archived at perma.cc/UL6C-AAAE ↩︎

  5. 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 ↩︎ ↩︎ ↩︎

  6. Branimir Lambov. Trie Memtables in Cassandra. Proceedings of the VLDB Endowment, volume 15, issue 12, pages 3359–3371, August 2022. doi:10.14778/3554821.3554828 ↩︎

  7. Dhruba Borthakur. The History of RocksDB. rocksdb.blogspot.com, November 2013. Archived at perma.cc/Z7C5-JPSP ↩︎

  8. Matteo Bertozzi. Apache HBase I/O – HFile. blog.cloudera.com, June 2012. Archived at perma.cc/U9XH-L2KL ↩︎

  9. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: A Distributed Storage System for Structured Data. 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). Acta Informatica, volume 33, issue 4, pages 351–385, June 1996. doi:10.1007/s002360050048 ↩︎

  11. Mendel Rosenblum and John K. Ousterhout. The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems, volume 10, issue 1, pages 26–52, February 1992. doi:10.1145/146941.146943 ↩︎

  12. Michael Armbrust, Tathagata Das, Liwen Sun, Burak Yavuz, Shixiong Zhu, Mukul Murthy, Joseph Torres, Herman van Hovell, Adrian Ionescu, Alicja Łuszczak, Michał Świtakowski, Michał Szafrański, Xiao Li, Takuya Ueshin, Mostafa Mokhtar, Peter Boncz, Ali Ghodsi, Sameer Paranjpye, Pieter Senster, Reynold Xin, and Matei Zaharia. Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores. Proceedings of the VLDB Endowment, volume 13, issue 12, pages 3411–3424, August 2020. doi:10.14778/3415478.3415560 ↩︎ ↩︎

  13. Burton H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, volume 13, issue 7, pages 422–426, July 1970. doi:10.1145/362686.362692 ↩︎

  14. Adam Kirsch and Michael Mitzenmacher. Less Hashing, Same Performance: Building a Better Bloom Filter. Random Structures & Algorithms, volume 33, issue 2, pages 187–218, September 2008. doi:10.1002/rsa.20208 ↩︎

  15. Thomas Hurst. Bloom Filter Calculator. hur.st, September 2023. Archived at perma.cc/L3AV-6VC2 ↩︎

  16. Chen Luo and Michael J. Carey. LSM-based storage techniques: a survey. The VLDB Journal, volume 29, pages 393–418, July 2019. doi:10.1007/s00778-019-00555-y ↩︎

  17. Subhadeep Sarkar and Manos Athanassoulis. Dissecting, Designing, and Optimizing LSM-based Data Stores. Tutorial at ACM International Conference on Management of Data (SIGMOD), June 2022. Slides archived at perma.cc/93B3-E827 ↩︎

  18. Mark Callaghan. Name that compaction algorithm. smalldatum.blogspot.com, August 2018. Archived at perma.cc/CN4M-82DY ↩︎

  19. Prashanth Rao. Embedded databases (1): The harmony of DuckDB, KùzuDB and LanceDB. thedataquarry.com, August 2023. Archived at perma.cc/PA28-2R35 ↩︎

  20. Hacker News discussion. Bluesky migrates to single-tenant SQLite. news.ycombinator.com, October 2023. Archived at perma.cc/69LM-5P6X ↩︎

  21. Rudolf Bayer and Edward M. McCreight. Organization and Maintenance of Large Ordered Indices. Boeing Scientific Research Laboratories, Mathematical and Information Sciences Laboratory, report no. 20, July 1970. doi:10.1145/1734663.1734671 ↩︎

  22. Douglas Comer. The Ubiquitous B-Tree. ACM Computing Surveys, volume 11, issue 2, pages 121–137, June 1979. doi:10.1145/356770.356776 ↩︎

  23. Alex Miller. Torn Write Detection and Protection. transactional.blog, April 2025. Archived at perma.cc/G7EB-33EW ↩︎

  24. C. Mohan and Frank Levine. ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. At ACM International Conference on Management of Data (SIGMOD), June 1992. doi:10.1145/130283.130338 ↩︎

  25. Hironobu Suzuki. The Internals of PostgreSQL. interdb.jp, 2017. ↩︎ ↩︎

  26. Howard Chu. LDAP at Lightning Speed. At Build Stuff ’14, November 2014. Archived at perma.cc/GB6Z-P8YH ↩︎

  27. Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, Radu Stoica, Stratos Idreos, Anastasia Ailamaki, and Mark Callaghan. Designing Access Methods: The RUM Conjecture. At 19th International Conference on Extending Database Technology (EDBT), March 2016. doi:10.5441/002/edbt.2016.42 ↩︎

  28. Ben Stopford. Log Structured Merge Trees. benstopford.com, February 2015. Archived at perma.cc/E5BV-KUJ6 ↩︎

  29. Mark Callaghan. The Advantages of an LSM vs a B-Tree. smalldatum.blogspot.co.uk, January 2016. Archived at perma.cc/3TYZ-EFUD ↩︎

  30. Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. At USENIX Annual Technical Conference, July 2019. ↩︎

  31. Igor Canadi, Siying Dong, Mark Callaghan, et al. RocksDB Tuning Guide. github.com, 2023. Archived at perma.cc/UNY4-MK6C ↩︎

  32. Gabriel Haas and Viktor Leis. What Modern NVMe Storage Can Do, and How to Exploit it: High-Performance I/O for High-Performance Storage Engines. Proceedings of the VLDB Endowment, volume 16, issue 9, pages 2090-2102. doi:10.14778/3598581.3598584 ↩︎

  33. Emmanuel Goossaert. Coding for SSDs. codecapsule.com, February 2014. ↩︎

  34. Jack Vanlightly. Is sequential IO dead in the era of the NVMe drive? jack-vanlightly.com, May 2023. Archived at perma.cc/7TMZ-TAPU ↩︎

  35. Alibaba Cloud Storage Team. Storage System Design Analysis: Factors Affecting NVMe SSD Performance (2). alibabacloud.com, January 2019. Archived at archive.org ↩︎

  36. Xiao-Yu Hu and Robert Haas. The Fundamental Limit of Flash Random Write Performance: Understanding, Analysis and Performance Modelling. dominoweb.draco.res.ibm.com, March 2010. Archived at perma.cc/8JUL-4ZDS ↩︎

  37. Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. WiscKey: Separating Keys from Values in SSD-conscious Storage. At 4th USENIX Conference on File and Storage Technologies (FAST), February 2016. ↩︎

  38. Peter Zaitsev. Innodb Double Write. percona.com, August 2006. Archived at perma.cc/NT4S-DK7T ↩︎

  39. Tomas Vondra. On the Impact of Full-Page Writes. 2ndquadrant.com, November 2016. Archived at perma.cc/7N6B-CVL3 ↩︎

  40. Mark Callaghan. Read, write & space amplification - B-Tree vs LSM. smalldatum.blogspot.com, November 2015. Archived at perma.cc/S487-WK5P ↩︎ ↩︎

  41. Mark Callaghan. Choosing Between Efficiency and Performance with RocksDB. At Code Mesh, November 2016. Video at youtube.com/watch?v=tgzkgZVXKB4 ↩︎

  42. Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis. Enabling Timely and Persistent Deletion in LSM-Engines. ACM Transactions on Database Systems, volume 48, issue 3, article no. 8, August 2023. doi:10.1145/3599724 ↩︎

  43. Lukas Fittl. Postgres vs. SQL Server: B-Tree Index Differences & the Benefit of Deduplication. pganalyze.com, April 2025. Archived at perma.cc/XY6T-LTPX ↩︎

  44. Drew Silcock. How Postgres stores data on disk – this one’s a page turner. drew.silcock.dev, August 2024. Archived at perma.cc/8K7K-7VJ2 ↩︎

  45. Joe Webb. Using Covering Indexes to Improve Query Performance. simple-talk.com, September 2008. Archived at perma.cc/6MEZ-R5VR ↩︎

  46. Michael Stonebraker, Samuel Madden, Daniel J. Abadi, Stavros Harizopoulos, Nabil Hachem, and Pat Helland. The End of an Architectural Era (It’s Time for a Complete Rewrite). At 33rd International Conference on Very Large Data Bases (VLDB), September 2007. ↩︎

  47. VoltDB Technical Overview White Paper. VoltDB, 2017. Archived at perma.cc/B9SF-SK5G ↩︎

  48. Stephen M. Rumble, Ankita Kejriwal, and John K. Ousterhout. Log-Structured Memory for DRAM-Based Storage. At 12th USENIX Conference on File and Storage Technologies (FAST), February 2014. ↩︎

  49. Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker. OLTP Through the Looking Glass, and What We Found There. At ACM International Conference on Management of Data (SIGMOD), June 2008. doi:10.1145/1376616.1376713 ↩︎

  50. Per-Åke Larson, Cipri Clinciu, Campbell Fraser, Eric N. Hanson, Mostafa Mokhtar, Michal Nowakiewicz, Vassilis Papadimos, Susan L. Price, Srikumar Rangarajan, Remus Rusanu, and Mayukh Saubhasik. Enhancements to SQL Server Column Stores. At ACM International Conference on Management of Data (SIGMOD), June 2013. doi:10.1145/2463676.2463708 ↩︎ ↩︎

  51. Franz Färber, Norman May, Wolfgang Lehner, Philipp Große, Ingo Müller, Hannes Rauhe, and Jonathan Dees. The SAP HANA Database – An Architecture Overview. IEEE Data Engineering Bulletin, volume 35, issue 1, pages 28–33, March 2012. ↩︎

  52. Michael Stonebraker. The Traditional RDBMS Wisdom Is (Almost Certainly) All Wrong. Presentation at EPFL, May 2013. ↩︎ ↩︎

  53. Adam Prout, Szu-Po Wang, Joseph Victor, Zhou Sun, Yongzhu Li, Jack Chen, Evan Bergeron, Eric Hanson, Robert Walzer, Rodrigo Gomes, and Nikita Shamgunov. Cloud-Native Transactions and Analytics in SingleStore. At ACM International Conference on Management of Data (SIGMOD), June 2022. doi:10.1145/3514221.3526055 ↩︎

  54. Tino Tereshko and Jordan Tigani. BigQuery under the hood. cloud.google.com, January 2016. Archived at perma.cc/WP2Y-FUCF ↩︎

  55. Wes McKinney. The Road to Composable Data Systems: Thoughts on the Last 15 Years and the Future. wesmckinney.com, September 2023. Archived at perma.cc/6L2M-GTJX ↩︎

  56. Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Sam Madden, Elizabeth O’Neil, Pat O’Neil, Alex Rasin, Nga Tran, and Stan Zdonik. C-Store: A Column-oriented DBMS. At 31st International Conference on Very Large Data Bases (VLDB), pages 553–564, September 2005. ↩︎

  57. Julien Le Dem. Dremel Made Simple with Parquet. blog.twitter.com, September 2013. ↩︎

  58. Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, and Theo Vassilakis. Dremel: Interactive Analysis of Web-Scale Datasets. At 36th International Conference on Very Large Data Bases (VLDB), pages 330–339, September 2010. doi:10.14778/1920841.1920886 ↩︎

  59. Joe Kearney. Understanding Record Shredding: storing nested data in columns. joekearney.co.uk, December 2016. Archived at perma.cc/ZD5N-AX5D ↩︎

  60. Jamie Brandon. A shallow survey of OLAP and HTAP query engines. scattered-thoughts.net, September 2023. Archived at perma.cc/L3KH-J4JF ↩︎ ↩︎

  61. Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis, and Philipp Unterbrunner. The Snowflake Elastic Data Warehouse. At ACM International Conference on Management of Data (SIGMOD), pages 215–226, June 2016. doi:10.1145/2882903.2903741 ↩︎ ↩︎

  62. Mark Raasveldt and Hannes Mühleisen. Data Management for Data Science Towards Embedded Analytics. At 10th Conference on Innovative Data Systems Research (CIDR), January 2020. ↩︎

  63. Jean-François Im, Kishore Gopalakrishna, Subbu Subramaniam, Mayank Shrivastava, Adwait Tumbde, Xiaotian Jiang, Jennifer Dai, Seunghyun Lee, Neha Pawar, Jialiang Li, and Ravi Aringunram. Pinot: Realtime OLAP for 530 Million Users. At ACM International Conference on Management of Data (SIGMOD), pages 583–594, May 2018. doi:10.1145/3183713.3190661 ↩︎ ↩︎

  64. Fangjin Yang, Eric Tschetter, Xavier Léauté, Nelson Ray, Gian Merlino, and Deep Ganguli. Druid: A Real-time Analytical Data Store. At ACM International Conference on Management of Data (SIGMOD), June 2014. doi:10.1145/2588555.2595631 ↩︎ ↩︎

  65. Chunwei Liu, Anna Pavlenko, Matteo Interlandi, and Brandon Haynes. Deep Dive into Common Open Formats for Analytical DBMSs. Proceedings of the VLDB Endowment, volume 16, issue 11, pages 3044–3056, July 2023. doi:10.14778/3611479.3611507 ↩︎ ↩︎

  66. Xinyu Zeng, Yulong Hui, Jiahong Shen, Andrew Pavlo, Wes McKinney, and Huanchen Zhang. An Empirical Evaluation of Columnar Storage Formats. Proceedings of the VLDB Endowment, volume 17, issue 2, pages 148–161. doi:10.14778/3626292.3626298 ↩︎

  67. Weston Pace. Lance v2: A columnar container format for modern data. blog.lancedb.com, April 2024. Archived at perma.cc/ZK3Q-S9VJ ↩︎

  68. Yoav Helfman. Nimble, A New Columnar File Format. At VeloxCon, April 2024. ↩︎

  69. Wes McKinney. Apache Arrow: High-Performance Columnar Data Framework. At CMU Database Group – Vaccination Database Tech Talks, December 2021. ↩︎

  70. Wes McKinney. Python for Data Analysis, 3rd Edition. O’Reilly Media, August 2022. ISBN: 9781098104023 ↩︎

  71. Paul Dix. The Design of InfluxDB IOx: An In-Memory Columnar Database Written in Rust with Apache Arrow. At CMU Database Group – Vaccination Database Tech Talks, May 2021. ↩︎

  72. Carlota Soto and Mike Freedman. Building Columnar Compression for Large PostgreSQL Databases. timescale.com, March 2024. Archived at perma.cc/7KTF-V3EH ↩︎

  73. Daniel Lemire, Gregory Ssi‐Yan‐Kai, and Owen Kaser. Consistently faster and smaller compressed bitmaps with Roaring. Software: Practice and Experience, volume 46, issue 11, pages 1547–1569, November 2016. doi:10.1002/spe.2402 ↩︎

  74. Jaz Volpert. An entire Social Network in 1.6GB (GraphD Part 2). jazco.dev, April 2024. Archived at perma.cc/L27Z-QVMG ↩︎

  75. Daniel J. Abadi, Peter Boncz, Stavros Harizopoulos, Stratos Idreos, and Samuel Madden. The Design and Implementation of Modern Column-Oriented Database Systems. Foundations and Trends in Databases, volume 5, issue 3, pages 197–280, December 2013. doi:10.1561/1900000024 ↩︎ ↩︎

  76. Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear. The Vertica Analytic Database: C-Store 7 Years Later. Proceedings of the VLDB Endowment, volume 5, issue 12, pages 1790–1801, August 2012. doi:10.14778/2367502.2367518 ↩︎

  77. Timo Kersten, Viktor Leis, Alfons Kemper, Thomas Neumann, Andrew Pavlo, and Peter Boncz. Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask. Proceedings of the VLDB Endowment, volume 11, issue 13, pages 2209–2222, September 2018. doi:10.14778/3275366.3284966 ↩︎ ↩︎

  78. Forrest Smith. Memory Bandwidth Napkin Math. forrestthewoods.com, February 2020. Archived at perma.cc/Y8U4-PS7N ↩︎

  79. Peter Boncz, Marcin Zukowski, and Niels Nes. MonetDB/X100: Hyper-Pipelining Query Execution. At 2nd Biennial Conference on Innovative Data Systems Research (CIDR), January 2005. ↩︎

  80. Jingren Zhou and Kenneth A. Ross. Implementing Database Operations Using SIMD Instructions. At ACM International Conference on Management of Data (SIGMOD), pages 145–156, June 2002. doi:10.1145/564691.564709 ↩︎

  81. Kevin Bartley. OLTP Queries: Transfer Expensive Workloads to Materialize. materialize.com, August 2024. Archived at perma.cc/4TYM-TYD8 ↩︎

  82. Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, and Hamid Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals. Data Mining and Knowledge Discovery, volume 1, issue 1, pages 29–53, March 2007. doi:10.1023/A:1009726021843 ↩︎

  83. Frank Ramsak, Volker Markl, Robert Fenk, Martin Zirkel, Klaus Elhardt, and Rudolf Bayer. Integrating the UB-Tree into a Database System Kernel. At 26th International Conference on Very Large Data Bases (VLDB), September 2000. ↩︎

  84. Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge, and Jeffrey Scott Vitter. Bkd-Tree: A Dynamic Scalable kd-Tree. At 8th International Symposium on Spatial and Temporal Databases (SSTD), pages 46–65, July 2003. doi:10.1007/978-3-540-45072-6_4 ↩︎

  85. Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. Generalized Search Trees for Database Systems. At 21st International Conference on Very Large Data Bases (VLDB), September 1995. ↩︎

  86. Isaac Brodsky. H3: Uber’s Hexagonal Hierarchical Spatial Index. eng.uber.com, June 2018. Archived at archive.org ↩︎

  87. Robert Escriva, Bernard Wong, and Emin Gün Sirer. HyperDex: A Distributed, Searchable Key-Value Store. At ACM SIGCOMM Conference, August 2012. doi:10.1145/2377677.2377681 ↩︎

  88. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. ISBN: 978-0-521-86571-5, available online at nlp.stanford.edu/IR-book ↩︎

  89. Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, and Steven Swanson. An Experimental Study of Bitmap Compression vs. Inverted List Compression. At ACM International Conference on Management of Data (SIGMOD), pages 993–1008, May 2017. doi:10.1145/3035918.3064007 ↩︎

  90. Adrien Grand. What is in a Lucene Index? At Lucene/Solr Revolution, November 2013. Archived at perma.cc/Z7QN-GBYY ↩︎

  91. Michael McCandless. Visualizing Lucene’s Segment Merges. blog.mikemccandless.com, February 2011. Archived at perma.cc/3ZV8-72W6 ↩︎

  92. Lukas Fittl. Understanding Postgres GIN Indexes: The Good and the Bad. pganalyze.com, December 2021. Archived at perma.cc/V3MW-26H6 ↩︎

  93. Jimmy Angelakos. The State of (Full) Text Search in PostgreSQL 12. At FOSDEM, February 2020. Archived at perma.cc/J6US-3WZS ↩︎

  94. Alexander Korotkov. Index support for regular expression search. At PGConf.EU Prague, October 2012. Archived at perma.cc/5RFZ-ZKDQ ↩︎

  95. Michael McCandless. Lucene’s FuzzyQuery Is 100 Times Faster in 4.0. blog.mikemccandless.com, March 2011. Archived at perma.cc/E2WC-GHTW ↩︎

  96. Steffen Heinz, Justin Zobel, and Hugh E. Williams. Burst Tries: A Fast, Efficient Data Structure for String Keys. ACM Transactions on Information Systems, volume 20, issue 2, pages 192–223, April 2002. doi:10.1145/506309.506312 ↩︎

  97. Klaus U. Schulz and Stoyan Mihov. Fast String Correction with Levenshtein Automata. International Journal on Document Analysis and Recognition, volume 5, issue 1, pages 67–85, November 2002. doi:10.1007/s10032-002-0082-8 ↩︎

  98. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient Estimation of Word Representations in Vector Space. At International Conference on Learning Representations (ICLR), May 2013. doi:10.48550/arXiv.1301.3781 ↩︎

  99. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. At Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, volume 1, pages 4171–4186, June 2019. doi:10.18653/v1/N19-1423 ↩︎

  100. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving Language Understanding by Generative Pre-Training. openai.com, June 2018. Archived at perma.cc/5N3C-DJ4C ↩︎

  101. Matthijs Douze, Maria Lomeli, and Lucas Hosseini. Faiss indexes. github.com, August 2024. Archived at perma.cc/2EWG-FPBS ↩︎

  102. Varik Matevosyan. Understanding pgvector’s HNSW Index Storage in Postgres. lantern.dev, August 2024. Archived at perma.cc/B2YB-JB59 ↩︎

  103. Dmitry Baranchuk, Artem Babenko, and Yury Malkov. Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. At European Conference on Computer Vision (ECCV), pages 202–216, September 2018. doi:10.1007/978-3-030-01258-8_13 ↩︎

  104. Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 42, issue 4, pages 824–836, April 2020. doi:10.1109/TPAMI.2018.2889473 ↩︎

最後更新於
3. 資料模型與查詢語言5. 編碼與演化