Speichern von Verzeichnishierarchie in einem Schlüsselwert Datenspeicher

Question

Was ist eine saubere / effiziente Methode der Verzeichnishierarchie / Baum in einem Schlüsselwert Datenbank zum Speichern (in meinem Fall MongoDB aber jeder von ihnen)?

Zum Beispiel einer Baumstruktur

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

Die Methode, die ich jetzt bin mit, jedes Objekt Links zu ihm übergeordneter

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

Dies macht es sehr effizient / schnell einzusetzen und jeden Aspekt des Baumes neu anordnen (zum Beispiel, wenn ich will Rot und all seine Kinder in die Autos Verzeichnis verschieben).

Aber diese Methode saugt, wenn ich für ein bestimmtes Verzeichnis rekursiv auf alle Unterverzeichnisse und ihre Kinder wollen. Um es effizient ich zu analysieren, kann eine Struktur haben zum Beispiel

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

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

Aber wenn ich den Baum ändern möchten, müssen eine ganze Reihe von Objekten berührt und verändert.

Gibt es andere Methoden, um eine Verzeichnisstruktur in einem KV Speicher zu speichern?

Answer 1

Die Methode, die Sie zur Zeit jetzt nutzen wird Adjazenzliste Modell genannt.

Ein weiteres Modell hierarchische Daten in einer (relationalen) Datenbank zu speichern ist die Nested Sets . Seine Implementierung in SQL-Datenbanken ist bekannt . Siehe auch dieser Artikel für den modifizierten Preorder Baum Traversierungsalgorithmus .

Eine sehr einfache Methode: Sie einen Pfad pro Objekt speichern könnte - mit denen sollte es leicht sein, Bäume abfragen in NoSQL-Datenbanken:

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

Wenn die Knoten werden einige Pfade entfernt oder umbenannt werden müssen aktualisiert werden. Aber im Allgemeinen sieht diese Methode vielversprechend. Sie haben nur ein Sonderzeichen als Trennzeichen zu reservieren. Der Stauraum Overhead sollte vernachlässigbar sein.

edit: diese Methode aufgerufen wird Pfad materialisiert

Schließlich ist hier einen Vergleich verschiedener Methoden zum hierarchischen Daten in NoSQL-Datenbanken .

Answer 2

Ich habe nicht eine riesige Menge von NoSQL-Erfahrung, so ist dies keine endgültige Antwort, aber hier ist, wie ich es habe nähern:

würde ich wahrscheinlich Ihren ersten Ansatz verwenden, wo Sie haben:

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

Und dann ein Karten reduzieren eingerichtet, um schnell die Kinder eines Verzeichnisses abfragen. MongoDB des Map-Funktionalität reduzieren ist nach wie vor nur in dem Entwicklungszweig und ich habe nicht mit ihm noch gearbeitet, aber in CouchDB (und ich nehme an, mit einem paar Modifikation, in MongoDB) Sie etwas tun könnten, wie:

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

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

Was würden Sie die Liste der Unterverzeichnisse für jedes übergeordnetes Verzeichnis.

Answer 3

Ich schlage vor, Speichern eines Heap auf die die IDs der Datenelemente. Ich denke, dies ist der beste Plan. Wenn Sie sehr viele Sachen brauchen könnte jeder Haufen Element ein Index zu einem anderen Haufen sein.

zB

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

Wenn das nicht klar Kommentar hinterlassen und ich werde mehr erklären, wenn ich nach Hause komme.

Answer 4

Erstellen Sie einen Index!

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