Szanowni Forumowicze,
Mam problem z drzewem kategorii Nestes Set Model, a dokładnie z sortowaniem. Wychodzą mi jakieś "kulfony", a nie znam się, niestety, zbyt dobrze na (My)SQL i dlatego proszę Was o pomoc.
Otóż chodzi, o coś z pozoru niezmiernie prostego, mamy np. tabele z atrybutami:
id | name(VARCHAR) | time_add(DATA) | last_change(DATA) | lft | rgt

Otóż, dla wyświetlenia pełnego drzewa z wyróżnieniem poziomów używam zapytania:

[SQL] pobierz, plaintext 
SELECT CONCAT( REPEAT( '-', COUNT( parent.name ) -1 ) , node.name ) AS name FROM nastedcategories 
AS node, nastedcategories AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY node.name ORDER BY  node.lft;
[SQL] pobierz, plaintext 

Jest, to zapytanie ze świetnego artykułu ze strony: http://dev.mysql.com/tech-resources/articl...hical-data.html

To mi sortuje po polu name, a gdybym chciał posortować po polu time_add? Które jest datą. Jak, to osiągnąć?

Dziękuję,
T.

P.S. Nie zamieszczam moich wypocin, ponieważ zaśmiecę nimi tylko wątek, a zależy mi na jego przejrzystości, ale jeżeli ktoś potrzebuje więcej informacji, to uprzejmie proszę o informację co mam zamieścić.
P.S.2. Dla ułatwienia pracy wrzucę przykładową tabelę(eksport z PHPMyAdmin):
[sql]--
-- Struktura tabeli dla `nastedcategories`
--

CREATE TABLE IF NOT EXISTS `nastedcategories` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(50) CHARACTER SET utf8 COLLATE utf8_polish_ci NOT NULL,
`time_add` timestamp NULL DEFAULT NULL,
`tlast_change` timestamp NULL DEFAULT NULL,
`lft` int(11) NOT NULL,
`rgt` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=28 ;

--
-- Zrzut danych tabeli `nastedcategories`
--

INSERT INTO `nastedcategories` (`id`, `name`, `time_add`, `tlast_change`, `lft`, `rgt`) VALUES
(1, 'ddd', '2011-03-08 22:27:09', '2011-03-10 22:27:18', 1, 24),
(2, 'aaa', '2011-03-01 22:27:30', '2011-03-03 22:27:34', 25, 28),
(3, 'bbb', '2011-03-03 22:27:41', '2011-03-02 22:27:44', 29, 38),
(4, 'ccc', '2011-03-01 22:27:48', '2011-03-17 22:27:53', 39, 42),
(5, 'eee', '2011-03-03 22:28:06', '2011-03-17 22:28:08', 43, 48),
(6, 'fff', '2011-03-05 22:28:10', '2011-03-09 22:28:13', 49, 50),
(7, 'ggg', '2011-03-13 22:28:29', '2011-03-15 22:28:33', 36, 37),
(8, 'hhh', '2011-03-14 22:28:35', '2011-03-16 22:28:37', 32, 35),
(9, 'iii', '2011-03-22 22:28:49', '2011-03-23 22:28:53', 30, 31),
(10, 'jjj', '2011-03-21 22:28:56', '2011-03-22 22:29:01', 33, 34),
(11, 'kkk', '2011-03-09 22:29:16', '2011-03-11 22:29:19', 22, 23),
(12, 'lll', '2011-03-01 22:29:32', '2011-03-03 22:29:34', 10, 21),
(13, 'mmm', '2011-03-05 22:29:45', '2011-03-16 22:29:49', 26, 27),
(14, 'nnn', '2011-03-03 22:31:26', '2011-03-17 22:31:28', 8, 9),
(15, 'ooo', '2011-03-15 22:31:46', '2011-03-17 22:31:49', 4, 7),
(16, 'ppp', '2011-03-18 22:31:55', '2011-03-19 22:31:59', 2, 3),
(17, 'qqq', '2011-03-22 22:32:03', '2011-03-23 22:32:05', 11, 20),
(18, 'rrr', '2011-03-29 22:32:50', '2011-03-31 22:32:52', 5, 6),
(19, 'sss', '2011-03-01 22:32:55', '2011-03-03 22:32:58', 18, 19),
(20, 'ttt', '2011-03-11 22:33:01', '2011-03-23 22:33:03', 14, 17),
(21, 'uuu', '2011-03-14 22:33:09', '2011-03-18 22:33:11', 12, 13),
(22, 'www', '2011-03-01 22:33:17', '2011-03-04 22:33:19', 15, 16),
(23, 'xxx', '2011-03-17 22:33:25', '2011-03-19 22:33:27', 44, 47),
(24, 'yyy', '2011-03-26 22:33:35', '2011-03-30 22:33:37', 40, 41),
(25, 'zzz', '2011-03-19 22:33:52', '2011-03-23 22:33:59', 45, 46),
(26, 'żżż', '2011-03-11 22:34:06', '2011-03-14 22:34:09', 53, 54);

Struktura NestedSet ma jak każda inna pewne wady i zalety. Jedną z jej wad jest fakt, że pobierane dane muszą być posortowane wg klucza LEFT by móc w ogóle utworzyć drzewko. Tak więc nie ma możliwości posortowania go na poziomie zapytania SQL.
Dopiero po pobraniu i utworzeniu drzewka musisz je posortować (na poziomie aplikacji - np. PHP).

