Sắp xếp một cây con trong cấu trúc phân cấp dữ liệu theo thứ bậc

Question

Tôi muốn yêu cầu bạn giúp tôi giải quyết vấn đề với việc sắp xếp cấu trúc dữ liệu phân cấp được lưu trữ dưới dạng bảng đóng cửa.

Tôi muốn sử dụng cấu trúc này để lưu trữ menu trang web của mình. Tất cả mọi thứ hoạt động tốt, nhưng vấn đề là tôi không biết làm thế nào để sắp xếp các subtree chính xác theo thứ tự tùy chỉnh. Tại thời điểm này cây được sắp xếp theo thứ tự các mục được thêm vào cơ sở dữ liệu.

Cấu trúc của tôi dựa trên Bill Karwin's article về Bảng đóng và một số bài đăng khác.

Dưới đây là cấu trúc cơ sở dữ liệu MySQL của tôi với một số dữ liệu DEMO:

-- 
-- Table `category` 
-- 

CREATE TABLE IF NOT EXISTS `category` (
    `id` int(11) NOT NULL AUTO_INCREMENT, 
    `name` varchar(100) COLLATE utf8_czech_ci NOT NULL, 
    `active` tinyint(1) NOT NULL, 
    PRIMARY KEY (`id`) 
) ENGINE=InnoDB; 


INSERT INTO `category` (`id`, `name`, `active`) VALUES 
(1, 'Cat 1', 1), 
(2, 'Cat 2', 1), 
(3, 'Cat 1.1', 1), 
(4, 'Cat 1.1.1', 1), 
(5, 'Cat 2.1', 1), 
(6, 'Cat 1.2', 1), 
(7, 'Cat 1.1.2', 1); 

-- 
-- Table `category_closure` 
-- 

CREATE TABLE IF NOT EXISTS `category_closure` (
    `id` bigint(20) NOT NULL AUTO_INCREMENT, 
    `ancestor` int(11) DEFAULT NULL, 
    `descendant` int(11) DEFAULT NULL, 
    `depth` int(11) DEFAULT NULL, 
    PRIMARY KEY (`id`), 
    KEY `fk_category_closure_ancestor_category_id` (`ancestor`), 
    KEY `fk_category_closure_descendant_category_id` (`descendant`) 
) ENGINE=InnoDB; 

INSERT INTO `category_closure` (`id`, `ancestor`, `descendant`, `depth`) VALUES 
(1, 1, 1, 0), 
(2, 2, 2, 0), 
(3, 3, 3, 0), 
(4, 1, 3, 1), 
(5, 4, 4, 0), 
(7, 3, 4, 1), 
(8, 1, 4, 2), 
(10, 6, 6, 0), 
(11, 1, 6, 1), 
(12, 7, 7, 0), 
(13, 3, 7, 1), 
(14, 1, 7, 2), 
(16, 5, 5, 0), 
(17, 2, 5, 1); 

Đây là câu hỏi của tôi CHỌN cho một cây:

SELECT c2.*, cc2.ancestor AS `_parent` 
FROM category AS c1 
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id) 
JOIN category AS c2 ON (cc1.descendant = c2.id) 
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1) 
WHERE c1.id = __ROOT__ AND c1.active = 1 
ORDER BY cc1.depth 

Đối với các trường hợp DEMO với __ROOT_ = 1 truy vấn đó nhận được:

id name  active  _parent 
1 Cat 1  1   NULL 
3 Cat 1.1  1   1 
6 Cat 1.2  1   1 
4 Cat 1.1.1 1   3 
7 Cat 1.1.2 1   3 

Nhưng nếu tôi ví dụ như cần thay đổi thứ tự của Cat 1.1 và Cat 1.2 (theo tên, hoặc một số thứ tự tùy chỉnh)?

Tôi đã thấy một số giải pháp đường dẫn (cách sắp xếp theo đường dẫn), nhưng tôi không biết cách tạo và thay đổi chúng.

Answer 1

Câu hỏi này xuất hiện thường xuyên không chỉ cho Bảng đóng cửa mà còn cho các phương pháp lưu trữ dữ liệu phân cấp khác. Nó không dễ dàng trong bất kỳ thiết kế nào.

Giải pháp mà tôi đã đưa ra cho Bảng đóng cửa bao gồm một lần kết hợp bổ sung. Mỗi nút trong cây tham gia vào chuỗi tổ tiên của nó, giống như truy vấn kiểu "đường dẫn". Sau đó sử dụng GROUP_CONCAT() để thu gọn đường dẫn thành chuỗi được phân cách bằng dấu phẩy, sắp xếp số id theo chiều sâu trong cây. Bây giờ bạn có một chuỗi mà bạn có thể sắp xếp.

SELECT c2.*, cc2.ancestor AS `_parent`, 
    GROUP_CONCAT(breadcrumb.ancestor ORDER BY breadcrumb.depth DESC) AS breadcrumbs 
