Ordenação arbitrária de registros em uma tabela

Uma necessidade comum ao usar um banco de dados é acessar os registros em ordem. Por exemplo, se eu tiver um blog, desejo reorganizar minhas postagens em ordem arbitrária. Essas entradas costumam ter muitos relacionamentos, portanto, um banco de dados relacional parece fazer sentido.

A solução comum que eu vi é adicionar uma coluna inteira order:

CREATE TABLE AS your_table (id, title, sort_order)
AS VALUES
  (0, 'Lorem ipsum',   3),
  (1, 'Dolor sit',     2),
  (2, 'Amet, consect', 0),
  (3, 'Elit fusce',    1);

Em seguida, podemos classificar as linhas orderpara obtê-las na ordem correta.

No entanto, isso parece desajeitado:

• Se eu quiser mover o registro 0 para o início, preciso reordenar todos os registros
• Se eu quiser inserir um novo registro no meio, preciso reordenar todos os registros depois dele.
• Se eu quiser remover um registro, tenho que reordenar todos os registros depois dele.

É fácil imaginar situações como:

• Dois registros têm o mesmo order
• Existem lacunas nos orderregistros entre

Isso pode acontecer com bastante facilidade por vários motivos.

Esta é a abordagem que aplicativos como o Joomla adotam:

Você pode argumentar que a interface aqui é ruim e que, em vez de os humanos editarem números diretamente, eles devem usar setas ou arrastar e soltar - e você provavelmente estaria certo. Mas nos bastidores, a mesma coisa está acontecendo.

Algumas pessoas propuseram usar um decimal para armazenar a ordem, para que você possa usar "2.5" para inserir um registro entre os registros nas ordens 2 e 3. E enquanto isso ajuda um pouco, é sem dúvida ainda mais confuso, porque você pode acabar com decimais estranhos (onde você para? 2,75? 2,875? 2,8125?)

Existe uma maneira melhor de armazenar pedidos em uma tabela?

Se eu quiser mover o registro 0 para o início, preciso reordenar todos os registros

Não, existe uma maneira mais simples.

update your_table
set order = -1 
where id = 0;

Se eu quiser inserir um novo registro no meio, preciso reordenar todos os registros depois dele.

Isso é verdade, a menos que você use um tipo de dados que suporte valores "entre". Os tipos flutuante e numérico permitem atualizar um valor para, digamos, 2,5. Mas varchar (n) também funciona. (Pense em 'a', 'b', 'c'; depois pense em 'ba', 'bb', 'bc'.)

Se eu quiser remover um registro, tenho que reordenar todos os registros depois dele.

Não, existe uma maneira mais simples. Apenas exclua a linha. As linhas restantes ainda serão classificadas corretamente.

É fácil imaginar situações como:

Dois registros têm a mesma ordem

Uma restrição única pode impedir isso.

Existem lacunas na ordem entre os registros

As lacunas não têm efeito sobre como um dbms classifica valores em uma coluna.

Algumas pessoas propuseram usar um decimal para armazenar a ordem, para que você possa usar "2.5" para inserir um registro entre os registros nas ordens 2 e 3. E enquanto isso ajuda um pouco, é sem dúvida ainda mais confuso, porque você pode acabar com decimais estranhos (onde você para? 2,75? 2,875? 2,8125?)

Você não para até que precise . O dbms não tem problema ao classificar valores com 2, 7 ou 15 casas após o ponto decimal.

Acho que seu problema real é que você deseja ver os valores na ordem de classificação como números inteiros. Você pode fazer isso.

create table your_table (
  id int primary key, 
  title varchar(13), 
  sort_order float
);

insert into your_table values
(0, 'Lorem ipsum', 2.0),
(1, 'Dolor sit', 1.5),
(2, 'Amet, consect', 0.0),
(3, 'Elit fusce', 1.0);

-- This windowing function will "transform" the floats into sorted integers.
select id, title,
       row_number() over (order by sort_order)
from your_table

É muito simples. Você precisa ter uma estrutura de "buraco de cardinalidade":

Você precisa ter 2 colunas:

1. pk = 32 bits integer
2. ordem = 64 bits bigint( não double )

Inserir / atualizar

1. Ao inserir o primeiro novo registro, defina order = round(max_bigint / 2).
2. Ao inserir no início da tabela, defina order = round("order of first record" / 2)
3. Ao inserir no final da tabela, defina order = round("max_bigint - order of last record" / 2) 4) Ao inserir no meio, definaorder = round("order of record before - order of record after" / 2)

Este método tem uma cardinalidade muito grande. Se você tiver um erro de restrição ou se tiver uma cardinalidade pequena, poderá reconstruir a coluna da ordem (normalizar).

Na situação máxima com normalização (com essa estrutura), você pode ter um "buraco de cardinalidade" em 32 bits.

Lembre-se de não usar tipos de ponto flutuante - a ordem deve ser um valor preciso!

Geralmente, a encomenda é feita de acordo com algumas informações nos registros, título, ID ou o que for apropriado para essa situação específica.

Se você precisar de um pedido especial, usar uma coluna inteira não é tão ruim quanto pode parecer. Por exemplo, para deixar espaço para um registro entrar em 5º lugar, você pode fazer algo como:

update table_1 set place = place + 1 where place > 5.

Espero que você possa declarar a coluna uniquee talvez ter um procedimento para tornar os rearranjos "atômicos". Os detalhes dependem do sistema, mas essa é a ideia geral.

