Speichern einer nachbestellbaren Liste in einer Datenbank

54

Ich arbeite an einem Wishlist-System, in dem Benutzer Artikel zu ihren verschiedenen Wishlists hinzufügen können, und ich plane, Benutzern zu ermöglichen, die Artikel später nachzubestellen. Ich bin mir nicht ganz sicher, wie ich das am besten in einer Datenbank speichern soll, während ich schnell bleibe und nicht in Unordnung gerate (diese App wird von einer relativ großen Benutzerbasis verwendet, daher möchte ich nicht, dass es ausfällt Sachen aufräumen).

Ich habe anfangs eine positionSpalte ausprobiert , aber es scheint ziemlich ineffizient zu sein, den Positionswert jedes anderen Elements zu ändern, wenn Sie sie verschieben.

Ich habe Leute gesehen, die eine Selbstreferenz verwendet haben, um auf den vorherigen (oder nächsten) Wert zu verweisen, aber es scheint, als müssten Sie eine ganze Reihe anderer Elemente in der Liste aktualisieren.

Eine andere Lösung, die ich gesehen habe, ist die Verwendung von Dezimalzahlen und das einfache Einfügen von Elementen in die Lücken zwischen ihnen. Dies scheint die bisher beste Lösung zu sein, aber ich bin mir sicher, dass es einen besseren Weg geben muss.

Ich würde sagen, eine typische Liste würde bis zu etwa 20 Elemente enthalten, und ich werde sie wahrscheinlich auf 50 begrenzen. Die Nachbestellung würde per Drag & Drop erfolgen und wird wahrscheinlich stapelweise erfolgen, um Rennbedingungen und dergleichen zu verhindern Ajax-Anfragen. Ich benutze Postgres (auf Heroku), wenn es darauf ankommt.

Hat jemand irgendwelche Ideen?

Prost für jede Hilfe!

Tom Brunoli
quelle
Können Sie ein wenig Benchmarking durchführen und uns mitteilen, ob IO oder Datenbank ein Engpass sein werden?
rwong
Verwandte Frage zum Stackoverflow .
Jordão
Mit Selbstreferenz müssen Sie nur 2 Elemente aktualisieren, wenn Sie ein Element von einem Ort in der Liste zum anderen verschieben. Siehe en.wikipedia.org/wiki/Linked_list
Pieter B
Hmm, ich bin mir nicht sicher, warum verknüpfte Listen in den Antworten kaum Beachtung finden.
Christiaan Westerbeek

Antworten:

32

Versuchen Sie zunächst nicht, mit Dezimalzahlen etwas Schlaues anzufangen, denn sie werden Sie ärgern. REALund DOUBLE PRECISIONsind ungenau und stellen möglicherweise nicht richtig dar, was Sie in sie setzen. NUMERICist genau, aber die richtige Abfolge von Zügen wird Ihnen die Präzision nehmen und Ihre Implementierung wird schlecht abbrechen.

Das Begrenzen von Bewegungen auf einzelne Höhen und Tiefen macht den gesamten Vorgang sehr einfach. Bei einer Liste mit fortlaufend nummerierten Elementen können Sie ein Element nach oben verschieben, indem Sie seine Position verringern und die Positionsnummer des vorherigen Dekrements erhöhen. (Mit anderen Worten, der Gegenstand 5würde werden 4und der , der Gegenstand war, 4wird 5effektiv ein Tausch, wie Morons in seiner Antwort beschrieben hat.) Das Herunterschieben wäre das Gegenteil. Indizieren Sie Ihre Tabelle nach einer eindeutigen Bezeichnung für eine Liste und Position, und Sie können dies mit zwei UPDATESekunden innerhalb einer Transaktion tun , die sehr schnell ausgeführt wird. Solange Ihre Benutzer ihre Listen nicht mit übermenschlicher Geschwindigkeit neu anordnen, ist dies nicht sehr belastend.

