Struktura drzewiasta w bazie danych Odc. 1

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:
tree_02

tree_01

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.

6 komentarzy do wpisu „Struktura drzewiasta w bazie danych Odc. 1”

Leave a Reply

%d bloggers like this: