Databases & Storage

What You Should Understand

• 能分類八種主流資料庫（relational、key-value、document、wide-column、graph、time-series、vector、NewSQL）並說出各自的代表產品與適用場景
• 能描述一條 SQL query 從 parser 到 storage engine 的完整執行流程，並解釋 EXPLAIN 的用途
• 理解 B+ tree index 的內部結構、composite index 的 leftmost prefix rule、以及 index 的寫入成本
• 能比較 LSM tree 與 B+ tree 的讀寫 tradeoff，並解釋 bloom filter、WAL、skiplist 的角色
• 知道 replication 與 sharding 的基本策略，以及 replication lag、hot partition 等經典陷阱
• 能依 workload（OLTP、OLAP、cache、vector search）做出有理由的資料庫選型

Database Landscape

Databases are classified by their data model — the shape of the data they are optimized to store and query. 沒有「最好的資料庫」，只有「最適合這個 workload 的資料庫」。面試時能先分類、再選型，就贏過一半的候選人。

直覺：relational 是預設值 — 資料量不大、關聯複雜、需要 transaction 時它幾乎總是對的。其他類型都是為了突破 relational 在某個維度的極限而生：key-value 追求延遲、wide-column 追求寫入吞吐、vector 追求相似度搜尋。

How a SQL Query Executes

Understanding the query lifecycle explains why some queries are fast and others are slow — and why EXPLAIN is your first debugging tool.

A query passes through these stages:

直覺：optimizer 像一個導航 app — 同一個目的地（query result）有很多條路（execution plans），它根據路況統計（table statistics）估每條路的成本，選最便宜的。統計過期（stale statistics）時它會選錯路，這就是為什麼 ANALYZE 很重要。

Why EXPLAIN Matters

EXPLAIN shows the plan the optimizer chose without running the query; EXPLAIN ANALYZE runs it and reports actual timings.

EXPLAIN ANALYZE
SELECT user_id, SUM(amount)
FROM transactions
WHERE created_at >= '2026-01-01'
GROUP BY user_id;
-- Look for: Seq Scan (full table scan) vs Index Scan,
-- estimated rows vs actual rows (bad estimates = stale statistics),
-- Sort spilling to disk, nested loop joins on large tables

你該養成的習慣：慢查詢先看 plan，確認三件事 — 是不是走了 full table scan、join order 是否合理、estimated rows 和 actual rows 是否差了幾個數量級。面試官問「query 很慢你怎麼辦」，答案永遠從 EXPLAIN 開始，而不是直接說「加 index」。

Indexes Deep Dive

An index is a separate data structure that trades write cost and storage for read speed. The dominant structure is the B+ tree.

Why B+ Tree (Not Binary Tree, Not Hash)

A B+ tree is a balanced tree where each node holds hundreds of keys (one node = one disk page, typically 8-16 KB):

• High fanout, low height: with fanout around 500, a 3-level tree indexes hundreds of millions of rows — any lookup costs about 3 page reads, $O(\log n)$ with a huge base
• All values live in leaf nodes, and leaves are linked in a sorted doubly-linked list — a range query walks the linked list sequentially
• Always balanced: inserts split nodes, deletes merge them, so worst case never degrades

比較三個候選結構：

直覺：disk read 的最小單位是一個 page（讀 1 byte 和讀 16 KB 成本一樣），所以好的 on-disk 結構要「每讀一個 page 就做最多的篩選」。B+ tree 每層砍掉 99.8% 的搜尋空間，binary tree 每層只砍 50%。

Clustered vs Non-Clustered Index

MySQL InnoDB 的 table 本身就是按 primary key 排序的 B+ tree（clustered）；secondary index 的 leaf 存的是 primary key，所以 secondary index 查完還要「回表」（back to the clustered index）再查一次。PostgreSQL 則所有 index 都是 secondary，指向 heap 中的 row。

Composite Index and the Leftmost Prefix Rule

