資料庫演算法 primer：由簡入深從 Hash Table 到 HNSW

日期：2026-04-22 情境： 接續 ES、Neo4j、Polyglot Persistence 三篇深入文，本篇是「演算法基礎篇」 — 把那些深入文裡掛名的所有演算法（inverted index / skip list / FST / BM25 / BFS / bidirectional BFS / subgraph isomorphism / HNSW / Volcano iterator / CBO …）由簡入深走一遍。

TL;DR

資料庫的速度全部建立在「用對的資料結構 + 對的演算法」上。本文按四層 progression 走：

基礎資料結構（hash table / sorted array / B-tree）— 為什麼 O(1) 跟 O(log n) 是 query 的兩大主戰場
全文檢索演算法（inverted index / skip list / FST / BM25）— 為什麼 ES 對「跨百萬文件找詞」比 SQL LIKE 快幾個量級
圖演算法（adjacency / BFS / bidirectional BFS / subgraph isomorphism）— 為什麼 Neo4j 對「多跳關係」比 RDBMS join 快
向量檢索演算法（brute KNN / KD-tree / LSH / HNSW）— 為什麼語意搜尋從不可行變成毫秒回應
查詢執行（Volcano iterator / CBO）— 為什麼同一條 SQL 寫法不同性能差 100×

每節先給直覺 + 圖示，再給複雜度分析 + 何時該用 / 不該用。

一、基礎資料結構：O(1) 與 O(log n) 兩大世界

1.1 Hash Table — O(1) 平均查詢

最熟悉但常被低估的資料結構。

key "alice"
   ↓ hash() 
   ↓ → 12345
   ↓ % bucket_count(64)
   ↓ → bucket 25
   ↓
[bucket 0] [bucket 1] ... [bucket 25 → ("alice", value)] ... [bucket 63]

操作複雜度：

Insert / Lookup / Delete：平均 O(1)，最差 O(n)（hash collision 全擠一個 bucket）
不支援範圍查詢（hash 隨機打散，相鄰 key 在不同 bucket）
不支援排序輸出

用在哪：

主鍵 lookup（SELECT * WHERE id = 5）
in-memory cache（Redis 內部就是 hash table）
HashJoin 的 build phase

為什麼不能全用 hash： 範圍查詢和排序輸出是 OLTP 必需，hash 完全不支援。

1.2 Sorted Array + Binary Search — O(log n)

sorted: [3, 7, 12, 18, 25, 33, 41, 50, 67, 89]

找 25：
  step 1: mid=index 4 (25) ✓ 中
  
找 30：
  step 1: mid=index 4 (25), 30 > 25 → 看右半
  step 2: mid=index 7 (50), 30 < 50 → 看左半 [33, 41]
  step 3: mid=index 5 (33), 30 < 33 → 看左半 [33] (空) → not found

每步把搜尋範圍砍半，n 個元素只要 log₂(n) 步。

問題： insert / delete 是 O(n)（要搬後面所有元素）。所以只適合「大量讀、少量寫」場景。

1.3 B-tree — O(log n) 而且能高效插入

B-tree 是 sorted array 的「分塊版本」：

graph TD
    Root["[10 | 20 | 30]"]
    L1["[3, 7]"]
    L2["[11, 15, 18]"]
    L3["[22, 25, 28]"]
    L4["[33, 41, 50]"]

    Root -->|< 10| L1
    Root -->|10-20| L2
    Root -->|20-30| L3
    Root -->|> 30| L4

    style Root fill:#fef3c7,stroke:#92400e,stroke-width:2px
    style L1 fill:#dbeafe
    style L2 fill:#dbeafe
    style L3 fill:#dbeafe
    style L4 fill:#dbeafe

每個節點存多個 key（不像 binary tree 只存一個），fanout 高（一個節點通常 100-200 個 key）。

為什麼 RDBMS index 全用 B-tree（不是 binary tree）：

fanout 高 → 樹高極低：100 萬 key 樹高才 3-4 層
每節點對齊 disk page：一個 page (4-8KB) 一個節點，I/O 次數 = 樹高
Insert/Delete 局部化：改動只影響一條路徑（O(log n)）

B+ tree 是 B-tree 的常見變體（PostgreSQL / MySQL 都用）：所有資料只放 leaf，內部節點只放 key 當索引 — 範圍掃描更快（leaf 之間有指標串起來，順序走過去就好）。

複雜度總結：

