Speichern einer nachbestellbaren Liste in einer Datenbank

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!

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.

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.

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.

"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

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)

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.

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.

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.