對閉合表中的子樹進行排序分層數據結構

Question

我想請求你幫助我排序分層數據結構的問題，存儲爲閉合表。

我想用這個結構來存儲我的網站菜單。一切正常，但問題是，我不知道如何按自定義順序排序確切的子樹。目前，樹按項目添加到數據庫的順序進行排序。

我的結構是基於Bill Karwin's article關於閉包表和一些其他職位。

這裏是我的MySQL數據庫結構與一些演示數據：

-- 
-- 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); 

這裏是我的一棵樹SELECT查詢：

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 

對於DEMO實例與__ROOT_ = 1查詢得到：

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 

但是，如果我例如需要更改Cat 1.1和Cat 1.2（根據名稱或某種自定義順序）的順序？

我見過一些麪包屑解決方案（如何通過麪包屑排序），但我不知道如何生成和更改它們。

Answer 1

這個問題不僅出現在Closure Table中，而且還出現在其他存儲分層數據的方法中。在任何設計中都不容易。

我爲Closure Table提出的解決方案涉及一個額外的連接。樹中的每個節點都連接到其祖先的鏈，就像「麪包屑」類型的查詢。然後使用GROUP_CONCAT（）將麪包屑摺疊成逗號分隔的字符串，並按樹中的深度對ID號進行排序。現在你有一個可以排序的字符串。

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   | 
+----+------------+--------+---------+-------------+ 

注意事項：

• ID值應該有統一的長度，因爲選「1,3」和「1,6」和「1327」可能不會給你想要的順序。但排序「001,003」和「001,006」和「001,327」會。因此，您需要以1000000+開始您的ID值，否則在category_closure表中使用ZEROFILL作爲祖先和後代。
• 在此解決方案中，顯示順序取決於類別標識的數字順序。 id值的數字順序可能不代表您要顯示樹的順序。或者您可能希望自由地改變顯示順序而不考慮數字ID值。或者您可能希望相同的類別數據出現在多個樹中，每個樹具有不同的顯示順序。
  如果您需要更多自由度，您需要將排序順序值與ID分開存儲，解決方案會變得更加複雜。但是在大多數項目中，使用快捷方式是可以接受的，將類別ID的雙重職責作爲樹顯示順序。

---

回覆您的評論：

是的，你可以存儲「兄弟排序順序」作爲封表的另一列，然後使用該值，而不是ancestor打造的麪包屑字符串。但是，如果你這樣做，你會得到大量的數據冗餘。也就是說，一個給定的祖先存儲在多行上，每個從它下行的路徑都有一個。因此，您必須在所有這些行上存儲相同的兄弟排序順序值，這會產生異常風險。

另一種方法是創建另一個表，其中只有一個行，並且連接到該表以獲取兄弟順序。

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   | 
+----+------------+--------+---------+-------------+