操作	Hash Table	Sorted Array	B-tree	B+ tree
Lookup	O(1)	O(log n)	O(log n)	O(log n)
Insert	O(1) amortized	O(n)	O(log n)	O(log n)
Range scan	❌	O(log n + k)	O(log n + k)	O(log n + k) 最快
Sort output	❌	✓	✓	✓

二、全文檢索：從 LIKE ‘%xxx%’ 走到 BM25

2.1 為什麼 SQL `LIKE` 慢

SELECT * FROM messages WHERE body LIKE '%詐騙%';

每筆 row 都要把 body 整串掃過、找子字串。100 萬筆 × 平均 500 字 = 5 億次字元比對。O(n × m)。

加 trigram index（PG 的 pg_trgm）能改善但天花板低 — 中文 trigram 的 selectivity 差。

2.2 Inverted Index — 反過來查

原始文件：
  doc 1: "張三今天去詐騙"
  doc 2: "李四在詐騙集團"

倒排索引：
  "張三"   → posting list: [1]
  "李四"   → posting list: [2]
  "今天"   → posting list: [1]
  "詐騙"   → posting list: [1, 2]
  "集團"   → posting list: [2]

查「詐騙」O(1) 找到 posting list [1, 2]，O(k) 走完 — 完全不掃原文。

2.3 Skip List — Posting List 的快速 AND/OR

兩個 posting list 做 AND：

list A: [1, 5, 9, 12, 18, 25, 33, 41, 50, ...]   (1000 個)
list B: [3, 18, 50, 100, ...]                     (10 個)

從 list B 出發（短的），對每個 b 找 list A 是否有 = b 的元素。Naive 線性 scan 是 O(

) per b。

Skip list 在 list A 上加多層 skip pointer：

level 2: [1, ──────────, 50, ──────, ... ]
level 1: [1, ──, 18, ──, 50, ──, ... ]
level 0: [1, 5, 9, 12, 18, 25, 33, 41, 50, ...]

要找 18：從 level 2 跳到 50 太遠 → 退回 level 1，從 1 跳到 18 → ✓。O(log n) per lookup。

兩個 posting list AND 的整體複雜度：O((

) × log(

))。實戰中常見 100K + 100 的兩 list AND 在毫秒內完成。

Skip list 是隨機資料結構：每個元素隨機決定要不要在 level 1 / level 2 出現（機率 1/2、1/4 …），平均高度 O(log n)。優點是不用像 B-tree 那樣 rebalance。

2.4 FST (Finite State Transducer) — Posting List 的壓縮

100 萬個 unique terms 的 inverted index，光 term 列表就佔大量空間。Lucene 用 FST 把 term → posting list ID 的對應壓縮成有限狀態機。

terms: ["alice", "alpha", "amy", "andrew", "ann"]

FST 共享 prefix:
  start → 'a' → ╭→ 'l' → 'i' → 'c' → 'e' → posting_id=0
              ├→ 'l' → 'p' → 'h' → 'a' → posting_id=1
              ├→ 'm' → 'y' → posting_id=2
              ├→ 'n' → 'd' → 'r' → 'e' → 'w' → posting_id=3
              ╰→ 'n' → 'n' → posting_id=4

共享 prefix 大幅壓縮儲存 — Lucene 的 term dictionary 通常 5-10× 壓縮率。同時 FST 支援 prefix scan（all terms starting with “al”）— startsWith query 走 FST 就行。

2.5 BM25 評分公式（重貼一次）

score(q, d) = Σ IDF(qi) · (f(qi, d) · (k1 + 1))
                          / (f(qi, d) + k1 · (1 - b + b · |d|/avgdl))

直覺：

「李四」（罕見）出現 1 次 > 「的」（常見）出現 1 次（IDF 部分）
短訊息中「李四」出現 1 次 > 萬字長文中「李四」出現 1 次（length normalization）
一個 term 第 50 次出現的貢獻幾乎 = 第 5 次（k1 飽和）

完整推導見 s3 ES 那篇。

2.6 全文檢索演算法總結

演算法	解的問題	複雜度
`LIKE '%xxx%'` 掃表	子字串搜尋	O(n × m)
Trigram index	短字串搜尋	O(n) 但高 constant
Inverted index + Skip list	詞層級 boolean query	O((m + log n) × k)
FST	term dictionary 壓縮 + prefix scan	O(L) per term
BM25	相關性排序	O(matched docs × avg query terms)

三、圖演算法：BFS、雙向 BFS、Subgraph Isomorphism

3.1 表示法：Adjacency List vs Matrix

Adjacency Matrix（密圖友善）：

     A B C D
