Stockage de la hiérarchie d'annuaires dans un magasin de données de valeurs-clés

Question

Qu'est-ce qu'une méthode propre / efficace pour stocker le répertoire Hiérarchie / arbre dans une base de données Key-Value (dans mon cas, MongoDB mais aucune d'entre elles)?

Par exemple, une arborescence

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

La méthode que j'utilise maintenant, chaque objet est lié à son parent

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

Cela rend très efficace / rapide d'insérer et de réorganiser n'importe quel aspect de l'arborescence (par exemple, si je souhaite déplacer Red et tous ses enfants dans le répertoire Cars).

Mais cette méthode est gênante lorsque je veux récursivement récursivement chercher tous les sous-répertoires et leurs enfants Pour qu’il soit efficace d’analyser, je peux avoir une structure par exemple

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

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

Mais si je veux modifier l’arbre, il faut toucher et modifier tout un tas d’objets.

Existe-t-il d'autres méthodes pour stocker une structure de répertoire dans un magasin KV?

Answer 1

La méthode que vous utilisez actuellement s'appelle modèle de liste de contiguïté .

Un autre modèle de stockage des données hiérarchiques dans une base de données (relationnelle) est le modèle de jeu imbriqué . Son implémentation dans des bases de données SQL est bien connue . Consultez également cet article sur l'algorithme modifié de traversée de l'arborescence de pré-ordre .

Une méthode très simple: vous pouvez stocker un chemin par objet. Avec ceux-ci, il devrait être facile d’interroger les arbres dans les bases de données NOSQL:

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

Lorsque les nœuds seront supprimés ou renommés, certains chemins doivent être mis à jour. Mais en général, cette méthode semble prometteuse. Il vous suffit de réserver un caractère spécial en tant que séparateur. Les frais généraux d’espace de stockage doivent être négligeables.

modifier: cette méthode s'appelle chemin matérialisé

Enfin, voici une comparaison de différentes méthodes pour les données hiérarchiques dans les bases de données NOSQL .

Answer 2

Je n'ai pas énormément d'expérience NOSQL. Ce n'est donc pas une réponse définitive, mais voici comment je l'aborderais:

J'utiliserais probablement votre première approche, où vous avez:

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

Et ensuite, configurez une carte-réduction pour interroger rapidement les enfants d'un répertoire. La fonctionnalité de réduction de carte de MongoDB est encore disponible uniquement dans la branche développement et je n'y ai pas encore travaillé, mais dans CouchDB (et je suppose, avec quelques modifications, dans MongoDB), vous pouvez faire quelque chose comme:

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

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

Ce qui vous donnerait la liste des sous-répertoires de chaque répertoire parent.

Answer 3

Je suggère de stocker un tas dans l'identifiant des éléments de données. Je pense que c'est le meilleur plan. Si vous avez besoin de beaucoup de choses, n'importe quel élément de tas peut être un index vers un autre tas.

par exemple

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

Si ce n'est pas clair, postez un commentaire et j'expliquerai plus quand je rentrerai à la maison.

Answer 4

Créez un index!

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