在闭包表层次结构数据结构中对子树进行排序 [英] Sorting a subtree in a closure table hierarchical-data structure

问题描述

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

I would like to ask you to help me with the problem with sorting of the hierarchical data structure stored as a closure table.

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

I wanted to use this structure to store my website menu. Everything works fine, but the problem is that I do not know how to sort the exact subtree in a custom order. At the moment the tree is sorted in the order in which the items were added to the database.

我的结构基于 Bill Karwin的文章关于闭包表和其他一些帖子.

My structure is based on Bill Karwin's article about Closure Tables and some other posts.

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

But what if I for example need to change the order of Cat 1.1 and Cat 1.2 (according to name, or some custom order)?

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

I have seen some breadcrumbs solution (how to sort by breadcrumbs), but I do not know how to generate and change them.

推荐答案

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

This question comes up frequently not only for Closure Table but also for other methods of storing hierarchical data. It's not easy in any of the designs.

我为Closure Table提出的解决方案涉及一个额外的联接.树中的每个节点都连接到其祖先链，就像面包屑"类型查询一样.然后使用GROUP_CONCAT()将面包屑折叠成逗号分隔的字符串，并按树中的深度对ID号进行排序.现在您有了一个可以用来排序的字符串.

The solution I've come up with for Closure Table involves one additional join. Every node in the tree joins to the chain of its ancestors, like a "breadcrumbs" type query. Then use GROUP_CONCAT() to collapse the breadcrumbs into a comma-separated string, sorting the id numbers by depth in the tree. Now you have a string by which you can sort.

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表中将ZEROFILL用于祖先和后代.
• 在此解决方案中，显示顺序取决于类别ID的数字顺序. id值的数字顺序可能不代表您要显示树的顺序.或者，您可能希望自由地更改显示顺序，而与数字id值无关.或者您可能希望同一类别数据出现在不止一棵树中，每棵树的显示顺序不同.
  如果需要更大的自由度，则需要将排序顺序值与ID分开存储，解决方案将变得更加复杂.但是在大多数项目中，可以使用快捷方式，将类别ID的双重职责指定为树的显示顺序.

• The id values should have uniform length, because sorting "1,3" and "1,6" and "1,327" might not give the order you intend. But sorting "001,003" and "001,006" and "001,327" would. So you either need to start your id values at 1000000+, or else use ZEROFILL for ancestor and descendant in the category_closure table.
• In this solution the display order depends on the numeric order of category id's. That numeric order of id values may not represent the order you want to display the tree. Or you may want the freedom to change the display order irrespective of the numeric id values. Or you may want the same category data to appear in more than one tree, each with different display order.
  If you need more freedom, you need to store the sort-order values separately from the id's, and the solution gets even more complex. But in most projects, it's acceptable to use a short-cut, giving the category id's double-duty as the tree display order.

发表您的评论

是的，您可以将同级排序顺序"存储为闭合表中的另一列，然后使用该值而不是ancestor来构建面包屑字符串.但是，如果这样做，最终将导致大量数据冗余.就是说，给定的祖先存储在多行中，每条路径都从该行降序存储.因此，您必须在所有这些行上为兄弟排序顺序存储相同的值，这会导致出现异常的风险.

Yes, you could store "sibling sort order" as another column in the closure table, then use that value instead of ancestor to build the breadcrumbs string. But if you do that, you end up with a lot of data redundancy. That is, a given ancestor is stored on multiple rows, one for each path descending from it. So you have to store the same value for sibling sort order on all of those rows, which creates the risk of an anomaly.

另一种方法是创建另一个表，树中每个不同的祖先只有一个行，然后连接到该表以获取同级顺序.

The alternative would be to create another table, with only one row per distinct ancestor in the tree, and join to that table to get the sibling order.

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

这篇关于在闭包表层次结构数据结构中对子树进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！