Representam ordenação em um banco de dados relacional

votos
32

Eu tenho uma coleção de objetos em um banco de dados. Imagens em uma galeria de fotos, produtos em um catálogo, capítulos de um livro, etc. Cada objeto é representado como uma linha. Eu quero ser capaz de ordenar arbitrariamente essas imagens, armazenar essa ordenação no banco de dados, então quando eu exibir os objetos, eles serão na ordem certa.

Por exemplo, digamos que eu estou escrevendo um livro, e cada capítulo é um objeto. I escrever meu livro, e colocar os capítulos na seguinte ordem:

Introdução, acessibilidade, Form vs. Function, erros, consistência, conclusão, índice

Ele vai para o editor, e volta com a seguinte ordem sugerida:

Introdução, forma, função, acessibilidade, consistência, erros, conclusão, índice

Como posso guardar essa ordenação no banco de dados de forma robusta, eficiente?

Eu tive as seguintes idéias, mas eu não estou emocionado com qualquer um deles:

  1. Array. Cada linha tem um ID de encomenda, quando a ordem é alterado (por meio de uma remoção seguida por uma inserção), os IDs dos pedidos são actualizados. Isso faz com que a recuperação fácil, uma vez que é apenas ORDER BY, mas parece fácil de quebrar.

    // REMOVAL
    UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
    UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
    // INSERT IGNORE ION
    UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
    UPDATE ... SET orderID=insertionID WHERE ID=addedID

  2. Lista encadeada. Cada linha tem uma coluna para o id da próxima linha na ordenação. Traversal parece caro aqui, embora possa por alguma forma de usar o ORDER BYque eu não estou pensando.

  3. Matriz espaçada. Defina o orderingID (como usado em # 1) para ser grande, de modo que o primeiro objeto é de 100, o segundo é de 200, etc. Então, quando uma inserção acontece, você só colocá-lo em (objectBefore + objectAfter)/2. Claro, isso teria de ser reequilibrado, ocasionalmente, para que você não tem coisas muito próximas entre si (mesmo com carros alegóricos, você finalmente correr em erros de arredondamento).

Nenhum deles parece particularmente elegante para mim. Alguém tem uma maneira melhor de fazer isso?

Publicado 22/08/2008 em 00:01
fonte usuário
Em outras línguas...                            


11 respostas

votos
5

Uma outra alternativa seria (se o seu RDBMS suporta) a utilizar colunas do tipo array. Enquanto isso quebra as regras de normalização, ele pode ser útil em situações como esta. Um banco de dados que eu sei sobre o que tem matrizes é PostgreSQL.

Respondeu 22/08/2008 em 06:32
fonte usuário

votos
3

Apenas um pensamento, considerando a opção # 1 vs # 3 : não a opção variedade espaçadas (# 3), apenas adiar o problema da matriz normal (# 1)? Seja qual for o algoritmo que você escolher, ou ele está quebrado, e você tiver problemas com o nº 3 posterior, ou ele funciona, em seguida, # 1 deve funcionar tão bem.

Respondeu 25/08/2008 em 18:24
fonte usuário

votos
3

O mixin acts_as_list em Rails lida com isso, basicamente, a maneira como você descrita no nº 1. Ele procura por uma coluna inteira chamada posição (do qual você pode substituir a nome do curso) e usando isso para fazer um ORDER BY. Quando você quiser reordenar as coisas que você atualizar as posições. Ele me serviu muito bem cada vez que eu usei-o.

Como uma nota lateral, você pode remover a necessidade de sempre se re-posicionamento em INSERT IGNORE S / exclusões usando numeração escassa - tipo de como voltar básica no dia ... você pode numerar as posições 10, 20, 30, etc. e se você precisa inserir algo entre 10 e 20 você só inseri-lo com uma posição de 15. da mesma forma, ao eliminar você pode simplesmente excluir a linha e deixar a lacuna. Você só precisa fazer re-numeração quando você realmente mudar a ordem ou se você tentar fazer uma inserção e não há nenhuma lacuna apropriada para inserir.

É claro que, dependendo da sua situação particular (por exemplo, se você tem as outras linhas já carregados na memória ou não) ele pode ou não pode fazer sentido usar a abordagem lacuna.

Respondeu 22/08/2008 em 00:11
fonte usuário

votos
2

Usar um número de ponto flutuante para representar a posição de cada item:

Item 1 -> 0.0

Item 2 -> 1.0

Item 3 -> 2.0

Item 4 -> 3.0

Você pode colocar qualquer item entre quaisquer outros dois itens por simples bisection:

Item 1 -> 0.0

Item 4 -> 0,5

Item 2 -> 1.0

Item 3 -> 2.0

(4 Item movido entre os itens 1 e 2).

O processo bisection pode continuar quase indefinidamente devido à forma como números de ponto flutuante são codificados em um sistema de computador.

Item 4 -> 0,5

Item 1 -> 0,75

Item 2 -> 1.0

Item 3 -> 2.0

(Mover o item 1 para a posição logo após o ponto 4)

Respondeu 18/09/2008 em 01:22
fonte usuário

votos
2

Se os objetos não são fortemente digitado por outros mesas, e as listas são curtos, apagando tudo no domínio e apenas re-inserir a lista correta é o mais fácil. Mas isso não é prático se as listas são grandes e você tem muitas limitações para abrandar a exclusão. Eu acho que seu primeiro método é realmente o mais limpo. Se você executá-lo em uma transação que você pode ter certeza que nada de estranho acontece enquanto você está no meio da atualização de parafuso até o fim.

Respondeu 22/08/2008 em 02:39
fonte usuário

votos
2

Eu faria um número consecutivo, com um gatilho na tabela que "abre espaço" para uma prioridade se ele já existe.

Respondeu 22/08/2008 em 00:12
fonte usuário

votos
1

Desde que eu principalmente correr para isso com Django, eu encontrei esta solução ser a mais viável. Parece que não há qualquer "caminho certo" para fazer isso em um banco de dados relacional.

Respondeu 29/03/2009 em 15:47
fonte usuário

votos
1

Eu tive esse problema também. Eu estava sob pressão de tempo pesado (não são todos nós) e eu fui com a opção # 1, e apenas linhas atualizadas que mudaram.

Se você trocar o item 1 com o item 10, basta fazer duas atualizações para atualizar os números de ordem do item 1 e ponto 10. Sei que é através de algoritmos simples, e é O (n) pior caso, mas que pior caso é quando você tem uma permutação total da lista. Quantas vezes é que vai acontecer? Isso é para você responder.

Respondeu 18/09/2008 em 01:34
fonte usuário

votos
1

Eu fiz isso no meu último projeto, mas foi para uma tabela que apenas ocasionalmente precisava ser especificamente ordenado, e não foi acessado com muita freqüência. Eu acho que a matriz espaçadas seria a melhor opção, porque reordenação seria mais barato no caso da média, apenas envolvendo uma alteração em um valor e uma consulta em duas).

