Đã đăng vào khoảng 7 giờ trước 10 phút đọc

PostgreSQL Bài 22: B-Tree Index: Cấu trúc cân bằng và các quy tắc tối ưu multi-column index

B-Tree (chính xác hơn là biến thể $B^+$Tree) là loại chỉ mục mặc định khi bạn thực hiện câu lệnh CREATE INDEX trong PostgreSQL. Đây cũng là loại index được sử dụng trong hơn 90% các bài toán truy vấn hằng ngày.

Dù quen thuộc, nhiều kỹ sư vẫn mắc các lỗi kinh điển: tạo index sai thứ tự cột trong chỉ mục kết hợp (Composite/Multi-column Index), không hiểu tại sao index không kích hoạt khi dùng toán tử phạm vi, hoặc lãng phí tài nguyên RAM vì tạo chỉ mục dư thừa.

Bài học này sẽ mổ xẻ cấu trúc vật lý của cây B-Tree bên trong data page, cách engine duyệt cây, và các nguyên lý vàng khi thiết kế Multi-column Index.

1. Cấu trúc vật lý của B-Tree trong PostgreSQL: Biến thể $B^+$Tree

PostgreSQL sử dụng biến thể của thuật toán Lehman & Yao B-Tree, với những đặc trưng quan trọng:

Toàn bộ con trỏ dữ liệu thực tế (ctid trỏ về Heap Table) chỉ nằm ở các trang lá (Leaf Pages).
Các tầng phía trên (Root Page và Internal Pages) chỉ đóng vai trò làm biển chỉ dẫn định tuyến (Routing).
Các trang lá được nối với nhau bằng danh sách liên kết đôi (Doubly-linked List) thông qua con trỏ Right Link và Left Link, cho phép duyệt dải dữ liệu xuôi/ngược (ORDER BY ASC/DESC) cực nhanh mà không cần leo ngược lại cây.

                         ┌───────────────────────┐
                         │   ROOT PAGE (Meta)    │
                         │   Keys: [20 | 50]     │
                         └───┬────────┬────────┬─┘
            ┌────────────────┘        │        └────────────────┐
            ▼                         ▼                         ▼
┌───────────────────────┐ ┌───────────────────────┐ ┌───────────────────────┐
│ INTERNAL PAGE         │ │ INTERNAL PAGE         │ │ INTERNAL PAGE         │
│ Keys: [5 | 12]        │ │ Keys: [28 | 40]       │ │ Keys: [65 | 80]       │
└───────┬───────────────┘ └───────────────────────┘ └───────────────────────┘
   ┌────┴────────┐
   ▼             ▼
┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ LEAF PAGE 1 │◄┼► LEAF PAGE 2│◄┼► LEAF PAGE 3│◄┼► LEAF PAGE 4│ ... (Doubly Linked)
│ (k:1, ctid) │ │ (k:6, ctid) │ │             │ │             │
│ (k:3, ctid) │ │ (k:8, ctid) │ │             │ │             │
│ (k:4, ctid) │ │ (k:11,ctid) │ │             │ │             │
└─────────────┘ └─────────────┘ └─────────────┘ └─────────────┘
       │
       ▼
 ┌───────────┐
 │ HEAP PAGE │ (Đọc dữ liệu dòng thực tế qua ctid)
 └───────────┘

1.1. Khái niệm High Key trong Page

Mỗi Leaf Page và Internal Page (ngoại trừ trang ngoài cùng bên phải) đều lưu một giá trị đặc biệt gọi là High Key.

High Key là giá trị chặn trên của trang đó.
Nhờ có High Key và con trỏ Right Link, PostgreSQL có thể thực hiện cơ chế Concurrent Read/Write mà không cần khóa toàn bộ cây (khóa chốt phân tầng - Lock Coupling) khi có hiện tượng chẻ trang (Page Split) xảy ra do lệnh INSERT.

2. Giải phẫu B-Tree Page bằng `pageinspect`

Hãy dùng extension pageinspect đã kích hoạt ở Bài 21 để soi trực tiếp cấu trúc cây B-Tree:

SQL

CREATE SCHEMA IF NOT EXISTS index_lab;

CREATE TABLE index_lab.users (
    id INT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    age INT NOT NULL,
    score NUMERIC(5, 2) NOT NULL
);