Drag-and-Drop-Bewegungen (z. B. Verschieben 6von Objekten zwischen Objekten 9und 10) sind etwas komplizierter und müssen unterschiedlich ausgeführt werden, je nachdem, ob die neue Position über oder unter der alten Position liegt. Im obigen Beispiel müssen Sie ein Loch öffnen, indem Sie alle Positionen, die größer als sind 9, erhöhen, die Position des Elements 6auf die neue Position aktualisieren 10und dann die Position von allem, was größer als 6die freie Stelle ist, verringern . Mit der gleichen Indexierung, die ich zuvor beschrieben habe, wird dies schnell gehen. Sie können dies tatsächlich etwas beschleunigen, indem Sie die Anzahl der Zeilen, die die Transaktion berührt, minimieren. Dies ist jedoch eine Mikrooptimierung, die Sie erst dann benötigen, wenn Sie nachweisen können, dass es einen Engpass gibt.

In beiden Fällen führt der Versuch, die Datenbank mit einer hausgemachten, allzu cleveren Lösung zu übertreffen, normalerweise nicht zum Erfolg. Datenbanken, die ihr Geld wert sind, wurden sorgfältig geschrieben, um diese Operationen sehr, sehr schnell von Leuten durchzuführen, die sehr, sehr gut darin sind.

Blrfl
quelle
Genau so habe ich es in einem System zur Angebotserstellung gehandhabt, das wir vor einer Million Jahren hatten. Selbst in Access war das Update sehr schnell.
HLGEM
Danke für die Erklärung, Blrfl! Ich habe versucht, die letztere Option auszuführen, aber ich habe festgestellt, dass beim Löschen von Elementen aus der Mitte der Liste Lücken in den Positionen verbleiben (dies war eine ziemlich naive Implementierung). Gibt es eine einfache Möglichkeit, Lücken wie diese zu vermeiden, oder muss ich sie jedes Mal manuell neu bestellen (wenn ich sie überhaupt verwalten muss)?
Tom Brunoli
2
@TomBrunoli: Ich würde ein wenig über die Implementierung nachdenken müssen, bevor ich das mit Sicherheit sage, aber Sie könnten in der Lage sein, die meisten oder alle Umnummerierungen automatisch mit Triggern durchzuführen. Wenn Sie z. B. Element 7 löschen, dekrementiert der Trigger alle Zeilen in derselben Liste, deren Nummer größer als 7 ist, nachdem der Löschvorgang ausgeführt wurde. Einfügungen würden dasselbe tun (das Einfügen eines Elements 7 würde alle Zeilen 7 oder höher inkrementieren). Der Auslöser für ein Update (z. B. Punkt 3 zwischen 9 und 10 verschieben) wäre etwas komplexer, liegt aber sicherlich im Bereich des Machbaren.
Blrfl
Ich hatte vorher noch nie nach Triggern gesucht, aber das scheint eine gute Möglichkeit zu sein.
Tom Brunoli
1
@TomBrunoli: Mir fällt auf, dass die Verwendung von Triggern zu Kaskaden führen kann. Gespeicherte Prozeduren mit allen Änderungen in einer Transaktion sind möglicherweise der bessere Weg dafür.
Blrfl
15

Dieselbe Antwort von hier https://stackoverflow.com/a/49956113/10608


Lösung: Erstellen Sie indexeine Zeichenfolge (da Zeichenfolgen im Wesentlichen eine unendliche "willkürliche Genauigkeit" aufweisen). Oder, wenn Sie ein int verwenden, erhöhen Sie indexum 100 anstelle von 1.

Das Leistungsproblem besteht darin, dass zwischen zwei sortierten Elementen keine Zwischenwerte vorhanden sind.

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

Mach es stattdessen so (bessere Lösung unten):

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

Noch besser: So löst Jira dieses Problem. Ihr "Rang" (was Sie als Index bezeichnen) ist ein String-Wert, der eine Tonne Luft zwischen den bewerteten Gegenständen lässt.

Hier ist ein echtes Beispiel einer Jira-Datenbank, mit der ich arbeite

   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

Beachten Sie dieses Beispiel hzztzz:i. Der Vorteil eines String-Ranges ist, dass Sie keinen Platz mehr zwischen zwei Gegenständen haben und trotzdem nichts anderes neu einstufen müssen. Sie müssen nur mehr Zeichen an die Zeichenfolge anhängen, um den Fokus einzugrenzen.

Alexander Bird
quelle
1
Ich habe versucht, einen Weg zu finden, um dies zu erreichen, indem ich nur einen einzigen Datensatz aktualisiere, und diese Antwort erklärt die Lösung, die ich mir in meinem Kopf ausgedacht habe, sehr gut.
NSjonas
13

