Chyba każdy programista tworzący dynamiczne strony internetowe w PHP zetknął się z problemem zaimplementowania struktury drzewiastej w bazie danych. Najczęściej ma to związek z konstrukcją menu, ale każdy serwis WWW jest właściwie o taką strukturę oparty.
Ja do niedawna konstruowałam takie struktury w oparciu o jedną tabelę rekurencyjną. Każdy rekord zawierał pole informujące wskazujące na rekord rodzica. Dla wygody stosowałam jeszcze pole ‘order’ którego wartość decydowała o kolejności elementów w sytuacji gdy jeden rodzic miał wielu potomków. Przykładowe drzewo, oraz tabela zawierająca jego dane przedstawione zostały na poniższych rysunkach:
Taka konstrukcja drzewa jest prosta do zaimplementowania i łatwo jest wyciągnąć informacje dotyczące potomków pierwszego rzędu mając informację o identyfikatorze rodzica. Zapytania są proste i wykonują się szybko. Bez problemu można też przenosić całe gałęzie z jednego do innego rodzica. Wymaga to tylko zmiany wartość identyfikatora rodzica w jednym rekordzie, no i ewentualnie przeliczenia wartości pola ‘order’ dla niektórych rekordów.
Niestety ten sposób ma poważne wady. Chcąc odtworzyć całe drzewo, albo wybraną gałąź trzeba wczytać wszystkie rekordy, albo skonstruować skomplikowane zapytanie a następnie przeprowadzić skomplikowane odtwarzanie struktury w skrypcie PHP. Zabierając się do mojego nowego projekty postanowiłam zgłębić temat. Natknęłam się, między innymi na stronę Huberta Lubaczewskiego (alias depesh) na której skrótowo przedstawiono tam idee różnych rozwiązań, oraz ich wady i zalety. Świetny materiał jeśli trzeba dokonać wyboru metody.
Mój wybór padł na metodę nested sets, ale o tym będę pisać w następnym artykule z tej serii.
Podobne artykuły:
- Struktura drzewiasta w bazie danych Odc. 6 Nested set – przenoszenie gałęzi
- Struktura drzewiasta w bazie danych Odc. 5 Nested set – dodawanie rekordu
- Struktura drzewiasta w bazie danych Odc. 4 Nested set – odczytywanie gałęzi
- Struktura drzewiasta w bazie danych Odc. 3 Nested set – odczytywanie struktury drzewa
- Struktura drzewiasta w bazie danych Odc. 2 Konstrukcja drzewa typu nested set
21 paź 2009 o 22:13
mowisz o czyms takim? http://artykuly.zyxist.com/czytaj.php/drzewa_w_php_i_mysql
tez to implementowalem i calkiem nieźle się sprawuje
21 paź 2009 o 23:05
Dokładnie o takim. Bardzo mi się to rozwiązanie podoba.
22 paź 2009 o 9:18
Witam!
Moim skromnym zdaniem lepiej zainteresować się tzw Drzewami Depesza.
22 paź 2009 o 10:17
To prawda, jest to interesujący sposób rozwiązania problemu. Może kiedyś go wypróbuję
22 paź 2009 o 13:03
Coś takiego zaimplementowalem na aukcjetv.PL, z tym, ze dodalem jeszcze depth . Działa wyienicie szybko!
24 wrz 2011 o 20:01
[...] Teorię można przeczytać tutaj: http://blog.bexlab.pl/struktura-drzewiasta-w-bazie-danych-odc-1/366/ [...]