Thiết kế và tối ưu dữ liệu dạng cây trong SQL: So sánh 4 mô hình thực chiến - ITFROMZERO - Share tobe shared! So sánh 4 mô hình lưu trữ dữ liệu dạng cây trong SQL: Adjacency List, Path Enumeration, Nested Sets và Closure Table kèm đánh giá hiệu năng thực tế và code tối ưu.

Table of Contents

Bối cảnh & Vấn đề thực tế

Làm sàn thương mại điện tử, hệ thống diễn đàn hay phần mềm nhân sự, sớm muộn bạn cũng đụng tới dữ liệu dạng cây (hierarchical data). Oái oăm ở chỗ: cơ sở dữ liệu quan hệ (RDBMS) sinh ra để quản lý các bảng 2 chiều phẳng. Trong khi đó, cấu trúc cây lại phân nhánh tự do và lồng nhau nhiều cấp.

Chọn sai mô hình ngay từ đầu thường kéo theo hai sự cố quen thuộc. Nhẹ thì hệ thống bắn liên tục vài chục câu query N+1 chỉ để render thanh menu đa cấp. Nặng thì database dính deadlock, CPU vọt lên 100% khi người dùng kéo thả đổi chỗ một danh mục cha. Trên MySQL hay PostgreSQL, kiến trúc bảng bạn chọn sẽ quyết định hệ thống chạy mượt hay sập khi dữ liệu chạm mốc vài trăm nghìn bản ghi.

Hiện có 4 cách tiếp cận phổ biến: Adjacency List, Path Enumeration (Materialized Path), Nested Sets và Closure Table. Không có giải pháp nào hoàn hảo cho mọi trường hợp. Bản chất ở đây là bạn chọn ưu tiên tốc độ đọc (Read) hay chi phí ghi và cập nhật (Write).

Cài đặt Schema mẫu

Để dễ so sánh, chúng ta cùng dựng cấu trúc cho cây danh mục công nghệ: Điện tử > Điện thoại > iOS / Android và Điện tử > Laptop.

1. Adjacency List (Danh sách kề)

Cách tiếp cận trực quan và quen thuộc nhất. Mỗi dòng chỉ cần thêm một cột parent_id trỏ thẳng về khóa chính của node cha.

CREATE TABLE categories_adj (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    parent_id INT NULL,
    CONSTRAINT fk_parent FOREIGN KEY (parent_id) REFERENCES categories_adj(id) ON DELETE CASCADE,
    INDEX idx_parent (parent_id)
);

INSERT INTO categories_adj (id, name, parent_id) VALUES
(1, 'Điện tử', NULL),
(2, 'Điện thoại', 1),
(3, 'Laptop', 1),
(4, 'iOS', 2),
(5, 'Android', 2);

2. Path Enumeration (Lưu đường dẫn – Materialized Path)

Ý tưởng mượn từ cấu trúc đường dẫn thư mục Unix (ví dụ /var/log/nginx/). Mỗi node lưu lại toàn bộ lộ trình đi từ node gốc đến chính nó.

CREATE TABLE categories_path (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    path VARCHAR(255) NOT NULL, -- Format chuẩn: 1/2/4/
    INDEX idx_path (path)
);

INSERT INTO categories_path (id, name, path) VALUES
(1, 'Điện tử', '1/'),
(2, 'Điện thoại', '1/2/'),
(3, 'Laptop', '1/3/'),
(4, 'iOS', '1/2/4/'),
(5, 'Android', '1/2/5/');

3. Nested Sets (Tập hợp lồng nhau)

Mô hình này đánh số thứ tự duyệt cây (pre-order traversal). Mỗi node giữ 2 mốc số nguyên: lft (left) và rgt (right). Mọi node con cháu đều có cặp chỉ số nằm lọt vào giữa khoảng (lft, rgt) của node cha.

CREATE TABLE categories_nested (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    lft INT NOT NULL,
    rgt INT NOT NULL,
    INDEX idx_lft_rgt (lft, rgt)
);

INSERT INTO categories_nested (id, name, lft, rgt) VALUES
(1, 'Điện tử', 1, 10),
(2, 'Điện thoại', 2, 7),
(3, 'Laptop', 8, 9),
(4, 'iOS', 3, 4),
(5, 'Android', 5, 6);

4. Closure Table (Bảng bao đóng quan hệ)

Tách rời dữ liệu thực thể và quan hệ phân cấp ra hai bảng riêng. Bảng phụ category_relations lưu mọi cặp quan hệ giữa tổ tiên và con cháu (ancestor – descendant) kèm độ sâu (depth).

CREATE TABLE categories_closure (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100) NOT NULL
);

