B-Tree Index — General Purpose Index

B-Tree là index mặc định của Postgres — và vì sao "index mọi cột" lại giết write throughput

CREATE INDEX không nói rõ loại gì thì Postgres dựng B-Tree. Đây là cấu trúc cân bằng (balanced tree) phù hợp với gần như mọi workload OLTP: tra cứu equality, range, sắp xếp, IS NULL, prefix LIKE 'abc%'. Lý do nó là mặc định không phải vì "tốt nhất cho mọi thứ" mà vì nó đủ tốt cho phần lớn truy vấn và kế thừa thứ tự — cùng một cấu trúc dùng để tìm bản ghi cũng dùng để duyệt theo ORDER BY. Hiểu B-Tree quyết định trực tiếp việc một index có được dùng hay không, và vì sao việc "thấy chậm là đánh index" thường làm write throughput sụt và bảng phình lên gấp đôi.

Cơ chế hoạt động

Postgres B-Tree hiện thực biến thể B-link tree của Lehman & Yao (theo Postgres docs chương "B-Tree Implementation"), thêm sửa đổi để hỗ trợ unique và xoá an toàn. Cây có ba loại trang: root, internal, leaf. Mỗi trang là một block 8KB (mặc định). Internal page chứa các key phân tách + downlink xuống trang con. Leaf page chứa key + TID ((block_no, item_offset)) trỏ vào heap tuple thật. Vì leaf được nối ngang bằng sibling pointer, một range scan đi xuống một lần rồi quét ngang dọc theo các leaf liền nhau — đây là lý do ORDER BY trên cột đã index không tốn thêm sort.

CREATE TABLE orders (
  id          bigserial PRIMARY KEY,
  customer_id bigint    NOT NULL,
  status      text      NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  total_cents bigint    NOT NULL
);

-- Index cho filter + sort phổ biến: liệt kê order của một customer theo thời gian
CREATE INDEX orders_customer_created_idx
  ON orders (customer_id, created_at DESC);

-- Covering index: nhét total_cents vào INCLUDE để chạy index-only scan
CREATE INDEX orders_customer_created_total_idx
  ON orders (customer_id, created_at DESC) INCLUDE (total_cents);

(customer_id, created_at DESC) là multicolumn index. Quy tắc leftmost prefix: index chỉ dùng được khi predicate gồm cột đầu (customer_id), với hoặc không kèm cột sau. Query WHERE created_at > now() - interval '1 day' mà không lọc theo customer_id sẽ không dùng index này.

Vài tính chất khác từ docs cần nhớ:

• B-Tree không index NULL cho mục đích equality, nhưng có index entry cho IS NULL (mặc định Postgres treat NULL là phân biệt).
• LIKE 'abc%' chỉ dùng được B-Tree khi collation là C hoặc khi tạo index với text_pattern_ops opclass.
• Từ Postgres 13, B-Tree có deduplication: khi nhiều row chia sẻ cùng key, leaf gộp thành một posting list, giảm kích thước index đáng kể với cột low-cardinality.
• INCLUDE (Postgres 11+) thêm payload column vào leaf nhưng không tham gia khoá — phục vụ index-only scan, không phải lookup.
• Index-only scan còn yêu cầu visibility map của heap page đó "all-visible"; nếu trang vừa update, vẫn phải đi heap để check visibility (MVCC).

Vấn đề gặp trong production

Failure mode 1: index mọi cột → write amplification. Mỗi index là một cấu trúc song song trên đĩa. Mỗi INSERT phải chèn vào tất cả index của bảng. Mỗi UPDATE mà động vào cột có index sẽ phá vỡ HOT (Heap-Only Tuple) update — Postgres không thể chỉ ghi tuple mới trong cùng page, nó phải tạo entry mới ở mọi index. Một bảng "đánh index mọi cột để chắc" có thể chậm gấp nhiều lần khi ghi và phình storage ra cùng tỉ lệ.

