跳轉到

10.3 總結與進階閱讀#

全書回顧#

這本書繞著一個核心事實展開：磁碟比記憶體慢 4~5 個數量級，所有磁碟演算法都是圍繞這個差距的補償設計。回顧各章的「一句話精華」：

  1. 儲存基礎：成本模型是尋找 + 旋轉（HDD）或頁讀寫（SSD），一切分析從這裡開始。
  2. 資料組織：分頁是 I/O 的原子單位，緩衝池用局部性把 I/O 攤薄。
  3. 磁碟排序：外部合併排序 2N(1+log_{B-1}(N/B)) 次頁 I/O，順序存取是靈魂。
  4. 磁碟雜湊：可擴展與線性雜湊讓「一次 I/O 查到」與「平滑擴張」共存。
  5. B樹家族：分支因子換樹高，B+tree 把隨機 I/O 壓到 3~4 次。
  6. 進階索引：ISAM 讀極速、LSM 寫極速、Bloom Filter 砍掉無謂讀取。
  7. 檔案系統：FAT 鏈結、inode 索引、日誌換一致。
  8. 資料庫引擎：所有積木組裝，WAL 用一次順序寫換取永不忘記。
  9. 分散式儲存：一致性雜湊管放置、副本與糾刪碼管冗餘、Merkle 樹管同步。
  10. 新興儲存：硬體世代交替時，重新推導成本模型。

三條貫穿全書的設計原則：

  • 攤提固定成本：一次搬大塊（分頁、批次、group commit）。
  • 把隨機變順序：合併排序的 run、LSM 的 SSTable、WAL 的追加寫。
  • 用冗餘與索引換時間：Bloom Filter 的位元、副本的空間、日誌的雙寫。

進階閱讀#

  • 經典教科書：Ramakrishna & Gehrke《Database Management Systems》第 8~11 章（本書 2~5 章的學術版）；Silberschatz《Database System Concepts》儲存與索引章節。
  • 原始論文：Bayer & McCreight 1972（B-tree）；Litwin 1980（linear hashing）；O'Neil et al. 1996（The Log-Structured Merge Tree）；Graefe 2011（Modern B-Tree Techniques，綜述聖經）。
  • 系統原始碼：SQLite（單檔 B+tree 資料庫的教科書級實作，約 15 萬行）；LevelDB/RocksDB（LSM 的工業實作）；CMU 15-445 課程的 BusTub（教學用儲存引擎）。
  • 分散式：Kleppmann《Designing Data-Intensive Applications》第 3 章（儲存與檢索）是本書第 6、9 章的最佳延伸；Dynamo 論文（2007）展示一致性雜湊與 quorum 的實戰。
  • 新硬體：Intel PMDK 文件與 FPTree 論文（PMem 上的 B+tree）；NVMe 規範與 io_uring 教學。

給讀者的最後建議#

儲存演算法的學習沒有捷徑，只有「讀源碼 + 量測 + 重造輪子」三件事。建議的實作路線：先寫一個分頁檔案管理器，再接緩衝池，然後在其上實作 B+tree——完成這三步，你就擁有了 SQLite 的雛形，書中所有公式都會從符號變成你親手量測過的數字。

全書練習總複習#

  1. 從零推導：N=10⁶ 頁、B=101 的外部排序總 I/O；再算同資料建 B+tree 後隨機查詢的 I/O，比較「先排序再查」與「直接查」的取捨。
  2. 設計題：為「寫入 10 萬筆/秒、查詢 1 萬筆/秒、資料 1TB」的時序資料庫選擇儲存結構，寫出完整理由鏈（結構 → 成本公式 → 硬體）。
  3. 綜合題：說明一筆 INSERT 從 SQL 到磁碟的完整路徑，標出每步涉及的章節與 I/O 次數。