FROM category AS c1 
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id) 
JOIN category AS c2 ON (cc1.descendant = c2.id) 
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1) 
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant) 
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1 
GROUP BY cc1.descendant 
ORDER BY breadcrumbs; 

+----+------------+--------+---------+-------------+ 
| id | name  | active | _parent | breadcrumbs | 
+----+------------+--------+---------+-------------+ 
| 1 | Cat 1  |  1 | NULL | 1   | 
| 3 | Cat 1.1 |  1 |  1 | 1,3   | 
| 4 | Cat 1.1.1 |  1 |  3 | 1,3,4  | 
| 7 | Cat 1.1.2 |  1 |  3 | 1,3,7  | 
| 6 | Cat 1.2 |  1 |  1 | 1,6   | 
+----+------------+--------+---------+-------------+ 

Hãy cẩn thận:

• Các giá trị id nên có chiều dài đồng phục, bởi vì sắp xếp "1,3" và "1,6" và "1.327" có thể không đưa ra theo thứ tự bạn có ý định. Nhưng sắp xếp "001,003" và "001,006" và "001,327" sẽ. Vì vậy, bạn hoặc cần phải bắt đầu các giá trị id của bạn tại 1000000+, hoặc người nào khác sử dụng ZEROFILL cho tổ tiên và hậu duệ trong bảng category_closure.
• Trong giải pháp này, thứ tự hiển thị phụ thuộc vào thứ tự số của id danh mục. Thứ tự số của các giá trị id có thể không đại diện cho thứ tự bạn muốn hiển thị cây. Hoặc bạn có thể muốn tự do thay đổi thứ tự hiển thị bất kể giá trị id số. Hoặc bạn có thể muốn cùng một dữ liệu danh mục xuất hiện trong nhiều hơn một cây, mỗi cây có thứ tự hiển thị khác nhau.
  Nếu bạn cần tự do hơn, bạn cần lưu trữ các giá trị sắp xếp thứ tự riêng biệt với id và giải pháp thậm chí còn phức tạp hơn. Nhưng trong hầu hết các dự án, có thể chấp nhận sử dụng một đoạn cắt ngắn, cho phép thực hiện nhiệm vụ kép của danh mục theo thứ tự hiển thị cây.

---

Re bình luận của bạn:

Có, bạn có thể lưu trữ "anh chị em ruột thứ tự sắp xếp" như một cột trong bảng đóng cửa, sau đó sử dụng giá trị đó thay vì ancestor để xây dựng chuỗi breadcrumbs. Nhưng nếu bạn làm điều đó, bạn kết thúc với rất nhiều dư thừa dữ liệu. Đó là, một tổ tiên đã cho được lưu trữ trên nhiều hàng, một cho mỗi đường dẫn giảm dần từ nó. Vì vậy, bạn phải lưu trữ cùng một giá trị cho thứ tự sắp xếp anh chị em trên tất cả các hàng đó, điều này tạo ra rủi ro của một sự bất thường.

Cách khác là tạo một bảng khác, chỉ với một hàng cho mỗi tổ tiên riêng biệt trên cây và tham gia bảng đó để nhận đơn đặt hàng anh chị em.

CREATE TABLE category_closure_order (
    ancestor INT PRIMARY KEY, 
    sibling_order SMALLINT UNSIGNED NOT NULL DEFAULT 1 
); 

SELECT c2.*, cc2.ancestor AS `_parent`, 
    GROUP_CONCAT(o.sibling_order ORDER BY breadcrumb.depth DESC) AS breadcrumbs 
FROM category AS c1 
JOIN category_closure AS cc1 ON (cc1.ancestor = c1.id) 
JOIN category AS c2 ON (cc1.descendant = c2.id) 
LEFT OUTER JOIN category_closure AS cc2 ON (cc2.descendant = c2.id AND cc2.depth = 1) 
JOIN category_closure AS breadcrumb ON (cc1.descendant = breadcrumb.descendant) 
JOIN category_closure_order AS o ON breadcrumb.ancestor = o.ancestor 
WHERE c1.id = 1/*__ROOT__*/ AND c1.active = 1 
GROUP BY cc1.descendant 
ORDER BY breadcrumbs; 

+----+------------+--------+---------+-------------+ 
| id | name  | active | _parent | breadcrumbs | 
+----+------------+--------+---------+-------------+ 
| 1 | Cat 1  |  1 | NULL | 1   | 
| 3 | Cat 1.1 |  1 |  1 | 1,1   | 
| 4 | Cat 1.1.1 |  1 |  3 | 1,1,1  | 
| 7 | Cat 1.1.2 |  1 |  3 | 1,1,2  | 
| 6 | Cat 1.2 |  1 |  1 | 1,2   | 
+----+------------+--------+---------+-------------+