Skip to content

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、ScyllaDB 和 HBase 8 所採用的演算法。這些系統都受 Google Bigtable 論文 9 的啟發；SSTable 和 memtable 兩個術語正是由該論文提出的。

這一演算法最初發表於 1996 年，名為 日誌結構合併樹（Log-Structured Merge-Tree，簡稱 LSM 樹）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)。其中第 2 位為 1，另外兩位為 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，很好地經受住了時間的考驗。時至今日，它仍然是幾乎所有關係資料庫中的標準索引實現，許多非關係資料庫也使用 B 樹。

與 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 中的分支因子為 6。實踐中的分支因子取決於頁引用和範圍邊界所需的空間，不過通常可達幾百。

如果要更新 B 樹中已有鍵的值，就先找到包含該鍵的葉頁，再用含有新值的版本覆蓋磁碟上的這一頁。如果要新增新鍵，則找到範圍涵蓋該鍵的頁，並把鍵加入其中。如果頁內沒有足夠的空閒空間容納新鍵，就把它拆成兩個半滿的頁，並更新父頁，以反映鍵範圍的新劃分。

圖 4-6. 在邊界鍵 337 處拆分頁，使 B 樹增長；父頁也隨之更新，以引用兩個子頁。

在 圖 4-6 中，我們想插入鍵 334，但負責 333–345 範圍的頁已經裝滿。於是把它拆成兩頁：一頁負責 333–337（幷包含新鍵），另一頁負責 337–344。父頁也必須更新，增加對兩個子頁的引用，並以 337 作為二者的邊界。如果父頁容不下新的引用，它也要拆分；這種拆分可能一路向上傳播到樹根。根頁拆分時，則在其上方建立一個新根。刪除鍵還可能需要合併節點，處理起來更加複雜 5。

這個演算法可以確保樹始終 平衡：包含 n 個鍵的 B 樹深度總是 O(log n)。大多數資料庫只需要三四層深的 B 樹，因此不必沿著很多頁引用就能找到目標頁。（一棵四層深、頁大小為 4 KiB、分支因子為 500 的樹，最多可以儲存 250 TB 資料。）

使 B 樹可靠

B 樹最基本的底層寫操作，是用新資料覆寫磁碟上的頁，並假定覆寫不會改變頁的位置：也就是說，頁被覆寫後，所有指向它的引用仍然有效。這與 LSM 樹一類日誌結構索引形成鮮明對比；後者只向檔案追加寫入（並最終刪除過時檔案），從不就地修改檔案。

一次覆寫多個頁——例如拆分頁時——是很危險的操作。如果資料庫只寫完其中一部分就崩潰，最終會留下損壞的樹（例如出現不屬於任何父頁的 孤兒頁）。如果硬體不能原子地寫入整頁，還可能留下只寫了一部分的頁，這稱為 頁撕裂（torn page）23。

為了讓資料庫能夠從崩潰中恢復，B 樹實現通常會在磁碟上維護一個額外的資料結構：預寫日誌（write-ahead log，WAL）。這是一個僅追加檔案；對 B 樹的每項修改，都必須先寫入 WAL，才能應用到樹本身的頁上。資料庫在崩潰後重新啟動時，會用這個日誌把 B 樹恢復到一致狀態 2 24。檔案系統中的對應機制稱為 日誌機制（journaling）。

為了提高效能，B 樹實現通常不會立刻把每個修改過的頁寫入磁碟，而是先把 B 樹頁在記憶體中緩衝一段時間。此時，預寫日誌還負責確保崩潰時不丟資料：只要資料已寫入 WAL，並透過 fsync() 系統呼叫刷到磁碟，它就是持久的，因為資料庫能夠在崩潰後將它恢復出來 25。

B 樹變體