Ich habe Leute gesehen, die eine Selbstreferenz verwendet haben, um auf den vorherigen (oder nächsten) Wert zu verweisen, aber es scheint, als müssten Sie eine ganze Reihe anderer Elemente in der Liste aktualisieren.

Warum? Angenommen, Sie verwenden eine verknüpfte Listentabelle mit Spalten (listID, itemID, nextItemID).

Das Einfügen eines neuen Elements in eine Liste kostet eine Einfügung und eine geänderte Zeile.

Das Neupositionieren eines Elements kostet drei Zeilenmodifikationen (das zu verschiebende Element, das Element davor und das Element vor seinem neuen Standort).

Das Entfernen eines Elements kostet eine Lösch- und eine geänderte Zeile.

Diese Kosten bleiben gleich, unabhängig davon, ob die Liste 10 Elemente oder 10.000 Elemente enthält. In allen drei Fällen gibt es eine Änderung weniger, wenn die Zielzeile das erste Listenelement ist. Wenn Sie häufiger mit dem letzten Listenelement arbeiten, kann es hilfreich sein, prevItemID anstelle von next zu speichern.

sqweek
quelle
10

"aber es scheint so, als wäre das ziemlich ineffizient"

Hast du das gemessen ? Oder ist das nur eine Vermutung? Machen Sie solche Annahmen nicht ohne Beweise.

"20 bis 50 Elemente pro Liste"

Ehrlich gesagt, das ist nicht "eine ganze Reihe von Dingen", für mich klingt das nur nach sehr wenigen.

Ich schlage vor, Sie halten sich an den "Positionsspalten" -Ansatz (wenn dies für Sie die einfachste Implementierung ist). Beginnen Sie bei solch kleinen Listengrößen nicht mit der unnötigen Optimierung, bevor Sie echte Leistungsprobleme feststellen

Doc Brown
quelle
6

Dies ist wirklich eine Frage des Maßstabs und des Anwendungsfalls.

Wie viele Elemente erwarten Sie in einer Liste? Wenn es Millionen sind, denke ich, dass Gong die Dezimaltrasse ist.

Bei 6 ist die Umnummerierung von ganzen Zahlen die naheliegende Wahl. s Die Frage ist auch, wie die Listen oder neu angeordnet werden. Wenn Sie einen Aufwärts- und einen Abwärtspfeil verwenden (um jeweils einen Steckplatz nach oben oder unten), würde das i Ganzzahlen verwenden und dann beim Verschieben mit dem vorherigen (oder nächsten) tauschen.

Außerdem, wie oft Sie festschreiben, wenn der Benutzer 250 Änderungen vornehmen kann, dann festschreiben Sie sofort, als ich Ganzzahlen mit der neuen Nummerierung wieder sage ...

tl; dr: Benötigen Sie weitere Informationen.


Edit: "Wish Lists" klingt wie eine Menge kleiner Listen (Annahme, das kann falsch sein). Also sage ich Integer mit Umnummerierung. (Jede Liste enthält ihre eigene Position)

Idioten
quelle
Ich werde die Frage mit etwas mehr Kontext aktualisieren
Tom Brunoli
Dezimalstellen funktionieren nicht, da die Genauigkeit begrenzt ist und jedes eingefügte Element möglicherweise 1 Bit benötigt
njzk2
3

Wenn das Ziel darin besteht, die Anzahl der Datenbankoperationen pro Neuordnungsoperation zu minimieren:

Vorausgesetzt, dass

  • Alle Einkaufsartikel können mit 32-Bit-Ganzzahlen aufgezählt werden.
  • Es gibt eine maximale Größenbeschränkung für die Wunschliste eines Benutzers. (Ich habe gesehen, dass einige beliebte Websites 20 - 40 Elemente als Limit verwenden.)

Speichern Sie die sortierte Wunschliste des Benutzers als gepackte Folge von Ganzzahlen (Integer-Arrays) in einer Spalte. Jedes Mal, wenn die Wunschliste neu angeordnet wird, wird das gesamte Array (einzelne Zeile; einzelne Spalte) aktualisiert - was mit einem einzelnen SQL-Update durchgeführt werden soll.

https://www.postgresql.org/docs/current/static/arrays.html


Wenn das Ziel anders ist, halten Sie sich an den Ansatz "Positionsspalte".