… É sem dúvida ainda mais confuso porque você pode acabar com decimais estranhos (onde você para? 2,75? 2,875? 2,8125?)

Quem se importa? Esses números estão disponíveis apenas para o computador lidar, portanto, não importa quantos dígitos fracionários eles tenham ou quão feios eles nos pareçam.

O uso de valores decimais significa que, para mover o item F entre os itens J e K, basta selecionar os valores da ordem para J e K, depois calculá-los como média e atualizar F. Duas instruções SELECT e uma instrução UPDATE (provavelmente feitas usando isolamento serializável para evitar bloqueios).

Se você deseja visualizar números inteiros em vez de frações na saída, calcule números inteiros no aplicativo cliente ou use as funções ROW_NUMBER () ou RANK () (se o seu RDBMS as incluir).

No meu próprio projeto, estou planejando tentar uma solução semelhante à solução de número decimal, mas usando matrizes de bytes:

def pad(x, x_len, length):
    if x_len >= length:
        return x
    else:
        for _ in range(length - x_len):
            x += b"\x00"
        return x

def order_index(_from, _to, count, length=None):
    assert _from != _to
    assert _from < _to

    if not length:
        from_len = len(_from)
        to_len = len(_to)
        length = max(from_len, to_len)

        _from = pad(_from, from_len, length)
        _to = pad(_to, to_len, length)

    from_int = int.from_bytes(_from, "big")
    to_int = int.from_bytes(_to, "big")
    inc = (to_int - from_int)//(count + 1)
    if not inc:
        length += 1
        _from += b"\x00"
        _to += b"\x00"
        return order_index(_from, _to, count, length)

    return (int.to_bytes(from_int + ((x+1)*inc), length, "big") for x in range(count))

>>> index = order_index(b"A", b"Z", 24)
>>> [x for x in index]
[b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X', b'Y']
>>> 
>>> index = order_index(b"A", b"Z", 25)
>>> [x for x in index]
[b'A\xf6', b'B\xec', b'C\xe2', b'D\xd8', b'E\xce', b'F\xc4', b'G\xba', b'H\xb0', b'I\xa6', b'J\x9c', b'K\x92', b'L\x88', b'M~', b'Nt', b'Oj', b'P`', b'QV', b'RL', b'SB', b'T8', b'U.', b'V$', b'W\x1a', b'X\x10', b'Y\x06']

A idéia é que você nunca pode ficar sem os possíveis valores intermediários, porque você apenas anexará b"\x00"a aos registros envolvidos se precisar de mais valores. ( inté ilimitado no Python 3, caso contrário, você teria que escolher uma fatia dos bytes no final para comparar, supondo que, entre dois valores adjacentes, as diferenças seriam compactadas no final.)

Por exemplo, dizer que você tem dois registros, b"\x00"e b"\x01", e você quer um registro para ir entre eles. Não há valores disponíveis entre 0x00e 0x01, portanto, você anexa b"\x00"a ambos, e agora você tem vários valores entre eles, que podem ser usados ​​para inserir novos valores.

>>> records = [b"\x00", b"\x01", b"\x02"]
>>> values = [x for x in order_index(records[0], records[1], 3)]
>>> records = records + values
>>> records.sort()
>>> records
[b'\x00', b'\x00@', b'\x00\x80', b'\x00\xc0', b'\x01', b'\x02']

O banco de dados pode classificá-lo facilmente, porque tudo acaba em ordem lexicográfica. Se você excluir um registro, ele ainda estará em ordem. No meu projeto, criei b"\x00"e b"\xff"as FIRSTe os LASTregistros, no entanto, para usá-los como valores virtuais "from" e "to" para preceder / acrescentar novos registros:

>>> records = []
>>> value = next(order_index(FIRST, LAST, 1))
>>> value
b'\x7f'
>>> records.append(value)
>>> value = next(order_index(records[0], LAST, 1))
>>> value
b'\xbf'
>>> records.append(value)
>>> records.sort()
>>> records
[b'\x7f', b'\xbf']
>>> value = next(order_index(FIRST, records[0], 1))
>>> value
b'?'
>>> records.append(value)
>>> records.sort()
>>> records
[b'?', b'\x7f', b'\xbf']

Achei esta resposta muito melhor. Citando-o inteiramente:

Os bancos de dados são otimizados para certas coisas. A atualização rápida de muitas linhas é uma delas. Isso se torna especialmente verdadeiro quando você deixa o banco de dados fazer seu trabalho.

Considerar:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

E você quer ir Beat Itpara o final, você teria duas consultas:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

E é isso. Isso aumenta muito bem com números muito grandes. Tente colocar alguns milhares de músicas em uma lista de reprodução hipotética em seu banco de dados e veja quanto tempo leva para mover uma música de um local para outro. Como estes têm formas muito padronizadas:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

Você tem duas instruções preparadas que podem ser reutilizadas com muita eficiência.

Isso fornece algumas vantagens significativas - a ordem da tabela é algo que você pode pensar. A terceira música tem um orderde 3, sempre. A única maneira de garantir isso é usar números inteiros consecutivos como a ordem. O uso de listas pseudo-vinculadas ou números decimais ou números inteiros com lacunas não permitirá garantir essa propriedade; nesses casos, a única maneira de obter a enésima música é ordenar a tabela inteira e obter o enésimo registro.

E realmente, isso é muito mais fácil do que você pensa. É simples descobrir o que você deseja fazer, gerar as duas instruções de atualização e outras pessoas olharem para essas duas instruções de atualização e perceberem o que está sendo feito.