Memorizzazione di un elenco riordinabile in un database

41

Sto lavorando a un sistema di liste di desideri, in cui gli utenti possono aggiungere elementi alle loro varie liste di desideri e ho intenzione di consentire agli utenti di riordinare gli articoli in seguito. Non sono molto sicuro del modo migliore per archiviarlo in un database rimanendo veloce e senza problemi (questa app verrà utilizzata da una base di utenti abbastanza ampia, quindi non voglio che vada giù per ripulire le cose).

Inizialmente ho provato una colonna position , ma sembra che sarebbe abbastanza inefficiente dover cambiare il valore di posizione di ogni altro oggetto quando li sposti.

Ho visto persone che usano un riferimento personale per riferirsi al valore precedente (o successivo), ma, ancora una volta, sembra che tu debba aggiornare un sacco di altri elementi nell'elenco.

Un'altra soluzione che ho visto è usare i numeri decimali e attaccare gli elementi negli spazi vuoti tra loro, che sembra la soluzione migliore finora, ma sono sicuro che ci deve essere un modo migliore.

Direi che un elenco tipico potrebbe contenere fino a circa 20 voci, e probabilmente lo limiterò a 50. Il riordino si baserà sul trascinamento della selezione e verrà probabilmente eseguito in lotti per prevenire condizioni di gara e tale dalle richieste Ajax. Sto usando postgres (su heroku) se è importante.

Qualcuno ha qualche idea?

Ciao per qualsiasi aiuto!

    
posta Tom Brunoli 18.04.2013 - 01:35
fonte

8 risposte

26

Per prima cosa, non provare a fare qualcosa di intelligente con i numeri decimali, perché ti faranno dispetto. REAL e DOUBLE PRECISION sono inesatti e potrebbero non rappresentare correttamente ciò che hai inserito. NUMERIC è esatto, ma la giusta sequenza di mosse ti farà perdere la precisione e la tua implementazione si interromperà male.

Limitare le mosse a singoli alti e bassi rende l'intera operazione molto facile. Per un elenco di elementi numerati in sequenza, è possibile spostare un elemento diminuendo la sua posizione e incrementando il numero di posizione di qualunque sia il decremento precedente. (In altre parole, l'elemento 5 diventerebbe 4 e quello che era l'elemento 4 diventa 5 , in effetti uno scambio come descritto da Morons nella sua risposta.) Spostarlo sarebbe l'opposto. Indicizza la tua tabella in base a qualsiasi elemento identifica un elenco e una posizione e puoi farlo con due UPDATE s all'interno di una transazione che verrà eseguita molto rapidamente. A meno che i tuoi utenti non riorganizzino le loro liste a velocità sovrumane, questo non causerà molto carico.

Le mosse drag-and-drop (ad esempio, spostare l'elemento 6 per sedersi tra gli elementi 9 e 10 ) sono un po 'più complicate e devono essere fatte in modo diverso a seconda che la nuova posizione sia sopra o sotto vecchia. Nell'esempio sopra, devi aprire un buco incrementando tutte le posizioni maggiori di 9 , aggiornando la posizione di 6 come nuova 10 e quindi decrementando la posizione di tutto superiore a 6 a riempire il posto vacante. Con la stessa indicizzazione che ho descritto prima, questo sarà veloce. Puoi farlo andare un po 'più veloce di quanto ho descritto, riducendo al minimo il numero di righe toccate dalla transazione, ma questa è una microottimizzazione di cui non hai bisogno finché non puoi provare che c'è un collo di bottiglia.

In ogni caso, tentare di superare il database con una soluzione fatta in casa, troppo intelligente per metà non porta solitamente al successo. I database che valgono la pena sono stati scrupolosamente scritti per fare queste operazioni molto, molto velocemente da persone che sono molto, molto brave a farlo.

    
risposta data 18.04.2013 - 14:16
fonte
10

"but it seems like that would be quite inefficient"

Hai misurato quello? O è solo un'ipotesi? Non fare assunzioni del genere senza alcuna prova.

"20 to 50 items per list"

Onestamente, questo non è "un sacco di elementi", per me sembra solo pochissimo.

Ti suggerisco di attenersi all'approccio della "posizione della colonna" (se questa è l'implementazione più semplice per te). Per elenchi di dimensioni così ridotte, non iniziare l'ottimizzazione non necessaria prima che si verifichino problemi di prestazioni reali

    
risposta data 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.

