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

Question

我想请您帮我解决以 封闭表 形式存储的分层数据结构的排序问题。

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

我的结构基于Bill Karwin的有关闭包表的文章和其他一些文章。

这是带有一些DEMO数据的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

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

我已经看到了一些面包屑解决方案（如何按面包屑排序），但是我不知道如何生成和更改它们。

Answer 1

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

我为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构建面包屑字符串。但是，如果这样做，最终将导致大量数据冗余。就是说，给定的祖先存储在多行中，每条路径都从其降序存储。因此，您必须为所有这些行上的同级排序顺序存储相同的值，这会导致出现异常的风险。

另一种方法是创建另一个表，只有 一个 在树中每个不同的祖先行，并加入到该表以获得同级次序。

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