Swoją drogą mimo iż taka struktura wymaga jedynie kluczy LEFT i RIGHT proponuję dodać PARENT_ID (oczywiste) oraz DEPTH (czyli poziom zagłębienia danego węzła względem roota). Koszt dodania takich dwóch kolumn jest zerowy, a w wielu przypadkach pozwalają one na łatwiejsze / lżejsze przetwarzanie danych.

Bardzo dziękuję za odpowiedź, nie spodziewałem się aż tak szybkiej reakcji.


Tego się właśnie obawiałem. A zna Pan jakiś szybki mechanizm takiego sortowania(gdyby, to była zwykła lista bez poziomów, to łatwizna, ale tutaj...) w PHP?
Zrobiłem kiedyś taki swój wraz z modelem drzewa kategorii, ale za przeproszeniem, był on skrajnie debilny. Zamulał jak leniwiec po obfitym obiedzie, w porze snu i 40C upale na pustyni.

Prosiłbym chociaż o jakąś podpowiedź co wpisać w google.

Pozdrawiam,
T.

Tak jak wspomniał poprzednik. Kolumna LEFT determinuje sposób sortowania. Miałem kiedyś podobny problem. Kolega wyżej proponuje sortowanie po stronie kodu PHP. Ja do tego podszedłem zgoła inaczej. Dla każdego atrybutu (kolumny) po którym chcę sortować (nazwa, czas etc.) tworzę osobną parę parametrów LEFT i RIGHT. Wymaga to więcej pracy po stronie bazy przy konstrukcji drzewa (polecam użycie procedury składowanej i tabeli tymczasowej trzymanej w pamięci engine typu MEMORY).

Przecież to jest zwykła "lista hierarchiczna" - czyli kilka zagnieżdżonych w sobie list. Każdą listę sortujesz z osobna, sprawdzasz czy ma ona w sobie kolejną zagnieżdżoną listę i jeżeli tak to sortujesz i ją - typowa rekurencja.

Co do szybkości... ile elementów będzie miało to drzewko? 50, 100, 500 tysięcy? Przecież posortowanie kilkudziesięciu czy kilkuset elementów nawet przy wykorzystaniu wolnego algorytmu będzie szybkie. A co do samych algorytmów - jest ich cała masa, ale w tym przypadku wątpię czy będzie jakaś zauważalna różnica pomiędzy nimi.

Czyli chodzi o, to że przy sortowaniu inną metodą niż na lft tworzysz tabelę(obliczasz wszystkie lft i rgt) na nowo tylko, że trzymasz ją"tymczasowo"? Tylko jak jest dużo wejśc na stronę, to wydajność raczej sporo spada, a jakby zrobić, to od razu, po każdym "sortowalnym" atrybucie zrobić atrybuty lft i rgt? Chodzi, o to:
id | name | name_lft | name_rgt | time_add | time_add lft | time_add rgt | ...
I przy każdym update, insert, delete zmieniać każde lft i rgt? Baza zamula praktycznie tylko przy zmianie jej zawartości, a nie przy odczycie. Mogę prosić o opinię na temat tego pomysłu? I dziękuję za podpowiedzi.


Dziękuję za nazwanie tego, to już pomoże. Zrobiłem właśnie taką funkcję rekurencyjną, tylko wydawał mi się, to lichy sposób, a chciałem żeby funkcja działał ość szybko nawet przy dużo więcej niż 100tys. rekordów. Ale przyznam się, nie jest mi, to zbytnio potrzebne. To byłoby tylko w celach "akademickich".
Dziękuję za podpowiedzi. Najwyżej wrzucę do tego moją starą funkcyję.

Dokładnie to miałem na myśli. Wszystkie pary atrybutów trzeba wyliczać przy zapisach, a nie odczytach. Robienie tego przy odczytach byłoby samobójstwem.



Ogólna zasada mówi, że to co można zrobić w bazie należy robić w bazie. Ale tak jak wyżej napisano - wszystko zależy na jakich zbiorach chcesz operować. Przy małych sposób i miejsce sortowania nie będzie miało znaczenia, przy dużych zbiorach znaczenie będzie miało ogromne.

Kategorie to względnie małe zbiory - z reguły do kilkudziesięciu elementów, tak więc darowałbym sobie zaśmiecanie bazy konstrukcjami typu [NAME|CREATED_AT|MODIFIED_AT]_[LEFT|RIGHT], a sortowanie wykonał po stronie aplikacji - szybko, dużo elastyczniej i wygodniej. W końcu ile tego jest...

[PHP] pobierz, plaintext 
$tree = ...;
 
$compareBy = 'title';
usort($tree, function($a, $b) use($compareBy) {
  return strcmp($a[$compareBy], $b[$compareBy]);
});
[PHP] pobierz, plaintext 

Jeżeli pobranie i przetworzenie drzewka jest aż tak kosztowe to przecież możesz sobie wygenerowane drzewko zapisać w pamięci i przy następnych odwołaniach wyciągnąć już gotowe.

PS. Ahh... to sortowanie to rekurencyjnie trzeba zrobić, ale to nie problem przerobić.

Właśnie dostałem też taką radę w innym miejscu, chyba jednak zrobię, to w bazie.


Jak ja się cieszę, że nie zdążyłem zamieścić wcześniej swojego kodu:-) Dzięki. Postanowiłem robić już wszystko na bazie, ale z ciekawości spróbuję dostosować ten kod do Kohana 3(jak na razie trzeba konwertować wynik ...->execute() na "zwykłą" tablicę, ponieważ nie wykrywa, że jest, to tablica, pomimo, że jak ją traktuje w innych miejscach jako tablicę, to działa. Sama potrzeba konwersji już nie jest ok. ). Na razie i tak nie sortuje mi tablicy, spróbuję dojść dlaczego.