Struktura drzewiasta w bazie danych Odc. 2 Konstrukcja drzewa typu nested set

Jak pisałam w poprzednim odcinku dotyczącym drzewek w bazie danych bardzo mi się spodobała idea drzewka typu Nested set, choć niektórzy namawiali mnie do zainteresowania się drzewami Depesza. Może kiedyś. Tymczasem porządkując swoją świeżo nabytą wiedzę i przemyślenia napiszę kilka słów o idei i typu Nested set.

Jak każde rozwiązanie to ma zarówno wady i zalety. Niewątpliwą zaletą jest to, że wszystkie niezbędne informacje mieszczą się w jednej tabeli. Drugą zaletą jest niezwykła łatwość z jaką można wyciągnąć strukturę dowolnie wybranej gałęzi nie martwiąc się o poziom zagłębienia, gdyż nie istnieje tu żaden limit. Przy czym danych wczytanych z bazy nie trzeba już w jakiś szczególny sposób obrabiać na poziomie php. Niewątpliwą wadą jest stopień skomplikowania zapytań, oraz to, że proste operacje jak dodawania, usuwanie i przesuwanie gałęzi wymagają wykonania większej ilości operacji na bazie danych niż w innych metodach.

Zanim się więc podejmie decyzję o zastosowaniu tej metody implementacji struktury drzewiastej trzeba się dobrze zastanowić, czy te wady są aż tak istotne. Jednym słowem trzeba się zastanowić jak będziemy używać tego drzewa. Jeśli przeważa odczytywanie drzewa lub poszczególnych gałęzi, to na pewno warto, bo można to zrobić jednym zapytaniem i minimalną ilością kodu php, a w dodatku można używać cache do przechowywania wyników zapytań co daje dodatkowe korzyści. Jeśli w grę wchodzi częste dodawanie, usuwanie i przesuwanie gałęzi to po pierwsze trzeba się będzie namęczyć przy konstrukcji zapytań, a po drugie będzie ich więcej. Jeśli więc połączenie z bazą danych nie jest szybkie i zapytania nie wykonują się błyskawicznie to może nie warto.

Ja postanowiłam zaimplementować u siebie ten model wprowadzając tylko niewielką modyfikację, z kilku powodów. Po pierwsze lubię się uczyć nowych rzeczy, więc traktuję to trochę jak rozrywkę intelektualną. Po drugie doszłam do wniosku, że u mnie drzewo będzie głównie odczytywana a rzadko modyfikowane, więc liczę na zysk w wydajności.

Pora więc przejść do przedstawienia idei modelu nested set. Posłużę się tym samym drzewem, które posłużyło jako przykład w poprzednim odcinku. Wyobraźmy sobie, że przemierzamy drzewo od lewej do prawej wzdłuż gałęzi tak jak to pokazuje poniższy rysunek. Mijając kolejne węzły numerujemy je kolejnymi liczbami całkowitymi póki nie przejdziemy całego drzewa, tak jak to zostało przedstawione na rysunku poniżej.
drzewo nested set

Tabela w bazie danych wygląda wtedy jak na rysunku poniżej i zawiera absolutnie wszystkie informacje niezbędne do obsługi tej struktury. Dla ułatwienia parametry ‘left’ i ‘right’ nazwałam odpowiednio ‘lft’ i ‘rgt’, żeby uniknąć konfliktu ze słowami kluczowymi LEFT i RGIHT zastrzeżonymi w SQL (jak wiadomo SQL nie rozróżnia wielkich i małych liter).
tabela drzewa nested set

