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

Question

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

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

我的结构基于Bill Karwin关于Closure Tables 的文章以及其他一些帖子.

这是我的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的顺序(根据名称或某些自定义顺序),该怎么办？

我已经看到了一些面包屑解决方案(如何按面包屑排序),但我不知道如何生成和更改它们.

Answer 1

这个问题不仅经常出现在关闭表中,而且还出现在存储分层数据的其他方法中.在任何设计中都不容易.

我为Closure Table提出的解决方案涉及一个额外的连接.树中的每个节点都连接到其祖先的链,就像"breadcrumbs"类型的查询一样.然后使用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"会.因此,您需要将您的id值设置为1000000+,否则请使用ZEROFILLcategory_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         |
+----+------------+--------+---------+-------------+