-- Sai: đánh index cho mọi cột "phòng khi cần"
CREATE INDEX ON orders (status);
CREATE INDEX ON orders (total_cents);
CREATE INDEX ON orders (created_at);
CREATE INDEX ON orders (customer_id);
CREATE INDEX ON orders (updated_at); -- cột này UPDATE liên tục → giết HOT

updated_at được sửa trên gần như mọi update; index trên nó nghĩa là không bao giờ có HOT update, bảng bloat nhanh, vacuum đuổi không kịp. Cách sửa: chỉ đánh index cho cột thật sự xuất hiện trong predicate hoặc ORDER BY của query có tần suất cao, và cân nhắc xem cột đó có bị update không.

-- Đúng: nhìn workload trước, chỉ giữ index phục vụ query thật
-- Giả sử query nóng là "đơn của customer X gần đây nhất":
CREATE INDEX orders_customer_created_idx
  ON orders (customer_id, created_at DESC);

-- Status thường chỉ có vài giá trị → partial index thay vì index cả cột
CREATE INDEX orders_pending_idx
  ON orders (created_at)
  WHERE status = 'pending';

Failure mode 2: sai thứ tự cột trong multicolumn index. Người ta hay đánh (created_at, customer_id) rồi ngạc nhiên khi query WHERE customer_id = ? không dùng index. Quy tắc: cột có equality đi trước, cột có range đi sau. (customer_id, created_at) chạy được cho WHERE customer_id = ? AND created_at > ?; đảo lại thì không.

Failure mode 3: LIKE với collation không phải C. Trên một database mặc định en_US.UTF-8, một B-Tree thường trên cột text không phục vụ được WHERE email LIKE 'foo%'. Triệu chứng: EXPLAIN cho Seq Scan dù có index. Sửa bằng opclass chuyên dụng:

-- Sai: index thường, LIKE prefix không dùng được khi collation != C
CREATE INDEX users_email_idx ON users (email);

-- Đúng: text_pattern_ops cho phép B-Tree phục vụ LIKE 'prefix%'
CREATE INDEX users_email_pattern_idx ON users (email text_pattern_ops);

Failure mode 4: index bloat. B-Tree không tự co lại sau khi xoá nhiều. DELETE chỉ đánh dấu, VACUUM reclaim space bên trong page nhưng hiếm khi trả page về OS. Sau vài tháng update/delete dồn dập, index có thể to gấp nhiều lần kích thước "lành mạnh" của nó, làm cache hit rate giảm và mọi query trên index chậm dần. Cách xử lý: REINDEX CONCURRENTLY index_name; (Postgres 12+) để rebuild không khoá ghi.

Failure mode 5: index không bao giờ được dùng. Người ta đánh xong rồi quên. Một index dead-weight vẫn chịu cost write và chiếm RAM trong shared buffer. Cần audit định kỳ bằng pg_stat_user_indexes để gỡ những index có idx_scan = 0 sau một quãng đủ dài.

Cách debug và monitor

Triệu chứng cần nhìn: query chậm ở P99 dù dữ liệu nhỏ; INSERT/UPDATE tăng latency sau khi thêm index; bảng phình to nhưng row count không đổi.

Công cụ cần biết:

• EXPLAIN (ANALYZE, BUFFERS) — xem plan thực tế: Index Scan, Index Only Scan, hay Bitmap Index Scan. Nếu thấy Seq Scan dù có index, check: predicate có khớp leftmost prefix không, collation/opclass có đúng không, planner có ước lượng row sai không (chạy ANALYZE).
• pg_stat_user_indexes — cột idx_scan (số lần index được dùng), idx_tup_read, idx_tup_fetch. Index nào idx_scan = 0 sau nhiều ngày là ứng viên drop. So với pg_stat_user_tables.seq_scan để biết bảng có đang full scan dù có index không.
• pg_stat_statements — top query theo total_exec_time và calls. Đây là nơi quyết định nên index gì, không phải đoán mò.
• pgstattuple extension, hàm pgstatindex() — đo bloat của một index cụ thể (leaf_fragmentation, avg_leaf_density). Density thấp là dấu hiệu nên reindex.
• pg_stat_user_tables.n_tup_hot_upd vs n_tup_upd — tỉ lệ HOT update. Tỉ lệ thấp trên một bảng update nóng thường do có index trên cột bị update.

