Armazenando Hierarquia de Diretórios em uma loja de Key-Value Data
Pergunta
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?
Solução
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 .
Outras dicas
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.
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.
Faça um índice!