A  [ 0 1 0 1 ]
B  [ 1 0 1 0 ]
C  [ 0 1 0 1 ]
D  [ 1 0 1 0 ]

查 A↔B 是否有邊 O(1)，但稀疏圖浪費 O(V²) 空間。

Adjacency List（稀疏圖友善，95% 真實圖都是稀疏的）：

A → [B, D]
B → [A, C]
C → [B, D]
D → [A, C]

空間 O(V + E)，遍歷 A 的鄰居 O(degree(A))。

3.2 Index-Free Adjacency（Neo4j 的核心）

Neo4j 把 adjacency list 物理化進 record：每個 node record 直接記第一個 relationship 的 disk offset，每個 relationship record 直接記下一個 relationship 的 offset。

走鄰居 = 指標跳躍（O(1) per hop），完全不需要任何 index。

3.3 BFS（Breadth-First Search）— 找最短路徑的基礎

從 A 開始 BFS：
  level 0: {A}
  level 1: {B, D}        ← A 的所有鄰居
  level 2: {C}           ← B, D 的鄰居 - 已訪問

複雜度 O(V + E)。要找 A 到 G 最短路徑就是 BFS 走到 G 那層為止。

問題：6 度分隔內找全部 → 平均 degree=100 的圖要走 100^6 = 10^12 個節點。爆炸。

3.4 Bidirectional BFS — 把指數對折

