在闭包表层次结构中对子树进行排序

Question

我想请您帮忙解决一个问题，即如何对存储为闭包表的层次数据结构进行排序。

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

我的结构基于Bill Karwin 的文章以及一些其他帖子。

下面是我的 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 的顺序怎么办？

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

- JCZ

---

+1 感谢您发布样例 DDL 和数据。 - Bill Karwin

当传奇人物出现在评论中时，我的内心被震撼到了。 - Srinivas Reddy Thatiparthy

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"和"1,327"进行排序可能会给出您想要的顺序。但是对于"001,003"、"001,006"和"001,327"进行排序可以得到正确的结果。所以你需要以1000000+开始你的id值，或者在category_closure表中为ancestor和descendant使用ZEROFILL。
• 在这个解决方案中，显示顺序取决于类别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         |
+----+------------+--------+---------+-------------+

- Bill Karwin

---

非常感谢Karwin先生，那么当我需要在某个层级上获得更多自由并创建自定义顺序时（以设置具有相同父项的菜单项的顺序），我可以添加类似于“同级优先级”列吗？还是这是一个不好的想法？ - JCZ

好奇为什么不在 Category 表格中存储排序顺序，这样就不需要第三个表格了？当我在祖先树中进行排序时，我总是使用 double，以便在需要在节点 1 和 2 之间插入新节点时，可以将其赋予 sortValue 1.5。 - TheSmileyCoder

@TheSmileyCoder 因为您可能需要多个包含相同类别但顺序不同的树。 - Bill Karwin

@BillKarwin 是的，我明白了。我想在我的工作中，我只需要自定义排序或按数据排序（例如按名称字母顺序）。我相信我更喜欢将其放在闭包方法的“仅”两个表中，除非我知道我需要支持多个自定义排序。无论如何，这是一个值得思考的问题，谢谢。 - TheSmileyCoder

@ScoobyDam，请使用 LPAD() 函数将数字填充零，直到数字具有统一的长度。请参阅 https://dev59.com/gmgu5IYBdhLWcg3wrIuR#11165118。 - Bill Karwin