Index 的原理與實戰 — B-Tree、Hash、GIN、GiST

前言

索引（Index）大概是後端工程師最常打交道的資料庫概念了。「查詢太慢？加個索引！」幾乎變成了條件反射。但索引不是萬靈丹——加錯索引不但不會變快，反而會拖慢寫入速度、浪費儲存空間。

我見過不少團隊的資料庫裡堆了上百個索引，其中一半從來沒被查詢用到，純粹佔空間。也見過明明加了索引卻完全沒效果的情況，一查才發現索引類型選錯了。

這篇文章會深入介紹 PostgreSQL 支援的幾種主要索引類型——B-Tree、Hash、GIN、GiST，解釋它們各自的原理、適用場景，以及實際建立和管理的技巧。理解這些之後，你就能做出更好的索引決策。

B-Tree 索引

原理

B-Tree（Balanced Tree）是最通用、也是預設的索引類型。它的結構類似一棵多路平衡搜尋樹：

B-Tree 結構示意（簡化版）：

[30 | 60]                    ← 根節點
          /    |     \
   [10|20]  [40|50]  [70|80|90]        ← 內部節點
   / | \    / | \    / | \ \
  葉子節點...                           ← 葉子節點（包含指向實際 row 的指標）

特性：

所有葉子節點在同一層（平衡）
葉子節點之間有雙向鏈結（方便範圍掃描）
搜尋、插入、刪除都是 O(log n)

適用場景

B-Tree 支援以下運算：=、<、>、<=、>=、BETWEEN、IN、IS NULL、LIKE 'prefix%'

-- 建立 B-Tree 索引（預設類型，不需要指定）
CREATE INDEX idx_orders_created ON orders (created_at);
-- 等同於：
CREATE INDEX idx_orders_created ON orders USING btree (created_at);

-- 等值查詢
SELECT * FROM orders WHERE created_at = '2024-06-15';  -- 走索引

-- 範圍查詢
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-06-30';  -- 走索引

-- 排序
SELECT * FROM orders ORDER BY created_at DESC LIMIT 10;  -- 走索引

-- 前綴 LIKE
SELECT * FROM customers WHERE name LIKE 'John%';  -- 走索引
SELECT * FROM customers WHERE name LIKE '%John';   -- 不走索引！

複合索引的順序很重要

-- 複合索引
CREATE INDEX idx_orders_status_date ON orders (status, created_at);

-- 以下查詢走索引：
SELECT * FROM orders WHERE status = 'completed';                          -- OK（用到第一個欄位）
SELECT * FROM orders WHERE status = 'completed' AND created_at > '2024-01-01';  -- OK（兩個都用到）
SELECT * FROM orders WHERE status = 'completed' ORDER BY created_at;      -- OK（完美匹配）

-- 以下查詢不走這個索引：
SELECT * FROM orders WHERE created_at > '2024-01-01';  -- 不走（跳過第一個欄位）

-- 經驗法則：
-- 複合索引的欄位順序應該是：
-- 1. 等值查詢的欄位放前面
-- 2. 範圍查詢的欄位放後面
-- 3. 排序欄位跟在查詢欄位後面

覆蓋索引（Index-Only Scan）

-- 如果查詢需要的所有欄位都在索引中，PostgreSQL 可以不讀 table
-- 這叫做 Index-Only Scan，非常快

-- 假設我們常執行這個查詢：
SELECT customer_id, SUM(amount) FROM orders
WHERE status = 'completed' GROUP BY customer_id;

-- 建立包含所有需要欄位的索引
CREATE INDEX idx_orders_covering ON orders (status, customer_id, amount);
-- 或者用 INCLUDE（PostgreSQL 11+）：
CREATE INDEX idx_orders_covering_v2 ON orders (status) INCLUDE (customer_id, amount);

-- INCLUDE 的好處：被包含的欄位不參與索引排序，索引更小
-- 但它們可以被 Index-Only Scan 使用

-- 驗證是否走 Index-Only Scan
EXPLAIN ANALYZE
SELECT customer_id, SUM(amount) FROM orders
WHERE status = 'completed' GROUP BY customer_id;

-- 理想輸出：
-- Index Only Scan using idx_orders_covering on orders
--   Index Cond: (status = 'completed')
--   Heap Fetches: 0  ← 越接近 0 越好

Hash 索引

原理

Hash 索引使用哈希表結構，只支援等值查詢（=）。

Hash Index 結構：