由於 B 樹已經存在很久，多年來發展出了許多變體。這裡只舉幾例：

  • 一些資料庫（如 LMDB）不覆寫頁，也不靠 WAL 進行崩潰恢復，而是採用寫時複製方案 26。修改過的頁寫入新的位置，併為樹中的父頁建立新版本，使其指向新位置。這種方法對併發控制也很有用，我們將在 “快照隔離與可重複讀” 中看到。
  • 可以不儲存完整的鍵，而只儲存其縮寫，以節省頁內空間。尤其在樹的內部頁中，鍵只需包含足夠的資訊，能夠充當鍵範圍之間的邊界即可。一頁容納的鍵越多，樹的分支因子就越大，層數也越少。
  • 為了加快按排序順序掃描鍵範圍，有些 B 樹實現會盡量安排樹的佈局，使葉頁在磁碟上也按順序出現，從而減少磁碟尋道。不過隨著樹不斷增長，這種順序很難維持。
  • 還可以向樹中加入額外的指標。例如，讓每個葉頁引用左右相鄰的兄弟頁，便能按順序掃描鍵，而不必反覆跳回父頁。

比較 B 樹與 LSM 樹

根據經驗，LSM 樹更適合寫入密集型應用，而 B 樹的讀取通常更快 27 28。不過，基準測試結果往往對工作負載的細節非常敏感。只有使用自己的實際工作負載測試系統，比較才有意義。此外，LSM 樹與 B 樹並非嚴格的二選一：儲存引擎有時會融合兩種方法的特點，例如維護多棵 B 樹，再用 LSM 風格將它們合併。本節將簡要討論衡量儲存引擎效能時值得考慮的幾個方面。

讀取效能

在 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（固態硬碟）已經在許多場景中取代 HDD，其中也包括 NVMe（Non-Volatile Memory Express，即透過 PCI Express 匯流排連線的快閃記憶體）；它們沒有這種機械限制。

儘管如此，SSD 的順序寫入吞吐量仍然高於隨機寫入。快閃記憶體每次可以讀寫一頁（通常為 4 KiB），卻只能按塊擦除（通常為 512 KiB）。同一個塊中，有些頁可能仍儲存有效資料，另一些頁中的資料則已經無用。擦除整個塊之前，控制器必須先把含有有效資料的頁搬到其他塊；這個過程稱為 垃圾回收（GC）33。

順序寫入每次寫入更大塊的資料，所以一個完整的 512 KiB 塊很可能都屬於同一個檔案；日後刪除這個檔案時，可以直接擦除整個塊，不必執行 GC。隨機寫入則更容易讓一個塊混雜有效頁和無效頁，因此在擦除塊之前，GC 必須完成更多搬運工作 34 35 36。

GC 佔用的寫入頻寬無法再供應用使用；而且 GC 帶來的額外寫入會加劇快閃記憶體磨損。因此，隨機寫入比順序寫入更快地損耗 SSD。

寫放大

無論採用哪種儲存引擎，應用發出的一次寫請求都會轉化為底層磁碟上的多次 I/O。對 LSM 樹而言，一個值首先寫入日誌以確保永續性；記憶體表寫入磁碟時又寫一次；此後每次所在的鍵值對參與壓實，還要再次寫入。（如果值遠大於鍵，可以把鍵和值分開存放，只壓實包含鍵和值引用的 SSTable，以降低這項開銷 37。）

B 樹索引也必須把每份資料至少寫兩次：一次寫入預寫日誌，一次寫入樹頁本身。為了確保 B 樹能在崩潰或斷電後正確恢復，有時即使頁內只有幾個位元組發生變化，也必須寫出整頁 38 39。

把某個工作負載實際寫入磁碟的總位元組數，除以不帶索引、只寫僅追加日誌時所需的位元組數，得到的比值就是 寫放大。（寫放大有時也按 I/O 操作次數而非位元組數定義。）在寫入密集型應用中，瓶頸可能是資料庫向磁碟寫入的速度。此時寫放大越高，在有限磁碟頻寬內每秒能處理的寫入就越少。