-- Chèn 10.000 dòng dữ liệu ngẫu nhiên
INSERT INTO index_lab.users (age, score)
SELECT 
    (random() * 60 + 18)::INT,
    (random() * 100)::NUMERIC(5, 2)
FROM generate_series(1, 10000);

-- Tạo B-Tree index trên age
CREATE INDEX idx_users_age ON index_lab.users(age);

Kiểm tra thống kê của Index (Metapage):

SQL

SELECT * FROM bt_metap('index_lab.idx_users_age');

Kết quả tiêu biểu:

Plaintext

 magic  | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples 
--------+---------+------+-------+----------+-----------+-------------+-------------------------
 340322 |       4 |    3 |     1 |        3 |         1 |           0 |                   10000

root = 3: Trang số 3 trong file index là Root Page.
level = 1: Cây có chiều cao (depth) là 1 tầng trung gian trước khi chạm đến tầng lá (tổng cộng 2 tầng). Điều này có nghĩa là để tìm kiếm một giá trị bất kỳ trong 10.000 dòng, engine chỉ mất tối đa 2 lần đọc block (I/O) là tìm thấy ctid!

3. Các toán tử B-Tree hỗ trợ

B-Tree Index chỉ có thể tối ưu cho các kiểu dữ liệu có thứ tự tuyến tính rõ ràng (có thể so sánh lớn hơn/nhỏ hơn).

Các toán tử được hỗ trợ đầy đủ gồm:

So sánh bằng: =
So sánh khoảng: <, <=, >, >=
Kiểm tra rỗng: IS NULL, IS NOT NULL
Khớp mẫu tiền tố: LIKE 'abc%' (với collation phù hợp hoặc text_pattern_ops).

B-Tree hoàn toàn vô dụng với các toán tử không xác định khoảng liên tục như:

LIKE '%abc' (ký tự đại diện ở đầu)
Toán tử chứa mảng/json: @>, ?
So sánh khác: != hoặc <> (trừ trường hợp dùng Partial Index).

4. Multi-column Index (Composite Index): Nguyên tắc thiết kế sống còn

Khi một bảng thường xuyên được truy vấn bằng điều kiện kết hợp nhiều cột (ví dụ: WHERE age = 25 AND score > 80), bạn có hai lựa chọn:

Tạo 2 index đơn lẻ trên age và score (PostgreSQL sẽ dùng BitmapAnd để gộp 2 index).
Tạo 1 Multi-column Index duy nhất: CREATE INDEX idx_users_age_score ON users(age, score).

Multi-column Index hầu như luôn mang lại hiệu năng đọc vượt trội hơn nhiều so với việc gộp nhiều index đơn lẻ. Tuy nhiên, thứ tự khai báo các cột bên trong index quyết định toàn bộ hiệu quả của nó.

4.1. Quy tắc Tiền tố bên trái (Leftmost Prefix Rule)

Khi bạn tạo index trên (col_a, col_b, col_c), cây B-Tree sẽ sắp xếp dữ liệu:

Sắp xếp trước tiên theo col_a.
Nếu col_a có các giá trị bằng nhau, sắp xếp tiếp theo col_b.
Nếu cả col_a và col_b bằng nhau, sắp xếp tiếp theo col_c.

CẤU TRÚC LOGIC CỦA INDEX (age, score):
(age: 20, score: 50.00) ──► ctid (0, 4)
(age: 20, score: 85.50) ──► ctid (0, 1)
(age: 20, score: 92.00) ──► ctid (0, 9)
(age: 21, score: 10.00) ──► ctid (0, 2)
(age: 21, score: 45.00) ──► ctid (0, 7)
(age: 22, score: 70.00) ──► ctid (0, 5)

Hãy quan sát danh sách trên:

Các giá trị age được xếp tăng dần từ 20 đến 22.
Tuy nhiên, nhìn riêng cột score: các số xuất hiện lần lượt là 50, 85, 92, 10, 45, 70 — hoàn toàn lộn xộn!

Hệ quả đối với câu truy vấn:

