Sortowanie poddrzewa w tabeli zamknięcia hierarchiczna struktura danych

Question

Sortowanie poddrzewa w tabeli zamknięcia hierarchiczna struktura danych

Chciałbym prosić o pomoc w problemie z sortowaniem hierarchicznej struktury danych przechowywanej jakotabela zamknięcia .

Chciałem użyć tej struktury do przechowywania menu mojej strony internetowej. Wszystko działa dobrze, ale problem polega na tym, że nie wiem Jak posortować dokładny podzbiór w niestandardowym porządku. W tej chwili drzewo jest posortowane w kolejności, w jakiej pozycje zostały dodane do bazy danych.

Moja struktura oparta jest na artykule Billa Karwina o tablicach zamknięcia i kilku innych postach.

Oto moja struktura bazy danych MySQL z kilkoma danymi 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);

Oto moje zapytanie SELECT dla jednego drzewa:

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

Dla przykładu DEMO z _ _ ROOT _ = 1 zapytanie otrzymuje:

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

Ale co jeśli na przykład będę musiał zmienić kolejność Cat 1.1 i Cat 1.2 (według nazwy, lub jakiegoś niestandardowego porządku)?

Widziałem jakieś rozwiązanie bułki tartej (jak sortować po bułce tartej), ale nie wiedzieć, jak je generować i zmieniać.

13

mysql hierarchical-data transitive-closure-table

Author: Jacco, 2012-12-28

Source

1 answers

score 15 · Accepted Answer

To pytanie pojawia się często nie tylko dla tabeli zamknięcia, ale także dla innych metod przechowywania danych hierarchicznych. Nie jest to łatwe w żadnym z projektów.

Rozwiązanie, które wymyśliłem dla tabeli zamknięcia, obejmuje jedno dodatkowe połączenie. Każdy węzeł w drzewie łączy się z łańcuchem swoich przodków, jak zapytanie typu "bułka tarta". Następnie użyj GROUP_CONCAT (), aby zwinąć bułkę tartą do oddzielonego przecinkami łańcucha, sortując numery id według głębokości w drzewie. Teraz masz sznurek według których można sortować.

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

Zastrzeżenia:

wartości id powinny mieć jednakową długość, ponieważ sortowanie "1,3", "1,6" i "1,327" może nie dać zamierzonej kolejności. Ale sortowanie "001,003" i "001,006 " i" 001,327 " byłoby. Więc albo musisz zacząć wartości id od 1000000+, albo użyj ZEROFILL dla przodka i potomka w tabeli category_closure.
w tym rozwiązaniu kolejność wyświetlania zależy od kolejności numerycznej identyfikatorów kategorii. kolejność wartości id może nie reprezentować kolejności wyświetlania drzewa. Możesz też chcieć swobody zmiany kolejności wyświetlania niezależnie od wartości liczbowych id. Możesz też chcieć, aby DANE tej samej kategorii były wyświetlane w więcej niż jednym drzewie, z których każde ma inną kolejność wyświetlania.
Jeśli potrzebujesz większej swobody, musisz przechowywać wartości sortowania oddzielnie od identyfikatorów, a rozwiązanie staje się jeszcze bardziej złożone. Ale w większości projektów dopuszczalne jest użycie skrótu, dając kategorię id jest podwójnym obowiązkiem jako kolejność wyświetlania drzewa.

Re twój komentarz:

Tak, możesz zapisać "kolejność sortowania rodzeństwa" jako inną kolumnę w tabeli zamknięcia, a następnie użyć tej wartości zamiast ancestor do zbudowania łańcucha bułki tartej. Ale jeśli to zrobisz, skończysz z dużą redundancją danych. Oznacza to, że dany przodek jest przechowywany w wielu wierszach, po jednym dla każdej ścieżki wychodzącej z niego. Więc musisz przechowywać tę samą wartość dla kolejności sortowania rodzeństwa we wszystkich tych wierszach, które stwarza ryzyko anomalii.

Alternatywą byłoby utworzenie innej tabeli, z tylko jednym wierszem na oddzielnego przodka w drzewie i dołączenie do tej tabeli, aby uzyskać kolejność rodzeństwa.

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