graph LR
    subgraph forward ["前向 BFS (從 A)"]
        A["A
level 0"]
        AB["A 的鄰居
level 1"]
        AC["...
level k/2"]
        A --> AB --> AC
    end
    subgraph backward ["後向 BFS (從 G)"]
        G["G
level 0"]
        GB["G 的鄰居
level 1"]
        GC["...
level k/2"]
        G --> GB --> GC
    end
    AC -.->|frontier 相交| GC

    style A fill:#fef3c7,stroke:#92400e,stroke-width:2px
    style G fill:#dcfce7,stroke:#166534,stroke-width:2px

關鍵：兩邊各走 k/2 層，總工作量 2 × d^(k/2) « d^k。

對 k=6, d=100：

單向：100^6 = 10^12 個節點
雙向：2 × 100^3 = 2 × 10^6 個節點

百萬倍 的差異。Neo4j 的 shortestPath() 內部就用 bidirectional BFS。

實作細節：交替擴展兩邊，每次選 frontier 較小的那邊先擴 — 確保 worst-case balanced。

3.5 Subgraph Isomorphism — 找特定 pattern

「圖中是否存在符合特定 pattern 的子結構」 — e.g. 找所有「三人互相認識」的 triangle。

通用演算法：VF2 (Cordella et al. 2004)、Ullmann’s algorithm — 都是 backtracking + 條件剪枝。一般情況 NP-hard。

Neo4j 不跑通用演算法：

起點 pinning：總有某個變數能用 indexed property 鎖定（label scan + filter）
Pattern 編譯成 Tree：選一條閉合邊（closing edge）打破環
Tree pattern 用 Expand 鏈式執行（多項式時間）
閉合邊用 Expand(Into) 驗證 — 確認兩個已知節點之間有特定關係

對「三角形」pattern：

MATCH (a)-[:KNOWS]->(b)-[:KNOWS]->(c)-[:KNOWS]->(a)

起點 a 限定 → Expand 到 b → Expand 到 c → 驗證 c-[:KNOWS]->a 存在

實際 NP-hardness 主要影響「unlabeled、無 indexed 起點、深度大」的查詢。OLTP 場景幾乎都有起點，多項式時間就夠。

3.6 圖演算法總結

演算法	解的問題	複雜度
Adjacency list	圖儲存	空間 O(V+E)
Index-free adjacency	圖 traversal	O(1) per hop
BFS	最短路徑 / k-hop	O(V+E)
Bidirectional BFS	已知終點的最短路徑	O(d^(k/2)) vs O(d^k)
Subgraph isomorphism (general)	找 pattern	NP-hard
Pattern matching with pinning	找有起點的 pattern	多項式時間
PageRank / Louvain	中心性 / 社群偵測	O(V+E) per iteration

四、向量檢索：從 brute KNN 走到 HNSW

4.1 Brute Force KNN — O(n × d)

query vector q (1024-dim)
資料庫 100 萬個 vector

for each v in 1M vectors:
  similarity = cosine(q, v)
top_k = sort by similarity, return top 10

每筆比對是 1024 次浮點乘加 + 1 次平方根。100 萬筆 ≈ 10^9 次運算 ≈ 1-10 秒。太慢，不可接受。

4.2 KD-tree — 低維度有效，高維度詛咒

KD-tree 是 binary tree 的高維變體：

每層按一個維度切（layer 0 用 dim 0，layer 1 用 dim 1 …）
Lookup 時根據 query 在當前 dim 的值決定走左 / 右

低維 (d ≤ 20) 效果好。高維 (d > 20) 因為「curse of dimensionality」失效 — 大部分情況要看遍所有 leaf。

對 1024 維的 embedding 完全不適用。

4.3 LSH (Locality Sensitive Hashing) — 機率近似

LSH 設計一系列 hash function 滿足「相似的 vector 容易撞到同一個 bucket」（與一般 hash 反過來）。

LSH bucket:
  bucket "abc" → [v1, v3, v7, v12]    ← 這些彼此相似機率高
  bucket "xyz" → [v2, v8, v15]

Query 時計算 q 的 LSH hash，只比對同 bucket 內的 vector — O(bucket size) 而非 O(n)。

問題：召回率 (recall) 取決於 hash function 設計，調參困難。對高品質結果不夠。

4.4 HNSW (Hierarchical Navigable Small World)

當前向量檢索的事實標準（FAISS、Milvus、ES、Weaviate 都用）。核心是「多層導航圖」：

graph TB
    subgraph L2 ["Layer 2 (稀疏 - 樞紐節點)"]
        A2((A)) --- E2((E))
    end
    subgraph L1 ["Layer 1 (中等)"]
        A1((A)) --- C1((C)) --- E1((E)) --- G1((G))
    end
    subgraph L0 ["Layer 0 (全量節點)"]
        A0((A)) --- B0((B)) --- C0((C)) --- D0((D)) --- E0((E)) --- F0((F)) --- G0((G)) --- H0((H))
    end

    A2 -.->|跳到下層| A1
    E2 -.->|跳到下層| E1
    A1 -.->|跳到下層| A0
    C1 -.->|跳到下層| C0
    E1 -.->|跳到下層| E0
    G1 -.->|跳到下層| G0

    style A2 fill:#fef3c7,stroke:#92400e,stroke-width:2px
    style E2 fill:#fef3c7,stroke:#92400e,stroke-width:2px

每個節點記住自己的 neighbors（不是全部）
上層節點少、連線稀疏跨度大
下層節點多、連線密集
高度分布按指數衰減（大部分節點只在 layer 0）

搜尋演算法 (greedy)：

1. 從最頂層的某個入口節點 ep 開始
2. 在當前層做 greedy search:
   - 看 ep 的所有 neighbor，找 cosine 最近 q 的那個 nearest
   - 如果 nearest 比 ep 還近 → 移動到 nearest，重複
   - 否則停下
3. 跳到下一層繼續 (起點 = 上一層找到的位置)
4. 到 layer 0 收集 ef (e.g. 100) 個候選
5. Rerank 候選回 top-k

複雜度近 O(log N)。100 萬個 1024-dim 向量大約 100 步內找到 top-10。

為什麼 small-world？ HNSW 的圖建構過程模擬「small-world graph」 — 大部分連線是局部的（短距離 neighbor），少量是長距離（樞紐連線）。這跟現實社交網路（六度分隔）拓撲類似 — 任何兩點都可以快速連到。

參數調整：

M：每個節點 neighbor 數（預設 16）— 大 = 召回好 / 記憶體多
efConstruction：建 index 時的搜尋深度（預設 200）— 大 = 索引品質好 / 建索引慢
ef：query 時的搜尋深度（預設 = k）— 大 = 召回好 / query 慢

實戰：建一次的索引品質決定永久召回上限，所以 efConstruction 寧可大也不要小。Query 時 ef 動態調。

4.5 向量檢索演算法總結

演算法	複雜度	適用
Brute force KNN	O(n × d)	小資料量 < 10K
KD-tree	低維 O(log n)，高維退化	維度 < 20
LSH	O(bucket size)	召回要求不高、超大規模
HNSW	O(log n) approximate	中大規模 + 高品質要求
IVF (Inverted File)	O(sqrt(n))	超大規模 + 願意調參

五、查詢執行：Volcano Iterator + Cost-Based Optimizer

前面的演算法是「實作層」的。對 query 而言，還有「怎麼拼出正確順序」的演算法。

5.1 Volcano Iterator Model — 所有現代 RDBMS 的 query engine 基礎

由 Goetz Graefe 1993 提出。核心：每個 operator 是 iterator，pull-based — 上層向下層 pull next row。

SELECT name FROM users WHERE age > 30 ORDER BY name

graph TD
    PR["ProduceResult [name]"]
    SO["Sort [by name]"]
    FI["Filter [age > 30]"]
    TS["TableScan [users]"]

    PR -->|next()| SO
    SO -->|next()| FI
    FI -->|next()| TS

    style TS fill:#fef3c7,stroke:#92400e,stroke-width:2px

執行時：ProduceResult.next() 呼叫 Sort.next()，Sort 必須先讀完所有 input 才能 sort，於是 Sort 一直 pull Filter.next()，Filter 一直 pull TableScan.next() 直到結束。

好處：每個 operator 獨立、容易組合、容易加新 operator。壞處：每筆 row 一次 virtual function call → CPU 效率不夠（後來有 vectorized execution / code generation 改善，但 Volcano 仍是教學起點）。

PostgreSQL、MySQL、Neo4j、Spark 都用 Volcano-style executor。

5.2 Cost-Based Optimizer (CBO) — 選對 plan 是 100× 差異

同一條 query 可以有多種 plan。e.g.：

SELECT * FROM users u JOIN orders o ON u.id = o.user_id WHERE u.country = 'TW';

可能 plan：

Plan A：scan users WHERE country=’TW’ → for each user, lookup orders by user_id (Nested Loop Join)
Plan B：scan orders → join users by id → filter country=’TW’ (Hash Join)
Plan C：sort users by id, sort orders by user_id, merge (Merge Join)

CBO 用 statistics 估每個 plan 的成本：

estimated_rows(users WHERE country='TW') 
  = total_users × selectivity('country=TW')
  = 1M × 0.05
  = 50,000

estimated_cost(Nested Loop) = 50K × log(orders.size) × index_lookup_cost
estimated_cost(Hash Join) = orders.size + users.size × hash_cost

選最低 cost 的。

CBO 的關鍵：statistics 要準。PostgreSQL 用 ANALYZE 重算統計、Neo4j 用 db.stats.retrieve('GRAPH COUNTS')。統計過期 → optimizer 走錯路 → query 慢 100 倍。

動態規劃 (DP) 找最佳 join order：

N 個 table 的 join 有 N! 種順序
DP 把問題拆成「subset 的最佳 plan」 + 「再 join 一個 table」
複雜度從 O(N!) 降到 O(N × 2^N) 仍然爆炸 — N > 12 時 PG 改用 GEQO (genetic algorithm)

六、學到的事 / 演算法選擇心智圖

讀完該回到「什麼問題用什麼工具」：

問題類型	演算法	實作工具
主鍵 lookup	Hash table	Redis / PG hash index
範圍掃描	B+ tree	PG / MySQL primary index
子字串搜尋	Trigram index	PG `pg_trgm`
詞層級全文檢索	Inverted index + BM25	Elasticsearch / Lucene / OpenSearch
多跳關係	Index-free adjacency + BFS	Neo4j / TigerGraph
兩點最短路徑	Bidirectional BFS	Neo4j `shortestPath`
Pattern 偵測	Subgraph isomorphism (with pinning)	Neo4j Cypher MATCH
語意相似搜尋	HNSW	Elasticsearch / FAISS / Milvus / pgvector + HNSW
數值聚合	Column store + SIMD	ClickHouse / DuckDB

七、深入閱讀建議路徑

入門（讀完本篇後）

Designing Data-Intensive Applications (Kleppmann) — Ch.3 Storage and Retrieval / Ch.2 Data Models 是這份 primer 的擴充版
Database Internals (Petrov) — 細節更深，每個演算法都有圖示

全文檢索深入

Information Retrieval Book (Manning et al.) — 免費線上書，Inverted index / BM25 / IR 基礎
Lucene in Action — 老但仍是 Lucene 唯一好書

圖資料庫深入

Graph Algorithms book (Hodler & Needham, Neo4j) — APOC / GDS 演算法實戰
Network Science (Barabási) — small-world / scale-free 拓撲學

向量檢索深入

HNSW 原始論文 — 演算法本尊
Pinecone learning center — ANN / IVF / HNSW / SCANN 實戰對比
FAISS wiki — Meta 出品 vector library，文件很完整

Query Optimizer 深入

Volcano paper (Graefe 1993)
How Query Engines Work (Andy Pavlo CMU 15-721) — CMU 高階課程錄影 + slides，免費

八、回到本系列其他 3 篇

讀完 primer 再回去看那 3 篇 deep-dive，每個演算法的「為什麼」應該都通了。