Câu truy vấn	Kích hoạt Index?	Giải thích chi tiết
`WHERE age = 20 AND score = 85.5`	CÓ (Tối ưu tuyệt đối)	Sử dụng toàn bộ cả 2 nhánh của cây B-Tree.
`WHERE age = 20`	CÓ (Index Scan)	Thỏa mãn tiền tố bên trái (`age`), engine tìm đến nhánh `age = 20`.
`WHERE score = 85.5`	KHÔNG (Seq Scan)	Bỏ qua tiền tố bên trái (`age`). Dữ liệu `score` nằm rải rác lộn xộn trên toàn bộ các trang lá, cây B-Tree không thể định tuyến.
`WHERE age = 20 ORDER BY score`	CÓ (Tránh bước Sort)	Vì trong phạm vi `age = 20`, các dòng `score` đã được sắp xếp sẵn theo thứ tự tăng dần.

4.2. Quy tắc Equality First, Range Second (Đẳng thức trước, Phạm vi sau)

Đây là quy tắc vàng thường bị bỏ quên nhất trong quá trình tối ưu cơ sở dữ liệu:

Quy tắc: Đặt tất cả các cột được lọc bằng dấu bằng (=) lên vị trí đầu tiên trong Multi-column Index; các cột lọc bằng phạm vi (<, >, BETWEEN, LIKE) bắt buộc phải đặt ở phía sau.

Xét bài toán thực tế: Bạn có câu query tìm kiếm đơn hàng:

SQL

SELECT * FROM orders 
WHERE status = 'PAID' AND created_at >= '2026-10-01' AND created_at < '2026-10-08';

Giả sử bạn phân vân giữa 2 cách đánh index:

Cách A (Sai lầm): CREATE INDEX idx_a ON orders(created_at, status);
Cách B (Chuẩn mực): CREATE INDEX idx_b ON orders(status, created_at);

Phân tích Cách A: Index trên (created_at, status)
Engine tìm đến mốc created_at = '2026-10-01'.
Trong suốt toàn bộ khoảng từ 01/10 đến 08/10, giá trị status bị xáo trộn liên tục:
['PAID', 'PENDING', 'CANCELLED', 'PAID', 'PENDING'...]
──► Engine buộc phải quét TẤT CẢ các mục trong khoảng ngày đó rồi lọc bỏ (Filter) status thừa.

Phân tích Cách B: Index trên (status, created_at)
Engine nhảy ngay lập tức đến đúng nhánh status = 'PAID'.
Bên trong nhánh 'PAID', toàn bộ các mốc created_at đã được sắp xếp tăng dần liên tục!
──► Engine chỉ cần quét một dải liên tục hẹp từ 01/10 đến 08/10 rồi dừng lại (Early Stop).

Kết luận: Cách B giảm số lượng leaf page cần đọc xuống gấp nhiều lần so với cách A.

5. Kỹ thuật Index-Only Scan và Mệnh đề `INCLUDE` (Covering Index)

Từ PostgreSQL 11+, tính năng Covering Index thông qua từ khóa INCLUDE cho phép một câu truy vấn đạt tới cảnh giới tối thượng về hiệu năng: Index-Only Scan (hoàn toàn không cần chạm vào bảng Heap).

5.1. Vấn đề của Index thông thường

Giả sử bạn có query:

SQL

SELECT score FROM index_lab.users WHERE age = 30;

Dù có index trên age, PostgreSQL vẫn phải:

Đọc index để lấy ctid.
Dùng ctid nhảy sang đọc Heap Page để lấy giá trị cột score.

Nếu có 5.000 user tuổi 30, engine phải thực hiện hàng ngàn phép đọc ngẫu nhiên (Random I/O) sang Heap Table.

5.2. Giải pháp: Sử dụng mệnh đề `INCLUDE`

SQL

-- Tạo Covering Index: age là Search Key (B-Tree), score là Payload đi kèm ở tầng lá
CREATE INDEX idx_users_age_include_score 
ON index_lab.users(age) 
INCLUDE (score);

CẤU TRÚC LEAF PAGE KHI DÙNG INCLUDE:
┌────────────────────────────────────────────────────────┐
│ LEAF TUPLE:                                            │
│  ├── Search Key: age = 30 (Dùng để định tuyến B-Tree)  │
│  ├── ctid: (0, 15)                                     │
│  └── Payload Data: score = 95.50 (Lưu kèm ở trang lá)  │
└────────────────────────────────────────────────────────┘

Quan sát Execution Plan:

SQL