An index on (city, age) sorts rows by city first, then by age within each city. It can serve:

• WHERE city = 'Taipei' — 用得到（leftmost column）
• WHERE city = 'Taipei' AND age = 30 — 用得到（完整前綴）
• WHERE city = 'Taipei' AND age $>$ 25 — 用得到（等值 + 範圍）
• WHERE age = 30 — 用不到 — age 只有在同一個 city 內才有序，全域來看是亂的

直覺：像電話簿按（姓, 名）排序 — 找「姓陳的」很快，找「名叫小明的」只能整本翻。所以 composite index 的欄位順序要把等值查詢的欄位放前面、範圍查詢的欄位放後面。

Covering Index

If the index contains every column the query needs, the engine answers from the index alone and never touches the table — an index-only scan. 例如 index (user_id, created_at, amount) 可以直接回答 SELECT amount WHERE user_id = 1 AND created_at 在某區間，少掉整個回表成本，常見能快一個數量級。

Index Types

The Cost of Indexes

Every index must be updated on every INSERT, UPDATE (of indexed columns), and DELETE:

• 寫入放大：一張表有 5 個 index，一次 insert 實際上是 6 次結構更新
• 佔用空間與 buffer pool：index 太多會把有用的資料頁擠出記憶體
• Optimizer 混淆：太多相似 index 可能讓 optimizer 選錯

Data Structures Behind Databases

Two storage engine families dominate: B+ tree engines (read-optimized, in-place updates) and LSM tree engines (write-optimized, append-only).

LSM Tree: Log-Structured Merge Tree

Writes never modify data in place. The path of a write:

1. WAL (Write-Ahead Log): append the change to a sequential log for durability — 先寫 log 再改資料，crash 後可以 replay
2. Memtable: insert into an in-memory sorted structure (usually a skiplist) — 寫入只是記憶體操作，極快
3. Flush to SSTable: when the memtable fills, write it to disk as an immutable Sorted String Table — 一次 sequential write
4. Compaction: background process merges SSTables, discarding overwritten and deleted entries

Reads must check the memtable, then SSTables from newest to oldest — this is read amplification. Mitigation: a bloom filter per SSTable lets the engine skip files that definitely do not contain the key.

Bloom Filter

A bloom filter is a probabilistic set membership structure: a bit array of size $m$ with $k$ hash functions. It answers either "definitely not present" or "possibly present" — false positives possible, false negatives impossible. False positive rate:

where $n$ is the number of inserted items. 直覺：用 1% 的空間換掉 99% 不必要的 disk read — Cassandra 讀一個不存在的 key 時，bloom filter 讓它幾乎不用碰 disk。

Structure-to-Database Map

LSM vs B+ Tree Tradeoff

直覺：B+ tree 像隨時保持排好序的書架 — 找書快，但每次插一本新書都要挪位置。LSM 像先把新書丟進門口的箱子（memtable），滿了再整箱搬進倉庫（SSTable），半夜找時間整理（compaction）— 收書極快，找書要多翻幾個箱子。

Normalization

Normalization removes redundancy by decomposing tables so that each fact is stored exactly once. Running example — a raw orders table:

orders(order_id, customer_name, customer_email, product_ids, product_names, unit_prices)

到 3NF 後的 schema：customers、products、orders、order_items — update 一個 email 只改一列，不會出現同一個客戶兩個不同 email 的 anomaly。

When to Denormalize

Normalization optimizes for write correctness; analytics optimizes for read speed. 分析查詢如果每次都要 join 五張表，慢且難寫，所以 data warehouse 刻意反正規化：

• Star schema: 一張寬的 fact table（交易、事件，含外鍵與 metrics）連到幾張 dimension tables（user、product、date）— 只需一層 join，columnar engine 掃描極快
• Pre-aggregated summary tables、把 dimension 屬性直接冗餘進 fact table 都是常見手法

Replication & Partitioning

Two orthogonal scaling tools: replication copies the same data to multiple nodes (availability + read scaling); partitioning/sharding splits data across nodes (capacity + write scaling).

