Đã đăng vào Thứ Hai, 11:26 CH 10 phút đọc

PostgreSQL Bài 23: Họ Index chuyên biệt: GIN, GiST, BRIN, Hash, SP-GiST – Chọn loại nào cho đúng case?

Ở Bài 22, chúng ta đã nắm trọn vẹn cách B-Tree tối ưu hóa cho dữ liệu vô hướng 1 chiều có thứ tự (=, <, >). Tuy nhiên, thế giới dữ liệu thực tế không chỉ dừng lại ở số nguyên hay chuỗi phẳng.

Khi bạn làm việc với mảng nhiều phần tử, tài liệu bán cấu trúc JSONB, tọa độ không gian 2D/3D (PostGIS), khoảng thời gian liên tục (tstzrange), hoặc các bảng Time-series/Log lên tới hàng trăm triệu bản ghi, B-Tree sẽ nhanh chóng bộc lộ giới hạn: hoặc không thể hỗ trợ toán tử, hoặc kích thước index phình to nuốt trọn bộ nhớ RAM.

PostgreSQL vượt trội hơn các RDBMS khác nhờ cung cấp một hệ sinh thái Index đa dạng. Bài học này sẽ mổ xẻ cơ chế, điểm mạnh/yếu và cách chọn đúng loại index giữa 5 họ chuyên biệt: GIN, GiST, BRIN, Hash, và SP-GiST.

1. Bản đồ tổng quan các họ Index trong PostgreSQL

                    HỆ SINH THÁI INDEX TRONG POSTGRESQL
                                     │
    ┌────────────────┬───────────────┼───────────────┬────────────────┐
    ▼                ▼               ▼               ▼                ▼
  B-Tree           GIN             GiST            BRIN          SP-GiST / Hash
(Scalar 1D)   (Tập hợp/Đảo)   (Không gian/Cây) (Khối cực lớn) (Phân vùng/Băm)

Loại Index	Cấu trúc dữ liệu cốt lõi	Toán tử đặc trưng	Dung lượng so với B-Tree	Ứng dụng thực tế kinh điển
B-Tree	Cây $B^+$Tree cân bằng	`=`, `<`, `>`, `BETWEEN`, `LIKE 'abc%'`	Tiêu chuẩn ( $1\times$ )	Khóa chính, Khóa ngoại, số liệu, chuỗi có thứ tự.
GIN	Inverted Index (Chỉ mục đảo)	`@>`, `?`, `?&`, `@@`, `&&`	Lớn ( $1.5\times - 3\times$ )	JSONB, Mảng (ARRAY), Full-Text Search, `pg_trgm`.
GiST	Generalized Search Tree (Cây R-Tree/B-Tree lồng)	`&&`, `<<`, `>>`, `<->`, `ST_DWithin`	Trung bình ( $1\times - 1.5\times$ )	Tọa độ địa lý (PostGIS), Khoảng giá trị (Range Types), k-NN.
BRIN	Block Range Index (Min/Max summary)	`=`, `<`, `>`, `BETWEEN`	Siêu nhỏ (0.1% - 1%)	Bảng IoT, Logs, Time-series nạp theo thời gian tăng dần.
SP-GiST	Space-Partitioned GiST (Quadtree, Trie)	`<<`, `>>`, `&&`, `@>`, `^@`	Trung bình	Tọa độ điểm phân bố không đều, chuỗi tiền tố (Trie), mạng IP.
Hash	Bảng băm 32-bit (Hỗ trợ WAL)	Chỉ duy nhất dấu bằng (`=`)	Nhỏ hơn B-Tree cho chuỗi dài	Chuỗi văn bản/UUID dài chỉ tìm kiếm chính xác tuyệt đối.

2. GIN (Generalized Inverted Index): Bậc thầy dữ liệu tập hợp

Như đã tìm hiểu ở các bài JSONB và FTS, GIN là một chỉ mục đảo. Thay vì lưu trữ cả hàng dữ liệu vào cây, GIN bóc tách từng phần tử con (elements / keys / lexemes) ra và trỏ ngược lại danh sách các dòng chứa phần tử đó (Posting List hoặc Posting Tree).

Dữ liệu gốc:
Row 1: tags = ['go', 'docker']
Row 2: tags = ['postgres', 'docker']
Row 3: tags = ['go', 'postgres', 'k8s']

