Sortowanie poddrzewa w hierarchicznej strukturze danych tabeli zamknięcia

Question

Chciałbym prosić o pomoc w rozwiązaniu problemu z hierarchiczną strukturą danych przechowywaną jako w tabeli 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 sortować dokładnie podtree w niestandardowej kolejności. W tej chwili drzewo jest sortowane w kolejności, w jakiej pozycje zostały dodane do bazy danych.

Moja struktura opiera się na Bill Karwin's article o tabelach zamknięcia i kilku innych postach.

Oto moja baza danych struktura MySQL z niektórymi 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); 

Tu jest mój kwerendę wybierającą na jednym drzewie:

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 

Na przykład DEMO z __ROOT_ = 1 zapytanie to:

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 muszę zmienić kolejność Cat 1.1 i Cat 1.2 (według nazwy lub niestandardowej kolejności)?

Widziałem kilka rozwiązań dotyczących bułki tartej (jak sortować za pomocą bułki tartej), ale nie wiem, jak je generować i zmieniać.

Answer 1

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

Rozwiązanie, które wymyśliłem dla tabeli zamknięcia, wymaga jednego dodatkowego sprzężenia. Każdy węzeł w drzewie łączy się z łańcuchem swoich przodków, podobnie jak zapytanie typu "bułka tarta". Następnie użyj GROUP_CONCAT(), aby zwinąć bułkę tartą w ciąg znaków rozdzielany przecinkami, sortując numery identyfikacyjne według głębokości w drzewie. Teraz masz ciąg znaków, który możesz 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   | 
+----+------------+--------+---------+-------------+ 

Ostrzeżenia:

• wartości ID powinien mieć jednolitą długość, ponieważ sortowanie „1.3” i „1,6” i „1327” może nie dać kolejność zamierzają. Ale sortowanie miałoby "001,003" i "001,006" oraz "001,327". Musisz albo zacząć od wartości id 1000000+, albo użyć 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. Ta numeryczna kolejność wartości id może nie odzwierciedlać kolejności wyświetlania drzewa. Lub możesz chcieć zmienić kolejność wyświetlania niezależnie od wartości liczbowych. Lub możesz chcieć, aby dane tej samej kategorii pojawiały się w więcej niż jednym drzewie, z których każdy ma inną kolejność wyświetlania.
  Jeśli potrzebujesz więcej swobody, musisz przechowywać wartości porządku sortowania oddzielnie od identyfikatorów, a rozwiązanie staje się jeszcze bardziej skomplikowane. Ale w większości projektów dopuszczalne jest użycie skrótu, nadającego podwójną rolę id kategorii jako kolejność wyświetlania drzewa.

---

Re Twój komentarz:

Tak, można przechowywać „rodzeństwo porządek” jako innej kolumny w tabeli zamknięcia, a następnie użyć tej wartości zamiast ancestor zbudować ciąg bułką tartą. Ale jeśli to zrobisz, otrzymasz dużo nadmiarowości danych. Oznacza to, że dany przodek jest przechowywany w wielu wierszach, po jednym dla każdej ścieżki od niego pochodzącej. Więc musisz przechowywać tę samą wartość dla porządku sortowania rodzeństwa na wszystkich tych wierszach, co stwarza ryzyko anomalii.

Alternatywą może być utworzenie innej tabeli, z jednym rzędem jeden wiersz na 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   | 
+----+------------+--------+---------+-------------+