Baumstrukturen in einer Nosql-Datenbank

Question

Ich entwickle eine Anwendung für Google App Engine, die BigTable für ihren Datenspeicher verwendet.

Es ist eine Anwendung zum gemeinsamen Schreiben einer Geschichte. Es ist ein sehr einfaches Hobby-Projekt, an dem ich nur zum Spaß arbeite. Es ist Open Source und Sie können es hier sehen: http://story.multifarce.com/

Die Idee ist, dass jeder einen Absatz schreiben kann, der dann von zwei anderen Personen validiert werden muss. Eine Geschichte kann auch in jedem Absatz verzweigt werden, so dass eine andere Version der Geschichte in eine andere Richtung weitergehen kann.

Stellen Sie sich folgende Baumstruktur:

Jede Zahl wäre ein Absatz sein. Ich möchte in der Lage sein, alle Absätze in jeder einzelnen Storyline auszuwählen. Grundsätzlich sind diese einzigartigen Handlungsstränge (2, 7, 2); (2, 7, 6, 5); (2, 7, 6, 11) und (2, 5, 9, 4). Ignoriere, dass der Knoten "2" zweimal erscheint, ich habe einfach ein Baumstrukturdiagramm von Wikipedia genommen.

Ich habe auch ein Diagramm einer vorgeschlagenen Lösung: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

Wie kann ich eine Struktur ist eine effiziente Leistung eingerichtet sowohl für das Schreiben, sondern vor allem zum Lesen?

Answer 1

Es gibt eine Reihe bekannter Methoden, Bäume in Datenbanken darzustellen; Jeder von ihnen hat seine Vor- und Nachteile. Hier sind die häufigsten:

• Adjacency list, wo jeder Knoten die ID seiner Eltern speichert.
• Materialized path, das ist die Strategie Keyur beschreibt. Dies ist auch der Ansatz, der von Entitätsgruppen (z. B. übergeordneten Entitäten) in App Engine verwendet wird. Es ist auch mehr oder weniger das, was Sie in Ihrem Update beschreiben.
• Nested sets, wobei jeder Knoten ‚links‘ und ‚rechts‘ IDs hat, so dass alle untergeordneten Knoten in diesem Bereich enthalten sind.
• Adjazenzliste mit einer Root-ID.

Jeder von diesen hat seine eigenen Vor- und Nachteile. Adjazenzlisten sind einfach und kostengünstig zu aktualisieren, erfordern jedoch mehrere Abfragen, um einen Teilbaum (einen für jeden Elternknoten) abzurufen. Erweiterte Adjazenzlisten ermöglichen das Abrufen eines gesamten Baums, indem die ID des Wurzelknotens in jedem Datensatz gespeichert wird.

Materialized Wege sind einfach zu implementieren und kostengünstig zu aktualisieren, und erlauben beliebige Teilbäume abfragt, sondern verhängen zunehmenden Aufwand für tiefe Bäume.

Verschachtelte Sätze sind härter zu implementieren und Aktualisierung erfordern im Durchschnitt die Hälfte der Knoten jedes Mal, wenn Sie eine Insertion machen. Sie ermöglichen es Ihnen, beliebige Teilbäume abzufragen, ohne dass der materialisierte Pfad eine zunehmende Schlüssellänge aufweist.

In Ihrem speziellen Fall, aber es scheint, wie Sie eine Baumstruktur brauchen eigentlich gar nicht tun: jede Geschichte, ein originelles abgezweigt, obwohl es sein kann, steht für sich allein.Was ich vorschlagen würde, ist ein "Story" -Modell, das eine Liste von Schlüsseln seiner Absätze enthält (zB in Python eine db.ListProperty (db.Key)). Um eine Story zu rendern, rufen Sie die Story ab und führen dann einen Batch-Abruf für alle Absätze durch. Um eine Geschichte zu verzweigen, dupliziere einfach den Story-Eintrag - die Verweise auf Paragraphen bleiben unverändert.

Answer 2

Eine Lösung, an die ich denken kann, ist - der Pfad zum Knoten ist auch der Schlüssel dieses Knotens. Also ist der Schlüssel des Knotens 11 "2/7/6/11". Sie können den Pfad durch eine einfache Schlüsselsuche aller Schlüssel im Pfad durchlaufen - "2/7/6/11", "2/7/6", "2/7", "2"