Início / dba / Perguntas / 46238
Accepted
JoseTeixeira
Asked: 2013-07-13 03:08:05 +0800 CST

lista encadeada em SQL e árvores

  • 772

Embora o SQL seja mais associado a operações semelhantes a tabelas e não tanto a recursivas, digamos que gostaríamos de implementar o conceito de lista vinculada (ou duplamente vinculada) (como temos, por exemplo, em C).
Existe alguma maneira de fazer isso de forma eficiente, considerando que podemos ter itens movendo-se de qualquer lugar para qualquer lugar em uma lista encadeada?
Alguma solução usando CLR?
Ou é realmente algo que nunca deve ser trazido para o SQL Server?

Observe que esta questão também evoluiu para uma discussão de árvores VS de listas vinculadas

Embora eu tenha fixado o SQL Server, esta é uma questão acadêmica, então uma solução em qualquer outra também é boa, mesmo que apenas cheguemos à conclusão de que isso é algo que nunca deve ser trazido para o banco de dados.

sql-server

1 respostas

  1. Best Answer

    Uma lista encadeada é apenas um grafo acíclico direcionado muito simples. Não há razão para que isso seja difícil ou deva ser evitado para o sql server.

    Pense nisso, as estruturas de árvore são mais complexas do que as listas encadeadas. Toda implementação de um fórum na internet que armazene dados em um banco de dados relacional implementou o básico de uma lista encadeada. Nesta mesma página, as respostas formam uma lista encadeada. Eles podem ser adicionados e excluídos. Eles podem ser movidos de posição (também conhecidos como classificados por votos).

    A representação específica a ser usada depende apenas das compensações que você deseja fazer entre a manutenção da lista (inserir, atualizar, excluir) e a recuperação.

    --Works great for INS/UPD/DEL, In order retrieval isn't the best.
CREATE TABLE Item (id int identity, next int, prev int) 

--makes in order retrieval fast, deletes are a problem, inserts may require re-numbering.    
CREATE TABLE Item (id int identity, position int) 

--Works great for in-order retrieval, and allow cheap insertion/deletion, 
--certain edge cases might be tricky to handle.
CREATE TABLE Item (id int identity, position Decimal(24,12)) 
--for inserts, use the average of the before and after, for deletes, just delete.

    Atualização: a pergunta é sobre árvores versus listas vinculadas no servidor SQL

    O SQL Server possui o tipo de dados HierarchyId, projetado para facilitar a implementação e a consulta de estruturas semelhantes a árvores.

    CREATE TABLE Item (id int identity, NodeId HierarchyId)
    • 9

relate perguntas