CREATE TABLE IF NOT EXISTS `tree` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` varchar(100) NOT NULL,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM;

INSERT INTO `tree` 
(`id`, `title`, `lft`, `rgt`) 
VALUES
(1, 'root', 1, 20),
(2, 'Windows', 2, 13),
(3, 'Linux', 14, 17),
(4, 'MacOS', 18, 19),
(5, 'Office', 3, 10),
(6, 'InternetExplorer', 11, 12),
(7, 'Iceweasel', 15, 16),
(8, 'Word', 4, 5),
(9, 'Excel', 6, 7),
(10, 'PowerPoint', 8, 9);

Jeśli ktoś nie wierzy to wystarczy poczekać na następny odcinek. Pokażę jak można wykonać wszystkie niezbędne operacje na tak zaimplementowanym drzewie. Postaram się pokazać oryginalne metody jak również różne wygodne modyfikacje.

10 komentarzy do wpisu „Struktura drzewiasta w bazie danych Odc. 2 Konstrukcja drzewa typu nested set”

  1. Z niecierpliwością czekam na dalsze artykuły związane z drzewkami. Sam nie mam czasu się tym zająć ani poczytać dogłebnie, więc twoje informacje są dla mnie przydatne. Tym bardziej że piszesz do rzeczy i na temat.

  4. Osobiście uważam, że powyższe rozwiązanie to koszmar. No… Chyba, że operujemy na 5-10 elementowym drzewku, którego nie chcemy w zasadzie wcale modyfikować. Dużo sensowniejszym rozwiązaniem jest struktura typu:
    ID, parentID, order, name

    Dla powyższego przykładu:
    1, 0, 10, root
    2, 1, 10, Windows
    3, 1, 20, Linux
    4, 1, 30, MacOS
    5, 2, 10, Office
    6, 2, 20, InternetExplorer
    7, 3, 10, Iceweasel
    8, 5, 10, Word
    9, 5, 20, Excel
    10, 5, 30, PowerPoint

    Zalety – w zasadzie wszystkie z Nested Set + prostota zapytań oraz obsługi. Wyświetlanie – prosta rekurencja… Dodając do bazy pole logiczne hasChildren można zmniejszyć ilość zapytań w rekurencji. Kolejność inkrementowana o 10 daje swobodną możliwość roszad w strukturze.

  5. Każda metoda implementacji drzewa ma swoje wady i zalety. Będę o nich, a także o możliwych modyfikacjach tej metody, pisać w następnych artykułach.

    A tak z ciekawości. Jaki algorytm zastosujesz chcąc wyciągnąć z bazy gałąź zaczynającą się od węzła ‘Windows’? Zaręczam Ci, że w zalecanej przez Ciebie metodzie to jest koszmar :)

  6. Coz Joanna, Mitchell ma poniekad racje z tym ze w jego przykladzie bedzie mozna zastosowac 2 rodzaje odczytu danych:
    1. wczytanie wszystkich rekordow z drzewa i ‘zgrupowanie’ ich w tablicy, na koncu ‘wyluskanie’ interesujacej nas galezi np:

    print_r($moje_drzewo[ 2 ]); // dla nazwy ‘windows’

    2. druga metoda to rekurencja czyli odwolywanie sie do tej samej metody.

    Oczywiscie, jak pierwsza moze byc szybsza niz druga (tylko 1 zapytanie do SQL) tak wiaze sie z wieksza ‘zabawa’ w pozniejzej obrobce danych.

    Najlepszym rozwiazaniem przy zlozonych drzewach zawierajacych rekordy powyzej 10tys. jest wprowadzenie ‘hierarchi’ do przykladu Mitchell’a.

    Hierarchia w prostych slowach to zapisanie ‘sciezki galezi’ przy kazdym rekordzie.

    Zalety to super szybkie wyszukiwanie w porownaniu do innych metod, wady natomiast (nie ma rozy bez kolcow) jesli postanowimy przeniesc kategorie pod inna galaz to bedziemy musieli ‘odswierzyc’ ‘sciezke galzi’ w kazdym ‘dziecku’ nalezacym do tej kategorii oraz tabelach kozystajacych z naszej tabeli kategorii. Co wydaje sie niewiele znaczacym problemem (dla dobrze napisanego algorytmu oraz metod praktycznie nie jest to problem)

    Pozdrawiam
    Robert

  7. Ależ ja dostrzegam zarówno wady jak i zalety innych metod. Ta jednak przypadła mi do gustu i postanowiłam ją zgłębić, przestudiować. Może przy okazji innego projektu zainteresuję się inną metodą. Dajcie mi szansę i przejrzyjcie dalsze części serii :)

    Co do trzymania ‘ścieżki gałęzi’ w bazie, to takie metody napawają mnie wstrętem. Po prostu nie znoszę redundancji danych w bazie :)

Leave a Reply

%d bloggers like this: