Qual seria a melhor maneira de implementar uma estrutura de dados de árvore personalizável (ou seja, uma estrutura em árvore com um número desconhecido de nível) em um banco de dados?
Eu fiz isso uma vez antes de usar uma tabela com uma chave estrangeira para si mesma.
Que outras implementações você pôde ver e essa implementação faz sentido?
sql
database-design
tree
CodeMonkey1313
fonte
fonte
Respostas:
Você mencionou o mais comumente implementado, que é a Lista de Adjacências: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets
Também existem outros modelos, incluindo caminho materializado e conjuntos aninhados: http://communities.bmc.com/communities/docs/DOC-9902
Joe Celko escreveu um livro sobre esse assunto, que é uma boa referência de uma perspectiva geral do SQL (isso é mencionado no link do artigo do conjunto aninhado acima).
Além disso, Itzik Ben-Gann tem uma boa visão geral das opções mais comuns em seu livro "Por dentro do Microsoft SQL Server 2005: consulta T-SQL".
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 é alterada. Alguns modelos fornecem melhores características de atualização da estrutura. É importante separar as alterações de estrutura de outras alterações de dados. Por exemplo, você pode modelar o organograma da empresa. Algumas pessoas modelarão isso como uma lista de adjacência, usando o ID do funcionário para vincular um funcionário ao supervisor. Geralmente, essa é uma abordagem abaixo do ideal. Uma abordagem que geralmente funciona melhor é modelar a estrutura organizacional separada dos próprios funcionários e manter o funcionário como um atributo da estrutura. Dessa forma, quando um funcionário sai da empresa, a estrutura organizacional em si não precisa ser alterada, apenas a associação com o funcionário que saiu.
2) A árvore é pesada para gravação ou leitura - algumas estruturas funcionam muito bem ao ler a estrutura, mas incorrem em sobrecarga adicional ao gravar na estrutura.
3) Quais tipos de informações você precisa obter da estrutura - algumas estruturas se destacam por fornecer certos tipos de informações sobre a estrutura. Os exemplos incluem encontrar um nó e todos os seus filhos, encontrar um nó e todos os seus pais, encontrar a contagem de nós filhos que atendem a determinadas condições etc. Você precisa saber quais informações serão necessárias a partir da estrutura para determinar a estrutura que melhor se adequará suas necessidades.
fonte
Dê uma olhada em Gerenciando dados hierárquicos no MySQL . Ele discute duas abordagens para armazenar e gerenciar dados hierárquicos (em forma de árvore) em um banco de dados relacional.
A primeira abordagem é o modelo de lista de adjacência, que é basicamente o que você descreve: ter uma chave estrangeira que se refere à própria tabela. Embora essa abordagem seja simples, pode ser muito ineficiente para determinadas consultas, como a construção de toda a árvore.
A segunda abordagem discutida no artigo é o modelo de conjunto aninhado. Essa abordagem é muito mais eficiente e flexível. Consulte o artigo para obter explicações detalhadas e consultas de exemplo.
fonte
Se você precisar usar o Relational DataBase para organizar a estrutura de dados em árvore, o Postgresql possui um módulo ltree legal que fornece um tipo de dados para representar rótulos de dados armazenados em uma estrutura hierárquica em forma de árvore. Você pode obter a idéia de lá (para mais informações, consulte: http://www.postgresql.org/docs/9.0/static/ltree.html )
Em geral, o LDAP é usado para organizar registros na estrutura hierárquica.
fonte
Ter uma mesa com uma chave estrangeira para si faz sentido para mim.
Em seguida, você pode usar uma expressão de tabela comum no SQL ou a instrução connect by anterior no Oracle para construir sua árvore.
fonte
Fantástica coleção de funções prontas para uso que podem ser usadas com o modelo de lista de adjacências para simplificar a vida.
http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html
fonte
Eu usei a seguinte implementação no SQL SERVER 2005. Verifique aqui
fonte
Se alguém que usa o MS SQL Server 2008 e superior, aterra sobre esta questão: o SQL Server 2008 e superior possui um novo recurso "hierarchyId" projetado especificamente para esta tarefa.
Mais informações em https://docs.microsoft.com/en-us/sql/relational-databases/hierarchical-data-sql-server
fonte