索引結構練習題 (Practice - Database Indexing)

需求	首選索引
通用查詢 / 範圍 / 排序	B-Tree（預設）
純等值查詢	Hash Index
寫多讀少 / 時序	LSM Tree
地理鄰近搜尋	Geospatial（R-Tree / Geohash）
全文檢索	Inverted Index

• 沒有索引：資料庫做 Full Table Scan（全表掃描），逐筆比對，時間複雜度 O(n)。
• 有索引：透過索引結構快速定位資料（像查目錄找頁碼），接近 O(log n)。

• WHERE 條件查詢（等值與範圍）
• JOIN 操作（避免 nested loop 全表比對）
• ORDER BY 排序（索引本身有序可直接利用）
• 前綴搜尋 LIKE 'abc%'（但 '%abc' 無效）

1. 佔用額外儲存空間 — 索引是獨立結構
2. 寫入變慢 — INSERT / UPDATE / DELETE 要同步更新所有相關索引
3. 太多索引反而拖效能 — 每次寫入要維護多個索引，查詢優化器也要花時間挑選

該建：

• 經常出現在 WHERE / JOIN / ORDER BY 的欄位
• 選擇性（selectivity）高的欄位（unique 或接近 unique）

不該建（或要小心）：

• 寫入極頻繁但查詢少的欄位
• 低選擇性欄位（如 is_deleted 只有兩種值）— 索引效益低
• 已經被複合索引涵蓋的欄位（避免重複）

1. 平衡 — 所有葉節點到根距離相同，查詢永遠 O(log n)
2. 多叉樹 — 每節點可存多個 key 和子節點指標（不是二元樹）
3. 磁碟友好 — 節點大小對齊磁碟頁（4KB / 8KB），減少 I/O 次數

差異	B-Tree	B+Tree
資料位置	內部 + 葉節點都能存	只有葉節點存資料
葉節點連結	無	葉節點間有 linked list
範圍查詢效率	較差（要回上層）	較好（沿葉節點線性走）

MySQL InnoDB 使用 B+Tree。PostgreSQL 的 B-Tree 也類似 B+Tree（有葉節點連結）。

• 等值查詢 WHERE id = 123
• 範圍查詢 BETWEEN、>、<、>=
• 排序 ORDER BY（可直接利用索引的有序性）
• 前綴搜尋 LIKE 'abc%'（但 '%abc' 無法，因打破順序）

B-Tree 索引。

CREATE TABLE products (
  product_id SERIAL PRIMARY KEY,   -- 自動建 B-Tree on product_id
  sku VARCHAR(100) UNIQUE          -- 自動建 B-Tree on sku
);

這些 B-Tree 維持排序，確保唯一性檢查 O(log n) 並支援範圍查詢（product_id BETWEEN 100 AND 200）。

• B-Tree → 讀取為主的工作負載。平衡樹 O(log n) 查詢可直接定位資料。
• LSM Tree → 寫入為主的工作負載。把隨機寫轉成順序寫（先 MemTable 再 flush 到 SSTable），吞吐量極高；代價是讀取時可能要查多層。

1. WAL（Write-Ahead Log） — 每次寫入前先 append 到 log 檔，掉電時可重播恢復
2. MemTable — 寫入記憶體中的排序結構（SkipList），支援快速查詢
3. SSTable（Sorted String Table） — MemTable 寫滿後 flush 成 不可變 的磁碟檔案

• Write Amplification（寫放大）：同一筆資料因為 Compaction（合併壓縮）可能被多次重寫到不同層，實際寫入量遠大於原始資料量。
• Bloom Filter：每個 SSTable 附帶的概率資料結構，可 O(1) 回答「這個 key 一定不在此 SSTable」，避免不必要的磁碟讀取，大幅加速查詢。

選 LSM Tree。

理由：

• 10 萬 QPS 寫入對 B-Tree 是極重負擔（隨機 I/O、節點分裂）
• LSM Tree 把寫入轉成順序 WAL + 記憶體 MemTable，寫入吞吐極高
• 讀取雖然多層查詢，但 Bloom Filter + Block Cache 能大幅緩解
• 具體選擇：Cassandra、HBase 或嵌入式的 RocksDB

典型應用：時序資料庫、log 收集、metric 儲存。

必要：

• 不 compaction → SSTable 不斷累積 → 查詢要掃很多檔案 → 讀取放大
• 舊版本（update / delete 的 tombstone）不清理 → 佔用空間

代價：

• 大量磁碟 I/O：合併時讀寫多個 SSTable
• CPU 使用：排序、解壓縮、重壓縮
• 寫放大：同一筆資料被多次重寫
• 可能影響前台效能：Compaction 和查詢共用 I/O 通道

生產系統通常在低峰時段排程 compaction，或用 rate limit 控制對前台的影響。

錯。 Hash Index 只支援 等值查詢（O(1)），不支援範圍查詢或排序，因為 hash 函數會打亂原始 key 的順序。範圍查詢必須掃全部 bucket → O(n)。

1. Chaining（鏈結法） — bucket 裡放 linked list 或 array，把所有同 bucket 的 key 串起來
2. Open Addressing（開放位址法） — 碰撞時往鄰近空位找（線性探測、二次探測、雙重雜湊）

