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

Question

Che cos'è un metodo pulito/efficiente per archiviare la gerarchia/struttura della directory in un database valori-chiave (nel mio caso MongoDB ma nessuno di essi)?

Per esempio una struttura ad albero

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

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

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

Questo rende molto efficiente/veloce per inserire e riordinare ogni aspetto della l'albero (ad esempio se voglio spostare Red e tutti i suoi bambini nella directory Cars).

Ma questo metodo fa schifo quando voglio tutte le sottodirectory e i loro figli per una determinata directory in modo ricorsivo. Per rendere più efficiente per analizzare posso avere una struttura ad esempio

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

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

Ma se voglio modificare l'albero, un sacco di oggetti necessario toccato e modificato.

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

Answer 1

Il metodo che si utilizza attualmente è chiamato adjacency list model.

Un altro modello per memorizzare i dati gerarchici in un database (relazionale) è lo nested set model. Il suo implementation in SQL databases is well known. Vedi anche this article for the modified preorder tree traversal algorithm.

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

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

Quando i nodi vengono rimossi o rinominati alcuni percorsi devono essere aggiornati. Ma in generale, questo metodo sembra promettente. Devi solo prenotare un personaggio speciale come separatore. Il sovraccarico dello spazio di archiviazione dovrebbe essere trascurabile.

edit: questo metodo viene chiamato materialized path

Infine, qui è a comparison of different methods for hierarchical data in NOSQL databases.

Answer 2

Non ho una quantità enorme di esperienza NoSQL, quindi questo non è una risposta definitiva, ma ecco come mi piacerebbe avvicino:

avrei probabilmente usare il tuo primo approccio, in cui si dispone:

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

E quindi impostare una mappa-ridurre per interrogare rapidamente i figli di una directory. map-ridurre di MongoDB funzionalità è ancora disponibile solo nel ramo di sviluppo e non ho lavorato con lui ancora, ma in CouchDB (e presumo, con qualche modifica, in MongoDB) si poteva fare qualcosa di simile:

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

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

Quale potrebbe fornire l'elenco delle sottodirectory per ciascuna directory principale.

Answer 3

Fare un indice!

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

Answer 4

suggerisco la memorizzazione di un mucchio ai i id degli elementi di dati. Penso che questo sia il piano migliore. Se hai bisogno di un sacco di cose, qualsiasi elemento dell'heap potrebbe essere un indice per un altro heap.

esempio

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

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