ti-enxame.com

Lista vinculada no SQL

Qual é a melhor maneira de armazenar uma lista vinculada em um banco de dados mysql para que as inserções sejam simples (ou seja, você não precisa reindexar um monte de coisas toda vez) e de forma que a lista possa ser facilmente retirada em ordem.

57
magicrobotmonkey

Armazene uma coluna inteira na sua tabela chamada 'position'. Registre um 0 para o primeiro item da sua lista, um 1 para o segundo item, etc. Indexe essa coluna no banco de dados e, quando desejar extrair seus valores, classifique por essa coluna.

 alter table linked_list add column position integer not null default 0;
 alter table linked_list add index position_index (position);
 select * from linked_list order by position;

Para inserir um valor no índice 3, modifique as posições das linhas 3 e acima e insira:

 update linked_list set position = position + 1 where position >= 3;
 insert into linked_list (my_value, position) values ("new value", 3); 
16
Adrian Dunston

Usando a solução de Adrian, mas em vez de aumentar em 1, aumente em 10 ou até 100. Em seguida, as inserções podem ser calculadas com metade da diferença do que você está inserindo sem precisar atualizar tudo abaixo da inserção. Escolha um número grande o suficiente para lidar com o número médio de inserções - se for muito pequeno, você deverá voltar a atualizar todas as linhas com uma posição mais alta durante uma inserção.

17
cfeduke

crie uma tabela com duas colunas de auto-referência PreviousID e NextID. Se o item for a primeira coisa na lista PreviousID será nulo, se for o último, NextID será nulo. O SQL terá algo parecido com isto:

create table tblDummy
{
     PKColumn     int     not null, 
     PreviousID     int     null, 
     DataColumn1     varchar(50)     not null, 
     DataColumn2     varchar(50)     not null,  
     DataColumn3     varchar(50)     not null, 
     DataColumn4     varchar(50)     not null, 
     DataColumn5     varchar(50)     not null, 
     DataColumn6     varchar(50)     not null, 
     DataColumn7     varchar(50)     not null, 
     NextID     int     null
}
15
B0fh

Uma lista vinculada pode ser armazenada usando ponteiros recursivos na tabela. Isso é muito parecido com as mesmas hierarquias armazenadas no Sql e isso está usando o padrão de associação recursiva.

Você pode aprender mais sobre isso aqui .

Eu espero que isso ajude.

4
user9252

A opção mais simples seria criar uma tabela com uma linha por item da lista, uma coluna para a posição do item e colunas para outros dados no item. Em seguida, você pode usar ORDER BY na coluna de posição para recuperar na ordem desejada.

create table linked_list
(   list_id   integer not null
,   position  integer not null 
,   data      varchar(100) not null
);
alter table linked_list add primary key ( list_id, position );

Para manipular a lista, atualize a posição e insira/exclua os registros conforme necessário. Então, para inserir um item na lista 1 no índice 3:

begin transaction;

update linked_list set position = position + 1 where position >= 3 and list_id = 1;

insert into linked_list (list_id, position, data)
values (1, 3, "some data");

commit;

Como as operações na lista podem exigir vários comandos (por exemplo, uma inserção exigirá um INSERT e um UPDATE), assegure-se de sempre executar os comandos em uma transação.

Uma variação dessa opção simples é aumentar a posição de algum fator para cada item, digamos 100, para que, ao executar um INSERT, você nem sempre precise renumerar a posição dos seguintes elementos. No entanto, isso requer um pouco mais de esforço para determinar quando incrementar os seguintes elementos, para que você perca a simplicidade, mas obtenha desempenho se tiver muitas inserções.

Dependendo dos seus requisitos, outras opções podem apelar, como:

  • Se você deseja executar muitas manipulações na lista e não muitas recuperações, pode preferir ter uma coluna de ID apontando para o próximo item da lista, em vez de usar uma coluna de posição. Então você precisa de lógica iterativa na recuperação da lista para obter os itens em ordem. Isso pode ser implementado com relativa facilidade em um processo armazenado.

  • Se você tiver muitas listas, uma maneira rápida de serializar e desserializar sua lista para texto/binário, e você deseja armazenar e recuperar apenas a lista inteira, armazene-a como um valor único em uma única coluna. Provavelmente não é o que você está pedindo aqui.

4
Rory

https://dba.stackexchange.com/questions/46238/linked-list-in-sql-and-trees sugere um truque para usar a coluna de posição de ponto flutuante para inserções e pedidos rápidos.

Também menciona o recurso SQL Server 2014 --- hierarchyid especializado.

2
Vadzim

Isso é algo que eu tenho tentado descobrir há um tempo. A melhor maneira que eu encontrei até agora é criar uma única tabela para a lista vinculada usando o seguinte formato (este é o pseudo-código):

LinkedList (

  • key1,
  • em formação,
  • key2

)

key1 é o ponto de partida. Chave2 é uma chave estrangeira que se vincula a ela mesma na próxima coluna. Então, suas colunas vincularão algo, algo assim

col1

  • key1 = 0,
  • information = 'olá'
  • key2 = 1

Chave1 é a chave primária de col1. key2 é uma chave estrangeira que leva à key1 de col2

col2

  • key1 = 1,
  • information = 'wassup'
  • key2 = null

key2 de col2 está definido como nulo porque não aponta para nada

Quando você entra pela primeira vez em uma coluna da tabela, é necessário garantir que key2 esteja definido como nulo ou ocorrerá um erro. Depois de inserir a segunda coluna, você pode voltar e definir a chave2 da primeira coluna como a chave primária da segunda coluna.

