Strutture ad albero in un database nosql

Question

Sto sviluppando un'applicazione per Google App Engine che utilizza BigTable per il suo datastore.

È un'applicazione che consente di scrivere una storia in modo collaborativo. È un progetto di hobby molto semplice a cui sto lavorando solo per divertimento. È open source e puoi vederlo qui: http://story.multifarce.com/

L'idea è che chiunque può scrivere un paragrafo, che poi deve essere convalidato da altre due persone. Una storia può anche essere ramificata in qualsiasi paragrafo, in modo che un'altra versione della storia possa continuare in un'altra direzione.

Immaginate la seguente struttura ad albero:

Ogni numero sarebbe un paragrafo. Voglio essere in grado di selezionare tutti i paragrafi in ogni trama unica. Fondamentalmente, quelle linee di storia uniche sono (2, 7, 2); (2, 7, 6, 5); (2, 7, 6, 11) e (2, 5, 9, 4). Ignora che il nodo "2" appare due volte, ho appena preso un diagramma della struttura ad albero da Wikipedia.

Ho anche fatto un diagramma di un soluzione proposta: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

Come posso creare una struttura è la prestazione efficiente sia per la scrittura, ma soprattutto per la lettura?

Answer 1

Ci sono un numero di modi ben noti per rappresentare alberi nei database; ognuno di loro ha i suoi pro e contro. Ecco i più comuni:

• Adjacency list, dove ogni nodo memorizza l'ID del suo genitore.
• Materialized path, che è la strategia che Keyur descrive. Questo è anche l'approccio utilizzato dai gruppi di entità (ad esempio, entità padre) in App Engine. È anche più o meno ciò che stai descrivendo nel tuo aggiornamento.
• Nested sets, in cui ogni nodo ha ID "sinistro" e "destro", in modo tale che tutti i nodi figlio siano contenuti in tale intervallo.
• Elenchi di adjidazione corredati di un ID radice.

Ognuno di questi ha i suoi vantaggi e svantaggi. Gli elenchi di adiacenza sono semplici ed economici da aggiornare, ma richiedono più query per recuperare una sottostruttura (una per ogni nodo genitore). Gli elenchi di adiacenza aumentati consentono di recuperare un intero albero archiviando l'ID del nodo radice in ogni record.

I percorsi materializzati sono facili da implementare ed economici da aggiornare e consentono di eseguire query su sottostrutture arbitrarie, ma impongono un sovraccarico crescente per alberi profondi.

I set nidificati sono più difficili da implementare e richiedono l'aggiornamento, in media, metà dei nodi ogni volta che si effettua un inserimento. Ti consentono di eseguire query su sottoalberi arbitrari, senza che il percorso materializzato del problema della lunghezza della chiave aumenti.

Nel tuo caso specifico, tuttavia, sembra che tu non abbia realmente bisogno di una struttura ad albero: ogni storia, ramificata da un originale sebbene possa essere, si regge da sola.Quello che vorrei suggerire è avere un modello "Story", che contiene un elenco di chiavi dei suoi paragrafi (ad esempio, in Python a db.ListProperty (db.Key)). Per eseguire il rendering di una storia, recuperi la storia, quindi esegui un recupero in batch per tutti i paragrafi. Per diramare una storia, è sufficiente duplicare la voce della storia, lasciando invariati i riferimenti ai Paragrafi.

Answer 2

Una soluzione a cui posso pensare è: il percorso del nodo è anche la chiave di quel nodo. Quindi la chiave del nodo 11 è "2/7/6/11". È possibile attraversare il percorso con una semplice ricerca di chiavi di tutte le chiavi nel percorso - "2/7/6/11", "2/7/6", "2/7", "2"