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

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

我的结构基于Bill Karwin's article关于关闭表和其他一些帖子。

这是我的 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，而且针对其他存储分层数据的方法也经常出现。任何设计都不容易。

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

关于mysql - 对闭包表分层数据结构中的子树进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14069674/