Armazenando uma lista reordenável em um banco de dados

41

Estou trabalhando em um sistema de lista de desejos, onde os usuários podem adicionar itens às suas várias listas de desejos, e planejo permitir que os usuários reordenem os itens mais tarde. Eu não tenho muita certeza sobre a melhor maneira de armazenar isso em um banco de dados enquanto permanece rápido e não está se transformando em uma bagunça (este aplicativo será usado por uma base de usuários razoavelmente grande, então eu não quero que ele desça para limpar o material).

Eu tentei inicialmente uma coluna position , mas parece que seria bastante ineficiente ter que alterar o valor da posição de todos os outros itens quando você os mover.

Eu tenho visto pessoas usando uma auto-referência para se referir ao valor anterior (ou próximo), mas, novamente, parece que você teria que atualizar muitos outros itens na lista.

Outra solução que vi foi usar números decimais e apenas colocar itens nas lacunas entre eles, o que parece ser a melhor solução até agora, mas tenho certeza que tem que haver uma maneira melhor.

Eu diria que uma lista típica conteria cerca de 20 ou mais itens, e eu provavelmente a limitarei a 50. O reordenamento estaria usando arrastar e soltar e provavelmente será feito em lotes para evitar condições de corrida e tal dos pedidos de ajax. Estou usando postgres (no heroku) se for importante.

Alguém tem alguma ideia?

Felicidades por qualquer ajuda!

    
por Tom Brunoli 18.04.2013 / 01:35
fonte

8 respostas

26

Primeiro, não tente fazer nada inteligente com números decimais, porque eles vão te irritar. REAL e DOUBLE PRECISION são inexatos e podem não representar corretamente o que você coloca neles. NUMERIC é exato, mas a sequência correta de movimentos irá deixá-lo sem precisão e sua implementação será prejudicada.

Limitar movimentos a altos e baixos torna toda a operação muito fácil. Para uma lista de itens numerados sequencialmente, você pode mover um item para cima, diminuindo sua posição e incrementando o número da posição de qualquer alteração anterior. (Em outras palavras, o item 5 se tornaria 4 e o que era o item 4 se torna 5 , efetivamente uma troca como Morons descreveu em sua resposta.) Mover para baixo seria o oposto. Indexar sua tabela pelo que identifica exclusivamente uma lista e posição e você pode fazê-lo com dois UPDATE s dentro de uma transação que será executada muito rapidamente. A menos que seus usuários estejam reorganizando suas listas em velocidades sobre-humanas, isso não causará muita carga.

Os movimentos de arrastar e soltar (por exemplo, mover o item 6 para ficar entre os itens 9 e 10 ) são um pouco mais complicados e precisam ser feitos de forma diferente dependendo se a nova posição está acima ou abaixo antigo. No exemplo acima, você precisa abrir um furo incrementando todas as posições maiores que 9 , atualizando a posição do item 6 para ser o novo 10 e diminuindo a posição de tudo maior que 6 para preencha o local desocupado. Com a mesma indexação que descrevi antes, isso será rápido. Você pode realmente fazer isso ir um pouco mais rápido do que eu descrevi, minimizando o número de linhas que a transação toca, mas isso é uma micro-otimização que você não precisa até que você possa provar que há um gargalo.

De qualquer forma, tentar superar o banco de dados com uma solução caseira e inteligente demais não resulta em sucesso. Bancos de dados que valem o seu sal foram cuidadosamente escritos para fazer essas operações muito rapidamente por pessoas que são muito, muito boas nisso.

    
por 18.04.2013 / 14:16
fonte
10

"but it seems like that would be quite inefficient"

Você mediu isso? Ou isso é apenas um palpite? Não faça tais suposições sem qualquer prova.

"20 to 50 items per list"

Honestamente, isso não é "um monte de itens", para mim soa muito poucos.

Sugiro que você se atenha à abordagem de "coluna de posição" (se essa for a implementação mais simples para você). Para tamanhos de lista tão pequenos, não inicie a otimização desnecessária antes de enfrentar problemas reais de desempenho

    
por 18.04.2013 / 08:23
fonte
10

I have seen people using a self-reference to refer to the previous (or next) value, but again, it seems like you would have to update a whole lot of other items in the list.

Por quê? Digamos que você use uma abordagem de tabela de lista vinculada com colunas (listID, itemID, nextItemID).

Inserir um novo item em uma lista custa uma inserção e uma linha modificada.

O reposicionamento de um item custa três modificações de linha (o item sendo movido, o item antes dele e o item antes de seu novo local).

A remoção de um item custa uma exclusão e uma linha modificada.

Esses custos permanecem os mesmos, independentemente de a lista ter 10 itens ou 10.000 itens. Nos três casos, há uma modificação a menos se a linha de destino for o primeiro item da lista. Se você estiver operando com mais frequência no item da lista último , pode ser benéfico armazenar prevItemID em vez de em seguida.

    
por 11.11.2016 / 07:30
fonte
8

Mesma resposta aqui link

Solução: crie index uma string (porque as strings, em essência, possuem uma "precisão arbitrária" infinita). Ou se você usar um int, incremente index por 100 em vez de 1.

O problema de desempenho é o seguinte: não há valores "entre" entre dois itens classificados.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

Em vez disso, faça assim (melhor solução abaixo):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Melhor ainda: eis como Jira resolve esse problema. Sua "classificação" (o que você chama de índice) é um valor de sequência que permite uma tonelada de espaço entre os itens classificados.

Aqui está um exemplo real de um banco de dados jira com o qual eu trabalho

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Observe este exemplo hzztzz:i . A vantagem de um rank de string é que você fica sem espaço entre dois itens, você ainda não precisa re-classificar qualquer outra coisa. Você acabou de adicionar mais caracteres à string para diminuir o foco.

    
por 21.04.2018 / 15:21
fonte
5

