PostgreSQL 內部機制深度解析：從 MVCC 到查詢執行引擎
0. 前言與生成說明
本文是一篇深度技術解析文章，目標是讓讀者完整理解 PostgreSQL 的內部運作機制。
文章目標
讀完本文，你將理解：
- PostgreSQL 的整體架構與模塊劃分
- MVCC（多版本並發控制）的實現原理
- Tuple 的物理結構與可見性判斷
- 查詢處理的完整流程：Parser → Analyzer → Optimizer → Executor
- Buffer Pool 管理機制
- 各類索引的實現原理
1. PostgreSQL 整體架構
PostgreSQL 是一個基於 進程模型 的關係型資料庫管理系統，使用 C 語言開發。其核心優勢包括：
| 特性 | 說明 |
|---|---|
| ACID 完整支援 | 完整的事務保證 |
| MVCC | 讀寫不互相阻塞 |
| 豐富的索引類型 | B-tree、Hash、GiST、GIN、BRIN、SP-GiST |
| 可擴展性 | 支援自定義資料類型、函數、索引方法 |
| SQL 標準兼容 | 高度遵循 SQL 標準 |
1.1 源代碼結構
從 PostgreSQL 源代碼結構可以看出其模塊化設計：
postgres-src/
├── src/
│ ├── backend/ # 後端核心
│ │ ├── access/ # 存儲訪問層（heap、index）
│ │ ├── catalog/ # 系統目錄
│ │ ├── commands/ # SQL 命令處理
│ │ ├── executor/ # 查詢執行器
│ │ ├── optimizer/ # 查詢優化器
│ │ ├── parser/ # SQL 解析器
│ │ ├── postmaster/ # 進程管理
│ │ ├── replication/ # 複製
│ │ ├── storage/ # 存儲層
│ │ │ ├── buffer/ # Buffer Pool
│ │ │ ├── lmgr/ # Lock Manager
│ │ │ └── smgr/ # Storage Manager
│ │ ├── tcop/ # Traffic Cop（查詢入口）
│ │ └── utils/ # 工具函數
│ ├── include/ # 頭文件
│ └── interfaces/ # 客戶端接口（libpq）
└── contrib/ # 擴展模塊1.2 進程架構
PostgreSQL 採用 多進程架構，每個客戶端連接對應一個獨立的後端進程：
flowchart TB
subgraph Client["客戶端"]
C1["Client 1"]
C2["Client 2"]
C3["Client N"]
end
subgraph Postmaster["Postmaster (主進程)"]
PM["postmaster<br/>監聽連接請求<br/>Fork 子進程"]
end
subgraph BackendProcesses["Backend Processes"]
B1["Backend 1<br/>處理 Client 1"]
B2["Backend 2<br/>處理 Client 2"]
B3["Backend N<br/>處理 Client N"]
end
subgraph BackgroundWorkers["Background Workers"]
BW["Background Writer<br/>定期寫髒頁"]
WW["WAL Writer<br/>寫 WAL 日誌"]
CP["Checkpointer<br/>執行 Checkpoint"]
AV["Autovacuum<br/>自動清理"]
SS["Stats Collector<br/>統計收集"]
end
subgraph SharedMemory["Shared Memory"]
BP["Buffer Pool"]
WAL["WAL Buffers"]
LOCK["Lock Tables"]
CLOG["Commit Log"]
end
C1 --> PM
C2 --> PM
C3 --> PM
PM -->|fork| B1
PM -->|fork| B2
PM -->|fork| B3
B1 <--> BP
B2 <--> BP
B3 <--> BP
BW <--> BP
WW <--> WAL
CP <--> BP關鍵角色說明：
| 進程 | 職責 |
|---|---|
| Postmaster | 主進程，監聽連接請求，fork 後端進程 |
| Backend | 處理單一客戶端的所有查詢 |
| Background Writer | 定期將髒頁寫入磁碟，減少 checkpoint 壓力 |
| WAL Writer | 將 WAL buffer 寫入磁碟 |
| Checkpointer | 執行 checkpoint，確保資料持久化 |
| Autovacuum | 自動執行 VACUUM 和 ANALYZE |
2. MVCC：多版本並發控制
2.1 MVCC 核心理念
PostgreSQL 的 MVCC 實現基於 Snapshot Isolation (SI)，核心原則：
讀操作永不阻塞寫操作，寫操作永不阻塞讀操作
與使用 Rollback Segment 的資料庫（如 Oracle）不同，PostgreSQL 將新版本資料 直接寫入原表：
flowchart LR
subgraph Oracle方式["Oracle: Rollback Segment"]
O1["原始資料"] -->|更新| O2["新資料<br/>(覆蓋原位置)"]
O1 -->|舊版本| RS["Rollback Segment"]
end
subgraph PG方式["PostgreSQL: 多版本存儲"]
P1["Tuple v1<br/>(xmin=100)"]
P2["Tuple v2<br/>(xmin=101)"]
P3["Tuple v3<br/>(xmin=102)"]
P1 -->|t_ctid| P2
P2 -->|t_ctid| P3
end2.2 Transaction ID (XID)
每個事務都有唯一的 Transaction ID (XID)：
// src/include/access/transam.h
typedef uint32 TransactionId;
#define InvalidTransactionId ((TransactionId) 0)
#define BootstrapTransactionId ((TransactionId) 1)
#define FrozenTransactionId ((TransactionId) 2)
#define FirstNormalTransactionId ((TransactionId) 3)XID 是 32 位無符號整數，存在 wraparound 問題（約 40 億事務後會繞回）。PostgreSQL 通過 VACUUM FREEZE 機制解決此問題。
2.3 Tuple 結構
每個 Tuple（資料行）包含 23 字節的固定頭部 加上實際資料：
// src/include/access/htup_details.h
struct HeapTupleHeaderData
{
union
{
HeapTupleFields t_heap; // 存儲在表中時使用
DatumTupleFields t_datum; // 記憶體中使用
} t_choice;
ItemPointerData t_ctid; // 當前或更新後的 TID (6 bytes)
uint16 t_infomask2; // 屬性數量 + 標誌位
uint16 t_infomask; // 各種標誌位
uint8 t_hoff; // 頭部偏移量
bits8 t_bits[]; // NULL bitmap
// 之後是實際的用戶資料
};
typedef struct HeapTupleFields
{
TransactionId t_xmin; // 插入此 tuple 的事務 ID
TransactionId t_xmax; // 刪除/鎖定此 tuple 的事務 ID
union
{
CommandId t_cid; // 插入/刪除的命令 ID
TransactionId t_xvac; // VACUUM FULL 的事務 ID
} t_field3;
} HeapTupleFields;Tuple 物理結構圖：
┌─────────────────────────────────────────────────────────┐
│ HeapTupleHeader │
├──────────────┬──────────────┬───────────┬───────────────┤
│ t_xmin │ t_xmax │ t_ctid │ t_infomask/2 │
│ (4 bytes) │ (4 bytes) │ (6 bytes) │ (4 bytes) │
├──────────────┴──────────────┴───────────┴───────────────┤
│ t_hoff (1 byte) │
├─────────────────────────────────────────────────────────┤
│ NULL Bitmap (變長) │
├─────────────────────────────────────────────────────────┤
│ Padding (對齊) │
├─────────────────────────────────────────────────────────┤
│ User Data │
│ (實際的欄位資料) │
└─────────────────────────────────────────────────────────┘2.4 可見性判斷規則
PostgreSQL 使用複雜的規則判斷一個 tuple 對當前事務是否可見：
flowchart TD
Start["檢查 Tuple 可見性"]
CheckXmin["檢查 t_xmin"]
XminInvalid{"t_xmin<br/>無效/已回滾?"}
XminCommitted{"t_xmin<br/>已提交?"}
XminCurrent{"t_xmin =<br/>當前事務?"}
XminInSnapshot{"t_xmin<br/>在 snapshot 中?"}
CheckXmax["檢查 t_xmax"]
XmaxInvalid{"t_xmax<br/>無效?"}
XmaxCommitted{"t_xmax<br/>已提交?"}
XmaxCurrent{"t_xmax =<br/>當前事務?"}
XmaxInSnapshot{"t_xmax<br/>在 snapshot 中?"}
Visible["可見"]
Invisible["不可見"]
Start --> CheckXmin
CheckXmin --> XminInvalid
XminInvalid -->|是| Invisible
XminInvalid -->|否| XminCommitted
XminCommitted -->|否| XminCurrent
XminCurrent -->|否| Invisible
XminCurrent -->|是| CheckXmax
XminCommitted -->|是| XminInSnapshot
XminInSnapshot -->|是| Invisible
XminInSnapshot -->|否| CheckXmax
CheckXmax --> XmaxInvalid
XmaxInvalid -->|是| Visible
XmaxInvalid -->|否| XmaxCommitted
XmaxCommitted -->|否| XmaxCurrent
XmaxCurrent -->|是| Invisible
XmaxCurrent -->|否| Visible
XmaxCommitted -->|是| XmaxInSnapshot
XmaxInSnapshot -->|是| Visible
XmaxInSnapshot -->|否| Invisible核心邏輯（簡化）：
// 簡化的可見性判斷邏輯
bool HeapTupleSatisfiesMVCC(HeapTuple tuple, Snapshot snapshot)
{
// 1. 檢查插入事務 (t_xmin)
if (!TransactionIdIsValid(tuple->t_xmin))
return false; // 無效的 tuple
if (TransactionIdIsCurrentTransactionId(tuple->t_xmin)) {
// 當前事務插入的，需檢查是否被當前事務刪除
if (TransactionIdIsValid(tuple->t_xmax))
return false;
return true;
}
if (!XidInMVCCSnapshot(tuple->t_xmin, snapshot))
return false; // 插入事務對當前 snapshot 不可見
// 2. 檢查刪除事務 (t_xmax)
if (!TransactionIdIsValid(tuple->t_xmax))
return true; // 未被刪除
if (XidInMVCCSnapshot(tuple->t_xmax, snapshot))
return true; // 刪除事務對當前 snapshot 不可見
return false; // 已被刪除
}2.5 Commit Log (CLOG)
事務狀態存儲在 Commit Log (CLOG) 中，每個事務使用 2 bits：
#define TRANSACTION_STATUS_IN_PROGRESS 0x00
#define TRANSACTION_STATUS_COMMITTED 0x01
#define TRANSACTION_STATUS_ABORTED 0x02
#define TRANSACTION_STATUS_SUB_COMMITTED 0x03CLOG 存儲在 pg_xact/ 目錄下，每個文件 256KB，可存儲 1M 個事務狀態。
2.6 事務隔離級別
PostgreSQL 支援三種隔離級別：
| 隔離級別 | 現象防止 | 實現方式 |
|---|---|---|
| READ COMMITTED | 髒讀 | 每條語句取新 snapshot |
| REPEATABLE READ | 髒讀、不可重複讀、幻讀 | 事務開始時取 snapshot |
| SERIALIZABLE | 所有異常 | SSI (Serializable Snapshot Isolation) |
Serializable Snapshot Isolation (SSI) 是 PostgreSQL 9.1 引入的真正可串行化實現，能檢測 Write Skew 等異常。
3. 查詢處理流程
一條 SQL 從接收到執行，經過多個階段：
flowchart TB
subgraph Client
SQL["SQL Query"]
end
subgraph TrafficCop["Traffic Cop (tcop/postgres.c)"]
TC["PostgresMain()"]
end
subgraph Parser["Parser 階段"]
LEX["Lexer<br/>詞法分析"]
SYN["Parser<br/>語法分析"]
PT["Parse Tree"]
end
subgraph Analyzer["Analyzer 階段"]
AN["transformStmt()"]
QT["Query Tree"]
end
subgraph Rewriter["Rewriter 階段"]
RW["QueryRewrite()"]
RWT["Rewritten Query"]
end
subgraph Planner["Planner/Optimizer 階段"]
PL["planner()"]
PATH["Path Selection"]
PLAN["Plan Tree"]
end
subgraph Executor["Executor 階段"]
EX["ExecutorRun()"]
RESULT["Query Result"]
end
SQL --> TC
TC --> LEX
LEX --> SYN
SYN --> PT
PT --> AN
AN --> QT
QT --> RW
RW --> RWT
RWT --> PL
PL --> PATH
PATH --> PLAN
PLAN --> EX
EX --> RESULT3.1 Parser：詞法與語法分析
Parser 使用 Flex (詞法) 和 Bison (語法) 生成：
src/backend/parser/
├── scan.l # Flex 詞法規則
├── gram.y # Bison 語法規則
├── parser.c # 入口
└── analyze.c # 語義分析範例：解析 SELECT 語句
SELECT name, age FROM users WHERE age > 18;解析後生成的 Parse Tree 結構：
typedef struct SelectStmt
{
NodeTag type; // T_SelectStmt
List *distinctClause; // DISTINCT
IntoClause *intoClause; // INTO
List *targetList; // SELECT 列表 [name, age]
List *fromClause; // FROM 子句 [users]
Node *whereClause; // WHERE 條件 [age > 18]
List *groupClause; // GROUP BY
Node *havingClause; // HAVING
List *sortClause; // ORDER BY
Node *limitCount; // LIMIT
Node *limitOffset; // OFFSET
...
} SelectStmt;3.2 Analyzer：語義分析
Analyzer 將 Parse Tree 轉換為 Query Tree，進行：
- 名稱解析：將表名、欄位名解析為 OID
- 類型檢查：確保表達式類型正確
- 權限初步檢查
- 視圖/規則展開準備
// src/backend/parser/analyze.c
Query *
transformStmt(ParseState *pstate, Node *parseTree)
{
switch (nodeTag(parseTree))
{
case T_SelectStmt:
return transformSelectStmt(pstate, (SelectStmt *) parseTree);
case T_InsertStmt:
return transformInsertStmt(pstate, (InsertStmt *) parseTree);
case T_UpdateStmt:
return transformUpdateStmt(pstate, (UpdateStmt *) parseTree);
case T_DeleteStmt:
return transformDeleteStmt(pstate, (DeleteStmt *) parseTree);
...
}
}3.3 Rewriter：規則重寫
Rewriter 處理：
- 視圖展開：將視圖查詢替換為底層表查詢
- 規則應用：應用 CREATE RULE 定義的規則
- 安全性屏障
// src/backend/rewrite/rewriteHandler.c
List *
QueryRewrite(Query *parsetree)
{
List *querylist;
List *results;
// 應用非 SELECT 規則
querylist = RewriteQuery(parsetree, NIL, 0);
// 處理每個重寫後的查詢
foreach(lc, querylist)
{
Query *query = (Query *) lfirst(lc);
results = lappend(results, fireRules(query, ...));
}
return results;
}3.4 Planner/Optimizer：查詢優化
優化器是 PostgreSQL 最複雜的模塊之一，負責生成最優執行計劃。
3.4.1 成本模型
PostgreSQL 使用基於成本的優化 (CBO)：
// 成本計算的核心參數
double seq_page_cost = 1.0; // 順序讀取一頁的成本
double random_page_cost = 4.0; // 隨機讀取一頁的成本
double cpu_tuple_cost = 0.01; // 處理一個 tuple 的成本
double cpu_index_tuple_cost = 0.005;
double cpu_operator_cost = 0.0025;總成本 = 啟動成本 + 運行成本
3.4.2 Path 與 Plan
優化器首先生成所有可能的 Path，然後選擇成本最低的轉換為 Plan：
flowchart TB
subgraph Paths["所有可能的 Path"]
P1["SeqScan Path<br/>cost=1000"]
P2["IndexScan Path<br/>cost=50"]
P3["BitmapScan Path<br/>cost=100"]
end
SELECT["選擇最低成本"]
PLAN["Plan Tree<br/>IndexScan"]
P1 --> SELECT
P2 --> SELECT
P3 --> SELECT
SELECT --> PLAN3.4.3 Join 策略
PostgreSQL 支援三種 Join 算法：
| 算法 | 適用場景 | 特點 |
|---|---|---|
| Nested Loop | 小表驅動大表 | 通用，支援所有 join 條件 |
| Merge Join | 兩表都已排序 | 需要等值條件 |
| Hash Join | 大表 join | 需要等值條件，內存敏感 |
flowchart TB
subgraph NL["Nested Loop"]
NL1["Outer: 掃描 A"]
NL2["Inner: 對每行掃描 B"]
NL1 --> NL2
end
subgraph MJ["Merge Join"]
MJ1["Sort A"]
MJ2["Sort B"]
MJ3["合併掃描"]
MJ1 --> MJ3
MJ2 --> MJ3
end
subgraph HJ["Hash Join"]
HJ1["Build: 構建 B 的 Hash 表"]
HJ2["Probe: 掃描 A，查 Hash"]
HJ1 --> HJ2
end3.4.4 動態規劃 Join 順序
對於多表 join，優化器使用 動態規劃 尋找最優順序：
4 表 Join 的探索過程：
Level 1: {A}, {B}, {C}, {D}
Level 2: {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D}
Level 3: {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}
Level 4: {A,B,C,D}當表數量超過 geqo_threshold（默認 12）時，使用 GEQO（遺傳算法） 進行啟發式搜索。
3.5 Executor：查詢執行
Executor 採用 Volcano 模型（迭代器模型）：
// 每個節點實現三個函數
ExecInitNode() // 初始化
ExecProcNode() // 獲取下一個 tuple（拉取模型）
ExecEndNode() // 清理執行流程：
flowchart TB
subgraph ExecutorModel["Volcano Iterator Model"]
ROOT["Result Node"]
JOIN["Join Node"]
SCAN1["Scan Node (A)"]
SCAN2["Scan Node (B)"]
ROOT -->|"ExecProcNode()"| JOIN
JOIN -->|"ExecProcNode()"| SCAN1
JOIN -->|"ExecProcNode()"| SCAN2
end
subgraph DataFlow["資料流向"]
D1["Tuple from A"] --> D2["Tuple from B"]
D2 --> D3["Joined Tuple"]
D3 --> D4["Result"]
end常見執行節點：
| 節點類型 | 功能 | 源代碼 |
|---|---|---|
| SeqScan | 順序掃描 | nodeSeqscan.c |
| IndexScan | 索引掃描 | nodeIndexscan.c |
| BitmapHeapScan | 位圖堆掃描 | nodeBitmapHeapscan.c |
| NestLoop | 嵌套循環 Join | nodeNestloop.c |
| HashJoin | Hash Join | nodeHashjoin.c |
| MergeJoin | 合併 Join | nodeMergejoin.c |
| Sort | 排序 | nodeSort.c |
| Aggregate | 聚合 | nodeAgg.c |
| Hash | 構建 Hash 表 | nodeHash.c |
4. 存儲引擎
4.1 Page 結構
PostgreSQL 的基本 I/O 單位是 Page（Block），默認 8KB：
┌─────────────────────────────────────────────────────────┐
│ PageHeaderData │
│ (24 bytes) │
├─────────────────────────────────────────────────────────┤
│ ItemIdData Array │
│ (Line Pointers，每個 4 bytes) │
│ [Item 1] [Item 2] [Item 3] ... [Item N] │
├─────────────────────────────────────────────────────────┤
│ │
│ Free Space │
│ │
├─────────────────────────────────────────────────────────┤
│ Tuple Data │
│ (從頁尾向上增長) │
│ [Tuple N] ... [Tuple 3] [Tuple 2] [Tuple 1] │
├─────────────────────────────────────────────────────────┤
│ Special Space │
│ (索引頁使用) │
└─────────────────────────────────────────────────────────┘// src/include/storage/bufpage.h
typedef struct PageHeaderData
{
PageXLogRecPtr pd_lsn; // 最後修改的 WAL LSN
uint16 pd_checksum; // 校驗和
uint16 pd_flags; // 標誌位
LocationIndex pd_lower; // 空閒空間起始
LocationIndex pd_upper; // 空閒空間結束
LocationIndex pd_special; // 特殊區域起始
uint16 pd_pagesize_version;
TransactionId pd_prune_xid; // 可能需要 pruning 的最舊 xid
} PageHeaderData;4.2 Heap 表存儲
PostgreSQL 使用 Heap 結構存儲表資料：
// src/backend/access/heap/heapam.c
// 主要接口函數
heap_beginscan() // 開始掃描
heap_getnext() // 獲取下一個 tuple
heap_fetch() // 通過 TID 獲取 tuple
heap_insert() // 插入 tuple
heap_delete() // 刪除 tuple（設置 t_xmax）
heap_update() // 更新 tuple（刪除舊的 + 插入新的）TID（Tuple Identifier）結構：
typedef struct ItemPointerData
{
BlockIdData ip_blkid; // 區塊號
OffsetNumber ip_posid; // 頁內偏移
} ItemPointerData;
// 例如 (1234, 5) 表示第 1234 頁的第 5 個 item4.3 TOAST：大對象存儲
當 tuple 超過約 2KB 時，PostgreSQL 使用 TOAST (The Oversized-Attribute Storage Technique) 壓縮或外置存儲：
flowchart LR
subgraph MainTable["主表"]
T1["Tuple<br/>含 TOAST 指針"]
end
subgraph TOASTTable["TOAST 表"]
C1["Chunk 1"]
C2["Chunk 2"]
C3["Chunk 3"]
end
T1 --> C1
C1 --> C2
C2 --> C3TOAST 策略：
| 策略 | 說明 |
|---|---|
| PLAIN | 不壓縮，不外置 |
| EXTENDED | 先壓縮，再外置（默認） |
| EXTERNAL | 只外置，不壓縮 |
| MAIN | 先壓縮，儘量不外置 |
5. Buffer Pool 管理
5.1 Buffer Pool 架構
Buffer Pool 是 PostgreSQL 的核心組件，管理所有的共享緩衝區：
flowchart TB
subgraph SharedBuffers["Shared Buffers (shared_buffers)"]
B1["Buffer 1<br/>Page from Table A"]
B2["Buffer 2<br/>Page from Index B"]
B3["Buffer 3<br/>Page from Table A"]
BN["Buffer N<br/>..."]
end
subgraph BufferDesc["Buffer Descriptors"]
D1["Desc 1<br/>tag, state, refcount"]
D2["Desc 2<br/>tag, state, refcount"]
D3["Desc 3<br/>tag, state, refcount"]
end
subgraph HashTable["Buffer Hash Table"]
HT["(RelFileNode, ForkNum, BlockNum)<br/>→ Buffer ID"]
end
HT --> D1
D1 --> B1
D2 --> B2
D3 --> B35.2 Buffer 狀態管理
// src/include/storage/buf_internals.h
typedef struct BufferDesc
{
BufferTag tag; // 標識：哪個表的哪一頁
int buf_id; // Buffer 池中的位置
/* 狀態標誌 */
pg_atomic_uint32 state; // 引用計數 + 標誌位
int wait_backend_pgprocno;
int freeNext; // 空閒列表鏈接
LWLock content_lock; // 內容鎖
} BufferDesc;
// 狀態標誌
#define BM_LOCKED (1U << 22) // 正在修改
#define BM_DIRTY (1U << 23) // 髒頁
#define BM_VALID (1U << 24) // 內容有效
#define BM_TAG_VALID (1U << 25) // tag 有效
#define BM_IO_IN_PROGRESS (1U << 26) // 正在進行 I/O
#define BM_IO_ERROR (1U << 27) // I/O 錯誤5.3 緩衝區替換算法
PostgreSQL 使用 Clock-Sweep 算法（類 LRU）：
flowchart TB
subgraph ClockSweep["Clock-Sweep 算法"]
direction LR
B1["Buffer 1<br/>usage=2"]
B2["Buffer 2<br/>usage=0"]
B3["Buffer 3<br/>usage=1"]
B4["Buffer 4<br/>usage=3"]
B5["Buffer 5<br/>usage=0"]
B1 --> B2 --> B3 --> B4 --> B5 --> B1
end
HAND["時鐘指針"]
HAND -.-> B2
ACTION["找到 usage=0 的 buffer<br/>驅逐並使用"]算法步驟：
- 時鐘指針順序掃描 buffer
- 如果 usage_count > 0，則減 1 並繼續
- 如果 usage_count = 0，則驅逐此 buffer
- 每次訪問 buffer 時，usage_count 增加（最大值限制）
5.4 Buffer I/O 流程
// src/backend/storage/buffer/bufmgr.c
Buffer
ReadBuffer(Relation reln, BlockNumber blockNum)
{
// 1. 查找 buffer hash table
buf_id = BufTableLookup(tag);
if (buf_id >= 0) {
// 2. 命中：增加引用計數
PinBuffer(buf_id);
return buf_id;
}
// 3. 未命中：分配新 buffer
buf_id = StrategyGetBuffer(); // Clock-Sweep
// 4. 如果是髒頁，先寫回
if (BufferIsDirty(buf_id))
FlushBuffer(buf_id);
// 5. 從磁碟讀取
smgrread(reln, blockNum, BufferGetBlock(buf_id));
// 6. 加入 hash table
BufTableInsert(tag, buf_id);
return buf_id;
}6. 索引系統
6.1 索引類型總覽
| 索引類型 | 適用場景 | 特點 |
|---|---|---|
| B-tree | 範圍查詢、等值查詢 | 默認類型，最通用 |
| Hash | 純等值查詢 | 較少使用 |
| GiST | 幾何類型、全文搜索 | 通用搜索樹 |
| GIN | 全文搜索、數組、JSONB | 倒排索引 |
| BRIN | 自然有序的大表 | 塊範圍索引，極小 |
| SP-GiST | 電話號碼、IP 地址 | 空間分區 GiST |
6.2 B-tree 索引
B-tree 是最常用的索引類型：
flowchart TB
subgraph BTree["B-tree 結構"]
ROOT["Root Page<br/>[10, 50, 100]"]
I1["Internal<br/>[1,3,7]"]
I2["Internal<br/>[15,30,45]"]
I3["Internal<br/>[55,70,90]"]
L1["Leaf: 1→TID1"]
L2["Leaf: 3→TID2"]
L3["Leaf: 7→TID3"]
L4["Leaf: 15→TID4"]
L5["Leaf: 30→TID5"]
ROOT --> I1
ROOT --> I2
ROOT --> I3
I1 --> L1
I1 --> L2
I1 --> L3
I2 --> L4
I2 --> L5
end// src/backend/access/nbtree/nbtinsert.c
// B-tree 插入流程
_bt_doinsert()
{
// 1. 從根節點開始查找
stack = _bt_search(rel, key);
// 2. 定位到葉子節點
buf = stack->bts_buf;
// 3. 插入 item
_bt_insertonpg(rel, buf, key, item);
// 4. 如果需要，分裂頁面
if (PageGetFreeSpace(page) < item_size)
_bt_split(rel, buf);
}6.3 GIN 索引（倒排索引）
GIN（Generalized Inverted Index）適用於全文搜索：
flowchart LR
subgraph Documents["文檔"]
D1["Doc1: hello world"]
D2["Doc2: hello postgres"]
D3["Doc3: world database"]
end
subgraph GINIndex["GIN 索引"]
direction TB
E1["hello → [1, 2]"]
E2["world → [1, 3]"]
E3["postgres → [2]"]
E4["database → [3]"]
end
D1 --> E1
D1 --> E2
D2 --> E1
D2 --> E3
D3 --> E2
D3 --> E46.4 BRIN 索引
BRIN（Block Range INdex）存儲資料塊範圍的摘要資訊：
flowchart TB
subgraph Table["表資料（按時間順序插入）"]
B1["Block 1-128<br/>date: 2024-01-01 ~ 2024-01-15"]
B2["Block 129-256<br/>date: 2024-01-16 ~ 2024-01-31"]
B3["Block 257-384<br/>date: 2024-02-01 ~ 2024-02-15"]
end
subgraph BRIN["BRIN 索引（極小）"]
I1["Block 1-128: min=01-01, max=01-15"]
I2["Block 129-256: min=01-16, max=01-31"]
I3["Block 257-384: min=02-01, max=02-15"]
end
B1 -.-> I1
B2 -.-> I2
B3 -.-> I3BRIN 索引非常小，適合：
- 自然有序的資料（時間戳、自增 ID）
- 超大表（TB 級）
- 可接受近似匹配
7. VACUUM 與資料清理
7.1 為什麼需要 VACUUM
由於 MVCC 產生多版本資料，舊版本需要清理：
flowchart LR
subgraph Before["VACUUM 前"]
T1["Tuple v1<br/>(已刪除)"]
T2["Tuple v2<br/>(已更新)"]
T3["Tuple v3<br/>(當前版本)"]
end
VACUUM["VACUUM"]
subgraph After["VACUUM 後"]
T4["Tuple v3<br/>(當前版本)"]
FS["Free Space"]
end
Before --> VACUUM --> After7.2 VACUUM 類型
| 類型 | 操作 | 鎖 |
|---|---|---|
| VACUUM | 標記死 tuple 的空間可重用 | 不阻塞讀寫 |
| VACUUM FULL | 重寫整個表 | 獨占鎖 |
| VACUUM FREEZE | 凍結舊事務 ID | 不阻塞讀寫 |
7.3 Autovacuum
Autovacuum 後台進程自動執行清理：
// 觸發條件
autovacuum_vacuum_threshold = 50 // 最小變更行數
autovacuum_vacuum_scale_factor = 0.2 // 表大小的比例
// 觸發公式
dead_tuples > threshold + scale_factor * table_size8. WAL 與恢復
8.1 Write-Ahead Logging
WAL (Write-Ahead Logging) 保證持久性：
sequenceDiagram
participant Client
participant Backend
participant WALBuffer
participant WALFile
participant DataFile
Client->>Backend: INSERT
Backend->>WALBuffer: 寫 WAL 記錄
Backend->>Backend: 修改 Buffer Pool
Backend->>Client: 成功
Note over WALBuffer,WALFile: COMMIT 時
WALBuffer->>WALFile: fsync WAL
Note over Backend,DataFile: 之後某時刻
Backend->>DataFile: 寫髒頁核心原則：先寫 WAL，再寫資料頁
8.2 WAL 段文件
pg_wal/
├── 000000010000000000000001
├── 000000010000000000000002
├── 000000010000000000000003
...每個 WAL 段默認 16MB，檔名編碼：
- 時間線 ID（8 位）
- LogId（8 位）
- LogSeg（8 位）
8.3 Checkpoint
Checkpoint 是恢復的安全點：
flowchart LR
subgraph Timeline["時間線"]
C1["Checkpoint 1"]
W1["WAL 1"]
W2["WAL 2"]
C2["Checkpoint 2"]
W3["WAL 3"]
CRASH["崩潰"]
end
C1 --> W1 --> W2 --> C2 --> W3 --> CRASH
RECOVERY["恢復：從 Checkpoint 2 開始重放 WAL 3"]
C2 -.-> RECOVERY9. 總結
PostgreSQL 的內部架構體現了優秀的軟體工程實踐：
核心設計決策
| 設計 | 選擇 | 優勢 |
|---|---|---|
| 並發控制 | MVCC + SI/SSI | 高並發，讀寫不阻塞 |
| 存儲 | Heap + TOAST | 簡單高效，大對象友好 |
| 進程模型 | 多進程 | 穩定性高，進程隔離 |
| 優化器 | 基於成本的動態規劃 | 查詢計劃品質高 |
| 索引 | 多種類型 | 適應不同場景 |
學習資源
- PostgreSQL 官方文檔
- The Internals of PostgreSQL by Hironobu SUZUKI
- Bruce Momjian’s Presentations
- PostgreSQL 源代碼