LSM 樹和 B 樹都有寫放大問題。孰優孰劣取決於許多因素，例如鍵和值的長度，以及覆蓋現有鍵與插入新鍵各有多頻繁。對典型工作負載而言，LSM 樹往往具有更低的寫放大，因為它不必寫出整頁，還可以壓縮 SSTable 中的資料塊 40。這也是 LSM 儲存引擎適合寫入密集型工作負載的原因之一。

寫放大除了影響吞吐量，也關係到 SSD 的磨損：儲存引擎的寫放大越低，SSD 損耗得就越慢。

測量儲存引擎的寫入吞吐量時，實驗必須執行足夠長的時間，才能顯現寫放大的影響。剛開始向空 LSM 樹寫入時，壓實尚未發生，全部磁碟頻寬都可供新寫入使用。隨著資料庫增長，新寫入便不得不與壓實共享磁碟頻寬。

磁碟空間使用

B 樹可能隨著時間推移逐漸 碎片化。例如，刪除大量鍵之後，資料庫檔案裡可能留下許多 B 樹不再使用的頁。以後向 B 樹新增資料時可以複用這些空閒頁，但它們位於檔案中間，很難歸還給作業系統，所以仍會佔用檔案系統空間。因此，資料庫需要後臺程序搬移並重新整理這些頁，例如 PostgreSQL 的清理（vacuum）程序 25。

碎片化對 LSM 樹來說問題較小，因為壓實過程本來就會定期重寫資料檔案，而且 SSTable 中不存在留有空閒空間的頁。此外，SSTable 中的鍵值對塊更便於壓縮，所以生成的磁碟檔案通常小於 B 樹。已經覆蓋的鍵和值會繼續佔用空間，直到在壓實中移除；不過採用分級壓實時，這項開銷相當低 40 41。按大小分層壓實（參見 “壓實策略”）會佔用更多磁碟空間，尤其是在壓實過程中臨時佔用的空間。

如果需要刪除某些資料並確信它們確實已經消失——例如為了遵守資料保護法規——磁碟上並存的多份副本也會帶來麻煩。在大多數 LSM 儲存引擎中，已刪除的記錄仍可能留在較高層級，直到代表刪除操作的墓碑傳遍所有壓實層級；這一過程可能持續很久。有些專門的儲存引擎設計可以更快地傳播刪除操作 42。

另一方面，SSTable 段檔案的不可變性很適合為資料庫建立時間點快照（例如用於備份，或複製一份資料庫進行測試）：只需寫出記憶體表，再記下當時存在哪些段檔案。只要不刪除屬於快照的檔案，就完全不必實際複製它們。B 樹會覆寫頁，因此很難如此高效地建立快照。

多列索引與二級索引

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

二級索引 也很常見。在關係資料庫中，可以用 CREATE INDEX 命令在同一張表上建立多個二級索引，從而按主鍵以外的列進行搜尋。例如，圖 3-1（見 第 3 章）中的各張表很可能都要在 user_id 列上建立二級索引，以便找出屬於同一使用者的所有行。

二級索引很容易用鍵值索引構建。主要區別在於，二級索引中的被索引值不一定唯一，也就是說，同一個索引條目下可能對應許多行（或文件、頂點）。有兩種解決辦法：把索引中的值做成匹配行識別符號的列表（類似全文索引的倒排列表）；或者在每個索引項後附加行識別符號，使它成為唯一項。B 樹一類就地更新的儲存引擎和日誌結構儲存都可以實現二級索引。

在索引中儲存值