Rule lint/phòng ngừa:

• Trước khi CREATE INDEX, bắt buộc có một query trong pg_stat_statements để justify nó.
• Tránh index cột có churn cao (updated_at, last_seen_at) trừ khi thật sự query theo nó.
• Dùng CREATE INDEX CONCURRENTLY trên production để không khoá ghi.
• Đặt cron audit index unused định kỳ.

Tradeoff

B-Tree đổi write cost + storage lấy read latency thấp và ổn định. Read được lợi: lookup O(log n), range scan tận dụng leaf liền nhau, hỗ trợ ORDER BY không tốn sort, hỗ trợ index-only scan với INCLUDE. Write phải trả: mỗi index thêm một lần ghi cho INSERT, có khả năng phá HOT update cho UPDATE, làm VACUUM nặng hơn, và chiếm thêm storage + shared buffer. So với các index chuyên biệt: GIN tốt hơn cho full-text/JSONB nhưng update đắt hơn nhiều; BRIN nhẹ hơn nhiều cho bảng cực lớn xếp theo thứ tự tự nhiên (time-series append-only) nhưng không hỗ trợ point lookup hiệu quả; Hash chỉ equality, không range, không sort. B-Tree không thắng cái nào tuyệt đối nhưng không thua quá xa ở cái nào — đó là lý do nó là mặc định. Quy tắc thực tế: mặc định B-Tree, đánh index theo query đã có thật trong pg_stat_statements, multicolumn theo thứ tự equality-trước-range, dùng partial/expression index khi predicate có thể đẩy vào index, và audit unused index như audit dead code.

Câu hỏi phỏng vấn

Vì sao B-Tree là index mặc định của Postgres, và khi nào nó không phải lựa chọn đúng?

B-Tree là mặc định vì nó là cấu trúc cân bằng cho phép O(log n) lookup, phục vụ được equality, range, IS NULL, prefix LIKE (với opclass phù hợp), và kế thừa thứ tự để phục vụ ORDER BY/MIN/MAX không cần sort thêm. Postgres hiện thực biến thể B-link tree của Lehman-Yao cho concurrency cao, từ Postgres 13 có thêm deduplication giảm size cho low-cardinality. Nó không đúng khi: cần full-text search hoặc query bên trong JSONB (GIN), bảng cực lớn xếp tự nhiên theo thời gian mà chỉ cần range thô (BRIN nhẹ hơn nhiều), hoặc cần index trên kết quả của function/expression dạng tập hợp (GIN/GiST). Hậu quả production khi dùng sai hoặc lạm dụng: đánh index mọi cột giết write throughput và phá HOT update làm table bloat; sai thứ tự cột trong multicolumn khiến index "có mà không dùng"; index trên text với collation không phải C không phục vụ được LIKE 'foo%' dù trông như phải chạy. Điểm ăn điểm là nêu được cả ba: cơ chế (balanced tree, leaf chứa TID, sibling pointer cho range), khi nào sai (specialized workload), và cost write/bloat khi đánh thừa — rồi nhắc audit qua pg_stat_user_indexes và pg_stat_statements.

Hands-on

Mục tiêu: benchmark có và không có index trên cùng một workload, quan sát write penalty, ép một index bị bloat rồi reindex.

Dựng Postgres bằng Docker và nạp dữ liệu:

