Armazenando Hierarquia de Diretórios em uma loja de Key-Value Data

Question

O que é um método limpo / eficiente para armazenar o diretório Hierarquia / árvore em um banco de dados Key-Value (no meu caso MongoDB mas qualquer deles)?

Por exemplo, uma estrutura de árvore

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

O método que estou usando agora, cada objeto links para ele de pai

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

Isto torna muito eficiente / rápido para inserir e reordenar qualquer aspecto da árvore (por exemplo, se eu quiser mover Red e tudo o que de crianças para o diretório Cars).

Mas este método é uma porcaria quando eu quero todos os subdiretórios e seus filhos para um determinado diretório de forma recursiva. Para torná-lo eficiente para analisar posso ter uma estrutura, por exemplo,

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

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

Mas se eu quiser modificar a árvore, um monte de objetos precisam tocado e modificado.

Existem outros métodos para armazenar uma estrutura de diretório em uma loja KV?

Answer 1

O método que você usa atualmente é agora chamado lista de adjacência modelo .

Outro modelo para armazenar dados hierárquicos em um banco de dados (relacional) é o modelo de conjunto aninhado . Sua em bancos de dados SQL é bem conhecido . Veja também este artigo para a árvore preorder modificado travessia algoritmo .

Um método muito simples: você pode armazenar um caminho por objeto - com aqueles que devem ser fáceis de árvores de comando em bancos de dados NoSQL:

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

Quando nós será removido ou renomeado alguns caminhos devem ser atualizados. Mas, em geral, este método parece promissor. Você só tem que reservar um caractere especial como separador. A sobrecarga de espaço de armazenamento deve ser insignificante.

edit: esse método é chamado caminho materializado

Finalmente, aqui está uma comparação de diferentes métodos para dados hierárquicos em bancos de dados NoSQL .

Answer 2

Eu não tenho uma enorme quantidade de experiência NoSQL, e isso não é uma resposta definitiva, mas aqui está como eu iria abordá-lo:

Eu provavelmente usaria sua primeira abordagem, onde você tem:

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

E, em seguida, criar um mapa-reduzir para consultar rapidamente os filhos de um diretório. Map-Reduce do MongoDB funcionalidade ainda está disponível apenas no ramo de desenvolvimento e eu não trabalhei com ele ainda, mas em CouchDB (e presumo, com algumas modificações, no MongoDB) você poderia fazer algo como:

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

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

O que lhe daria a lista de sub-diretórios para cada diretório pai.

Answer 3

Eu sugiro armazenar uma pilha ao do ID de um dos itens de dados. Acho que este é o melhor plano. Se você precisa de muitas e muitas coisas qualquer elemento pilha poderia ser um índice para outro heap.

ex

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

Se isto não é pós clara um comentário e vou explicar mais quando eu chegar em casa.

Answer 4

Faça um índice!

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