Сортировка поддерева в иерархической структуре данных закрывающей таблицы

Question

Я хотел бы попросить вас помочь мне решить проблему с сортировкой иерархической структуры данных, хранящейся в виде таблицы закрытия.

Я хотел использовать эту структуру для хранения меню моего сайта. Все отлично работает, но проблема в том, что я не знаю, как отсортировать точное поддерево в произвольном порядке. На данный момент дерево отсортировано в порядке, в котором элементы были добавлены в базу данных.

Моя структура основана на статье Билла Карвина о таблицах закрытия и некоторых других постах.

Вот моя структура базы данных 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

Для экземпляра DEMO с __ROOT_ = 1 этот запрос получает:

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, но и для других методов хранения иерархических данных. Это не легко в любом из проектов.

Решение, которое я придумал для Closure Table, включает одно дополнительное соединение. Каждый узел дерева присоединяется к цепочке своих предков, как запрос типа "хлебные крошки". Затем используйте GROUP_CONCAT(), чтобы свернуть панировочные сухари в строку, разделенную запятыми, сортируя номера идентификаторов по глубине в дереве. Теперь у вас есть строка, по которой вы можете сортировать.

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+, либо использовать ZEROFILL для предка и потомка в таблице category_closure.
• В этом решении порядок отображения зависит от числового порядка идентификаторов категорий. Этот числовой порядок значений идентификаторов может не соответствовать порядку отображения дерева. Или вы можете захотеть изменить порядок отображения независимо от числовых значений идентификатора. Или вы можете захотеть, чтобы одни и те же данные категории появлялись в более чем одном дереве, каждое с разным порядком отображения.
  Если вам нужно больше свободы, вам нужно хранить значения порядка сортировки отдельно от идентификаторов, и решение становится еще более сложным. Но в большинстве проектов допустимо использовать ярлык с двойной обязанностью идентификатора категории в качестве порядка отображения дерева.

---

Re ваш комментарий:

Да, вы можете сохранить "порядок сортировки по одному брату" как другой столбец в таблице замыканий, а затем использовать это значение вместо 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         |
+----+------------+--------+---------+-------------+