索引中的鍵是查詢要搜尋的內容，而值可以採用以下幾種形式：

  • 如果實際資料（行、文件或頂點）直接儲存在索引結構中，這就是 聚簇索引。例如，MySQL 的 InnoDB 儲存引擎總是把表的主鍵作為聚簇索引；SQL Server 則允許每張表指定一個聚簇索引 43。
  • 另一種選擇是讓值引用實際資料：它可以是相應行的主鍵（InnoDB 的二級索引便是如此），也可以直接引用磁碟上的位置。後一種情況下，存放行的地方稱為 堆檔案；堆檔案中的資料沒有特定順序，可以是僅追加的，也可以記錄已刪除的行，以便日後用新資料覆寫。例如，Postgres 就使用堆檔案 44。
  • 兩者之間的折中稱為 覆蓋索引 或 包含列的索引：完整的行仍儲存在堆檔案或主鍵聚簇索引中，但索引也會儲存表的 部分 列 45。這樣，一些查詢只用索引就能得到答案，不必再解析主鍵或訪問堆檔案；此時稱該索引 覆蓋 了查詢。覆蓋索引可以加快某些查詢，但重複資料會佔用更多磁碟空間，也會拖慢寫入。

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

更新值但不改變鍵時，只要新值不大於舊值，堆檔案就能就地覆寫記錄。如果新值更大，情況會複雜一些：記錄可能必須移到堆內空間足夠的新位置。此時，要麼更新所有索引，使其指向記錄在堆中的新位置；要麼在舊位置留下一個轉發指標 2。

全記憶體儲存

本章到目前為止討論的資料結構，都是對磁碟侷限的應對。與主記憶體相比，磁碟處理起來很麻煩。無論是磁性硬碟還是 SSD，要想獲得良好的讀寫效能，都必須仔細安排資料在磁碟上的佈局。不過我們能容忍這種麻煩，是因為磁碟有兩項顯著優勢：它是持久的（斷電後內容不會丟失），而且每 GB 的成本低於 RAM。

隨著 RAM 越來越便宜，磁碟的每 GB 成本優勢正在減弱。許多資料集本來就沒有那麼大，因此完全可以把它們全部放進記憶體，必要時還可以分佈到多臺機器上。於是，記憶體資料庫 發展了起來。

有些記憶體鍵值儲存（如 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。

一種選擇是按每行一位直接儲存這些點陣圖。不過，點陣圖中通常有大量的 0，也就是十分 稀疏。這時還可以使用遊程編碼：統計連續出現的 0 或 1 的數量，並存下這個數字，如 圖 4-8 底部所示。Roaring 點陣圖會在兩種位圖表示之間切換，總是選用更緊湊的一種 73。這樣可以極其高效地編碼一整列。

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

WHERE product_sk IN (31, 68, 69):
載入 product_sk = 31、product_sk = 68 和 product_sk = 69 對應的三張點陣圖，再計算三者的按位 或，這個操作可以非常高效地完成。
WHERE product_sk = 30 AND store_sk = 3:
載入 product_sk = 30 和 store_sk = 3 對應的點陣圖，再計算按位 與。之所以可行，是因為各列中的行順序相同：一列點陣圖中的第 k 位，與另一列點陣圖中的第 k 位對應同一行。

點陣圖也可以回答圖查詢，例如找出社交網路中所有“被使用者 X 關注、同時又關注使用者 Y”的使用者 74。列式資料庫還有許多其他壓縮方案，參見參考文獻 75。

Note

不要把列式資料庫與 寬列（又稱 列族）資料模型混為一談。寬列模型的一行可以有數千列，各行也不必擁有相同的列 9。儘管名字相似，寬列資料庫其實是面向行的，因為它會把同一行的所有值存放在一起。Google Bigtable、Apache Accumulo 和 HBase 都屬於寬列模型。

列儲存中的排序順序

在列式儲存中，行的儲存順序並不一定重要。最簡單的方式是按插入順序存放，因為插入新行時只需向每一列追加資料。不過，也可以像此前處理 SSTable 那樣，為資料指定某種順序，並把這種順序用作索引機制。

注意，分別對每一列獨立排序毫無意義，因為那樣就再也不知道不同列中的哪些項屬於同一行。我們之所以能夠重建一行，正是因為一列中的第 k 項與另一列中的第 k 項屬於同一行。