Leader-Follower Replication

• All writes go to the leader; the leader ships its WAL to followers, which replay it
• Reads can be served by followers — read replicas offload analytics and dashboard queries from the primary
• Synchronous replication: leader waits for follower ack — no data loss on failover, but higher write latency. Asynchronous: fast writes, but a crashed leader may lose the last few transactions

Replication Lag

Async followers are always slightly behind — 通常幾十毫秒，尖峰或大批次寫入時可能好幾秒甚至分鐘級。經典症狀：

• 使用者剛更新個人資料，重新整理後看到舊資料（read-your-writes violation）— 解法：該使用者的讀取暫時導回 leader
• DS 最常踩的坑：ETL 或 dashboard 讀 read replica，尖峰時 lag 拉大 → 報表少算了最後幾分鐘的訂單，看起來像 metrics 突然下跌

Sharding Strategies

Hot Partition Problem

一個 shard 吃掉不成比例的流量：celebrity user、以 timestamp 當 shard key、爆紅商品。解法：換 shard key（加 salt、hash 化）、把熱 key 再細分、熱資料前面加 cache。

Consistent Hashing

Naive hashing (server = hash(key) mod N) remaps almost all keys when N changes. Consistent hashing places servers and keys on a ring; each key belongs to the next server clockwise:

• Adding or removing a node only remaps about $k/n$ of the keys（k 個 keys、n 個 nodes）
• Virtual nodes: each physical server owns many points on the ring, smoothing out load imbalance

這是 Cassandra、DynamoDB、分散式 cache 分配資料的核心機制 — 面試講 sharding 時能主動帶到 consistent hashing 是加分題。

Choosing a Database

Redis vs Memcached

大多數場景選 Redis — 資料結構讓它遠不只是 cache。Memcached 的優勢只剩「多執行緒 + 極簡」，適合純字串快取塞滿大記憶體機器。

PostgreSQL: The "Everything Database"

在資料量與流量到達極限之前，PostgreSQL 一套可以打天下：

面試好答案的形狀：「先用 PostgreSQL + extension 驗證產品，等某個 workload 的規模真的撐不住，再遷到專用系統」— 這展現你懂 operational complexity 的成本，而不是堆砌技術名詞。

MongoDB Architecture Basics

• Stores BSON documents in collections; schema flexible, one document 通常對應一個 aggregate（user + 內嵌的 addresses）
• Replica set: one primary + secondaries, automatic failover election
• Sharded cluster: mongos router + config servers + shards; shard key 選錯是最常見的災難
• Default storage engine WiredTiger 其實是 B+ tree based；document-level locking

適合：schema 演化快、讀寫模式以「整份文件」為單位。不適合：需要跨 document 的複雜 join 與強一致 transaction 的核心帳務系統。

OLTP vs OLAP

Decision Table by Workload

Real-World Use Cases

Case 1: 推薦系統 Feature Store — Redis 還是 DynamoDB？

你負責的推薦系統要在 50ms 內完成 inference，其中 feature fetching 的預算只有 10ms：要撈 user 的近 7 天行為統計、item 的熱門度分數等約 30 個 features。Batch pipeline 每小時把算好的 features 寫進 online store，serving 時以 user_id / item_id 為 key 讀出。

• Redis：in-memory，p99 在 1ms 以內；hash 結構天然對應 feature map；但資料要塞進記憶體，成本隨 feature 數量線性上升，且要自己顧 cluster 運維
• DynamoDB：fully managed、容量幾乎無上限、依用量計費；p99 個位數毫秒（可加 DAX cache 到微秒級）；但 latency 稍高、query 彈性低
• 常見架構：DynamoDB 做 source of truth、Redis 做熱 key cache，或直接用 Feast 之類的 feature store framework 管理兩層

面試 follow-up：