Cấu trúc GIN Index (Inverted):
'docker'   ──► [Row 1, Row 2]
'go'       ──► [Row 1, Row 3]
'k8s'      ──► [Row 3]
'postgres' ──► [Row 2, Row 3]

2.1. Điểm mạnh và Điểm yếu

Điểm mạnh: Tốc độ tìm kiếm các bài toán tập hợp (@> - chứa, && - giao nhau) cực nhanh vì engine chỉ cần thực hiện phép hợp (Union) hoặc giao (Intersection) giữa các danh sách posting.
Điểm yếu: Chi phí ghi (INSERT/UPDATE) đắt đỏ nhất trong các loại index. Khi bạn chèn 1 dòng có 20 tags, GIN phải cập nhật 20 vị trí khác nhau trong cây index.
Cơ chế giảm tải (Fastupdate): Mặc định GIN có bộ nhớ đệm fastupdate = on. Dữ liệu mới ghi được gom vào một danh sách tạm thời (Pending List) rồi mới xả (flush) vào cấu trúc chính sau đó, giúp tăng tốc độ ghi bù lại chi phí dọn dẹp.

3. GiST (Generalized Search Tree): Không gian đa chiều và Khoảng giá trị

Trong khi B-Tree chỉ chia đôi tập dữ liệu theo 1 chiều tuyến tính, GiST là một khung sườn (framework) cây tìm kiếm cho phép lập chỉ mục cho các cấu trúc dữ liệu hình học, phân cấp hoặc chồng lấn.

Biến thể nổi tiếng nhất của GiST là R-Tree (Bounding Box Tree) dùng trong hệ thống thông tin địa lý (GIS).

CƠ CHẾ HỘP BAO (BOUNDING BOX) CỦA GIST:
┌──────────────────────────────────────────────┐
│ ROOT BOX (Bao trùm toàn bộ bản đồ)          │
│ ┌──────────────────────┐ ┌─────────────────┐ │
│ │ Node Box A (Quận 1)  │ │ Node Box B      │ │
│ │  ┌────┐   ┌────┐     │ │ (Quận 3)        │ │
│ │  │Point│  │Point│    │ │                 │ │
│ │  └────┘   └────┘     │ │                 │ │
│ └──────────────────────┘ └─────────────────┘ │
└──────────────────────────────────────────────┘

3.1. Các kịch bản bắt buộc phải dùng GiST:

Dữ liệu không gian địa lý (PostGIS): Tìm các điểm nằm trong bán kính $X$ mét (ST_DWithin), kiểm tra xem một đường thẳng có cắt một đa giác hay không (ST_Intersects).
Khoảng giá trị (Range Types): Như ở Bài 12, kiểm tra chồng chéo lịch trình (&&) và tạo ràng buộc loại trừ (EXCLUDE USING GIST).
Tìm kiếm hàng xóm gần nhất (k-Nearest Neighbors - k-NN): GiST hỗ trợ toán tử đo khoảng cách <-> trực tiếp trên cây index để lấy ra Top-N kết quả gần nhất trong nháy mắt.

4. BRIN (Block Range Index): Vũ khí tối thượng cho Big Data & Time-Series

Hãy tưởng tượng bạn có bảng sensor_readings hoặc audit_logs chứa 500 triệu dòng, dung lượng đĩa 100 GB.

Nếu tạo một B-Tree Index trên cột created_at, kích thước file index có thể ngốn tới 10 GB – 15 GB RAM! Khi index vượt quá RAM, server sẽ bị cạn kiệt bộ nhớ đệm và I/O đĩa tăng vọt.

BRIN ra đời để giải quyết chính xác bài toán này.

4.1. Nguyên lý hoạt động của BRIN

BRIN không lưu giá trị của từng dòng riêng lẻ. Thay vào đó, nó gom các Data Page liền kề nhau thành một dải (Block Range - mặc định là 128 trang, tương đương $128 \times 8\text{ KB} = 1\text{ MB}$ dữ liệu).

Với mỗi dải 128 trang đó, BRIN chỉ lưu đúng 2 giá trị: Giá trị nhỏ nhất (MIN) và Giá trị lớn nhất (MAX).

BRIN INDEX (Chỉ lưu tóm tắt Min/Max cho từng cụm block):
┌────────────────────────┬─────────────────────┬─────────────────────┐
│ Dải Block (Pages)      │ MIN created_at      │ MAX created_at      │
├────────────────────────┼─────────────────────┼─────────────────────┤
│ Range 1: Block 0 - 127 │ 2026-10-01 00:00:00 │ 2026-10-01 04:15:20 │
│ Range 2: Block 128-255 │ 2026-10-01 04:15:21 │ 2026-10-01 08:30:00 │
│ Range 3: Block 256-383 │ 2026-10-01 08:30:01 │ 2026-10-01 12:45:00 │
└────────────────────────┴─────────────────────┴─────────────────────┘

