Estrutura da base de dados para a estrutura de dados em árvore
qual seria a melhor maneira de implementar uma estrutura de dados de árvore personalizável (ou seja, uma estrutura de árvore com um número desconhecido de níveis) numa base de dados?
Já fiz isto uma vez antes de usar uma mesa com uma chave estranha.que outras implementações você poderia ver, e esta implementação faz sentido?
6 answers
Você menciona a mais comumente implementada, que é a lista de adjacência: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets
Também existem outros modelos, incluindo caminhos materializados e conjuntos aninhados.: http://communities.bmc.com/communities/docs/DOC-9902
[1] Joe Celko escreveu um livro sobre este assunto, que é uma boa referência a partir de uma perspectiva geral SQL (ele é mencionado no aninhado definir a ligação do artigo acima).Also, Itzik Ben-Gann has a good overview of the most common options in his book "Inside Microsoft SQL Server 2005: T-SQL Querying".
As principais coisas a considerar ao escolher um modelo são:
1) Frequência da mudança de estrutura - com que frequência a estrutura real da árvore muda. Alguns modelos oferecem melhores características de atualização da estrutura. No entanto, é importante separar as alterações estruturais de outras alterações de dados. Por exemplo, você talvez queira modelar o organigrama de uma empresa. Algumas pessoas irão modelar isso como uma lista de adjacência, usando o ID do empregado para ligar um empregado ao seu supervisor. Esta é geralmente uma abordagem sub-ótima. Uma abordagem que muitas vezes funciona melhor é modelar a estrutura org separada dos próprios empregados, e manter o empregado como um atributo da estrutura. Desta forma, quando um empregado deixa a empresa, a estrutura organizacional em si não precisa de ser mudanças, apenas o associação com o empregado que saiu.
2) é a árvore write-heavy ou read-heavy - algumas estruturas funcionam muito bem ao ler a estrutura, mas incorrem em sobrecarga adicional ao escrever para a estrutura.
3) Que tipos de informação você precisa para obter da estrutura - algumas estruturas se sobressaem em fornecer certos tipos de informação sobre a estrutura. Exemplos incluem encontrar um nó e todos os seus filhos, encontrar um nó e todos os seus pais, encontrar a contagem de nós de crianças que cumprem certas condições, etc. Você precisa saber que informações serão necessárias a partir da estrutura para determinar a estrutura que melhor se ajustará às suas necessidades.
Dê uma vista de olhos em gerir os dados hierárquicos em MySQL. Discute duas abordagens para armazenar e Gerenciar dados hierárquicos (como árvore) em um banco de dados relacional.
A primeira abordagem é o modelo de Lista de adjacência, que é o que você essencialmente descreve: ter uma chave estrangeira que se refere à própria tabela. Embora esta abordagem seja simples, pode ser muito ineficiente para certas consultas, como a construção de toda a árvore.
A segunda abordagem discutida no o artigo é o modelo de conjunto aninhado. Esta abordagem é muito mais eficiente e flexível. Consulte o artigo para obter uma explicação detalhada e perguntas de exemplo.Se tiver de usar a base de dados relacional para organizar a estrutura de dados da árvore, então o Postgresql tem um módulo 'ltree' fixe que fornece o tipo de dados para representar as legendas dos dados armazenados numa estrutura hierárquica em árvore. Podes ter a ideia a partir daí.(Para mais informações, ver: http://www.postgresql.org/docs/9.0/static/ltree.html)
Em LDAP comum é usado para organizar registos na estrutura hierárquica.
Você pode então usar uma expressão de tabela comum em SQL ou a ligação por declaração prévia em Oracle para construir a sua árvore.
Uma colecção fantástica de funções prontas a usar que podem ser usadas com o modelo da lista de adjacência para tornar a vida mais simples.
Http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html