• Feature 更新頻率從每小時變成即時（streaming），架構要怎麼改？（Kafka + stream processing 直寫 online store，注意 late event 與亂序）
• Redis node 掛掉時 serving 怎麼辦？（replica failover + 降級策略：用 default feature values，模型要對 missing features robust）
• 怎麼避免 training 和 serving 讀到的 features 不一致？（同一套 feature 定義產 offline / online 兩份 — train-serving skew 的核心解法）

Case 2: A/B Testing 實驗數據 — OLTP 與 OLAP 分離

公司的實驗平台每天產生上億筆 exposure / conversion events。早期團隊直接把 events 寫進 production PostgreSQL 並在上面跑分析 SQL，結果實驗報表一跑，線上 API 的 p99 latency 就飆高。

• 問題本質：OLTP 和 OLAP 是兩種完全不同的 access pattern — row store 為了小交易優化，被迫做全表掃描時會把 buffer pool 洗掉
• 重構：events 走 Kafka 進 columnar warehouse（BigQuery / ClickHouse），建 star schema — exposure fact table 連 experiment、variant、user dimension tables；PostgreSQL 只留實驗設定（metadata）
• 收益：分析查詢從分鐘級降到秒級（columnar 只掃需要的欄位 + 高壓縮率），且與線上系統完全隔離

面試 follow-up：

• 為什麼 columnar storage 對這種查詢快？（只讀取涉及的欄位、同型別資料壓縮率高、vectorized execution）
• 實驗結果需要「準即時」監控 guardrail metrics，怎麼辦？（streaming aggregation 進 real-time OLAP 如 ClickHouse / Druid，接受近似值）
• 如果 dashboard 讀的是 replica 而 replication lag 突然變大，會看到什麼？（最新時段 metrics 假性下跌 — 要監控 lag 並在 dashboard 標註 data freshness）

Case 3: 推薦系統 Embedding 檢索 — Vector DB 選型

你們的 two-tower 模型產出 100 萬個 item embeddings（768 維），serving 時要拿 user embedding 找 top-100 最相似的 items，延遲預算 20ms。Exact 的暴力搜尋是 $O(n \cdot d)$，百萬級勉強可行但無法再長大，所以需要 ANN（approximate nearest neighbor）index。

• HNSW（hierarchical navigable small world graph）：高 recall、低延遲，但 index 佔記憶體大、建構慢
• IVF（inverted file，先 cluster 再只搜最近的幾個 clusters）：省記憶體、建構快，recall 稍低
• 選型階梯：百萬級以內 → pgvector（少一個系統要維運，還能跟 metadata filter 同一條 SQL）；上億級、高 QPS → 專用系統（Milvus、Weaviate 自架，或 Pinecone 全託管）
• 別忘了 metadata filtering（只推在架商品）— pre-filter 和 post-filter 對 recall 的影響是常見追問

面試 follow-up：

• Recall 和 latency 怎麼 tradeoff？（HNSW 的 ef_search、IVF 的 nprobe 都是搜尋廣度旋鈕 — 調大則 recall 高、延遲高）
• Item embeddings 每天 retrain 後全量更新，index 怎麼換？（build new index offline → 原子切換 alias，避免邊寫邊讀的一致性問題）
• 為什麼不直接把 embeddings 放 Redis 然後暴力算？（百萬級 768 維每次 query 要幾十億次乘法 — 延遲和 CPU 成本都撐不住；ANN 用 sublinear 搜尋換 approximate 結果）

Hands-on: Databases in Python

EXPLAIN QUERY PLAN with sqlite3: Index vs Full Scan

import sqlite3

conn = sqlite3.connect(":memory:")
cur = conn.cursor()

# A transactions table with no index (except the implicit rowid)
cur.execute("""
    CREATE TABLE transactions (
        id INTEGER PRIMARY KEY,
        user_id INTEGER,
        amount REAL,
        created_at TEXT
    )
""")
cur.executemany(
    "INSERT INTO transactions (user_id, amount, created_at) VALUES (?, ?, ?)",
    [(i % 1000, i * 1.5, f"2026-01-{i % 28 + 1:02d}") for i in range(100_000)],
)

