Archiviazione della gerarchia di directory in un archivio dati valore-chiave

Question

Che cos'è un metodo pulito / efficiente per archiviare la directory Hierarchy / tree in un database Key-Value (nel mio caso MongoDB ma uno qualsiasi di essi)?

Ad esempio una struttura ad albero

- Cars 
   + Audi 
   + BMW
      - M5
   + Ford
- Color
   + Red
      - Apple
      - Cherry
   + Purple
- Funny

Il metodo che sto usando ora, ogni oggetto si collega al suo genitore

{ 
  dir: "red"
  parent-dir: "color"
}

Questo rende molto efficiente / veloce l'inserimento e il riordino di qualsiasi aspetto dell'albero (ad esempio se voglio spostare Red e tutti i suoi figli nella directory Cars).

Ma questo metodo fa schifo quando voglio ricorsivamente tutte le sottodirectory e i loro figli per una determinata directory. Per rendere più efficiente l'analisi, ad esempio, posso avere una struttura

{ 
  dir: "red"
  children: "audi, bmw, ford"
}

{ 
  dir: "bmw"
  children: "m5"
}

Ma se voglio modificare l'albero, un intero gruppo di oggetti deve essere toccato e modificato.

Esistono altri metodi per archiviare una struttura di directory in un archivio KV?

Answer 1

Il metodo attualmente in uso si chiama modello di elenco di adiacenza .

Un altro modello per archiviare i dati gerarchici in un database (relazionale) è il modello di set nidificato . La sua l'implementazione nei database SQL è ben nota . Vedi anche questo articolo per l'algoritmo di attraversamento dell'albero di preordine modificato .

Un metodo molto semplice: è possibile memorizzare un percorso per oggetto - con quelli dovrebbe essere facile interrogare gli alberi nei database NOSQL:

{ path: "Color", ... }
{ path: "Color.Red", ... }
{ path: "Color.Red.Apple", ... }
{ path: "Color.Red.Cherry", ... }

Quando i nodi verranno rimossi o rinominati, alcuni percorsi devono essere aggiornati. Ma in generale, questo metodo sembra promettente. Devi solo riservare un carattere speciale come separatore. Lo spazio di archiviazione ambientale dovrebbe essere trascurabile.

modifica: questo metodo è chiamato percorso materializzato

Infine, ecco un confronto di diversi metodi per dati gerarchici nei database NOSQL .

Answer 2

Non ho una grande esperienza NOSQL, quindi questa non è una risposta definitiva, ma ecco come la approccerei:

Probabilmente userei il tuo primo approccio, dove hai:

{
  dir: 'dir_name',
  parent_dir: 'parent_dir_name'
}

E quindi imposta una riduzione mappa per interrogare rapidamente i figli di una directory. La funzionalità di riduzione della mappa di MongoDB è ancora disponibile solo nel ramo di sviluppo e non ci ho ancora lavorato, ma in CouchDB (e presumo, con alcune modifiche, in MongoDB) potresti fare qualcosa del genere:

map:
function(doc) {
  emit( doc.parent_dir, doc.dir );
}

reduce:
function(key, values) {
  return( values );
}

Che ti darebbe l'elenco delle sottodirectory per ciascuna directory principale.

Answer 3

Suggerisco di archiviare un heap nell'ID degli elementi di dati. Penso che questo sia il miglior piano. Se hai bisogno di molte cose, qualsiasi elemento heap potrebbe essere un indice di un altro heap.

ad esempio

{" id: xxx " ;, " id: yyy " ;, " sub-heap-id: zzz " ....}

Se questo non è chiaro, pubblica un commento e spiegherò di più quando torno a casa.

Answer 4

Crea un indice!

http://www.mongodb.org/display/DOCS/Indexes