Đánh chỉ mục cơ sở dữ liệu: Cây B mà bạn vẫn dựa vào

Index thường được ví như mục lục: cấu trúc giúp cơ sở dữ liệu tìm row mà không đọc toàn bảng. Nhưng B-tree PostgreSQL không đứng yên bên cạnh dữ liệu. Nó là cấu trúc đồng thời, tổ chức theo page, phải giữ cân bằng khi transaction chèn, cập nhật, xóa, rollback và đọc phiên bản row cũ.

Một index có thể biến phép dò chọn lọc thành vài lần đọc page, nhưng cũng chiếm cache, khuếch đại ghi và tạo thêm access path cho planner. Câu hỏi đúng là: access pattern nào xứng đáng có bản sao key đã sắp thứ tự, và phần đọc tiết kiệm có bù được chi phí ghi cùng bảo trì?

CREATE INDEX mặc định dùng B-tree vì key có thứ tự trả lời được nhiều loại câu hỏi: so sánh bằng, khoảng, thứ tự theo tiền tố, giá trị nhỏ nhất hoặc lớn nhất và phân trang có thứ tự. Khi hiểu các page phía dưới những thao tác đó, việc thiết kế index sẽ bớt phụ thuộc vào mẹo truyền miệng.

Page, fanout và lý do cây luôn thấp #

PostgreSQL đọc và ghi block cố định, mặc định 8 KiB. Page B-tree chứa nhiều cặp key-pointer đã sắp thứ tự. Page nội bộ hướng đến page con; page lá chứa index tuple trỏ vào heap. Liên kết sibling nối các lá để range scan đi ngang từ điểm bắt đầu.

Nếu payload dùng được của một page là $P$ byte, còn một separator kèm child pointer trung bình tốn $K$ byte, fanout gần đúng là:

Với $N$ entry đã đánh index, chiều cao lý tưởng là:

$F$, $P$, $K$, $N$ và $H$ lần lượt là fanout, payload page, chi phí key, số entry và chiều cao. Với fanout 300, hàng trăm triệu entry chỉ cần vài tầng. Tầng trên thường nằm trong cache, nên lookup chỉ cần rất ít lần đọc chưa cache.

Bên trong mỗi page, việc chọn separator cũng là một phép binary search. Có thể mô tả traversal rút gọn mà chưa đưa cơ chế đồng thời và buffer manager của PostgreSQL vào như sau:

type InternalPage = {
  kind: 'internal';
  separators: number[];
  children: Page[];
};

type LeafPage = {
  kind: 'leaf';
  entries: Array<{ key: number; rowId: string }>;
  next?: LeafPage;
};

type Page = InternalPage | LeafPage;

function lowerBound(values: number[], target: number): number {
  let low = 0;
  let high = values.length;
  while (low < high) {
    const middle = Math.floor((low + high) / 2);
    if (values[middle]! < target) low = middle + 1;
    else high = middle;
  }
  return low;
}

function findLeaf(root: Page, key: number): LeafPage {
  let page = root;
  while (page.kind === 'internal') {
    const childIndex = lowerBound(page.separators, key);
    page = page.children[childIndex]!;
  }
  return page;
}

Khi lá đầy, thao tác chèn cấp phát sibling, chia entry rồi đẩy separator lên parent. Parent có thể tiếp tục split; root split sẽ tạo root mới và tăng chiều cao một tầng.

function splitLeaf(full: LeafPage): { left: LeafPage; separator: number; right: LeafPage } {
  const middle = Math.ceil(full.entries.length / 2);
  const left: LeafPage = { kind: 'leaf', entries: full.entries.slice(0, middle) };
  const right: LeafPage = {
    kind: 'leaf',
    entries: full.entries.slice(middle),
    next: full.next,
  };
  left.next = right;
  return { left, separator: right.entries[0]!.key, right };
}

Triển khai thật còn có latch, write-ahead log, high key và giao thức split an toàn. Invariant vẫn là: page có thứ tự, child phụ trách một khoảng key và mọi lá cùng độ sâu.

Lookup, range và order thực ra là một năng lực #

Vì lá đã sắp xếp, B-tree hỗ trợ =, <, <=, >=, >, BETWEEN và ORDER BY. Equality đi đến một lá. Range tìm cận dưới rồi bước qua các lá kề nhau đến cận trên. Truy vấn ordered có thể tránh một bước sort.

