Sortierung eines Teilbaums in einer Verschlusstabelle hierarchische Datenstruktur

Question

Ich möchte Sie bitten, mir bei der Sortierung der hierarchischen Datenstruktur zu helfen, die als Verschlusstabelle gespeichert ist.

Ich wollte diese Struktur verwenden, um meine Website Menü zu speichern. Alles funktioniert gut, aber das Problem ist, dass ich nicht kenne, wie man den genauen Teilbaum in einer kundenspezifischen Reihenfolge sortiert. Im Moment wird der Baum in der Reihenfolge sortiert, in der die Elemente zur Datenbank hinzugefügt wurden.

Meine Struktur basiert auf Bill Karwin's article über Closure Tabellen und einige andere Beiträge.

Hier ist meine MySQL-Datenbankstruktur mit einigen Demo-Daten:

-- 
-- 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); 

Hier meine SELECT-Abfrage für einen Baum ist:

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 

Für die DEMO-Instanz mit __ROOT_ = 1, die Abfrage bekommt:

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 

Aber was ist, wenn ich zum Beispiel die Reihenfolge von Cat 1.1 und Cat 1.2 ändern muss (entsprechend dem Namen oder einer kundenspezifischen Bestellung)?

Ich habe einige Breadcrumbs-Lösung (wie nach Breadcrumbs sortieren) gesehen, aber ich weiß nicht, wie man sie erzeugt und ändert.

Answer 1

Diese Frage wird häufig nicht nur für Closure Table, sondern auch für andere Methoden zum Speichern hierarchischer Daten gestellt. Es ist nicht einfach in jedem der Designs.

Die Lösung, die ich für Closure Table entwickelt habe, beinhaltet einen zusätzlichen Join. Jeder Knoten in der Baumstruktur verbindet sich mit der Kette seiner Vorfahren wie eine Abfrage vom Typ "Brotkrumen". Verwenden Sie dann GROUP_CONCAT(), um die Breadcrumbs in eine durch Kommas getrennte Zeichenfolge zu reduzieren und die ID-Nummern nach Tiefe in der Struktur zu sortieren. Jetzt haben Sie eine Zeichenfolge, nach der Sie sortieren können.

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

Caveats:

• Die ID-Werte sollen einheitliche Länge haben, denn "1,3" und "1,6" und "1327" gibt möglicherweise nicht die Reihenfolge Sie beabsichtigen, zu sortieren. Aber sortieren würde "001,003" und "001,006" und "001,327". Daher müssen Sie entweder Ihre ID-Werte bei 1000000+ oder alternativ ZEROFILL für Vorgänger und Nachkommen in der Tabelle category_closure verwenden.
• In dieser Lösung hängt die Anzeigereihenfolge von der numerischen Reihenfolge der Kategorie-IDs ab. Diese numerische Reihenfolge der ID-Werte entspricht möglicherweise nicht der Reihenfolge, in der der Baum angezeigt werden soll. Oder Sie möchten die Freiheit, die Anzeigereihenfolge unabhängig von den numerischen ID-Werten zu ändern. Oder Sie möchten, dass die Daten der gleichen Kategorie in mehr als einer Baumstruktur mit unterschiedlichen Anzeigereihenfolgen angezeigt werden.
  Wenn Sie mehr Freiheit benötigen, müssen Sie die Werte für die Sortierreihenfolge getrennt von den IDs speichern, und die Lösung wird noch komplexer. Aber in den meisten Projekten ist es akzeptabel, eine Abkürzung zu verwenden, wobei die doppelte Pflicht der Kategorie-ID als Baum-Anzeigereihenfolge angegeben wird.

---

Re Ihr Kommentar:

Ja, könnten Sie „Geschwister Sortierreihenfolge“ als eine andere Spalte in der Verschlusstabelle speichern, dann diesen Wert anstelle von ancestor um die Brotkrumen String zu bauen. Aber wenn Sie das tun, haben Sie eine Menge Datenredundanz. Das heißt, ein bestimmter Vorgänger wird in mehreren Zeilen gespeichert, eine für jeden davon absteigenden Pfad. Sie müssen also den gleichen Wert für die Sortierreihenfolge der Geschwister in allen diesen Zeilen speichern, wodurch das Risiko einer Anomalie entsteht.

Die Alternative wäre, eine weitere Tabelle zu erstellen, mit nur eine Zeile pro verschiedenen Vorfahren in der Struktur und Join zu dieser Tabelle, um die Geschwisterreihenfolge zu erhalten.

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