Home > Bazy danych > Jak implementować drzewo w bazie danych?

Jak implementować drzewo w bazie danych?

Drzewo w bazie danych to jeden z problemów, o których fajnie się dyskutuje na studiach. Istnieje wiele sposobów implementacji drzewa, znany hacker Depesz wymienił 5. Niestety, często zapomina się o najważniejszych i najprostszych metodach. Żadnych identyfikatorów rodzica. Tylko ścieżka – która jest opisana tekstowo. Lub identyfikator rodzica i ścieżka. Na przykład:

Identyfikator rekordu

Identyfikator rodzica

Ścieżka

1

 

0001

2

1

0001 / 0002

3

1

0001 / 0003

4

3

0001 / 0003 / 0004

5

3

0001 / 0003 / 0005

6

1

0001 / 0006

7

1

0001 / 0007

 

Jakie są zalety takiego rozwiązania? Prostota implementacji, błyskawiczne wyszukiwanie potomków, szybkie wyszukiwanie rodziców, miłe przeglądanie bazy w konsoli SQL, szybkie sortowanie. Oczywiście, gdy potrzebujemy sortowania to należy użyć dodatkowego identyfikatora kolejności, na przykład:

Identyfikator rekordu

Identyfikator rodzica

Kolejność

Ścieżka # Kolejność

1

 

1

0001 # 0001

2

1

2

0001 / 0002 # 0002

3

1

1

0001 / 0003 # 0001

4

3

1

0001 / 0003 / 0004 # 0001

5

3

2

0001 / 0003 / 0005 # 0002

6

1

3

0001 / 0006 # 0003

7

1

4

0001 / 0007 # 0004

 

Zestawienie zalet i wad rozwiązanie z ścieżką:

  • Wady
    • Więcej miejsca na dysku
  • Zalety
    • Prosta implementacja
    • Prostota modelu
    • Błyskawiczne wyszukiwanie potomków
    • Szybkie wyszukiwanie rodziców
    • Szybkie sortowanie
    • Miłe przeglądanie bazy w trybie administratora

Czy są lepsze rozwiązania? Oczywiście. Wystarczy wprowadzić założenie, że w naszym drzewie może być tylko kilka poziomów zagłębienia i liczba ta jest określona przez programistę systemu. Wtedy, w bazie danych możemy zapisywać informację w następujący sposób:

Identyfikator rekordu

Rodzic poziom 1

Rodzic poziom 2

Kolejność

1

  

1

2

1

 

2

3

1

 

1

4

1

3

1

5

1

3

2

6

1

 

3

7

1

 

4

 

W świecie prawdziwych problemów, często właśnie ta trywialna implementacja drzewa będzie najlepsza: jest najprostsza w implementacji i jest rewelacyjnie szybka. Przykłady kodu:

Moim zdaniem, najprostsze rozwiązanie jest zwykle najlepsze.

Categories: Bazy danych Tags:
  1. w
    April 22nd, 2009 at 20:06 | #1

    sprobuj w takim rozwiazaniu przeniesc jakas galaz drzewa (z dziecmi) z jednego rodzica do drugiego.

  2. April 23rd, 2009 at 07:17 | #2

    @w to rzeczywiście jest wadą. Operacje przenoszenia rekordów pomiędzy gałęziami będą wolniejsze. Jednak operacje odczytu rekordów są szybsze. Coś za coś. Szybki odczyt kosztem wolnej aktualizacji.

  3. May 11th, 2009 at 07:40 | #3

    Mając identyfikator rodzica i procedurę tworzącą “ścieżkę” da się to bardzo prosto zrobić.

    PseudoSQL z głowy, więc pewnie będzie wymagał dopracowania:

    UPDATE drzewo SET rodzic = 7 where id = 2; // 0001 / 0002
    UPDATE drzewo SET sciezka = nowa_sciezka( id ) WHERE sciezka LIKE ’0001 / 0002%’;

  4. May 11th, 2009 at 09:54 | #4

    @Diabl0 – dzięki za podpowiedź, w ten sposób rzeczywiście można aktualizować gałęzie – “LIKE %” rządzi. Jednak, w opisanym przeze mnie rozwiązaniu, żeby przenosić gałęzie to trzeba aktualizować wiele rekordów. To jest wadą mojego rozwiązania. Zaletą mojego rozwiązania ze ścieżką, jest jednak szybkość odczytu, sortowanie itp. PS. to właśnie Twój artykuł zainspirował mnie do mojego artykułu: http://diabl0.gazeta.ie/2009/03/drzewo-depesza-w-mysql/. Jednak MySQL mnie nie interesuje więc odwołałem się do Depesza. To moja forma polemiki – ciężki rozwiązania kontra lekkie rozwiązania.

  1. No trackbacks yet.

Subscribe without commenting