Struktury drzewiaste w bazie nosql

Rozwijam aplikację dla Google App Engine, która używa BigTable do swojego magazynu danych.

To aplikacja o pisaniu artykułu. To bardzo prosty projekt hobby, nad którym pracuję dla Zabawy. Jest to open source i można go zobaczyć tutaj: http://story.multifarce.com/

Chodzi o to, że każdy może napisać akapit, który następnie musi zostać zatwierdzony przez dwie inne osoby. Historię można również rozgałęziać w dowolnym akapicie, tak aby inny wersja historii może być kontynuowana w innym kierunku.

Wyobraź sobie następującą strukturę drzewa:

Każda liczba będzie akapitem. Chcę być w stanie wybrać wszystkie akapity w każdym unikalnym wątku. Zasadniczo te unikalne linie fabularne to (2, 7, 2); (2, 7, 6, 5); (2, 7, 6, 11) oraz (2, 5, 9, 4). Ignoruj, że węzeł " 2 " pojawia się dwa razy, właśnie wziąłem diagram struktury drzewa z Wikipedii.

Zrobiłem też schemat proponowanego rozwiązania: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

Jak skonfigurować strukturę czy wydajność jest efektywna zarówno do pisania, ale co najważniejsze do czytania?

Author: Community, 2010-07-19
Source

2 answers

Istnieje wiele znanych sposobów reprezentowania drzew w bazach danych; każdy z nich ma swoje plusy i minusy. Oto najczęstsze:

  • Adjacency list , gdzie każdy węzeł przechowuje ID swojego rodzica.
  • zmaterializowana Ścieżka, którą opisuje klucz strategii. Jest to również podejście stosowane przez grupy jednostek (np. jednostki macierzyste) w silniku aplikacji. Jest to również mniej więcej to, co opisujesz w swojej aktualizacji.
  • zagnieżdżone zbiory , gdzie każdy węzeł ma ID 'lewy' i 'prawy', tak że wszystkie węzły potomne są zawarte w tym zakresie.
  • Adjacency lists agumented with a root ID.

Każdy z nich ma swoje wady i zalety. Listy przylegające są proste i tanie w aktualizacji, ale wymagają wielu zapytań do pobrania poddrzewa (po jednym dla każdego węzła nadrzędnego). Rozszerzone listy przylegające umożliwiają pobieranie całego drzewa, przechowując ID węzła głównego w każdym rekordzie.

Zmaterializowane ścieżki są łatwe do wdrożenia i tanie w aktualizacji, i pozwalają na zapytania dowolnych podtypów, ale nakładają rosnące koszty ogólne dla głębokich drzew.

Zagnieżdżone zestawy są trudniejsze do zaimplementowania i wymagają średnio aktualizacji połowy węzłów za każdym razem, gdy wstawiasz. Pozwalają one na odpytywanie dowolnych podzbiorów, bez rosnącego problemu z długością klucza zmaterializowana ścieżka ma.

W twoim konkretnym przypadku wydaje się jednak, że w ogóle nie potrzebujesz struktury drzewa: każda historia, rozgałęziona oryginał, choć może być, stoi sam. Sugerowałbym posiadanie modelu "Story", który zawiera listę kluczy jego akapitów (np. w Pythonie db.ListProperty (db.Klucz)). Aby renderować wątek, pobierasz wątek, a następnie wykonujesz pobieranie wsadowe dla wszystkich akapitów. Aby wyodrębnić wątek, po prostu zduplikuj wpis wątku - pozostawiając odniesienia do akapitów bez zmian.

 16
Author: Nick Johnson,
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
2010-07-20 09:05:30

Jedno rozwiązanie, o którym myślę, to - ścieżka do węzła jest również kluczem tego węzła. Klucz węzła 11 to "2/7/6/11". Możesz przemierzać ścieżkę za pomocą prostego wyszukiwania wszystkich klawiszy w ścieżce - "2/7/6/11", "2/7/6", "2/7", "2"

 0
Author: Keyur,
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
2010-07-19 18:54:07