EXPLAIN (ANALYZE, BUFFERS)
SELECT score FROM index_lab.users WHERE age = 30;

Kế hoạch thực thi:

Plaintext

Index Only Scan using idx_users_age_include_score on users  (cost=0.29..12.50 rows=150 width=6) (actual time=0.025..0.060 rows=150 loops=1)
  Index Cond: (age = 30)
  Heap Fetches: 0
  Buffers: shared hit=3

Index Only Scan: Dữ liệu score được đọc trực tiếp từ trang lá của index trên RAM.
Heap Fetches: 0: Số lần phải nhảy sang đọc bảng Heap là con số không tròn trĩnh! Tốc độ truy vấn tăng từ 5 đến 10 lần.

Phân biệt (age, score) vs (age) INCLUDE (score):

Nếu bạn cần lọc cả WHERE age = 30 AND score > 80: Hãy tạo Multi-column (age, score).

Nếu bạn chỉ lọc WHERE age = 30 nhưng SELECT score: Hãy dùng (age) INCLUDE (score). Cột nằm trong INCLUDE không tham gia vào cấu trúc cân bằng cây, giúp index nhẹ hơn và giảm chi phí duy trì khi ghi dữ liệu.

6. Tính năng B-Tree Deduplication (Từ PostgreSQL 13+)

Trên các cột có độ phân tán thấp (Low Cardinality - ví dụ cột status chỉ có 3-4 giá trị nhưng bảng có 100 triệu dòng), B-Tree Index truyền thống sẽ bị phình to vì phải lưu hàng triệu cặp ('PAID', ctid1), ('PAID', ctid2) lặp lại.

Từ PostgreSQL 13, tính năng B-Tree Deduplication được bật mặc định:

Engine gom toàn bộ các khóa trùng lặp thành một bản ghi duy nhất đi kèm một danh sách mảng các ctid (Posting List).
Kết quả: Giúp tiết kiệm từ 30% đến 60% dung lượng đĩa và RAM cache, đồng thời tăng tốc độ tìm kiếm.

7. Bảng tổng hợp các quy tắc vàng khi thiết kế B-Tree Index

Tuân thủ Leftmost Prefix: Index (A, B, C) chỉ phục vụ tốt cho các truy vấn có (A), (A, B), hoặc (A, B, C). Nó vô dụng nếu câu query chỉ tìm theo (B) hoặc (C).
Quy tắc dấu bằng trước, phạm vi sau: Cột = luôn đứng trước cột <, >, BETWEEN.
Ưu tiên độ chọn lọc (Cardinality/Selectivity): Với các cột cùng dùng dấu =, cột nào có độ phân tán dữ liệu cao hơn (nhiều giá trị khác biệt hơn) thường được ưu tiên đặt trước để thu hẹp tập tìm kiếm sớm nhất.
Tận dụng INCLUDE để đạt Index Only Scan: Đưa các cột chỉ xuất hiện ở mệnh đề SELECT vào INCLUDE thay vì nhồi nhét vào key chính của B-Tree.
Không lạm dụng Index: Mỗi index bổ sung sẽ làm chậm thao tác INSERT, UPDATE, DELETE và làm tăng nguy cơ vô hiệu hóa tính năng HOT Update đã học ở Bài 21.

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

B-Tree trong PostgreSQL là cấu trúc $B^+$Tree tự cân bằng; toàn bộ ctid trỏ về Heap Table nằm tại các trang lá.
Thứ tự cột trong Multi-column Index quyết định khả năng kích hoạt và phạm vi quét của cây.
Kỹ thuật Covering Index với INCLUDE giúp loại bỏ hoàn toàn việc đọc bảng Heap (Heap Fetches: 0).
Từ Postgres 13+, tính năng Deduplication tự động tối ưu các cột có nhiều giá trị trùng lặp.

Bài 23 xem tiếp: Họ Index chuyên biệt: GIN, GiST, BRIN, Hash, SP-GiST – Chọn loại nào cho đúng case? — chúng ta sẽ rời khỏi lãnh địa B-Tree để khám phá bức tranh toàn cảnh về 5 họ index chuyên sâu khác của PostgreSQL: khi nào dùng BRIN cho bảng hàng trăm triệu dòng time-series để tiết kiệm 99% RAM, và sự khác biệt giữa GiST vs SP-GiST.

PostgreSQL