0.4 · 資料結構地基

Part 0 前置知識

預估 25 分鐘

難度：入門

B-Tree

Hash

Big-O

TL;DR · 本章重點

Big-O 給上界、不給常數：O(log n) 通常比 O(n) 好，但 n 小時常數可以反轉勝負 —— 為什麼小資料量用陣列線性搜尋反而比 hash table 快。
Hash table：平均 O(1) 存取，靠雜湊函式把 key 映射到桶。記憶體 KV 的基礎 —— Redis / Memcached、磁碟上的 Bitcask。
B-Tree：n 路平衡樹、每節點是磁碟頁大小。寫入要原地更新（需 WAL 保 crash recovery）、讀快。傳統關聯式 DB 的索引結構。
外部排序（external sort）：資料大於 RAM 時、分段排序 + 合併。MapReduce 的 shuffle、SSTable 的合併、Spark sort-merge join 全用這個。
Ch3 在比較 B-Tree vs LSM-Tree 兩家儲存引擎 —— 沒有這章的基礎會卡。

1) Big-O 的直覺

描述「輸入 n 變大時，時間/空間如何成長」的上界。

Big-O	名稱	n=10	n=1000	n=10⁶	典型例子
O(1)	常數	1	1	1	Hash table 查
O(log n)	對數	3	10	20	B-Tree 查
O(n)	線性	10	1000	10⁶	陣列線性搜尋
O(n log n)	線性對數	30	10⁴	2×10⁷	排序
O(n²)	平方	100	10⁶	10¹²	巢狀循環

Big-O 不是常數

O(1) 的 hash table 查可能比 O(log n) 的 B-Tree 查慢——如果常數因子大、或 cache miss 多。實務上要看 benchmark，不能只看漸進複雜度。

2) Hash Table：O(1) 的代價

核心想法

key  ── hash function ──▶ bucket index
"alice"             ──▶  bucket 7
"bob"               ──▶  bucket 3
"carol"             ──▶  bucket 7   ← 衝突！

衝突處理：chaining（同 bucket 接 linked list）或 open addressing（往下一個空 bucket 找）。

為什麼磁碟上不常用純 hash index

Hash 結構沒有順序——範圍查詢 WHERE age BETWEEN 20 AND 30 必須掃整張表
衝突太多時退化成 O(n)
不適合 cache（隨機 bucket 跳）

但記憶體內完美：Redis、Memcached 核心、Bitcask 磁碟 KV 都用 hash。

3) B-Tree：n 路平衡樹

                  [10 | 20]
                 /    |    \
             [3,7] [12,15] [25,30]

為什麼是 n 路而不是 2 路

磁碟讀取是「以 page 為單位」（典型 4KB / 16KB）。一次讀進來上百個 key——所以節點分支因子 = 一頁能塞的 key 數，通常 100–1000 路。

樹高 = log₁₀₀(n)：10 億筆資料樹高 ~5。讀一筆 = 5 次磁碟 I/O。

原地更新的代價

UPDATE 直接改頁、寫回磁碟——但寫到一半斷電會留下半壞的頁。所以需要 WAL：先寫 log，crash 後 replay。

Ch3 的主軸

B-Tree（原地更新、隨機寫）vs LSM-Tree（追加寫、批次合併）——這是 DDIA Ch3 整章的對比。寫密集場景 LSM 勝、讀密集場景 B-Tree 勝。

4) 外部排序：資料 > RAM 時的排序

場景：10TB 資料要排序，RAM 64GB

Step 1: 把資料切成 64GB 片段
Step 2: 每片段在 RAM 內快速排序，寫回磁碟成「已排序檔」
Step 3: 多路合併—— 每個檔讀一個元素到 RAM、選最小、寫出、讀下一個

最終得到一個全域排序的大檔。

這是 MapReduce shuffle、LSM-Tree compaction、Spark sort-merge join 的共同骨架。理解外部排序 = 理解大規模資料處理的核心機制。

5) 與 DDIA 章節的對應

DDIA 章節	用到的資料結構
Ch3 儲存引擎	Hash table、B-Tree、LSM-Tree、Bloom filter、SSTable
Ch6 分區	Consistent hashing
Ch10 批次處理	外部排序（MapReduce shuffle）、sort-merge join
Ch11 串流	Log-structured storage、hash join in streaming

想更深入？

資源	內容
CLRS 第 6, 11, 18 章	演算法經典—— 排序、hash、B-Tree
VisuAlgo B-Tree	互動式 B-Tree 視覺化
Database Internals by Alex Petrov	DB 內部資料結構深入
The Log-Structured Merge-Tree (O'Neil 1996)	LSM 原始論文

章末自評

The Next Chapter

0.5 作業系統地基

本章 §3 提到 B-Tree 原地更新需要 WAL —— 但 WAL 為什麼又快又安全？答案在下一章：OS 的 page cache 讓「先寫一筆順序的 log」遠快於「原地改隨機頁面」、fsync 又保證 commit 不會在斷電時消失。Ch3 / Ch7 / Ch8 都假設你看得懂這條鏈。

Continue Reading→

0.4 · 資料結構地基 ​

1) Big-O 的直覺 ​

2) Hash Table：O(1) 的代價 ​

核心想法 ​

為什麼磁碟上不常用純 hash index ​

3) B-Tree：n 路平衡樹 ​

為什麼是 n 路而不是 2 路 ​

原地更新的代價 ​

4) 外部排序：資料 > RAM 時的排序 ​

5) 與 DDIA 章節的對應 ​

想更深入？ ​

章末自評 ​