Stellen Sie in Bezug auf die "Geschwindigkeit" sicher, dass Sie den Ansatz für gespeicherte Prozeduren vergleichen. Während das Ausgeben von mehr als 20 separaten Updates für ein Wunschzettel-Shuffle langsam sein kann, gibt es möglicherweise eine schnelle Möglichkeit, gespeicherte Prozeduren zu verwenden.

rwong
quelle
3

OK, ich stehe vor diesem kniffligen Problem, und alle Antworten in diesem Q & A-Beitrag haben viele Inspirationen geliefert. Aus meiner Sicht hat jede Lösung ihre Vor- und Nachteile.

  • Wenn das positionFeld lückenlos fortlaufend sein muss, müssen Sie die gesamte Liste grundsätzlich neu anordnen. Dies ist eine O (N) -Operation. Der Vorteil ist, dass die Client-Seite keine spezielle Logik benötigt, um die Bestellung zu erhalten.

  • Wenn wir die O (N) -Operation vermeiden wollen, ABER IMMER NOCH eine genaue Reihenfolge einhalten möchten, besteht eine der Vorgehensweisen darin, "Selbstreferenz zur Bezugnahme auf den vorherigen (oder nächsten) Wert" zu verwenden. Dies ist ein Lehrbuchszenario für verknüpfte Listen. Es werden NICHT "eine ganze Reihe anderer Elemente in der Liste" angezeigt. Dies erfordert jedoch, dass der Client (ein Webdienst oder eine mobile App) die verknüpfte Listen-Travesal-Logik implementiert, um die Reihenfolge abzuleiten.

  • Einige Variationen verwenden keine Referenz, dh verknüpfte Liste. Sie legen fest, dass die gesamte Reihenfolge als eigenständiger Blob dargestellt wird, z. B. als JSON-Array in einer Zeichenfolge [5,2,1,3,...]. Eine solche Bestellung wird dann an einem getrennten Ort aufbewahrt. Dieser Ansatz hat auch den Nebeneffekt, dass der clientseitige Code diesen getrennten Auftrags-Blob beibehalten muss.

  • In vielen Fällen müssen wir die genaue Reihenfolge nicht wirklich speichern, sondern nur einen relativen Rang unter den einzelnen Datensätzen beibehalten. Daher können Lücken zwischen aufeinanderfolgenden Datensätzen zugelassen werden. Zu den Variationen gehören: (1) Verwenden einer Ganzzahl mit Lücken wie 100, 200, 300 ..., aber Sie werden schnell keine Lücken mehr haben und dann den Wiederherstellungsprozess benötigen; (2) Verwenden von Dezimalzahlen mit natürlichen Lücken, aber Sie müssen entscheiden, ob Sie mit der möglichen Genauigkeitsbeschränkung leben können. (3) Verwenden Sie einen auf Zeichenfolgen basierenden Rang, wie in dieser Antwort beschrieben, aber achten Sie auf die kniffligen Implementierungsfallen .

  • Die wirkliche Antwort kann "es kommt darauf an". Überprüfen Sie Ihre Geschäftsanforderungen. Wenn es sich zum Beispiel um ein Wunschzettelsystem handelt, würde ich persönlich gerne ein System verwenden, das in wenigen Rängen als "must-have", "good-to-have", "maybe-later" organisiert ist und dann Gegenstände ohne Einzelheiten präsentiert Reihenfolge in jedem Rang. Wenn es sich um ein Zustellsystem handelt, können Sie die Zustellzeit sehr gut als einen groben Rang verwenden, der mit einer natürlichen Lücke einhergeht (und die Vermeidung von natürlichen Konflikten, da keine Zustellung gleichzeitig erfolgen würde). Ihr Kilometerstand kann variieren.

RayLuo
quelle
2

Verwenden Sie eine Gleitkommazahl für die Positionsspalte.

Sie können dann die Liste neu anordnen, indem Sie nur die Positionsspalte in der "verschobenen" Zeile ändern.

Grundsätzlich, wenn Ihr Benutzer "rot" nach "blau" aber vor "gelb" positionieren möchte

Dann müssen Sie nur noch rechnen

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

Nach einigen Millionen Neupositionierungen erhalten Sie möglicherweise Gleitkommazahlen, die so klein sind, dass es kein "Dazwischen" gibt - dies ist jedoch ungefähr so ​​wahrscheinlich wie das Sichten eines Einhorns.

