Quan hệ & dữ liệu dạng cây

Các kiểu quan hệ

Quan hệ	Cách lưu	Ví dụ
1 : 1	Bảng phụ dùng chung khoá chính với bảng chính, để tách cột lớn hoặc ít đọc khỏi bảng nóng	users và user_profiles(user_id PK, bio, avatar_url…)
1 : n	Cột khoá ngoại ở phía “nhiều”, có index	orders.customer_id
n : n	Bảng nối, khoá chính ghép (a_id, b_id) và thêm index (b_id, a_id) để tra theo chiều ngược lại	post_tags(post_id, tag_id)
Cây	Một trong bốn cách bên dưới	Danh mục, bình luận lồng nhau, sơ đồ tổ chức

Bảng nối n:n có thể mang thêm thuộc tính của chính quan hệ: enrollments(student_id, course_id, enrolled_at, grade). Khi đó nó là một thực thể thật, có thể cần khoá chính riêng.

Bốn cách lưu cây

Ví dụ danh mục: Điện tử → Máy tính → Laptop → Laptop gaming.

Adjacency list: mỗi nút trỏ về cha

CREATE TABLE categories (
  id        BIGINT PRIMARY KEY,
  parent_id BIGINT NULL,
  name      VARCHAR(100) NOT NULL,
  FOREIGN KEY (parent_id) REFERENCES categories (id)
  -- MySQL 8.x âm thầm bỏ qua REFERENCES viết ngay sau cột; khai báo FOREIGN KEY riêng như trên
);
CREATE INDEX idx_categories_parent ON categories (parent_id);

-- toàn bộ cây con của danh mục 1 (MySQL 8+, PostgreSQL)
WITH RECURSIVE sub AS (
  SELECT id, parent_id, name, 0 AS depth FROM categories WHERE id = 1
  UNION ALL
  SELECT c.id, c.parent_id, c.name, s.depth + 1
  FROM categories c JOIN sub s ON c.parent_id = s.id
)
SELECT * FROM sub;

Đơn giản, toàn vẹn nhờ khoá ngoại, di chuyển một nhánh chỉ là sửa một parent_id. Đọc cả cây con cần recursive CTE (mỗi tầng một lượt join); cây sâu và đọc rất nhiều thì chậm.

Materialized path: lưu đường dẫn từ gốc

path = '/1/4/9/'. Lấy cây con: WHERE path LIKE '/1/4/%' (dùng được index vì so sánh từ đầu chuỗi). Lấy tổ tiên: tách chuỗi path. Di chuyển một nhánh phải sửa path của mọi nút con. Không có khoá ngoại đảm bảo path đúng. PostgreSQL có kiểu ltree chuyên cho cách này.

Nested set: mỗi nút có khoảng [lft, rgt]

Nút con nằm trong khoảng của nút cha. Lấy cả cây con chỉ một câu: WHERE lft BETWEEN :lft AND :rgt, rất nhanh. Đổi lại, chèn hay di chuyển một nút phải đánh lại lft, rgt của rất nhiều nút. Hợp với cây gần như không đổi, đọc rất nhiều.

Closure table: lưu mọi cặp tổ tiên – con cháu

CREATE TABLE category_paths (
  ancestor_id   BIGINT NOT NULL,
  descendant_id BIGINT NOT NULL,
  depth         INT NOT NULL,          -- 0 là chính nó
  PRIMARY KEY (ancestor_id, descendant_id)
);
CREATE INDEX idx_paths_descendant ON category_paths (descendant_id);

-- cây con của 1
SELECT c.* FROM categories c
JOIN category_paths p ON p.descendant_id = c.id
WHERE p.ancestor_id = 1;

-- tổ tiên của 9 (breadcrumb), từ gốc xuống
SELECT c.* FROM categories c
JOIN category_paths p ON p.ancestor_id = c.id
WHERE p.descendant_id = 9
ORDER BY p.depth DESC;

Đọc cây con và tổ tiên đều nhanh, có thể dùng khoá ngoại. Tốn chỗ: số dòng bằng tổng độ sâu của mọi nút. Chèn nút mới thêm một dòng cho mỗi tổ tiên; di chuyển nhánh phải xoá và chèn lại nhiều dòng.

So sánh

	Adjacency list	Materialized path	Nested set	Closure table
Đọc cây con	Recursive CTE	LIKE 'prefix%'	BETWEEN	Một JOIN
Đọc tổ tiên	Recursive CTE	Tách chuỗi	BETWEEN ngược	Một JOIN
Chèn nút	Rất rẻ	Rẻ	Đắt	Trung bình
Di chuyển nhánh	Rất rẻ	Sửa cả nhánh	Rất đắt	Đắt
Khoá ngoại	Có	Không	Không	Có

Mặc định nên chọn adjacency list. Recursive CTE đã có ở MySQL 8 và PostgreSQL, đủ nhanh cho cây vài nghìn tới vài chục nghìn nút. Thêm closure table khi phải đọc cây con hoặc breadcrumb rất nhiều trên cây lớn.

Ghi nhớ

1. n:n dùng bảng nối với khoá ghép và index theo chiều ngược lại.
2. Cây: adjacency list + recursive CTE là mặc định; closure table khi đọc nhiều; nested set khi cây gần như không đổi.