B-tree index trong PostgreSQL hoạt động thế nào Cơ bản

Vấn đề

Một bảng btree_demo có 100.000 dòng: sequence_no integer PRIMARY KEY, passenger_name text. Ba câu query trông na ná nhau:

SELECT sequence_no, passenger_name FROM btree_demo WHERE sequence_no = 42000;
SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE 'passenger-4200%';
SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE '%9999';

Query	Kết quả
sequence_no = 42000	Dùng index, nhanh
LIKE 'passenger-4200%'	Dù passenger_name đã có index, vẫn quét toàn bảng, chậm hơn khoảng 350 lần
LIKE '%9999'	B-tree thông thường không giúp được, kể cả sau khi sửa; phải dùng GIN với pg_trgm, hoặc index trên reverse()

Con số 350 lần so sánh hai query khác nhau, nên chỉ để thấy chênh lệch về plan, không phải benchmark công bằng.

Bài này chạy cả ba trên PostgreSQL 17 thật, xem plan thật, để trả lời chính xác “index giúp được gì và không giúp được gì”.

Khái niệm cốt lõi

CREATE INDEX không kèm USING sẽ tạo B-tree — loại index mặc định và phổ biến nhất. Nó là cây cân bằng nhiều nhánh: mỗi node (một page 8 kB) chứa hàng trăm key và trỏ tới hàng trăm node con, nên cây rất nông. Index trên 100.000 dòng trong demo dưới đây chỉ chiếm:

     relname     | index_pages | index_size
-----------------+-------------+------------
 btree_demo_pkey |         276 | 2208 kB

276 page (mỗi page 8kB) cho 100.000 key — tức trung bình khoảng 362 key mỗi page. Index demo này chỉ có 2 tầng: bt_metap() (extension pageinspect) báo root ở level 1, nghĩa là root trỏ thẳng xuống leaf.

Khi số leaf vượt quá số con trỏ một root chứa được (vài trăm), PostgreSQL thêm tầng internal. Với hệ số phân nhánh này, cây vẫn chỉ 3 tầng dù bảng có hàng triệu dòng. Đây là lý do tìm kiếm trên B-tree gần như không chậm đi khi bảng lớn thêm gấp 10 lần.

Cấu trúc gồm ba loại page:

Loại page	Chứa gì	Vai trò
Root	Key phân cách + con trỏ xuống tầng dưới	Điểm bắt đầu mọi lần tìm kiếm
Internal	Key phân cách + con trỏ	Thu hẹp phạm vi tìm
Leaf	Key thật + TID (block, item) trỏ vào heap	Nơi tìm thấy dòng; các leaf nối với nhau theo thứ tự

Tìm sequence_no = 42000: root → leaf → heap là 3 buffer, rồi đi ngang qua các leaf

Phóng to sơ đồ

Root page → Leaf page42000 ở leaf nào?

◀ Trước▶ PhátTiếp ▶↺ Từ đầuBước 1/4

Buffer 1: so sánh 42000 với các key phân cách ở root, chọn con trỏ xuống đúng leaf. Cây demo chỉ có 2 tầng nên root trỏ thẳng xuống leaf.

Vì leaf nối thành chuỗi, sau khi định vị điểm bắt đầu PostgreSQL đi ngang qua một khoảng giá trị mà không quay lại root. Đó là lý do range scan và ORDER BY rẻ.

Điểm quan trọng nhất, hay bị hiểu sai: B-tree so sánh giá trị bằng toán tử <, <=, =, >=, >. Nó không “tìm chuỗi con” — đó là việc của toán tử LIKE, và không phải mọi cách dùng LIKE đều dịch được thành phép so sánh mà B-tree hiểu.

Cách hoạt động

1. Equality — tìm đúng một dòng

Index Scan using btree_demo_pkey on btree_demo  (cost=0.29..8.31 rows=1 width=19) (actual time=0.004..0.004 rows=1 loops=1)
  Index Cond: (sequence_no = 42000)
  Buffers: local hit=3