Sie können dies mit einem ganzzahligen Feld mit einer Anfangslücke von beispielsweise 1000 implementieren. Ihr Anfangsring wäre also 1000-> blau, 2000-> gelb, 3000-> rot. Nachdem Sie Rot nach Blau "bewegt" haben, erhalten Sie 1000-> Blau, 1500-> Rot, 2000-> Gelb.

Das Problem ist, dass Sie mit einer scheinbar großen anfänglichen Lücke von 1000 nur 10 Zügen in eine Situation wie 1000-> blau, 1001-puce, 1004-> biege geraten, in der Sie nicht mehr in der Lage sind um etwas nach "blau" einzufügen, ohne die ganze Liste neu zu nummerieren. Bei Verwendung von Gleitkommazahlen befindet sich immer ein "halber" Punkt zwischen den beiden Positionen.

James Anderson
quelle
4
Das Indizieren und Sortieren in einer auf Floats basierenden Datenbank ist teurer als ints. Ints sind auch ein netter Ordinaltyp ... müssen nicht als Bits gesendet werden, um auf dem Client sortiert zu werden (der Unterschied zwischen zwei Zahlen, die beim Drucken gleich sind, aber unterschiedliche Bitwerte aufweisen).
Bei jedem Schema, das ints verwendet, müssen Sie jedoch jedes Mal, wenn sich die Reihenfolge ändert, alle / die meisten Zeilen in der Liste aktualisieren. Mit floats aktualisieren Sie nur die Zeile, die sich bewegt hat. Auch "schwimmt teurer als ints" hängt sehr stark von der verwendeten Implementierung und Hardware ab. Die zusätzliche CPU ist im Vergleich zu der CPU, die zum Aktualisieren einer Zeile und der zugehörigen Indizes erforderlich ist, mit Sicherheit unbedeutend.
James Anderson
5
Für die Neinsager ist diese Lösung genau das, was Trello ( trello.com ) tut. Öffnen Sie Ihren Chrome-Debugger und vergleichen Sie die json-Ausgabe vor / nach einer Neuanordnung (Ziehen / Ablegen einer Karte) "pos": 1310719, + "pos": 638975.5. Um fair zu sein, machen die meisten Leute keine Trello-Listen mit 4 Millionen Einträgen, aber die Listengröße und der Anwendungsfall von Trello sind für benutzersortierbare Inhalte ziemlich verbreitet. Und alles, was vom Benutzer sortiert werden kann, hat in etwa nichts mit hoher Leistung zu tun. Die Sortiergeschwindigkeit zwischen int und float ist dafür nicht geeignet, insbesondere wenn die Datenbank hauptsächlich durch die E / A-Leistung eingeschränkt wird.
Zelk
1
@PieterB Was 'warum nicht eine 64-Bit-Ganzzahl verwenden' betrifft, so ist dies für den Entwickler meistens Ergonomie, würde ich sagen. Es gibt ungefähr so ​​viel Bittiefe <1,0 wie> 1,0 für einen durchschnittlichen Gleitkommawert. Sie können also die Spalte 'Position' auf 1,0 setzen und 0,5, 0,25, 0,75 genauso einfach einfügen wie das Verdoppeln. Bei ganzen Zahlen müsste die Standardeinstellung 2 ^ 30 sein, was es schwierig macht, beim Debuggen darüber nachzudenken. Ist 4073741824 größer als 496359787? Beginnen Sie mit dem Zählen der Ziffern.
Zelk
1
Außerdem ist es nicht so schwer, einen Fall zu lösen, bei dem der Platz zwischen den Zahlen knapp wird. Bewege einen von ihnen. Wichtig ist jedoch, dass dies nach besten Kräften funktioniert und viele gleichzeitige Bearbeitungen durch verschiedene Parteien (z. B. Trello) möglich sind. Sie können zwei Zahlen teilen, vielleicht sogar ein bisschen zufälliges Rauschen einstreuen, und voila, auch wenn jemand anderes zur gleichen Zeit dasselbe getan hat, gibt es immer noch eine globale Bestellung, und Sie mussten nicht innerhalb einer Transaktion EINFÜGEN, um diese zu erhalten Dort.
Zelk