Przechowywanie hierarchii katalogów w magazynie danych klucz-wartość

Question

Co to jest czysta/wydajna metoda przechowywania katalogu Hierarchia/drzewo w bazie danych klucza-wartości (w moim przypadku MongoDB, ale żaden z nich)?

Na przykład struktura drzewa

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

Sposób używam teraz, każdy linki obiektów na jego rodzic

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

To sprawia, że ​​jest bardzo skuteczny/fast wstawić i zmienić kolejność jakiegokolwiek aspektu drzewo (na przykład, jeśli chcę przenieść czerwony i wszystkie jego dzieci do katalogu Cars).

Ale ta metoda jest do bani, kiedy chcę rekurencyjnie wszystkie podkatalogi i ich potomków dla danego katalogu. Aby było skuteczne, aby zanalizować mogę mieć strukturę na przykład

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

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

Ale jeśli chcesz zmodyfikować drzewa, cała masa obiektów trzeba dotknąć i modyfikowane.

Czy są jakieś inne metody przechowywania struktury katalogów w magazynie KV?

Answer 1

Obecnie używana metoda nazywa się adjacency list model.

Kolejnym modelem do przechowywania danych hierarchicznych w (relacyjnej) bazie danych jest nested set model. Jest to implementation in SQL databases is well known. Zobacz także this article for the modified preorder tree traversal algorithm.

bardzo prosty sposób: można przechowywać ścieżkę za obiekt - z tych, to powinno być łatwe do kwerendy drzew w bazach NoSQL:

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

Kiedy węzły zostaną usunięte lub przemianowane niektóre ścieżki muszą być aktualizowane. Generalnie jednak ta metoda wygląda obiecująco. Musisz tylko zarezerwować specjalną postać jako separator. Narzut miejsca do przechowywania powinien być nieistotny.

edit: ta metoda jest wywoływana materialized path

Wreszcie, tutaj jest a comparison of different methods for hierarchical data in NOSQL databases.

Answer 2

nie mam ogromną ilość doświadczenia NoSQL, więc nie jest to ostateczna odpowiedź, ale oto jak bym go podejść:

I prawdopodobnie wykorzystywać swoje pierwsze podejście, gdzie trzeba:

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

Następnie skonfiguruj mapę - zmniejsz, aby szybko wyszukać dzieci w katalogu. Funkcja zmniejszania map MongoDB jest nadal dostępna tylko w gałęzi rozwojowej i nie pracowałem jeszcze z nią, ale w CouchDB (i zakładam, z kilkoma modyfikacjami, w MongoDB) możesz zrobić coś takiego:

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

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

Który dałby ci listę podkatalogów dla każdego katalogu nadrzędnego.

Answer 3

Utwórz indeks!

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

Answer 4

Proponuję przechowywania sterty na identyfikator-tych elementów danych. Myślę, że to najlepszy plan. Jeśli potrzebujesz dużo rzeczy, każdy element sterty może być indeksem do innej sterty.

np

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

Jeśli to nie jest jasne, dodaj komentarz i opiszę bardziej, gdy wrócę do domu.