对闭包表分层数据结构中的子树进行排序

我想请你帮我解决存储为分层数据结构的排序问题封闭表.

我想使用这个结构来存储我的网站菜单。一切正常，但问题是我不知道如何对子树进行精确排序按自定义顺序。目前，树按照项目添加到数据库的顺序排序。

我的结构基于比尔·卡尔文的文章 http://karwin.blogspot.cz/2010/03/rendering-trees-with-closure-tables.html关于闭包表和其他一些帖子。

这是我的 MySQL 数据库结构和一些 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);

这是我对一棵树的 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

对于查询得到的 __ROOT_ = 1 的 DEMO 实例：

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 的顺序（根据名称或某些自定义顺序）怎么办？

我见过一些面包屑解决方案（如何按面包屑排序），但我不知道如何生成和更改它们。

这个问题不仅对于闭包表经常出现，而且对于其他存储分层数据的方法也经常出现。任何设计都不容易。

我为 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”和“1,327”进行排序可能不会给出您想要的顺序。但对“001,003”、“001,006”和“001,327”进行排序会。所以你要么需要从 1000000+ 开始你的 id 值，要么使用ZEROFILL对于category_closure 表中的祖先和后代。
• 在此解决方案中，显示顺序取决于类别 ID 的数字顺序。 id 值的数字顺序可能不代表您想要显示树的顺序。或者您可能希望自由更改显示顺序，而不管数字 id 值如何。或者您可能希望相同的类别数据出现在多个树中，每个树具有不同的显示顺序。
  如果您需要更多自由，则需要将排序顺序值与 id 分开存储，并且解决方案会变得更加复杂。但在大多数项目中，使用快捷方式是可以接受的，赋予类别 id 作为树显示顺序的双重职责。

回复您的评论：

是的，您可以将“兄弟排序顺序”存储为闭包表中的另一列，然后使用该值而不是ancestor构建面包屑字符串。但如果这样做，最终会产生大量数据冗余。也就是说，给定的祖先存储在多行中，每行对应从它下降的每条路径。因此，您必须在所有这些行上存储相同的同级排序顺序值，这会产生异常风险。

另一种方法是创建另一个表，仅使用one树中每个不同祖先的行，并连接到该表以获得同级顺序。

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