value → hash(value) → bucket → row pointer

特性：

只支援 = 運算
查找是 O(1)（理論上）
不支援排序、範圍查詢
PostgreSQL 10 之前不是 WAL-logged（不安全），10+ 才修復

適用場景

-- 建立 Hash 索引
CREATE INDEX idx_sessions_token ON sessions USING hash (session_token);

-- 走索引：
SELECT * FROM sessions WHERE session_token = 'abc123def456';  -- 等值查詢

-- 不走索引：
SELECT * FROM sessions WHERE session_token > 'abc';           -- 範圍查詢
SELECT * FROM sessions ORDER BY session_token;                 -- 排序

Hash vs B-Tree 的選擇

-- 比較索引大小
CREATE INDEX idx_token_btree ON sessions USING btree (session_token);
CREATE INDEX idx_token_hash ON sessions USING hash (session_token);

SELECT
    indexname,
    pg_size_pretty(pg_relation_size(indexname::regclass)) AS size
FROM pg_indexes
WHERE tablename = 'sessions' AND indexname LIKE 'idx_token%';

-- 結果（示例）：
-- idx_token_btree | 256 MB
-- idx_token_hash  | 128 MB  ← Hash 索引通常更小

我的建議：除非你確定只有等值查詢，且欄位值很長（例如 UUID、hash string），否則用 B-Tree 就好。B-Tree 的通用性好太多了。

GIN 索引

原理

GIN（Generalized Inverted Index，通用倒排索引）專為「一個欄位包含多個值」的場景設計。

GIN Index 結構（倒排索引）：

以 JSONB 為例：
{"tags": ["python", "backend"]} → row 1
{"tags": ["python", "devops"]}  → row 2
{"tags": ["backend", "sql"]}    → row 3

GIN 索引建立的映射：
  "python"  → [row 1, row 2]
  "backend" → [row 1, row 3]
  "devops"  → [row 2]
  "sql"     → [row 3]

查詢 "python" 時，直接從映射找到 [row 1, row 2]

適用場景

-- 1. JSONB 查詢
CREATE INDEX idx_events_payload ON events USING GIN (payload);

-- @> 包含查詢（走 GIN 索引）
SELECT * FROM events WHERE payload @> '{"type": "purchase"}';

-- ? 存在性查詢
SELECT * FROM events WHERE payload ? 'error_code';

-- 2. 陣列查詢
CREATE TABLE articles (
    id SERIAL PRIMARY KEY,
    title TEXT,
    tags TEXT[]
);

CREATE INDEX idx_articles_tags ON articles USING GIN (tags);

-- 陣列包含查詢
SELECT * FROM articles WHERE tags @> ARRAY['python'];       -- 包含 python
SELECT * FROM articles WHERE tags && ARRAY['python','sql'];  -- 包含 python 或 sql

-- 3. 全文搜尋
ALTER TABLE articles ADD COLUMN search_vector TSVECTOR;
UPDATE articles SET search_vector = to_tsvector('english', title);
CREATE INDEX idx_articles_search ON articles USING GIN (search_vector);

SELECT * FROM articles
WHERE search_vector @@ to_tsquery('english', 'python & tutorial');

-- 4. 三元組模糊搜尋（pg_trgm）
CREATE EXTENSION pg_trgm;
CREATE INDEX idx_customers_name_trgm ON customers USING GIN (name gin_trgm_ops);

-- 支援 LIKE 任意位置匹配
SELECT * FROM customers WHERE name LIKE '%john%';     -- 走 GIN 索引！
SELECT * FROM customers WHERE name ILIKE '%john%';    -- 也走索引
-- 還支援相似度搜尋
SELECT * FROM customers WHERE name % 'jonh';          -- 模糊匹配（容錯拼字）

GIN 的注意事項

-- GIN 索引的寫入較慢，因為每次插入可能需要更新多個映射
-- 可以用 fastupdate 加速寫入（延遲合併到主索引）
CREATE INDEX idx_events_payload ON events USING GIN (payload)
WITH (fastupdate = on);  -- 預設就是 on

-- 但 fastupdate 會讓查詢略慢（需要同時查 pending list）
-- 高寫入場景可以定期手動清理：
SELECT gin_clean_pending_list('idx_events_payload');

-- 查看 GIN 索引大小（通常比 B-Tree 大）
SELECT
    indexname,
    pg_size_pretty(pg_relation_size(indexname::regclass)) AS size