Esta é realmente uma questão de escala e caso de uso ...

Quantos itens você espera em uma lista? Se milhões, eu acho que a rota decimal é o óbvio.

Se 6, então, a renumeração de inteiros é a escolha óbvia. s Também as perguntas são como as listas ou reorganizadas. Se você estiver usando uma setas para cima e para baixo (subindo ou descendo um slot de cada vez), o i iria usar números inteiros, em seguida, trocar com o anterior (ou o próximo) em movimento.

Além disso, com que frequência você confirma, se o usuário pode fazer 250 mudanças e depois confirmar de uma vez, do que digamos inteiros com renumeração de novo ...

tl; dr: Precisa de mais informações.

Edit: "Wish lists" soa como um monte de listas pequenas (suposição, isso pode ser falso) .. Então eu digo Integer com renumeração. (Cada lista contém sua própria posição)

    
por 18.04.2013 / 02:00
fonte
3

Se o objetivo é minimizar o número de operações do banco de dados por operação de reordenação:

Supondo que

  • Todos os itens de compras podem ser enumerados com números inteiros de 32 bits.
  • Existe um limite máximo de tamanho para a lista de desejos de um usuário. (Eu vi algum site popular usar 20 - 40 itens como limite)

Armazena a lista de desejos ordenada do usuário como uma seqüência compacta de inteiros (matrizes inteiras) em uma coluna. Toda vez que a lista de desejos é reordenada, toda a matriz (única linha; coluna única) é atualizada - que deve ser executada com uma única atualização SQL.

link

Se o objetivo for diferente, continue com a abordagem "coluna de posição".

Com relação à "velocidade", certifique-se de comparar a abordagem do procedimento armazenado. Embora a emissão de 20 + separar atualizações para uma lista de pedidos aleatória possa ser lenta, pode haver uma maneira rápida de usar o procedimento armazenado.

    
por 18.04.2013 / 08:41
fonte
2

OK, enfrento esse problema complicado recentemente, e todas as respostas nesta postagem de Q & A deram muitas inspirações. Do jeito que eu vejo, cada solução tem seus prós e contras.

  • Se o campo position tiver que ser seqüencial sem intervalos, você basicamente precisará reordenar a lista inteira. Esta é uma operação O (N). A vantagem é que o lado do cliente não precisaria de nenhuma lógica especial para obter o pedido.

  • Se quisermos evitar a operação O (N) MAS AINDA manter uma seqüência precisa, uma das abordagens é usar "auto-referência para se referir ao valor anterior (ou próximo)". Este é um cenário de lista vinculada de livro de texto. Por design, ele não incorrerá "um monte de outros itens na lista". No entanto, isso exige que o lado do cliente (um serviço da web ou talvez um aplicativo móvel) implemente a lógica travesal da lista vinculada para obter o pedido.

  • Algumas variações não usam referência, ou seja, lista vinculada. Eles escolhem representar o pedido inteiro como um blob independente, como um array JSON em uma string [5,2,1,3,...] ; essa ordem será armazenada em um local separado. Essa abordagem também tem um efeito colateral de exigir que o código do lado do cliente mantenha esse blob de pedido separado.

  • Em muitos casos, não precisamos realmente armazenar a ordem exata, precisamos apenas manter uma classificação relativa entre cada registro. Portanto, podemos permitir intervalos entre registros sequenciais. Variações incluem: (1) usando números inteiros com lacunas como 100, 200, 300 ... mas você rapidamente ficará sem lacunas e precisará do processo de recuperação; (2) usando o decimal que vem com lacunas naturais, mas você precisará decidir se pode conviver com o eventual limitação de precisão; (3) usando a classificação baseada em string conforme descrito em esta resposta mas tenha cuidado com armadilhas de implementação complicadas .

  • A resposta real pode ser "depende". Revise sua exigência de negócios. Por exemplo, se é um sistema de lista de desejos, pessoalmente eu ficaria feliz em usar um sistema organiza por apenas alguns postos como "must-have", "good-to-have", "talvez mais tarde" e, em seguida, apresentar itens sem particular ordem dentro de cada classificação. Se for um sistema de entrega, você pode muito bem usar o tempo de entrega como uma classificação aproximada que vem com lacuna natural (e prevenção de conflitos naturais, pois nenhuma entrega aconteceria ao mesmo tempo). Sua milhagem pode variar.

por 16.07.2018 / 04:51
fonte
1

Use um número de ponto flutuante para a coluna de posição.

Você pode reorganizar a lista alterando apenas a coluna de posição na linha "movida".

Basicamente, se o usuário quiser posicionar "vermelho" depois de "azul", mas antes de "amarelo"

Então você só precisa calcular

red.position = ((yellow.position - blue.position) / 2) + blue.position

Após alguns milhões de reposicionamentos, você pode obter números de ponto flutuante tão pequenos que não há "entre" - mas isso é quase tão provável quanto avistar um unicórnio.

Você poderia implementar isso usando um campo inteiro com uma lacuna inicial de, digamos, 1000. Assim, seu oredring inicial seria 1000- > blue, 2000- > Yellow, 3000- > Red. Depois de "mover" Vermelho após azul, você terá 1000- > azul, 1500- > Vermelho, 2000- > Amarelo.

O problema é que, com um espaço inicial aparentemente grande de 1000, apenas 10 movimentos o levarão a uma situação como 1000- > blue, 1001-puce, 1004- > biege ...... onde você não será mais possível inserir nada depois de "azul" sem renumerar toda a lista. Usando números de ponto flutuante sempre haverá um ponto "intermediário" entre as duas posições.

    
por 18.04.2013 / 03:48
fonte