Além disso, eu imagino ORDER BY seria muito altamente otimizado por fornecedores de banco de dados, então aproveitando que a função seria vantajoso para o desempenho em oposição à implementação lista ligada.

Respondeu 22/08/2008 em 02:58
fonte usuário

votos
0

Esquema 1 e Esquema # 3 tem a mesma complexidade em todas as operações, exceto INSERTas gravações. Esquema # 1 tem o (n) escreve sobre INSERTe Esquema # 3 tem ó (1) escreve sobre INSERT.

Para cada outra operação de banco de dados, a complexidade é o mesmo.

Esquema nº 2 não deve mesmo ser considerado porque sua DELETErequer O (n) lê e escreve. Esquema 1 e Esquema # 3 tem O (1) DELETEtanto para ler e escrever.

novo método

Se os seus elementos têm um elemento pai distinta (ie eles compartilham uma linha de chave estrangeira), então você pode tentar o seguinte ...

Django oferece uma solução de banco de dados agnóstica para armazenar listas de números inteiros dentro CharField(). Uma desvantagem é que o comprimento máximo da cadeia armazenada não pode ser maior do que max_length, o que é dependente do DB.

Em termos de complexidade, isso daria Esquema # 1 O (1) escreve para INSERT, porque a informação ordenação seria armazenado como um único campo na linha do elemento pai.

Outra desvantagem é que um JOINpara a linha pai é agora obrigado a atualizar ordenação.

https://docs.djangoproject.com/en/dev/ref/validators/#django.core.validators.validate_comma_separated_integer_list

Respondeu 15/12/2018 em 14:48
fonte usuário

votos
0

Eu tive o mesmo problema e provavelmente passou pelo menos uma semana de mim mesmo sobre a modelagem de dados adequada, mas eu acho que eu finalmente consegui-lo. Usando o tipo de dados de matriz no PostgreSQL, você pode armazenar a chave primária de cada item solicitado e atualizar essa matriz em conformidade com inserções ou exclusões quando seu pedido mudanças. Fazendo referência a uma única linha permitirá que você para mapear todos os seus objetos com base na ordenação na coluna matriz.

Ainda é um pouco agitado de uma solução, mas ele provavelmente vai funcionar melhor do que a opção # 1, uma vez que a opção 1 requer a atualização do número de ordem de todas as outras linhas quando encomendar mudanças.

Respondeu 28/01/2016 em 10:32
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more