Execution Time: 0.008 ms

sequence_no = 42000 dịch thẳng thành một phép so sánh =. PostgreSQL đi từ root xuống leaf theo các key phân cách, chỉ chạm 3 page, mất 0.008 ms.

2. Range + ORDER BY — không cần Sort riêng

SELECT sequence_no FROM btree_demo
WHERE sequence_no BETWEEN 42000 AND 42009
ORDER BY sequence_no;

Index Only Scan using btree_demo_pkey on btree_demo  (cost=0.29..4.47 rows=9 width=4) (actual time=0.007..0.007 rows=10 loops=1)
  Index Cond: ((sequence_no >= 42000) AND (sequence_no <= 42009))
  Heap Fetches: 0
  Buffers: local hit=3

BETWEEN dịch thành >= và <= — vẫn là toán tử B-tree hiểu được. Vì leaf page đã có thứ tự sẵn, PostgreSQL đọc liên tiếp 10 entry mà không cần một bước Sort riêng cho ORDER BY sequence_no.

Heap Fetches: 0 xác nhận query không phải quay lại bảng — vì SELECT sequence_no chỉ cần đúng cột đã nằm trong index. Điều kiện kèm theo: visibility map phải đánh dấu page là all-visible, nghĩa là bảng đã được VACUUM (vacuum và bloat). Bảng vừa ghi nhiều thì Heap Fetches sẽ lớn.

Đổi SELECT sequence_no thành SELECT * với cùng điều kiện đó:

Index Scan using btree_demo_pkey on btree_demo  (cost=0.29..8.47 rows=9 width=19) (actual time=0.003..0.003 rows=10 loops=1)
  Index Cond: ((sequence_no >= 42000) AND (sequence_no <= 42009))
  Buffers: local hit=3

Tên node đổi từ Index Only Scan thành Index Scan — vì passenger_name không có trong index, PostgreSQL phải quay lại heap lấy nó. Buffers vẫn là 3 vì dữ liệu đang nằm trong cache; trên bảng lớn hơn nhiều, bước quay lại heap này là chỗ tốn I/O thật.

3. LIKE dạng prefix — có index vẫn Seq Scan, vì sao?

Thêm index trên passenger_name rồi chạy:

SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE 'passenger-4200%';

Seq Scan on btree_demo  (cost=0.00..1887.00 rows=10 width=4) (actual time=0.127..2.797 rows=11 loops=1)
  Filter: (passenger_name ~~ 'passenger-4200%'::text)
  Rows Removed by Filter: 99989
  Buffers: local hit=637
Execution Time: 2.799 ms

Có index mà vẫn Seq Scan, đọc 637 page, loại 99.989 dòng để lấy 11 dòng. Nguyên nhân không phải PostgreSQL “quên” dùng index — mà là collation của database:

 datcollate
------------
 en_US.utf8

Với locale khác C, PostgreSQL không thể chắc chắn thứ tự sắp xếp theo locale đó trùng với thứ tự byte cần thiết để dùng B-tree cho so sánh prefix. Đây không phải chuyện hiếm — hầu hết database production không dùng locale C.

Cách sửa: tạo index với operator class text_pattern_ops, so sánh theo byte thay vì theo locale:

CREATE INDEX btree_demo_name_pattern_idx ON btree_demo (passenger_name text_pattern_ops);

Chạy lại đúng câu query trên:

Index Scan using btree_demo_name_pattern_idx on btree_demo  (cost=0.42..8.44 rows=10 width=4) (actual time=0.030..0.034 rows=11 loops=1)
  Index Cond: ((passenger_name ~>=~ 'passenger-4200'::text) AND (passenger_name ~<~ 'passenger-4201'::text))
  Filter: (passenger_name ~~ 'passenger-4200%'::text)
  Buffers: local hit=2 read=3
Execution Time: 0.048 ms

