Danh mục sản phẩm phân cấp nhiều tầng: so sánh adjacency list, materialized path và closure table. Chọn cái nào?

Adjacency list — mỗi node giữ parent_id.

• Ghi cực rẻ, di chuyển nhánh chỉ là đổi một cột.
• Nhược điểm: lấy toàn bộ cây con cần đệ quy.

create table categories (id bigserial primary key, parent_id bigint references categories(id), name text);

with recursive tree as (
  select id, parent_id from categories where id = $1
  union all
  select c.id, c.parent_id from categories c join tree t on c.parent_id = t.id
)
select * from tree;

Materialized path — mỗi node lưu đường dẫn tổ tiên dạng chuỗi (1/7/22 hoặc kiểu ltree). Lấy cây con chỉ là một lần quét tiền tố, đọc rất nhanh. Nhược điểm: di chuyển một nhánh phải cập nhật path của toàn bộ con cháu, và độ sâu bị giới hạn bởi độ dài chuỗi.

Closure table — bảng phụ lưu mọi cặp tổ tiên–con cháu kèm khoảng cách.

create table category_paths (
  ancestor_id   bigint not null references categories(id),
  descendant_id bigint not null references categories(id),
  depth         int not null,
  primary key (ancestor_id, descendant_id)
);

Truy vấn tổ tiên lẫn con cháu đều là một lần tra index, không đệ quy; đổi lại tốn O(n) dòng phụ mỗi node và mọi thao tác chèn/di chuyển phải bảo trì bảng này trong transaction.

Cách chọn: cây nông và đọc ít (menu vài tầng) → adjacency list, ngại gì phức tạp. Đọc nhiều, cấu trúc ít thay đổi (danh mục sàn thương mại điện tử) → materialized path, PostgreSQL có sẵn ltree với index GiST. Cây thay đổi thường xuyên và truy vấn tổ tiên/con cháu đều nặng (phân quyền theo phòng ban, BOM) → closure table. Còn nested set đọc nhanh nhưng mỗi lần chèn phải đánh số lại phần lớn cây nên hiện ít dùng cho dữ liệu ghi thường xuyên.