Khi chạy: WHERE created_at = '2026-10-01 06:00:00'
──► Engine nhìn vào BRIN: 06:00:00 chỉ có thể nằm ở Range 2 (Block 128-255).
──► Bỏ qua hoàn toàn Range 1 và Range 3! Chỉ đọc đúng 128 trang của Range 2.

4.2. Thử nghiệm so sánh thực tế: B-Tree vs BRIN

Tạo bảng log 1 triệu dòng được nạp theo thứ tự thời gian tăng dần:

SQL

CREATE SCHEMA IF NOT EXISTS brin_lab;

CREATE TABLE brin_lab.system_logs (
    id BIGINT GENERATED ALWAYS AS IDENTITY,
    created_at TIMESTAMPTZ NOT NULL,
    message TEXT
);

-- Chèn 1 triệu dòng có thời gian tăng dần liên tục:
INSERT INTO brin_lab.system_logs (created_at, message)
SELECT 
    '2026-01-01 00:00:00Z'::timestamptz + (i * interval '2 seconds'),
    'Log message content number ' || i
FROM generate_series(1, 1000000) AS i;

-- Tạo 1 B-Tree Index và 1 BRIN Index để so sánh:
CREATE INDEX idx_logs_btree ON brin_lab.system_logs USING BTREE (created_at);
CREATE INDEX idx_logs_brin  ON brin_lab.system_logs USING BRIN  (created_at);

Kiểm tra kích thước của hai index:

SQL

SELECT 
    pg_size_pretty(pg_relation_size('brin_lab.idx_logs_btree')) AS btree_size,
    pg_size_pretty(pg_relation_size('brin_lab.idx_logs_brin'))  AS brin_size;

Kết quả kinh ngạc:

Plaintext

 btree_size | brin_size 
------------+-----------
 21 MB      | 48 kB

B-Tree tốn 21 MB.
BRIN chỉ tốn đúng 48 KB (nhỏ hơn gần 450 lần!).
Với bảng 500 triệu dòng, B-Tree tốn 11 GB thì BRIN chỉ tốn khoảng 25 MB — hoàn toàn nằm gọn trong L3 Cache của CPU!

Điều kiện tiên quyết để dùng BRIN: Dữ liệu vật lý lưu trên đĩa bắt buộc phải có sự tương quan mạnh mẽ với thứ tự thời gian (Physical Correlation). Tức là các dòng ghi vào sau phải có giá trị ngày/ID lớn hơn các dòng ghi trước. Nếu dữ liệu bị xáo trộn lung tung, Min/Max của các block sẽ bị chồng chéo hoàn toàn, khiến BRIN mất tác dụng và quay về quét toàn bộ bảng.

Bạn có thể kiểm tra độ tương quan bằng query:

SQL
SELECT correlation FROM pg_stats 
WHERE tablename = 'system_logs' AND attname = 'created_at';
-- Nếu correlation xấp xỉ 1.0 (hoặc -1.0) ──► DÙNG BRIN NGAY!

5. SP-GiST (Space-Partitioned GiST): Phân vùng không gian không cân bằng

GiST là một cây cân bằng (tương tự B-Tree). Nhưng có những dạng dữ liệu không gian phân bổ cực kỳ méo mó (ví dụ: 90% dân số sống tập trung tại các thành phố lớn, nông thôn rất thưa thớt). Nếu ép một cây cân bằng vào dữ liệu này, các nhánh sẽ bị phình to bất thường.

SP-GiST cho phép phân chia không gian thành các vùng kích thước không đều nhau (dùng các thuật toán kinh điển như Quadtree, k-d Tree, hoặc Radix Trie):

Ứng dụng thực tế của SP-GiST:

Tìm kiếm địa chỉ IP và dải mạng (INET/CIDR): Cực kỳ tối ưu nhờ thuật toán cây tiền tố (Radix Tree).
Chuỗi văn bản có chung tiền tố: Tìm kiếm chuỗi tiền tố (LIKE 'prefix%' hoặc toán tử ^@ - cluster URL, danh bạ điện thoại).
Tọa độ điểm 2D phân bố bất đối xứng.