Perché? Supponiamo che tu prenda un approccio alla tabella dell'elenco collegato con colonne (listID, itemID, nextItemID).

L'inserimento di un nuovo elemento in un elenco costa un inserto e una riga modificata.

Il riposizionamento di un articolo costa tre modifiche di riga (l'elemento che viene spostato, l'elemento precedente e l'elemento prima della sua nuova posizione).

La rimozione di un elemento costa un'eliminazione e una riga modificata.

Questi costi rimangono gli stessi indipendentemente dal fatto che l'elenco contenga 10 elementi o 10.000 elementi. In tutti e tre i casi c'è una modifica in meno se la riga di destinazione è la prima voce dell'elenco. Se lavori più spesso sull'elemento ultimo dell'elenco potrebbe essere utile memorizzare prevItemID anziché successivo.

    
risposta data 11.11.2016 - 07:30
fonte
8

La stessa risposta da qui link

Soluzione: crea index una stringa (perché le stringhe, in sostanza, hanno una "precisione arbitraria" infinita). O se usi un int, incrementa index per 100 invece di 1.

Il problema di prestazioni è questo: non ci sono "tra" i valori tra due elementi ordinati.

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

Invece, fai come questo (migliore soluzione sotto):

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

Ancora meglio: ecco come Jira risolve questo problema. Il loro "rango" (quello che tu chiami indice) è un valore stringa che consente una tonnellata di respiro tra gli oggetti classificati.

Ecco un esempio reale di un database jira con cui lavoro

   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

Nota questo esempio hzztzz:i . Il vantaggio di un rank di stringa è che hai esaurito la stanza tra due elementi, tu ancora non devi ri-classificare qualcos'altro. Devi solo aggiungere altri caratteri alla stringa per restringere il campo.

    
risposta data 21.04.2018 - 15:21
fonte
5

Questa è davvero una questione di scala e utilizza il caso ..

Quanti oggetti ti aspetti in una lista? Se milioni, penso che gong la via decimale è ovvia.

Se 6 allora la rinumerazione di interi è la scelta più ovvia. S Anche le domande sono come le liste o riorganizzate. Se utilizzi frecce su e giù (spostandoti verso l'alto o verso il basso di uno slot alla volta), userei numeri interi e poi scambierò il prev (o il successivo) in movimento.

Anche con quale frequenza ti impegni, se l'utente può effettuare 250 modifiche, quindi effettua il commit in una volta, poi dico interi con la rinumerazione di nuovo ...

tl; dr: hai bisogno di ulteriori informazioni

Modifica: "Wish list" sembra un sacco di piccole liste (supposizione, questo può essere falso) .. Quindi dico Integer con rinumerazione. (Ogni lista contiene la propria posizione)

    
risposta data 18.04.2013 - 02:00
fonte
3

Se l'obiettivo è minimizzare il numero di operazioni del database per ogni operazione di riordino:

Supponendo che

  • Tutti gli articoli dello shopping possono essere enumerati con numeri interi a 32 bit.
  • Esiste un limite di dimensioni massime per la lista dei desideri di un utente. (Ho visto alcuni siti Web popolari utilizzare da 20 a 40 elementi come limite)

Memorizza la lista dei desideri ordinati dell'utente come una sequenza impacchettata di interi (matrici di interi) in una colonna. Ogni volta che la lista dei desideri viene riordinata, viene aggiornata l'intera matrice (riga singola, colonna singola), che deve essere eseguita con un singolo aggiornamento SQL.

link

Se l'obiettivo è diverso, segui l'approccio "colonna di posizione".

Per quanto riguarda la "velocità", assicurati di confrontare l'approccio della stored procedure. Sebbene pubblicare più di 20 aggiornamenti separati per una lista dei desideri sia casuale, potrebbe esserci un modo veloce con la stored procedure.

    
risposta data 18.04.2013 - 08:41
fonte
2

OK Affronto questo delicato problema di recente, e tutte le risposte in questo post di Q & A hanno dato molti spunti. Per come la vedo io, ogni soluzione ha i suoi pro e contro.

  • Se il campo position deve essere sequenziale senza spazi vuoti, dovrai sostanzialmente riordinare l'intero elenco. Questa è un'operazione O (N). Il vantaggio è che il lato client non avrebbe bisogno di alcuna logica speciale per ottenere l'ordine.

  • Se vogliamo evitare l'operazione O (N) MA ANCORA mantenere una sequenza precisa, uno degli approcci è usare "auto-riferimento per riferirsi al valore precedente (o successivo)". Questo è uno scenario elenco di libri di testo collegati. In base alla progettazione, NON incorre in "un sacco di altri articoli nell'elenco". Tuttavia, ciò richiede il lato client (un servizio Web o forse un'app mobile) per implementare la logica travesal della lista collegata per derivare l'ordine.

  • Alcune varianti non usano il riferimento, ad esempio la lista collegata. Scelgono di rappresentare l'intero ordine come un blob autonomo, come un JSON-array-in-a-string [5,2,1,3,...] ; tale ordine verrà quindi memorizzato in un luogo separato. Questo approccio ha anche un effetto collaterale nel richiedere il codice lato client per mantenere quel blob di ordine separato.

  • In molti casi, non abbiamo davvero bisogno di memorizzare l'ordine esatto, abbiamo solo bisogno di mantenere un rango relativo tra ogni record. Pertanto possiamo consentire intervalli tra record sequenziali. Le varianti includono: (1) utilizzo di interi con spazi come 100, 200, 300 ... ma si esauriranno rapidamente gli spazi vuoti e quindi sarà necessario il processo di recupero; (2) utilizzando decimale che viene fornito con spazi naturali, ma dovrai decidere se puoi vivere con l'eventuale limitazione di precisione; (3) usando il rank basato su stringhe come descritto in questa risposta ma fai attenzione trappole di implementazione difficili .

  • La vera risposta può essere "dipende". Rivedi i tuoi requisiti aziendali. Ad esempio, se si tratta di un sistema di liste dei desideri, personalmente userò felicemente un sistema organizzato da pochi ranghi come "must-have", "good-to-have", "forse-later", e quindi presentare gli articoli senza particolari ordine all'interno di ciascun grado. Se si tratta di un sistema di consegna, è possibile utilizzare molto bene i tempi di consegna come un rango approssimativo che si accompagna a un divario naturale (e alla prevenzione naturale dei conflitti in quanto nessuna consegna avverrebbe nello stesso momento). Il tuo chilometraggio può variare.

risposta data 16.07.2018 - 04:51
fonte
1

Utilizza un numero in virgola mobile per la colonna di posizione.

Puoi quindi riordinare la lista cambiando solo la colonna di posizione nella riga "spostata".

Fondamentalmente se il tuo utente vuole posizionare "rosso" dopo "blu" ma prima "giallo"

Quindi devi solo calcolare

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

Dopo alcuni milioni di riposizionamenti potresti ottenere dei numeri in virgola mobile così piccoli che non ci sono "tra" - ma questo è più probabile che avvistare un unicorno.

Potresti implementarlo usando un campo intero con un gap iniziale di dire 1000. Quindi il tuo oring iniziale dovrebbe essere 1000, > blu, 2000- > Giallo, 3000- > Rosso. Dopo aver "spostato" il rosso dopo il blu, avresti 1000- > blu, 1500- > Rosso, 2000- e gt; Giallo.

Il problema è che con un gap iniziale apparentemente ampio di 1000 un minimo di 10 mosse ti porterà in una situazione come 1000- > blue, 1001-puce, 1004- > biege ...... dove tu non sarà più possibile inserire nulla dopo "blu" senza ri-numerare l'intera lista. Usando i numeri in virgola mobile ci sarà sempre un punto "a metà strada" tra le due posizioni.

    
risposta data 18.04.2013 - 03:48
fonte

Leggi altre domande sui tag