2.799 ms → 0.048 ms: nhanh hơn khoảng 58 lần, 637 buffers → 5 buffers. PostgreSQL dịch LIKE 'passenger-4200%' thành khoảng so sánh byte >= 'passenger-4200' AND < 'passenger-4201' — một dải mà B-tree với text_pattern_ops hiểu và định vị trực tiếp được.

Cùng câu LIKE 'passenger-4200%'	Plan	Thời gian	Buffers
Index mặc định (en_US.utf8)	Seq Scan	2.799 ms	637
text_pattern_ops	Index Scan	0.048 ms	5

Index text_pattern_ops có một cái giá: nó so sánh theo byte nên không phục vụ <, > hay ORDER BY theo thứ tự locale. Cần cả hai kiểu truy vấn thì giữ hai index, hoặc tạo một index với COLLATE "C". Với cột varchar, dùng varchar_pattern_ops.

4. LIKE bắt đầu bằng % — B-tree thường không cứu được

SELECT sequence_no FROM btree_demo WHERE passenger_name LIKE '%9999';

Seq Scan on btree_demo  (cost=0.00..1887.00 rows=10 width=4) (actual time=0.322..3.313 rows=10 loops=1)
  Filter: (passenger_name ~~ '%9999'::text)
  Rows Removed by Filter: 99990
  Buffers: local hit=637

Kể cả với text_pattern_ops đã tạo ở bước trước, câu này vẫn Seq Scan. Lý do khác hẳn: %9999 không có phần đầu cố định để dịch thành một khoảng so sánh — giá trị khớp có thể bắt đầu bằng bất kỳ ký tự nào.

B-tree định vị bằng cách so sánh có thứ tự; một điều kiện “kết thúc bằng X” không thu hẹp được vị trí bắt đầu trong cây. Một B-tree trực tiếp trên cột không giải quyết được việc này. Có hai hướng:

• GIN với pg_trgm: hỗ trợ cả LIKE '%x%'.
• Expression index trên reverse() (riêng cho điều kiện “kết thúc bằng”): tạo index (reverse(passenger_name) text_pattern_ops) rồi viết lại query thành WHERE reverse(passenger_name) LIKE reverse('%9999') (tức '9999%' trên chuỗi đảo ngược). Khi đó B-tree lại dùng được.

Bảng tra: toán tử nào dùng được B-tree?

Điều kiện	Dùng B-tree thường?	Ghi chú
col = x, col IN (...)	Có
col < x, >, BETWEEN, ORDER BY col	Có	Giữ thứ tự, không cần Sort
col IS NULL	Có	B-tree có lưu NULL
col LIKE 'abc%', locale C	Có	Tự dịch thành khoảng so sánh
col LIKE 'abc%', locale en_US	Không	Cần text_pattern_ops hoặc COLLATE "C"
col LIKE '%abc'	Không	Dùng reverse(col) expression index hoặc GIN pg_trgm
col LIKE '%abc%', ILIKE	Không	GIN/GiST với pg_trgm
lower(col) = x	Chỉ khi có index trên lower(col)	Expression index
col <> x	Gần như không	Hầu hết dòng đều khớp

Index nhiều cột: PostgreSQL 18 thêm skip scan cho B-tree nhiều cột, nên mất cột đầu không còn luôn là thảm hoạ; chi tiết ở thứ tự cột composite index.

Ví dụ thực tế

Ví dụ thực tế

Một bảng orders có cột tracking_code text (dạng "TRK-2026-004821"), và ứng dụng cho phép tìm theo mã đầy đủ hoặc theo tiền tố ("TRK-2026-").

Nếu database không chạy locale C, CREATE INDEX ON orders (tracking_code) mặc định sẽ không tăng tốc tìm kiếm prefix — y hệt tình huống ở trên.

Phải tạo thêm CREATE INDEX ON orders (tracking_code text_pattern_ops) nếu tìm kiếm prefix là truy vấn thường xuyên. Kiểm tra datcollate của database trước khi giả định index thường sẽ tự động phục vụ LIKE 'x%'.