CREATE TABLE category_relations (
    ancestor_id INT NOT NULL,
    descendant_id INT NOT NULL,
    depth INT NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id),
    INDEX idx_descendant (descendant_id),
    CONSTRAINT fk_ancestor FOREIGN KEY (ancestor_id) REFERENCES categories_closure(id) ON DELETE CASCADE,
    CONSTRAINT fk_descendant FOREIGN KEY (descendant_id) REFERENCES categories_closure(id) ON DELETE CASCADE
);

INSERT INTO categories_closure (id, name) VALUES
(1, 'Điện tử'), (2, 'Điện thoại'), (3, 'Laptop'), (4, 'iOS'), (5, 'Android');

-- Ghi nhận quan hệ (kể cả quan hệ chính nó với độ sâu 0)
INSERT INTO category_relations (ancestor_id, descendant_id, depth) VALUES
(1,1,0), (2,2,0), (3,3,0), (4,4,0), (5,5,0),
(1,2,1), (1,3,1), (1,4,2), (1,5,2),
(2,4,1), (2,5,1);

Thực thi truy vấn và thao tác dữ liệu

Hiệu năng thực tế bộc lộ rõ nhất qua hai kịch bản: đọc toàn bộ nhánh con và chèn/di chuyển node.

Truy vấn 1: Lấy toàn bộ cây con bên dưới “Điện thoại” (id = 2)

Adjacency List: Từ MySQL 8.0 và PostgreSQL, chúng ta dùng Common Table Expression (CTE) đệ quy. Query chạy trong một lượt quét mà không cần gọi nhiều vòng lặp từ application layer:

WITH RECURSIVE SubTree AS (
    SELECT id, name, parent_id, 1 AS level
    FROM categories_adj WHERE id = 2
    UNION ALL
    SELECT c.id, c.name, c.parent_id, st.level + 1
    FROM categories_adj c
    INNER JOIN SubTree st ON c.parent_id = st.id
)
SELECT * FROM SubTree;

Path Enumeration: Dùng toán tử LIKE với tiền tố cố định để tận dụng B-Tree Index:
```
SELECT * FROM categories_path
WHERE path LIKE '1/2/%';
```
Nested Sets: Tốc độ đọc đứng đầu trong cả 4 mô hình. Câu lệnh chỉ là một phép lọc số học đơn giản với chỉ mục composite (lft, rgt):
```
SELECT child.*
FROM categories_nested parent
JOIN categories_nested child ON child.lft BETWEEN parent.lft AND parent.rgt
WHERE parent.id = 2;
```

Closure Table: Chỉ cần một phép JOIN 2 bảng cơ bản, không cần tính toán đệ quy:

SELECT c.*
FROM categories_closure c
JOIN category_relations r ON c.id = r.descendant_id
WHERE r.ancestor_id = 2;

Truy vấn 2: Thêm mới hoặc di chuyển một nhánh cây

Đây là khâu bộc lộ rõ sự chênh lệch về chi phí ghi:

Adjacency List: Thêm node con chỉ tốn duy nhất 1 câu INSERT độc lập (thời gian thực thi tầm 1ms). Di chuyển nhánh cây cũng chỉ cần 1 câu lệnh UPDATE parent_id. Rất nhanh và an toàn.
Path Enumeration: Thêm node mới chỉ cần lấy chuỗi path của cha rồi ghép thêm ID mới. Tuy nhiên, khi chuyển một node cha sang vị trí khác, bạn phải cập nhật lại chuỗi path của toàn bộ cây con bên dưới bằng hàm cắt ghép chuỗi.
Nested Sets: Ghi dữ liệu cực kỳ tốn kém. Chèn thêm một node mới vào giữa cây buộc database phải cập nhật lại giá trị lft và rgt của toàn bộ các node đứng sau (+2):
```
-- Phải bọc trong Transaction có lock
UPDATE categories_nested SET rgt = rgt + 2 WHERE rgt > 4;
UPDATE categories_nested SET lft = lft + 2 WHERE lft > 4;
INSERT INTO categories_nested (name, lft, rgt) VALUES ('HarmonyOS', 5, 6);
```
Trên bảng có 500.000 bản ghi, hai câu UPDATE này quét qua hàng trăm nghìn dòng, dễ dẫn đến lock bảng diện rộng và nghẽn I/O.
Closure Table: Khi thêm node mới, bạn chèn 1 dòng vào bảng danh mục và nhân bản các mối quan hệ của cha sang node mới:
```
INSERT INTO categories_closure (id, name) VALUES (6, 'HarmonyOS');
INSERT INTO category_relations (ancestor_id, descendant_id, depth)
SELECT ancestor_id, 6, depth + 1
FROM category_relations
WHERE descendant_id = 2
UNION ALL
SELECT 6, 6, 0;
```
Thao tác này chỉ ghi thêm dòng mới vào bảng phụ, không can thiệp hay sửa đổi các dòng dữ liệu sẵn có.