FROM pg_indexes WHERE tablename = 'events';

GiST 索引

原理

GiST（Generalized Search Tree）是一個通用的索引框架，支援各種空間和幾何查詢。

GiST 的核心概念：

每個節點代表一個「邊界框」（bounding box）
查詢時從根節點開始，只進入可能包含目標的子樹
類似 R-Tree 的概念


適用的資料類型：

幾何形狀（點、線、多邊形）
範圍類型（int4range, tstzrange）
全文搜尋（tsvector）
網路地址（inet）

適用場景

-- 1. 地理空間查詢（最常見的 GiST 用途）
CREATE EXTENSION postgis;

CREATE TABLE stores (
    id SERIAL PRIMARY KEY,
    name TEXT,
    location GEOMETRY(Point, 4326)
);

CREATE INDEX idx_stores_location ON stores USING GIST (location);

-- 找出距離某個點 5 公里內的所有店家
SELECT name, ST_Distance(location::geography, ST_MakePoint(121.5654, 25.0330)::geography) AS distance_m
FROM stores
WHERE ST_DWithin(location::geography, ST_MakePoint(121.5654, 25.0330)::geography, 5000)
ORDER BY distance_m;

-- 2. 範圍類型查詢（排班系統、訂房系統超好用）
CREATE TABLE room_bookings (
    id SERIAL PRIMARY KEY,
    room_id INT,
    during TSTZRANGE NOT NULL,
    guest_name TEXT,
    -- 使用 EXCLUDE 約束防止重疊訂房
    EXCLUDE USING GIST (room_id WITH =, during WITH &&)
);

CREATE INDEX idx_bookings_during ON room_bookings USING GIST (during);

-- 查詢某段時間內的訂房
SELECT * FROM room_bookings
WHERE during && tstzrange('2024-06-01', '2024-06-30');

-- 嘗試插入重疊的訂房會失敗
INSERT INTO room_bookings (room_id, during, guest_name)
VALUES (1, '[2024-06-15, 2024-06-20)', 'Alice');  -- OK

INSERT INTO room_bookings (room_id, during, guest_name)
VALUES (1, '[2024-06-18, 2024-06-22)', 'Bob');    -- ERROR: conflicting key

-- 3. 全文搜尋（GiST vs GIN）
-- GiST 全文索引比 GIN 小，但查詢較慢
-- 適合更新頻繁的場景
CREATE INDEX idx_articles_search_gist ON articles USING GIST (search_vector);

索引管理實戰

建立索引而不鎖表

-- 一般的 CREATE INDEX 會鎖住寫入
-- 在生產環境要用 CONCURRENTLY
CREATE INDEX CONCURRENTLY idx_orders_customer ON orders (customer_id);

-- 注意事項：
-- 1. CONCURRENTLY 會比一般建立慢 2-3 倍
-- 2. 如果中途失敗，會留下一個 INVALID 索引，需要手動清理
-- 3. 不能在 transaction 中使用

-- 檢查是否有 INVALID 索引
SELECT indexname, indexdef
FROM pg_indexes
WHERE schemaname = 'public'
  AND indexname IN (
    SELECT indexrelid::regclass::text
    FROM pg_index
    WHERE NOT indisvalid
  );

-- 清理 INVALID 索引
DROP INDEX CONCURRENTLY IF EXISTS idx_orders_customer;
-- 然後重新建立

找出未使用的索引

-- 找出從未被使用的索引（浪費空間和寫入效能）
SELECT
    schemaname || '.' || tablename AS table,
    indexname,
    idx_scan AS times_used,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size,
    pg_size_pretty(pg_total_relation_size(relid)) AS table_total_size
FROM pg_stat_user_indexes
JOIN pg_index USING (indexrelid)
WHERE idx_scan = 0
  AND NOT indisunique             -- 保留 UNIQUE 約束的索引
  AND NOT indisprimary            -- 保留 PK
  AND pg_relation_size(indexrelid) > 1024 * 1024  -- 只看 > 1MB 的
ORDER BY pg_relation_size(indexrelid) DESC;

找出重複的索引

-- 找出完全重複或被其他索引覆蓋的索引
SELECT
    a.indexname AS redundant_index,
    b.indexname AS covering_index,
    pg_size_pretty(pg_relation_size(a.indexname::regclass)) AS redundant_size,
    a.indexdef
FROM pg_indexes a
JOIN pg_indexes b ON a.tablename = b.tablename
    AND a.indexname != b.indexname
    AND b.indexdef LIKE a.indexdef || '%'  -- b 包含 a 的所有欄位
