Jak reprezentować strukturę podobną do drzewa w db

Zaczynam projekt i jestem w fazie projektowania: tzn. nie zdecydowałem jeszcze, na którym frameworku db będę używał. Będę miał kod, który tworzy strukturę podobną do "lasu". Oznacza to, że wiele drzew, gdzie każde drzewo jest standardem: węzły i krawędzie. Po tym jak kod utworzy te drzewa chcę je zapisać w db. (a potem w końcu je wyciągnąć)

Naiwnym podejściem do reprezentowania danych w db jest relacyjny db z dwiema tabelami: węzłami i krawędziami. Czyli tabela węzłów będzie miała identyfikator węzła, dane węzła itp.. A tabela krawędzi będzie mapowaniem identyfikatora węzła do identyfikatora węzła.

Czy jest lepsze podejście? Czy biorąc pod uwagę (ograniczone) założenia, które podaję, jest to najlepsze podejście? A jeśli dodamy założenie, że drzewa są stosunkowo małe - czy lepiej zapisać całe drzewo jako blob w db? Jakiego typu db powinienem użyć w tym przypadku? Proszę skomentować szybkość / skalowalność.

Thanks

Author: Bill Karwin, 2011-07-04

2 answers

Pokazałem rozwiązanie podobne do tabel węzły i krawędzie, w mojej odpowiedzi na pytanie StackOverflow: Jaki jest najbardziej efektywny / elegancki sposób parsowania płaskiej tabeli w drzewo? nazywam to rozwiązanie "tabelą zamknięcia".

Zrobiłem prezentację na temat różnych metod przechowywania i korzystania z drzew w SQL, Modele danych hierarchicznych z SQL i PHP . Zademonstrowałem, że przy odpowiednich indeksach (w zależności od zapytań, które trzeba uruchomić) projekt tabeli zamknięcia może mieć Bardzo dobra wydajność, nawet przy dużych kolekcjach krawędzi (około 500K krawędzi w moim demo).

Omówiłem również projekt w mojej książce, Antypatterns SQL: unikanie pułapek programowania baz danych.

 17
Author: Bill Karwin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:34:04

Upewnij się, że używasz jakiegoś niskopoziomowego kodowania dla treedowanej istoty, aby zapobiec zapętleniu. Encja może być częścią, tematem, folderem itp.

Za pomocą pliku encji oraz Pliku encji-Xref można zapętlić jedną z powiedzmy dwóch relacji między dwoma plikami, relacją rodzica i potomka.

Poziom to poziom encji znaleziony w drzewie. Kod niskiego poziomu dla encji jest najniższym poziomem encji znalezionym w dowolnym drzewie w dowolnym miejscu. Sprawdź, czy kod niskiego poziomu element, który chcesz utworzyć, jest mniejszy lub równy, aby zapobiec pętli. po dodaniu encji jako dziecka stanie się ona co najmniej o jeden poziom niższa.

 1
Author: eric,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-04-01 19:54:20