Bảng so sánh tổng hợp

Tiêu chí	Adjacency List	Path Enumeration	Nested Sets	Closure Table
Lấy cây con	Khá (Recursive CTE)	Nhanh (Index LIKE)	Cực nhanh (BETWEEN)	Rất nhanh (JOIN)
Lấy chuỗi tổ tiên	Khá (Recursive CTE)	Cần tách chuỗi / CTE	Rất nhanh	Rất nhanh (depth > 0)
Thêm node mới	Cực nhanh (1 lệnh INSERT)	Nhanh (1 lệnh INSERT)	Rất chậm (Re-indexing lft/rgt)	Nhanh (Insert vài row phụ)
Di chuyển nhánh	Rất dễ (Update 1 dòng)	Phức tạp (Update chuỗi)	Rất phức tạp & dễ deadlock	Gọn (Xóa & ghi lại quan hệ)
Ràng buộc toàn vẹn	Rất chặt (Foreign Key)	Yếu (Dựa vào chuỗi text)	Yếu (Dựa vào số học logic)	Rất chặt (Foreign Key)
Dung lượng lưu trữ	O(N) – Tối thiểu	O(N) – Thấp	O(N) – Thấp	O(N * depth) – Tốn disk nhất

Kiểm tra & Giám sát hiệu năng

Để hệ thống chạy ổn định ở môi trường production, bạn cần dùng EXPLAIN ANALYZE để kiểm tra chỉ mục và kế hoạch thực thi.

1. Bẫy Index trên Path Enumeration

Lỗi kinh điển khi dùng LIKE là đặt ký tự đại diện ở đầu: LIKE '%/2/%'. Câu lệnh này làm vô hiệu hóa B-Tree index, ép database phải quét toàn bộ bảng (Full Table Scan). Trên bảng 500.000 dòng, thời gian thực thi có thể tăng vọt từ 3ms lên hơn 800ms.

Muốn tận dụng Index Range Scan, bạn luôn phải giữ tiền tố cố định:

-- Tốt: Tận dụng Index Range Scan (Execution time: ~2-3ms)
EXPLAIN ANALYZE SELECT * FROM categories_path WHERE path LIKE '1/2/%';

-- Xấu: Full Table Scan do mất tiền tố index (Execution time: ~800ms)
EXPLAIN ANALYZE SELECT * FROM categories_path WHERE path LIKE '%/2/%';

2. Nguy cơ treo đệ quy với Adjacency List

Recursive CTE tạo bảng tạm trong RAM. Biến hệ thống cte_max_recursion_depth trên MySQL mặc định chặn ở mức 1.000 vòng lặp. Nếu dữ liệu xuất hiện vòng lặp kín do lỗi code (node A trỏ cha node B, node B lại trỏ ngược về A), query sẽ ngốn sạch tài nguyên và treo đến khi chạm ngưỡng timeout:

-- Kiểm tra giới hạn đệ quy hiện tại
SHOW VARIABLES LIKE 'cte_max_recursion_depth';

-- Nới lỏng giới hạn cho phiên làm việc nếu cây thực tế sâu hơn
SET SESSION cte_max_recursion_depth = 5000;

3. Kinh nghiệm chọn giải pháp trong thực tế

Adjacency List + Recursive CTE: Phù hợp cho 80% ứng dụng hiện nay chạy trên MySQL 8.0+ hoặc PostgreSQL. Cấu trúc bảng tối giản, toàn vẹn dữ liệu được đảm bảo bằng Foreign Key, chạy rất tốt với cây sâu dưới 10-15 tầng.
Closure Table: Đáng đầu tư khi bạn xây dựng hệ thống bình luận đa cấp kiểu Reddit hay cây phân quyền nhiều nhánh. Mô hình này hỗ trợ tìm khoảng cách giữa 2 node bất kỳ và di chuyển nhánh nhanh chóng mà không gây lock bảng.
Nested Sets: Chỉ nên dùng cho dữ liệu gần như tĩnh, tỷ lệ đọc/ghi áp đảo trên 99/1. Ví dụ điển hình là cây địa giới hành chính (Quốc gia > Tỉnh > Huyện > Xã). Dữ liệu hành chính hầu như không bao giờ đổi, trong khi thao tác gom toàn bộ con cháu lại diễn ra liên tục.
Path Enumeration: Lựa chọn phù hợp khi bạn cần in ngay thanh điều hướng (breadcrumb) lên giao diện mà không muốn tốn thêm bất kỳ câu JOIN hay đệ quy nào.