17

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

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

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

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

4

1 回答 1

18

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

我为 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         |
+----+------------+--------+---------+-------------+
于 2012-12-28T18:53:35.037 回答