Isso é o melhor método para inserir muitas entradas por vez, depois voltar e definir as chaves estrangeiras de acordo (ou criar uma GUI que faça isso apenas para você)

Aqui está um código real que eu preparei (todo o código real funcionou no MSSQL. Você pode pesquisar algumas vezes a versão do SQL que está usando!):

createtable.sql

create table linkedlist00 (

key1 int primary key not null identity(1,1),

info varchar(10),

key2 int

)

register_foreign_key.sql

alter table dbo.linkedlist00

add foreign key (key2) references dbo.linkedlist00(key1)

* Coloquei-os em dois arquivos separados, porque isso deve ser feito em duas etapas. O MSSQL não permitirá que você faça isso em uma única etapa, porque a tabela ainda não existe para referência à chave estrangeira.

A lista vinculada é especialmente poderosa nos relacionamentos um para muitos . Então, se você já quis fazer uma série de chaves estrangeiras? Bem, esta é uma maneira de fazê-lo! Você pode criar uma tabela principal que aponte para a primeira coluna na tabela da lista vinculada e, em vez do campo "informações", você pode usar uma chave estrangeira para a tabela de informações desejada.

Exemplo:

Digamos que você tenha uma burocracia que mantenha formas.

Digamos que eles tenham uma tabela chamada armário de arquivos

FileCabinet (

  • ID do gabinete (pk)
  • ID dos arquivos (fk))

cada coluna contém uma chave primária para o gabinete e uma chave estrangeira para os arquivos. Esses arquivos podem ser formulários de impostos, documentos de seguro de saúde, permissões de excursões, etc.

Arquivos(

  • ID dos arquivos (pk)

  • ID do arquivo (fk)

  • ID do próximo arquivo (fk)

)

serve como um contêiner para os arquivos

Arquivo(

  • ID do arquivo (pk)

  • Informações sobre o arquivo

)

este é o arquivo específico

Pode haver melhores maneiras de fazer isso, dependendo das suas necessidades específicas. O exemplo ilustra apenas o uso possível.

2
HumbleWebDev

Este post é antigo, mas ainda dá US $ 0,02. Atualizar todos os registros em uma tabela ou conjunto de registros soa maluco para resolver pedidos. a quantidade de indexação também é loucura, mas parece que a maioria aceitou.

A solução maluca que surgiu para reduzir as atualizações e a indexação é criar duas tabelas (e, na maioria dos casos, você não classifica todos os registros em apenas uma tabela). Tabela A para armazenar os registros da lista que está sendo classificada e tabela B para agrupar e manter um registro da ordem como uma sequência. a sequência de pedidos representa uma matriz que pode ser usada para solicitar os registros selecionados no servidor da web ou na camada do navegador de um aplicativo de página da web.

Create Table A{
Id int primary key identity(1,1),
Data varchar(10) not null
B_Id int
}

Create Table B{
Id int primary key Identity(1,1),
GroupName varchat(10) not null,
Order varchar(max) null
}

O formato da picada da ordem deve ser id, posição e algum separador para dividir () sua string. no caso da interface do usuário do jQuery, a função .sortable ('serialize') gera uma sequência de pedidos para você que é POST amigável que inclui a identificação e a posição de cada registro na lista.

A verdadeira mágica é a maneira que você escolhe para reordenar a lista selecionada usando a sequência de pedidos salva. isso dependerá do aplicativo que você está construindo. aqui está um exemplo novamente do jQuery para reordenar a lista de itens: http://ovisdevelopment.com/oramincite/?p=155

2
FlyTigert

Aumente o 'índice' SERIAL em 100, mas adicione manualmente valores intermediários com um 'índice' igual a Anterior + Próximo/2. Se você saturar as 100 linhas, reordene o índice novamente em 100s.

Isso deve manter a sequência com o índice primário.

1
Stephen

Existem algumas abordagens em que posso pensar imediatamente, cada uma com diferentes níveis de complexidade e flexibilidade. Suponho que seu objetivo é preservar um pedido na recuperação, em vez de exigir armazenamento como uma lista vinculada real.

O método mais simples seria atribuir um valor ordinal a cada registro na tabela (por exemplo, 1, 2, 3, ...). Em seguida, ao recuperar os registros, especifique um pedido na coluna ordinal para recuperá-los.

Essa abordagem também permite recuperar os registros sem considerar a participação em uma lista, mas permite a participação em apenas uma lista e pode exigir uma coluna "id da lista" adicional para indicar a qual lista o registro pertence.

Uma abordagem um pouco mais elaborada, mas também mais flexível, seria armazenar informações sobre associação a uma lista ou listas em uma tabela separada. A tabela precisaria de 3 colunas: o ID da lista, o valor ordinal e um ponteiro de chave estrangeira para o registro de dados. Sob essa abordagem, os dados subjacentes não sabem nada sobre sua participação em listas e podem ser facilmente incluídos em várias listas.

1
Mike Monette

Eu acho que é muito mais simples adicionar uma coluna criada do tipo Datetime e uma coluna de posição de int, então agora você pode ter posições duplicadas, na instrução select use a posição order by , criou a opção desc e sua lista será buscada em ordem.

1
Poncho

Uma lista pode ser armazenada fazendo com que uma coluna contenha o deslocamento (posição do índice da lista) - uma inserção no meio está incrementando tudo acima do novo pai e fazendo uma inserção.

0
Daniel Papasian