6. Hash Index: Sự trở lại từ PostgreSQL 10

Trước phiên bản PostgreSQL 10, Hash Index bị xem như "phế tích" vì không hỗ trợ ghi WAL (nếu database crash hoặc dùng trên Replica Streaming thì dữ liệu Hash Index bị hỏng hoàn toàn).

Từ PostgreSQL 10 trở đi, Hash Index đã được viết lại hoàn toàn: hỗ trợ ghi WAL đầy đủ, an toàn tuyệt đối khi crash recovery và tương thích hoàn toàn với bản sao Replication.

6.1. Đặc trưng của Hash Index

Sử dụng hàm băm 32-bit ánh xạ giá trị vào các bucket.
Chỉ hỗ trợ DUY NHẤT một toán tử: Dấu bằng (=).
Không hỗ trợ so sánh khoảng (<, >), không hỗ trợ sắp xếp (ORDER BY).

6.2. Khi nào nên dùng Hash Index thay vì B-Tree?

Khi bạn cần đánh index trên một cột có chuỗi ký tự rất dài (ví dụ: URL dài 200 ký tự, chuỗi Token băm SHA-256 / UUID, hoặc Token JWT) và câu truy vấn chỉ luôn luôn tìm chính xác tuyệt đối (WHERE token = '...'):

B-Tree phải lưu toàn bộ chuỗi ký tự dài đó vào từng node của cây, làm index phình to.
Hash Index chỉ lưu giá trị băm 4-byte của chuỗi đó vào bucket, giúp kích thước index nhỏ hơn B-Tree đáng kể và thao tác so sánh số băm diễn ra trong $O(1)$ .

7. Cây quyết định: Chọn loại Index nào cho đúng bài toán?

Dưới đây là sơ đồ tư duy thực chiến giúp bạn chọn đúng loại index chỉ trong 5 giây:

BẠN CẦN ĐÁNH INDEX TRÊN CỘT NÀO?
 │
 ├── Dữ liệu là JSONB, Mảng (Array), hoặc Full-Text Search?
 │     └──► CHỌN GIN (Nếu JSONB chỉ query @> chọn GIN jsonb_path_ops)
 │
 ├── Dữ liệu là Tọa độ GIS (PostGIS), hoặc Khoảng thời gian (Range Types)?
 │     └──► CHỌN GiST
 │
 ├── Dữ liệu là Bảng Log/IoT/Time-series khổng lồ (Ghi liên tục, correlation ~ 1)?
 │     └──► CHỌN BRIN (Tiết kiệm 99% RAM)
 │
 ├── Dữ liệu là Dải mạng IP (INET/CIDR) hoặc Chuỗi tìm tiền tố Trie?
 │     └──► CHỌN SP-GiST
 │
 ├── Cột chuỗi rất dài (URL, Hash Token) và CHỈ query dấu bằng (=)?
 │     └──► CHỌN HASH
 │
 └── Tất cả các trường hợp vô hướng còn lại (ID, Số, Ngày tháng, Enum, Text thông thường)?
       └──► MẶC ĐỊNH CHỌN B-TREE

8. Tóm tắt & Bài tiếp theo

Đừng chỉ biết mỗi B-Tree; việc chọn sai loại index có thể làm hệ thống chậm đi hàng trăm lần hoặc lãng phí hàng chục Gigabytes RAM vô ích.
GIN là vua của dữ liệu tập hợp (JSONB, ARRAY, FTS), nhưng chi phí ghi nặng.
GiST chuyên trị hình học không gian đa chiều, bài toán loại trừ đặt phòng và k-NN search.
BRIN là "vũ khí bí mật" cho dữ liệu lớn (Big Data/Time-Series), nén dung lượng index xuống mức tối thiểu nhờ cơ chế Min/Max theo dải block.
Hash Index (từ Postgres 10+) là giải pháp thay thế hoàn hảo cho B-Tree trên các chuỗi dài chỉ tìm kiếm chính xác.

Bài 24 xem tiếp: Kỹ thuật Partial Index và Expression-based Index: Tối ưu dung lượng và tốc độ — chúng ta sẽ tìm hiểu cách đánh index có chọn lọc chỉ trên 5% dữ liệu quan trọng của bảng (WHERE status = 'FAILED') để thu nhỏ kích thước index, và cách đánh index trên các hàm tính toán (LOWER(email), DATE(created_at)).

PostgreSQL