WHERE a.schemaname = 'public';

-- 更精確的做法：比較索引欄位
SELECT
    t.tablename,
    array_agg(a.indexname) AS duplicate_indexes,
    array_agg(pg_size_pretty(pg_relation_size(a.indexname::regclass))) AS sizes,
    a.indexdef
FROM pg_indexes a
JOIN pg_indexes t ON a.tablename = t.tablename AND a.indexdef = t.indexdef AND a.indexname != t.indexname
WHERE a.schemaname = 'public'
GROUP BY t.tablename, a.indexdef;

索引維護

-- 查看索引膨脹率
SELECT
    nspname || '.' || relname AS index_name,
    pg_size_pretty(pg_relation_size(i.indexrelid)) AS index_size,
    idx_scan AS scans,
    idx_tup_read AS tuples_read,
    idx_tup_fetch AS tuples_fetched
FROM pg_stat_user_indexes ui
JOIN pg_index i ON ui.indexrelid = i.indexrelid
JOIN pg_class c ON i.indexrelid = c.oid
JOIN pg_namespace n ON c.relnamespace = n.oid
ORDER BY pg_relation_size(i.indexrelid) DESC
LIMIT 20;

-- REINDEX：重建索引（可以減少膨脹）
-- 在 PostgreSQL 12+ 可以 CONCURRENTLY
REINDEX INDEX CONCURRENTLY idx_orders_customer;
-- 重建整張表的所有索引
REINDEX TABLE CONCURRENTLY orders;

效能影響測試

-- 實際測試不同索引類型的查詢效能
-- 以 100 萬筆 JSONB 資料為例

-- 準備測試資料
CREATE TABLE test_json (
    id SERIAL PRIMARY KEY,
    data JSONB
);

INSERT INTO test_json (data)
SELECT jsonb_build_object(
    'type', (ARRAY['A','B','C','D','E'])[floor(random()*5+1)],
    'value', floor(random()*1000),
    'tags', (SELECT jsonb_agg(t) FROM (
        SELECT (ARRAY['red','blue','green','yellow','purple'])[floor(random()*5+1)] AS t
        FROM generate_series(1, floor(random()*3+1)::int)
    ) sub)
)
FROM generate_series(1, 1000000);

-- 測試：無索引
EXPLAIN ANALYZE SELECT * FROM test_json WHERE data @> '{"type": "A"}';
-- Seq Scan → 約 800ms

-- 測試：GIN 索引
CREATE INDEX idx_test_gin ON test_json USING GIN (data);
EXPLAIN ANALYZE SELECT * FROM test_json WHERE data @> '{"type": "A"}';
-- Bitmap Index Scan → 約 50ms（快 16 倍）

-- 測試：B-Tree on generated column
ALTER TABLE test_json ADD COLUMN data_type TEXT GENERATED ALWAYS AS (data->>'type') STORED;
CREATE INDEX idx_test_btree_type ON test_json (data_type);
EXPLAIN ANALYZE SELECT * FROM test_json WHERE data_type = 'A';
-- Index Scan → 約 30ms（更快，但只能查 type 欄位）

小結

索引選擇的核心原則：

| 索引類型 | 適用場景 | 支援運算 | 大小 | 寫入影響 |
|———|———|———|——|———|
| B-Tree | 通用查詢、排序、範圍 | =, <, >, BETWEEN, LIKE prefix | 中 | 低 |
| Hash | 純等值查詢 | = | 小 | 低 |
| GIN | 陣列、JSONB、全文搜尋 | @>, ?, &&, @@ | 大 | 高 |
| GiST | 地理空間、範圍、幾何 | &&, @>, <@, << | 中 | 中 |

實務建議：

1. 預設用 B-Tree：90% 的情況 B-Tree 就夠了
2. JSONB 查詢用 GIN：比 generated column + B-Tree 靈活得多
3. 地理空間用 GiST：這是 PostGIS 的標準配備
4. 定期清理未使用的索引：每個多餘的索引都在拖慢寫入
5. 生產環境一定用 CONCURRENTLY：不要鎖表建索引

延伸閱讀建議：

• PostgreSQL Index Types 官方文件
• Use The Index, Luke — 跨資料庫索引最佳實踐
• pgHero — PostgreSQL 效能監控工具，會自動建議索引
• Dexter — 自動索引建議工具