CREATE TABLE orders (
  id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
  customer_id bigint NOT NULL,
  status text NOT NULL,
  total_cents integer NOT NULL CHECK (total_cents >= 0),
  created_at timestamptz NOT NULL DEFAULT now()
);

CREATE INDEX orders_created_at_idx ON orders (created_at);

-- Tìm điểm đầu của khoảng, sau đó đi qua các page lá kề nhau.
SELECT id, customer_id, total_cents, created_at
FROM orders
WHERE created_at >= timestamptz '2025-03-01 00:00:00+00'
  AND created_at <  timestamptz '2025-04-01 00:00:00+00'
ORDER BY created_at;

-- Cùng thứ tự ấy giúp tìm các row mới nhất với chi phí thấp.
SELECT id, created_at
FROM orders
ORDER BY created_at DESC
LIMIT 50;

Có index không có nghĩa PostgreSQL luôn dùng nó. Nếu tháng Ba chiếm gần hết bảng, sequential scan có thể rẻ hơn hàng nghìn lần đi từ index sang heap. Trừ index-only scan, PostgreSQL vẫn đọc heap để lấy cột và kiểm tra visibility.

Composite index và covering index phải đi theo hình dạng truy vấn #

B-tree nhiều cột sắp theo thứ tự từ điển. (customer_id, created_at) nhóm theo customer rồi sắp từng nhóm theo thời gian, khớp truy vấn lịch sử sau:

CREATE INDEX orders_customer_created_idx
  ON orders (customer_id, created_at DESC);

SELECT id, status, total_cents, created_at
FROM orders
WHERE customer_id = 42017
  AND created_at < timestamptz '2025-03-28 12:00:00+00'
ORDER BY created_at DESC
LIMIT 25;

Index thu hẹp customer_id = 42017, rồi scan khoảng thời gian; nó cũng phục vụ riêng leading column. Nhưng WHERE created_at >= ... trên mọi customer kém hiệu quả vì timestamp rải giữa các nhóm. Thông thường, đặt cột equality trước range; sau một range rộng, cột sau thường chỉ lọc chứ không thu hẹp khoảng liên tục.

INCLUDE lưu payload ở lá mà không biến nó thành search key, tạo covering index cho truy vấn ổn định:

CREATE INDEX orders_customer_created_cover_idx
  ON orders (customer_id, created_at DESC)
  INCLUDE (status, total_cents);

EXPLAIN (ANALYZE, BUFFERS)
SELECT created_at, status, total_cents
FROM orders
WHERE customer_id = 42017
ORDER BY created_at DESC
LIMIT 25;

Nếu visibility map đánh dấu heap page là all-visible, Index Only Scan có thể bỏ qua heap. Covering chưa đủ: page vừa đổi vẫn có thể cần kiểm tra visibility.

Partial index và expression index cho phép cấu trúc vật lý khớp một access pattern hẹp hơn nữa:

CREATE INDEX orders_open_customer_idx
  ON orders (customer_id, created_at DESC)
  INCLUDE (total_cents)
  WHERE status IN ('pending', 'processing');

CREATE INDEX users_lower_email_idx ON users (lower(email));

SELECT id FROM users WHERE lower(email) = lower('Ada@example.com');

Query phải suy ra predicate của partial index và dùng đúng indexed expression. Khi tập con phù hợp, cấu trúc nhỏ hơn và rẻ ghi hơn.

Selectivity và mô hình chi phí của planner #

Selectivity là tỷ lệ row còn lại sau predicate. ID unique có selectivity cao; cờ boolean thường thấp. Planner ước lượng row từ thống kê ANALYZE: tỷ lệ null, số giá trị phân biệt, most-common values và histogram. Sau đó nó tính chi phí page tuần tự, page ngẫu nhiên, CPU và heap visit.

ANALYZE orders;

EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT id, total_cents
FROM orders
WHERE customer_id = 42017
  AND created_at >= now() - interval '30 days';

Đọc plan từ node thực thi đi lên. So sánh rows= với actual rows= và xem buffer hit/read. Sai số lớn có thể do dữ liệu lệch, thống kê cũ hoặc planner coi các cột tương quan là độc lập; đó không phải lý do để tắt sequential scan.

-- Tăng mẫu thống kê cho cột có phân phối lệch.
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 1000;