docker run -d --name pg-bench -e POSTGRES_PASSWORD=pw -p 5432:5432 postgres:16
sleep 5
docker exec -i pg-bench psql -U postgres <<'SQL'
CREATE TABLE orders (
  id          bigserial PRIMARY KEY,
  customer_id bigint    NOT NULL,
  status      text      NOT NULL,
  created_at  timestamptz NOT NULL DEFAULT now(),
  total_cents bigint    NOT NULL
);
INSERT INTO orders (customer_id, status, total_cents, created_at)
SELECT (random()*100000)::bigint,
       (ARRAY['pending','paid','shipped','cancelled'])[1+floor(random()*4)],
       (random()*1000000)::bigint,
       now() - (random() * interval '365 days')
FROM generate_series(1, 5000000);
ANALYZE orders;
SQL

Đo baseline read không index:

docker exec -i pg-bench psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total_cents FROM orders
WHERE customer_id = 42 AND created_at > now() - interval '30 days'
ORDER BY created_at DESC LIMIT 20;"

Sẽ thấy Seq Scan quét 5 triệu row, từ vài trăm ms tới vài giây tuỳ máy. Tạo index và đo lại:

docker exec -i pg-bench psql -U postgres -c "
CREATE INDEX CONCURRENTLY orders_customer_created_idx
  ON orders (customer_id, created_at DESC);"

docker exec -i pg-bench psql -U postgres -c "
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total_cents FROM orders
WHERE customer_id = 42 AND created_at > now() - interval '30 days'
ORDER BY created_at DESC LIMIT 20;"

Plan đổi sang Index Scan, latency rơi xuống mức sub-millisecond cho query này. Đẩy total_cents vào INCLUDE và rerun để thấy Index Only Scan:

docker exec -i pg-bench psql -U postgres -c "
DROP INDEX orders_customer_created_idx;
CREATE INDEX orders_customer_created_idx
  ON orders (customer_id, created_at DESC) INCLUDE (total_cents);
VACUUM ANALYZE orders;"

Đo write penalty bằng pgbench custom script:

cat > /tmp/insert.sql <<'EOF'
INSERT INTO orders (customer_id, status, total_cents)
VALUES ((random()*100000)::bigint, 'pending', (random()*1000000)::bigint);
EOF

docker cp /tmp/insert.sql pg-bench:/tmp/insert.sql

# Không có index phụ (chỉ PK)
docker exec -i pg-bench psql -U postgres -c "DROP INDEX IF EXISTS orders_customer_created_idx;"
docker exec pg-bench pgbench -U postgres -n -f /tmp/insert.sql -c 8 -j 2 -T 30 postgres

# Có index phụ
docker exec -i pg-bench psql -U postgres -c "
CREATE INDEX orders_customer_created_idx
  ON orders (customer_id, created_at DESC) INCLUDE (total_cents);"
docker exec pg-bench pgbench -U postgres -n -f /tmp/insert.sql -c 8 -j 2 -T 30 postgres

So sánh TPS hai lần — TPS lần thứ hai luôn thấp hơn, mức độ tuỳ vào số index và hardware. Thêm vài index nữa rồi đo lại để thấy write throughput tụt rõ rệt theo số index.

Ép bloat và đo bằng pgstattuple:

docker exec -i pg-bench psql -U postgres <<'SQL'
CREATE EXTENSION IF NOT EXISTS pgstattuple;
-- Update churn trên cột có trong index → phá HOT update
UPDATE orders SET created_at = created_at + interval '1 second'
WHERE id % 10 = 0;
SELECT * FROM pgstatindex('orders_customer_created_idx');
SQL

Nhìn leaf_fragmentation và avg_leaf_density. Rebuild và đo lại:

docker exec -i pg-bench psql -U postgres <<'SQL'
REINDEX INDEX CONCURRENTLY orders_customer_created_idx;
SELECT * FROM pgstatindex('orders_customer_created_idx');
SQL

Density sẽ tăng và leaf_fragmentation giảm sau reindex. Cuối cùng audit index usage:

docker exec -i pg-bench psql -U postgres -c "
SELECT schemaname, relname, indexrelname, idx_scan, idx_tup_read
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC;"

Index nào idx_scan = 0 sau khi đã chạy workload thật là ứng viên drop. Dọn dẹp:

docker rm -f pg-bench