Struktura bazy danych dla struktury danych drzewa

151

Jaki byłby najlepszy sposób na zaimplementowanie konfigurowalnej (tj. Struktury drzewiastej z nieznaną liczbą poziomów) struktury danych w bazie danych?

Zrobiłem to raz, zanim użyłem tabeli z kluczem obcym do siebie.

Jakie inne implementacje widzisz i czy ta implementacja ma sens?

CodeMonkey1313
źródło

Odpowiedzi:

80

Wspominasz o najczęściej wdrażanym, jakim jest Lista sąsiedztwa: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets

Istnieją również inne modele, w tym zmaterializowana ścieżka i zestawy zagnieżdżone: http://communities.bmc.com/communities/docs/DOC-9902

Joe Celko napisał książkę na ten temat, która jest dobrym punktem odniesienia z ogólnej perspektywy SQL (wspomina o tym link do zagnieżdżonego artykułu powyżej).

Ponadto Itzik Ben-Gann w swojej książce „Inside Microsoft SQL Server 2005: T-SQL Querying” ma dobry przegląd najczęściej używanych opcji.

Najważniejsze kwestie do rozważenia przy wyborze modelu to:

1) Częstotliwość zmian struktury - jak często zmienia się faktyczna struktura drzewa. Niektóre modele zapewniają lepszą charakterystykę aktualizacji struktury. Ważne jest jednak, aby oddzielić zmiany struktury od innych zmian danych. Na przykład możesz chcieć modelować schemat organizacyjny firmy. Niektóre osoby modelują to jako listę kontaktów, używając identyfikatora pracownika do powiązania pracownika z jego przełożonym. Jest to zwykle podejście nieoptymalne. Podejściem, które często działa lepiej, jest modelowanie struktury organizacyjnej oddzielonej od samych pracowników i utrzymywanie pracownika jako atrybutu struktury. W ten sposób, kiedy pracownik odchodzi z firmy, sama struktura organizacyjna nie musi się zmieniać, a jedynie skojarzenie z pracownikiem, który odszedł.

2) Czy drzewo jest ciężkie do zapisu, czy do odczytu - niektóre struktury działają bardzo dobrze podczas odczytywania struktury, ale powodują dodatkowe obciążenie podczas zapisywania do struktury.

3) Jakie rodzaje informacji musisz uzyskać ze struktury - niektóre struktury są doskonałe w dostarczaniu pewnego rodzaju informacji o strukturze. Przykłady obejmują znalezienie węzła i wszystkich jego elementów podrzędnych, znalezienie węzła i wszystkich jego rodziców, znalezienie liczby węzłów podrzędnych spełniających określone warunki itp. Musisz wiedzieć, jakie informacje będą potrzebne ze struktury, aby określić strukturę, która najlepiej pasuje Twoje potrzeby.

JeremyDWill
źródło
Witam, mam dokładnie ten sam problem, co w pytaniu i chciałbym zadać Ci pytanie dotyczące powyższych tematów. Biorąc pod uwagę strukturę, jak w temacie numer jeden (organizacyjna tabela strukturalna (nie strukturalna dla pracowników) z odwołaniem ParentId w tej samej tabeli), muszę ustawić, kto jest szefem określonego obszaru. Przydzielę bezpośrednio do niego wszystkich pracowników danego obszaru. Gdzie umieściłbyś szefa tego konkretnego obszaru? W tym samym obszarze czy w jednej grupie powyżej? Moje podejście polega na odesłaniu go do powyższej grupy, co moim zdaniem daje mi lepszą strukturę. Dzięki.
Marcos Buarque
1
Wydaje się, że pierwszy link jest uszkodzony.
Jorge Leitao
Doskonała odpowiedź. Dzięki @JeremyDWill!
bobocopy
56

Spojrzeć Zarządzanie hierarchicznych danych w MySQL . Omawia dwa podejścia do przechowywania i zarządzania danymi hierarchicznymi (podobnymi do drzewa) w relacyjnej bazie danych.

Pierwsze podejście to model listy przylegania, który jest tym, co w zasadzie opisujesz: posiadanie klucza obcego, który odnosi się do samej tabeli. Chociaż to podejście jest proste, może być bardzo nieefektywne w przypadku niektórych zapytań, takich jak budowanie całego drzewa.

Drugie podejście omówione w artykule to model zbioru zagnieżdżonego. Takie podejście jest znacznie bardziej wydajne i elastyczne. Zapoznaj się z artykułem, aby uzyskać szczegółowe wyjaśnienia i przykładowe zapytania.

Ayman Hourieh
źródło
Twój link ma bardzo interesujący temat, który jest omawiany. dzięki!
Fritz
9

Jeśli musisz używać Relational DataBase do organizowania struktury drzewiastej, Postgresql ma moduł cool ltree, który zapewnia typ danych do reprezentowania etykiet danych przechowywanych w hierarchicznej strukturze drzewiastej. Stamtąd możesz wziąć pomysł (więcej informacji: http://www.postgresql.org/docs/9.0/static/ltree.html )

W powszechnym przypadku LDAP służy do organizowania rekordów w strukturze hierarchicznej.

yurilo
źródło
2

Posiadanie stolika z obcym kluczem ma dla mnie sens.

Następnie możesz użyć wspólnego wyrażenia tabeli w języku SQL lub połączyć za pomocą wcześniejszej instrukcji w Oracle, aby zbudować drzewo.

Aaron Daniels
źródło
Mam tabelę dziennika z kolumną tożsamości LogID i kolumną ParentLogID z FK, który wskazuje z powrotem na kolumnę LogID. Kiedy zapisywany jest pierwszy wiersz dziennika transakcji, chwytam SCOPE_IDENTITY (). Wszystkie inne rekordy dziennika są zapisywane z tą wartością w kolumnie ParentLogID. Jest to naprawdę przydatne do grupowania wierszy, które należą do siebie. To jedyny prawdziwy sposób, aby zobaczyć, co się stało, bez tego byłby to ogromny bałagan wierszy dziennika z wielu transakcji, wszystkie pomieszane razem.
KM.
@KM - Powiedział „ma sens”, a nie „nie ma sensu”
John Rasch
1

Użyłem następującej implementacji na serwerze SQL SERVER 2005. Sprawdź tutaj

emzero
źródło