Come conservare gli articoli ordinati che cambiano spesso posizione in DB

Question

Devo essere in grado di memorizzare un grande elenco di articoli ordinati nel DB. Finora questo è straight-forward:

ID Position OtherFields 
1  45  ... 
2 4736  ... 
3 514  ... 
... 

Nelle query, ho sempre bisogno di ottenere solo alcuni elementi (filtrati in base OtherFields) ma nell'ordine corretto. Facile, mettendo un indice sulla posizione e usando "ordina per posizione".

Ora il problema: Gli articoli cambiare la loro posizione di frequente, e non solo da 1 o 2. Se ID 2 cambia la posizione 4736-2000, ho bisogno di aggiornare la sua posizione e quella di tutti gli elementi tra vecchia posizione 2000 e 4735, aggiungendo 1 in ogni riga. E non è solo un ID che cambia per transazione, ma alcuni, e ci possono essere molte transazioni in breve tempo.

Penso che il modo più elegante per gestire il aggiornamento problema sarebbe utilizzando una lista collegata al posto di una colonna posizione in cui posso semplicemente rimuovere ID 2 dalla sua vecchia posizione, collegando il suo predecessore al suo successore e poi inserirla altrove collegandolo tra il suo nuovo predecessore e il suo successore. Sarebbe un numero costante e limitato di aggiornamenti per cambio di posizione e sarebbe anche il mio modo preferito di gestire le modifiche (in Java nel mio caso). Tuttavia, questo solleva il problema N + 1 per nell'effettuare l'interrogazione nell'ordine corretto: anche per alcuni elementi, nel caso peggiore devo passare per l'intero elenco per trovare il loro ordine corretto.

Quindi la mia domanda è: cosa consiglieresti per ottenere un buon equilibrio tra gli aggiornamenti necessari e le prestazioni delle query?

Finora vedo due direzioni promettenti:

1. c'è un DBMS (idealmente OpenSource) in grado di gestire le liste collegate non solo con lo zucchero sintattico, ma anche con una buona prestazione, per esempio usando gli indici interni per gli elementi collegati?

2. Forse sarebbe anche un'opzione per avere solo un BLOB in cui sarebbe archiviata l'intera lista collegata! Quanto grande potrebbe ottenere una tale lista collegata/quanta memoria utilizzerebbe nel DB e quando viene scaricata diciamo 1.000.000 di voci? Sto usando Java + Hibernate nel caso abbia importanza. Immagino che elaborare anche l'intera lista in memoria dopo aver recuperato il BLOB dovrebbe essere piuttosto veloce !?

Ma naturalmente anche altre idee sono benvenute!

Answer 1

Se si riduce il vincolo che la colonna Position deve contenere numeri interi da 1 a N e invece consente di contenere qualsiasi numero, è possibile eseguire sia ricerche che aggiornamenti in modo efficiente.

È possibile inserire un elemento tra due altri elementi con posizione A e B calcolando il DIV medio (A + B). Ad esempio, se A è 10000 e B è 12000, la nuova posizione è 11000. Occasionalmente si esaurire gli spazi a causa del clustering, a quel punto è possibile eseguire l'intera tabella ridistribuendo le posizioni in modo più uniforme.

Answer 2

Quanto segue potrebbe essere utile.Non rispondere alle vostre domande direttamente, ma potrebbe far luce su come fare questo (se è possibile per le vostre esigenze):

ranking entries in mysql table

Answer 3

Cosa succede ad usare un decimale per posizione? Se lo fai, è possibile utilizzare il seguente metodo per metterla tra le altre posizioni:

record originali sono:

ID Position Otherfields 
-------------------------- 
1  1.0 
2  2.0 
. 
. 
. 
5000 5000.0 

Poi dicono si sposta ID da 1 a poco prima 5000

ID Position Otherfields 
-------------------------- 
1  4999.9 
2  2.0 
. 
. 
. 
5000 5000.0 

Ora diciamo che vuoi inserire l'ID 2 tra 1 e 5000:

ID Position Otherfields 
-------------------------- 
1  4999.9 
2  4999.91 
. 
. 
. 
5000 5000.0 

In questo modo si modifica solo una registrazione d ...

UPDATE:

dopo aver riletto @ Mark Byers' suggerimento sembra che le nostre soluzioni sono molto simili, anche se con un decimale sembra molto più semplice per me ...