# Without an index: the plan is a full table scan
rows = cur.execute(
    "EXPLAIN QUERY PLAN SELECT * FROM transactions WHERE user_id = 42"
).fetchall()
# plan: SCAN transactions  (reads all 100k rows)

# Create a secondary index on user_id
cur.execute("CREATE INDEX idx_txn_user ON transactions(user_id)")

rows = cur.execute(
    "EXPLAIN QUERY PLAN SELECT * FROM transactions WHERE user_id = 42"
).fetchall()
# plan: SEARCH transactions USING INDEX idx_txn_user (user_id=?)
# B+ tree lookup touches ~100 rows instead of 100k

Composite Index and the Leftmost Prefix Rule

# Composite index: sorted by user_id first, then created_at
cur.execute(
    "CREATE INDEX idx_txn_user_date ON transactions(user_id, created_at)"
)

# Uses the index: filters on the leftmost column + a range on the second
cur.execute("""
    EXPLAIN QUERY PLAN
    SELECT * FROM transactions
    WHERE user_id = 42 AND created_at >= '2026-01-15'
""").fetchall()
# plan: SEARCH ... USING INDEX idx_txn_user_date (user_id=? AND created_at>?)

# Cannot use the composite index: skips the leftmost column
cur.execute("""
    EXPLAIN QUERY PLAN
    SELECT * FROM transactions WHERE created_at >= '2026-01-15'
""").fetchall()
# plan: SCAN transactions  (created_at alone is not sorted globally)

# Covering index: the query needs only indexed columns -> no table lookup
cur.execute("""
    EXPLAIN QUERY PLAN
    SELECT created_at FROM transactions WHERE user_id = 42
""").fetchall()
# plan: SEARCH ... USING COVERING INDEX idx_txn_user_date (user_id=?)

A Simple Bloom Filter

import hashlib

class BloomFilter:
    """Probabilistic set: 'definitely not in' or 'possibly in'."""

    def __init__(self, m_bits=1_000_000, k_hashes=5):
        self.m = m_bits
        self.k = k_hashes
        self.bits = bytearray(m_bits // 8 + 1)

    def _positions(self, item):
        # Derive k positions from k salted hashes of the item
        for i in range(self.k):
            digest = hashlib.sha256(f"{i}:{item}".encode()).hexdigest()
            yield int(digest, 16) % self.m

    def add(self, item):
        for pos in self._positions(item):
            self.bits[pos // 8] |= 1 << (pos % 8)

    def might_contain(self, item):
        # False -> definitely absent; True -> present with prob 1 - p_fp
        return all(
            self.bits[pos // 8] & (1 << (pos % 8))
            for pos in self._positions(item)
        )

# LSM read path: skip an SSTable when the filter says "definitely absent"
sstable_filter = BloomFilter()
for key in ["user:1", "user:7", "user:42"]:
    sstable_filter.add(key)

sstable_filter.might_contain("user:42")   # True  -> go read the SSTable
sstable_filter.might_contain("user:999")  # False -> skip the disk read entirely

Interview Signals

What interviewers listen for:

• 被問「query 很慢怎麼辦」時，你先說 EXPLAIN 看 plan，而不是反射性地說「加 index」
• 你能解釋 B+ tree 為什麼適合 disk（高 fanout、低樹高、leaf 串成 linked list 支援 range scan），而不是只會背「index 讓查詢變快」
• 你講 sharding 時會主動提 hot partition 和 consistent hashing，講 replication 時會主動提 replication lag 對報表的影響
• 你做選型時先問 workload（讀寫比例、latency 需求、資料量、一致性需求），並承認「先用 PostgreSQL」常是最好的答案
• 你知道 OLTP 和 OLAP 要分離，且能說出 columnar storage 為什麼對分析查詢快

Practice

Flashcards

Quiz