因此，即使資料按列儲存，排序也必須以整行為單位。資料庫管理員可以根據自己對常見查詢的瞭解，選擇表按哪些列排序。例如，如果查詢經常針對“上個月”這樣的日期範圍，就可以把 date_key 作為第一個排序鍵。這樣查詢只需掃描上個月的行，比掃描所有行快得多。

對於第一排序列中取值相同的行，可以用第二列進一步決定順序。例如，如果 圖 4-7 以 date_key 為第一排序鍵，那麼把 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 傳給同一個運算元，得到另一張點陣圖。最後把兩張點陣圖傳給“按位與”運算元，如 圖 4-9 所示。結果點陣圖中，特定門店售出的每一筆香蕉都對應一個 1。

圖 4-9. 兩張點陣圖的按位與運算非常適合向量化處理。

這兩種方法的實現大不相同，但都已投入實際使用 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℃ 的所有觀測記錄。使用一維索引，要麼必須掃描 2013 年的所有記錄（不考慮溫度）再按溫度篩選，要麼反過來處理。二維索引則可以同時按時間戳和溫度縮小結果範圍 87。

全文檢索

全文檢索允許按關鍵詞搜尋一組文字文件（網頁、產品描述等），關鍵詞可以出現在文字中的任意位置 88。資訊檢索是一門龐大而專門的學科，往往還要針對具體語言進行處理。例如，一些亞洲語言書寫時不會在詞與詞之間新增空格或標點，因此把文字切分成詞需要藉助模型，判斷哪些字元序列構成一個詞。全文檢索還經常需要匹配相似但不完全相同的詞（例如拼寫錯誤或同一個詞的不同語法形式），以及同義詞。這些問題都超出了本書的範圍。

不過從核心原理看，全文檢索也可以視為一種多維查詢：文字中可能出現的每個詞（即一個 詞項）都是一個維度。包含詞項 x 的文件在維度 x 上取值為 1，不包含 x 則取值為 0。搜尋提到“紅蘋果”的文件，就是同時尋找 紅 維度和 蘋果 維度都為 1 的文件。這樣一來，維度數可能非常龐大。

許多搜尋引擎使用 倒排索引 回答這類查詢。它是一種鍵值結構：鍵是詞項，值是所有包含該詞項的文件 ID 列表，即 倒排列表。如果文件 ID 是連續數字，倒排列表也可以表示成 圖 4-8 那樣的稀疏點陣圖：如果 ID 為 n 的文件包含詞項 x，那麼詞項 x 的點陣圖中第 n 位就是 1 89。

現在，查詢同時包含詞項 x 和 y 的所有文件，就類似於用向量化資料倉庫查詢尋找滿足兩個條件的行（圖 4-9）：載入 x 和 y 對應的兩張點陣圖，再計算按位與。即使點陣圖經過遊程編碼，這個操作也可以高效完成。

Elasticsearch 和 Solr 使用的全文索引引擎 Lucene 就採用這種方法 90。它把從詞項到倒排列表的對映儲存在類似 SSTable 的有序檔案中，再使用本章前面介紹的日誌結構方法，在後臺合併這些檔案 91。PostgreSQL 的 GIN 索引也透過倒排列表支援全文檢索，以及 JSON 文件內部的索引 92 93。

除了把文字切分成詞，還可以找出所有長度為 n 的子串，稱為 n-gram。例如，字串 "hello" 的 3-gram（n = 3）是 "hel"、"ell" 和 "llo"。如果為所有 3-gram 建立倒排索引，就能搜尋任意長度至少為三個字元的子串。這樣的索引甚至支援在搜尋查詢中使用正則表示式，缺點是體積相當大 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 索引時，首先要指定 探測數（probes），也就是需要檢查多少個分割槽。探測數越大，查詢越準確，但也越慢，因為必須比較更多向量。
分層可導航小世界（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、ScyllaDB、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. 編碼與演化