Struktury drzewa w bazie danych nosql

Question

Zajmuję się tworzeniem aplikacji do Google App Engine, która wykorzystuje BigTable do przechowywania danych.

Jest to aplikacja do wspólnego pisania opowiadania. To bardzo prosty projekt hobby, nad którym pracuję tylko dla zabawy. Jest open source i możesz 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. Opowiadanie może być również rozgałęzione w dowolnym akapicie, aby inna wersja historii mogła być kontynuowana w innym kierunku.

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

Każdy numer będzie pkt. Chcę móc wybrać wszystkie akapity w każdej unikalnej linii fabularnej. Zasadniczo te wyjątkowe wątki fabularne to (2, 7, 2); (2, 7, 6, 5); (2, 7, 6, 11) i (2, 5, 9, 4). Zignoruj, że węzeł "2" pojawia się dwa razy, po prostu wziąłem diagram struktury drzewa z Wikipedii.

Ja również schemat proponowanego rozwiązania: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

Jak mogę skonfigurować struktura jest wydajność skuteczna zarówno w formie pisemnej, ale przede wszystkim do czytania?

Answer 1

Istnieje wiele dobrze znanych sposobów reprezentowania drzew w bazach danych; każdy z nich ma swoje wady i zalety. Oto najczęściej:

• Adjacency list, gdzie każdy węzeł przechowuje identyfikator jego rodzica.
• Materialized path, którą strategię opisuje Keyur. Jest to również podejście stosowane przez grupy jednostek (np. Podmioty nadrzędne) w App Engine. Jest to mniej więcej to, co opisujesz w swojej aktualizacji.
• Nested sets, gdzie każdy węzeł ma identyfikatory "lewo" i "prawo", tak że wszystkie węzły potomne znajdują się w tym zakresie.
• Listy rozgrywane z użyciem identyfikatora użytkownika root.

Każda z nich ma swoje zalety i wady. Listy rozgłoszeniowe są proste i tanie w aktualizacji, ale wymagają wielu zapytań w celu pobrania poddrzewa (po jednym dla każdego węzła nadrzędnego). Rozszerzone listy przyległości umożliwiają odzyskanie całego drzewa poprzez przechowywanie identyfikatora węzła głównego w każdym rekordzie.

Zmaterializowane ścieżki są łatwe do wdrożenia i tanie w aktualizacji oraz umożliwiają wyszukiwanie arbitralnych poddrzew, ale narzucają rosnące obciążenie dla głębokich drzew.

Zestawy zagnieżdżone są trudniejsze w implementacji i wymagają aktualizacji średnio połowy węzłów przy każdym wstawianiu. Pozwalają one na wyszukiwanie dowolnych poddrzew, bez zwiększania długości zmaterializowanej ścieżki długości klucza.

W twoim konkretnym przypadku wydaje się, że w rzeczywistości nie potrzebujesz wcale struktury drzewa: każda historia, niezależnie od tego, jak rozgrywa się oryginał, jest samodzielna.To, co sugerowałbym, to posiadanie modelu "Story", który zawiera listę kluczy w swoich akapitach (np. W Pythonie a db.ListProperty (db.Key)). Aby wyrenderować historię, należy pobrać Historię, a następnie wykonać pobieranie wsadowe dla wszystkich akapitów. Aby rozgłaszać historię, wystarczy powielać wpis do historii - pozostawiając niezmienione odniesienia do akapitów.

Answer 2

Jedno rozwiązanie, o którym mogę pomyśleć to: ścieżka do węzła jest również kluczem tego węzła. Zatem kluczem węzła 11 jest "2/7/6/11". Możesz przemierzyć ścieżkę za pomocą prostego wyszukiwania kluczy wszystkich klawiszy na ścieżce - "2/7/6/11", "2/7/6", "2/7", "2"