場景	建議索引
WHERE id = 123（等值，高頻）	Hash（O(1) 最快）
WHERE created_at BETWEEN ...	B-Tree（範圍）
ORDER BY name	B-Tree（排序）
WHERE name LIKE 'abc%'	B-Tree（前綴）
通用場景 / 不確定	B-Tree（預設）

1. 範圍查詢需求普遍 — 生產 SQL 大量出現 BETWEEN、ORDER BY，Hash Index 完全無法處理
2. 效能穩定 — B+Tree O(log n) 可預測；Hash 在碰撞嚴重時退化到 O(n)
3. 空間使用 — B+Tree 結構緊湊；Hash Index bucket 多時會浪費空間
4. Rehash 成本 — Hash 表滿了要重建整個表，對大型表代價過高

InnoDB 仍保留 Adaptive Hash Index（自動偵測熱點 key，內部建立 hash 表加速等值查詢），但不對使用者開放手動建立。

鄰近搜尋是 二維空間問題，但兩個獨立的一維索引無法有效處理：

• 只用緯度索引 → 找到一條「橫跨全球的長條帶」，經度索引派不上用場
• 兩個索引做交集 → 形成一個 矩形區域，比真正要的 圓形半徑 大得多，最後還要再過濾超出距離的結果

需要專門的空間索引（Geohash / R-Tree / S2 / H3）來快速過濾候選區域。

(C) Geohash。

它將經緯度轉換成 Base32 字串，鄰近的點通常共享相同前綴，可以直接搭配現成的 B-Tree 前綴索引，不需要特殊資料結構。

• Quadtree：固定切成 4 等份（NE / NW / SE / SW），不管資料分佈。結構簡單但不適應資料密度。
• R-Tree：用 彈性、可重疊的矩形（MBR） 根據實際資料分佈來組織資料，能同時處理點、多邊形、道路網絡。

R-Tree 是現代生產環境的標準（PostGIS、SQLite R*Tree、Oracle Spatial、MySQL SPATIAL）。

選 H3（Uber 自己設計的）。

理由：

• 6 邊形 cell 到所有鄰居距離相等 → 鄰近搜尋更均勻
• k_ring(cell, k) 可快速取中心 cell 周圍 k 層的 cell → 對應「3km 半徑」
• 多解析度（resolution） 支援不同粒度的聚合（熱力圖、區域統計）
• 天然適合分散式聚合（hash cell_id 就能 shard）

若用 Geohash 則邊界效應嚴重；R-Tree 做聚合不如 H3 的 cell 直接切分直觀。

• Forward Index（正排索引）：文件 → 包含的單字（document → words）
• Inverted Index（倒排索引）：單字 → 出現在哪些文件（word → documents）

Inverted Index 讓全文檢索可以 O(1) 跳到對應 term 的 posting list，快速找到所有包含該單字的文件。

1. 查 apple 的 posting list → [Doc1, Doc3]
2. 查 dog 的 posting list → [Doc2, Doc3]
3. 取兩個 posting list 的 交集 → [Doc3]

結果：只有 Doc3 同時包含 apple 和 dog。OR 查詢則取聯集；NOT 查詢取差集。

• Elasticsearch / OpenSearch（搜尋引擎）— 底層是 Apache Lucene，行業標準
• Apache Solr — 同樣基於 Lucene
• PostgreSQL FTS — to_tsvector() + GIN 索引（Generalized Inverted iNdex）
• MySQL FULLTEXT — MATCH ... AGAINST 語法
• Sourcegraph / VSCode 全域搜尋 — 程式碼符號檢索

類別：全文檢索、日誌分析、程式碼搜尋、spam 過濾。

需要 positions（term 在文件中的位置）。

比對過程：

1. 取 apple 的 posting list，含 positions，如 (Doc1, pos=[2]), (Doc3, pos=[5,9])
2. 取 pie 的 posting list，如 (Doc1, pos=[3]), (Doc3, pos=[12])
3. 只有當 pie.pos = apple.pos + 1 才匹配：
   • Doc1: apple@2, pie@3 → 3 = 2+1 ✓
   • Doc3: apple@5, pie@12 → ✗；apple@9, pie@12 → ✗
4. 結果：Doc1

這就是為什麼 Inverted Index 通常要存 positions，代價是儲存空間更大。

問題	解法
通用查詢首選	B-Tree（範圍、排序、前綴都支援）
純等值查詢極致速度	Hash Index（O(1)，但無排序）
寫多於讀 / 海量 ingest	LSM Tree（順序 I/O，Cassandra/RocksDB）
地理鄰近搜尋	Geohash（簡單）/ R-Tree（SQL 標準）/ H3（Uber 鄰近）/ S2（Google 地圖）
全文檢索	Inverted Index（Elasticsearch / Lucene）
碰撞處理	Chaining（鏈結）or Open Addressing（開放位址）
LSM 查詢加速關鍵	Bloom Filter（判斷 key 是否在 SSTable）
B-Tree vs B+Tree	生產環境用 B+Tree（葉節點鏈結，範圍更快）
Geospatial 陷阱	別用兩個 1D 索引；用專門的 2D 空間索引