Trade-offs

Ưu điểm

• Cây nông (2-3 tầng cho hàng triệu dòng nhờ hệ số phân nhánh cao) nên tốc độ tìm kiếm gần như không đổi khi bảng lớn thêm
• Hỗ trợ cả equality, range, và giữ được thứ tự cho ORDER BY/LIMIT mà không cần Sort riêng
• text_pattern_ops mở rộng B-tree sang tìm kiếm prefix hiệu quả, không cần đổi sang loại index khác

Nhược điểm

• Chỉ hỗ trợ toán tử so sánh có thứ tự; không giúp được LIKE '%x', full-text search, hay tìm theo tập hợp
• Locale khác C (phổ biến trong production) âm thầm vô hiệu hoá index thường cho tìm kiếm prefix — dễ bị bỏ sót vì EXPLAIN không cảnh báo, chỉ đơn giản chọn Seq Scan
• Mỗi index thêm (kể cả text_pattern_ops song song với index thường) tốn thêm dung lượng và làm ghi chậm hơn

Sai lầm thường gặp

Sai lầm thường gặp

Thấy Seq Scan trong EXPLAIN và kết luận “index bị hỏng” hoặc “PostgreSQL không dùng index”. Trong ví dụ trên, index vẫn tồn tại và hợp lệ — chỉ là toán tử LIKE với locale mặc định không dịch được thành phép so sánh B-tree hiểu.

Trước khi nghi ngờ index, kiểm tra:

1. Toán tử trong WHERE có phải loại B-tree hỗ trợ không.
2. Nếu là LIKE, database có chạy locale C hoặc index có text_pattern_ops không.
3. Planner có ước lượng ít dòng đủ để việc dùng index rẻ hơn scan toàn bảng không.

🎮 Thử tay

• Chọn loại index: khi nào B-tree, khi nào loại khác, khi nào không cần index.

Checklist khi thiết kế B-tree index

1. Đối chiếu điều kiện WHERE với bảng tra ở trên: B-tree chỉ dịch được <, <=, =, >=, > (gồm BETWEEN, IN, IS NULL).
2. Có tìm kiếm LIKE 'prefix%': kiểm tra datcollate; nếu khác C, tạo index với text_pattern_ops (varchar_pattern_ops cho varchar) hoặc COLLATE "C".
3. Cần cả prefix search lẫn ORDER BY/so sánh theo locale: giữ hai index, vì text_pattern_ops không phục vụ thứ tự locale.
4. Có LIKE '%suffix' hoặc '%x%': đừng thêm B-tree thường; dùng GIN pg_trgm hoặc expression index trên reverse().
5. Muốn Index Only Scan: chỉ SELECT cột có trong index và để VACUUM giữ visibility map, nếu không Heap Fetches sẽ lớn.
6. Mỗi index thêm tốn dung lượng và làm ghi chậm hơn; chỉ thêm cho truy vấn thường xuyên.

Tóm tắt

Tóm tắt

• B-tree là cây cân bằng nhiều nhánh: 100.000 dòng chỉ cần 276 page, cây cao 2-3 tầng
• Chỉ dịch được các điều kiện dùng <, <=, =, >=, > — bao gồm BETWEEN và LIKE 'prefix%' khi điều kiện locale đúng
• SELECT chỉ cột có trong index → Index Only Scan (Heap Fetches: 0); thêm cột khác → phải quay lại heap
• Với locale khác C (mặc định ở hầu hết production), LIKE 'prefix%' cần index tạo với text_pattern_ops mới dùng được — nếu không sẽ âm thầm rơi về Seq Scan
• LIKE '%suffix' không B-tree nào giúp được, vì không có điểm bắt đầu cố định để so sánh có thứ tự

Tham khảo

• PostgreSQL 17 — Index Types
• PostgreSQL 17 — B-Tree Indexes
• PostgreSQL 17 — Operator Classes
• PostgreSQL 17 — Index-Only Scans and Covering Indexes