-- Cho planner biết status và customer_id có thể tương quan.
CREATE STATISTICS orders_customer_status_stats (dependencies, mcv)
  ON customer_id, status
  FROM orders;

ANALYZE orders;

PostgreSQL có thể dùng custom plan theo parameter ban đầu rồi chuyển sang generic plan. Generic plan dễ sai khi một tenant có nửa bảng còn các tenant khác chỉ có vài chục row. Hãy sửa estimate, statistics hoặc query boundary trước khi ép planner bằng setting.

MVCC, write amplification và công việc bảo trì #

Với MVCC, UPDATE thường tạo heap tuple mới. Mỗi index bị ảnh hưởng có thể cần entry mới, còn entry cũ chờ vacuum xác nhận không transaction nào cần. Vì vậy, quá nhiều index tối ưu đọc có thể bóp nghẹt ghi.

Một lần ghi kéo theo heap, mọi index liên quan, page split, WAL, dirty buffer, vacuum và replication. Key rộng cùng INCLUDE giảm fanout và tăng write amplification. Key ngẫu nhiên chạm page khắp cây; key tăng đơn điệu cải thiện locality nhưng có thể làm lá ngoài cùng thành hot page.

HOT update xảy ra khi không indexed column nào đổi và tuple mới vừa cùng heap page. Nó tránh entry index mới; thêm index vào cột đổi thường xuyên có thể làm mất tối ưu này.

SELECT
  schemaname,
  relname,
  indexrelname,
  idx_scan,
  pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
ORDER BY pg_relation_size(indexrelid) DESC;

SELECT
  relname,
  n_tup_upd,
  n_tup_hot_upd,
  n_dead_tup,
  last_autovacuum,
  last_autoanalyze
FROM pg_stat_user_tables
WHERE relname = 'orders';

Autovacuum dọn dead tuple khi an toàn, cập nhật visibility và statistics. VACUUM (ANALYZE) không rebuild index; bloat có thể còn dù chỗ trống được tái sử dụng nội bộ. REINDEX CONCURRENTLY dựng lại index hỏng hoặc phình lớn nhưng cần thêm thời gian và đĩa. Fillfactor chừa chỗ để giảm split, đổi lại index lớn hơn, nên chỉ chỉnh sau đo đạc.

Các kiểu thất bại và lựa chọn thay thế #

Lỗi phổ biến gồm index (customer_id) dư thừa bên cạnh (customer_id, created_at), index cột selectivity thấp không có partial predicate, và covering index quá lớn phải ghi lại sau mỗi lần đổi status.

Implicit cast, function lệch indexed expression và LIKE '%tree%' cũng làm B-tree mất tác dụng. OFFSET 100000 vẫn phải đi qua 100.000 entry; seek pagination dùng key có thứ tự:

SELECT id, created_at
FROM orders
WHERE (created_at, id) < (
  timestamptz '2025-03-28 12:00:00+00',
  900000
)
ORDER BY created_at DESC, id DESC
LIMIT 50;

CREATE INDEX orders_seek_idx ON orders (created_at DESC, id DESC);

B-tree là lựa chọn mặc định chứ không phải đáp án phổ quát:

Về vận hành, CREATE INDEX thường chặn ghi; CONCURRENTLY giảm blocking nhưng lâu hơn, tốn thêm tài nguyên và không chạy trong transaction block. Unique build có thể vấp dữ liệu trùng. Lỗi phần cứng hoặc đổi collation có thể buộc reindex. Vì index là durable state, vòng đời của nó phải nằm trong migration, monitoring và kế hoạch khôi phục.

Takeaways #

B-tree nhanh vì page chứa nhiều separator, fanout cao giữ cây thấp và liên kết lá phục vụ range/order sau một lần traversal. Composite order, partial predicate, expression và INCLUDE phải bắt nguồn từ query shape thật.

Planner vẫn dựa trên selectivity và I/O ước lượng; MVCC vẫn có thể buộc index hit sang heap. Mỗi access path khuếch đại ghi, chiếm cache, tác động HOT và tăng việc vacuum. Hãy đo bằng EXPLAIN (ANALYZE, BUFFERS), giữ index thực sự hoàn vốn, và chọn GIN, BRIN, GiST hoặc sequential scan khi bài toán không phải scalar key có thứ tự.