Reihenfolge in einer relationalen Datenbank darstellen

Question

Ich habe eine Sammlung von Objekten in einer Datenbank. Bilder in einer Fotogalerie, Produkte in einem Katalog, Kapitel in einem Buch usw. Jedes Objekt wird als eine Reihe dargestellt. Ich möchte in der Lage sein, diese Bilder beliebig zu ordnen und diese Reihenfolge in der Datenbank zu speichern. Wenn ich die Objekte zeige, sind sie in der richtigen Reihenfolge.

Nehmen wir zum Beispiel an, ich schreibe ein Buch, und jedes Kapitel ist ein Objekt. Ich schreibe mein Buch und legte die Kapitel in der folgenden Reihenfolge:

Einführung, Zugänglichkeit, Form vs. Funktion, Fehler, Konsistenz, Schlussfolgerung, Index

Es geht an den Editor, und kommt zurück mit der folgenden empfohlenen Reihenfolge:

Einführung, Form, Funktion, Zugänglichkeit, Konsistenz, Fehler, Schlussfolgerung, Index

Wie kann ich diese Bestellung robust und effizient in der Datenbank speichern?

Ich habe folgende Ideen hat, aber ich bin nicht begeistert, mit einem von ihnen:

1. Array. Jede Zeile hat eine Bestell-ID. Wenn die Bestellung geändert wird (über eine Entnahme gefolgt von einer Einfügung), werden die Bestell-IDs aktualisiert. Dies macht die Suche einfach, da es nur ORDER BY ist, aber es scheint einfach zu brechen.

   // REMOVAL
UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
// INSERTION
UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
UPDATE ... SET orderID=insertionID WHERE ID=addedID

2. verlinkte Liste. Jede Zeile hat eine Spalte für die ID der nächsten Zeile in der Reihenfolge. Traversal scheint hier kostspielig zu sein, obwohl es irgendwie möglich sein kann, ORDER BY zu verwenden, an die ich nicht denke.

3. Platzierte Anordnung. Legen Sie die orderID (wie in # 1 verwendet) als groß fest, also ist das erste Objekt 100, das zweite ist 200 usw. Wenn eine Insertion stattfindet, platzieren Sie sie einfach unter (objectBefore + objectAfter)/2. Natürlich müsste dies gelegentlich neu ausbalanciert werden, so dass Sie nicht zu nahe beieinander sind (selbst mit Floats würden Sie eventuell zu Rundungsfehlern kommen).

Keines von diesen scheint mir besonders elegant. Hat jemand einen besseren Weg, es zu tun?

Answer 1

Da ich mit Django meistens auf dieses Problem gestoßen bin, habe ich festgestellt, dass this solution am brauchbarsten ist. Es scheint, dass es keinen "richtigen Weg" gibt, dies in einer relationalen Datenbank zu tun.

Answer 2

Die Acts_as_list MixIn in Rails behandelt dies im Grunde die Art, wie Sie in # 1 umrissen. Es sucht nach einer INTEGER-Spalte namens position (von der Sie natürlich den Namen überschreiben können) und verwendet diese, um ORDER BY auszuführen. Wenn Sie Dinge neu ordnen möchten, aktualisieren Sie die Positionen. Es hat mir jedes Mal gut gedient, wenn ich es benutzt habe.

Als eine Randnotiz können Sie die Notwendigkeit entfernen immer auf INSERTS/DELETES neu zu positionieren, indem Sie spärliche Nummerierung - Art der grundlegenden zurück in den Tag ... Sie können Ihre Positionen 10, 20, 30 usw.und wenn Sie etwas zwischen 10 und 20 einfügen müssen, fügen Sie es einfach mit einer Position von 15 ein. Ebenso können Sie beim Löschen einfach die Zeile löschen und die Lücke verlassen. Sie müssen nur dann neu nummerieren, wenn Sie die Bestellung tatsächlich ändern oder wenn Sie versuchen, eine Beilage zu erstellen, und es gibt keine geeignete Lücke zum Einfügen.

Abhängig von Ihrer speziellen Situation (z. B. ob Sie die anderen Zeilen bereits in den Speicher geladen haben oder nicht) ist es sinnvoll oder nicht sinnvoll, den Lücken-Ansatz zu verwenden.

Answer 3

Ich würde eine fortlaufende Nummer machen, mit einem Trigger auf der Tabelle, die Platz für eine Priorität schafft, wenn sie bereits existiert.

Answer 4

Wenn die Objekte nicht stark von anderen Tabellen getastet werden und die Listen kurz sind, ist es am einfachsten, alles in der Domäne zu löschen und nur die korrekte Liste neu einzufügen. Aber das ist nicht praktisch, wenn die Listen groß sind und Sie viele Einschränkungen haben, um das Löschen zu verlangsamen. Ich denke deine erste Methode ist wirklich die sauberste. Wenn Sie es in einer Transaktion ausführen, können Sie sicher sein, dass nichts Ungewöhnliches passiert, während Sie sich in der Mitte des Updates befinden, um die Bestellung zu vermasseln.

Answer 5

Ich tat dies in meinem letzten Projekt, aber es war für eine Tabelle, die nur gelegentlich speziell bestellt werden musste, und wurde nicht zu oft zugegriffen. Ich denke, dass die Anordnung mit Abstand die beste Option wäre, da eine Umordnung im Durchschnitt am billigsten wäre, da nur eine Änderung an einem Wert und eine Abfrage an zwei vorgenommen wird.

Auch würde ich mir vorstellen, ORDER BY wäre ziemlich stark von Datenbank-Anbietern optimiert, so dass die Nutzung dieser Funktion wäre vorteilhaft für die Leistung im Gegensatz zu der Linked-List-Implementierung.

Answer 6

Eine andere Alternative wäre (wenn Ihr RDBMS dies unterstützt), Spalten des Typs array zu verwenden. Während dies die Normalisierungsregeln bricht, kann es in Situationen wie dieser nützlich sein. Eine Datenbank, von der ich weiß, dass sie Arrays hat, ist PostgreSQL.

Answer 7

Nur ein Gedanke in Anbetracht Option # 1 vs # 3: verschiebt nicht die Option "Abstand voneinander" (# 3) nur das Problem des normalen Arrays (# 1)? Egal welcher Algorithmus Sie wählen, entweder ist er kaputt, und Sie werden später mit # 3 Probleme bekommen, oder es funktioniert, und dann sollte # 1 genauso gut funktionieren.

Answer 8

eine Gleitkommazahl Verwenden der Position der einzelnen Elemente zu repräsentieren:

Item 1 -> 0.0

Artikel 2 -> 1.0

Punkt 3 -> 2.0

Punkt 4 -> 3.0

Sie können jedes Element zwischen zwei anderen Elementen durch einfache Halbierung platzieren:

Item 1 -> 0.0

Punkt 4 -> 0.5

Artikel 2 -> 1.0

Punkt 3 -> 2.0

(Verschoben Punkt 4 zwischen den Elementen 1 und 2).

Der Bisektionsprozess kann fast unbegrenzt fortgesetzt werden, da die Fließkommazahlen in einem Computersystem codiert sind.

Artikel 4 -> 0.5

Artikel 1 -> 0,75

Artikel 2 -> 1.0

Artikel 3 -> 2,0

(Verschieben Punkt 1 in die Position unmittelbar nach Artikel 4)

Answer 9

Ich hatte dieses Problem auch. Ich stand unter starkem Zeitdruck (sind wir nicht alle) und ich ging mit Option # 1, und nur die Zeilen, die sich geändert haben.

Wenn Sie Artikel 1 mit Artikel 10 tauschen, tun Sie einfach zwei Updates, um die Bestellnummern von Artikel 1 und Artikel 10 zu aktualisieren. Ich weiß, es ist algorithmisch einfach, und es ist O (n) schlimmsten Fall, aber dieser schlimmste Fall ist, wenn Sie eine vollständige Permutation der Liste haben. Wie oft wird das passieren? Das musst du beantworten.

Answer 10

Ich hatte das gleiche Problem und habe wahrscheinlich mindestens eine Woche mit mir über die richtige Datenmodellierung verbracht, aber ich denke, ich habe es endlich. Unter Verwendung des Array-Datentyps in PostgreSQL können Sie den Primärschlüssel jedes bestellten Artikels speichern und das Array entsprechend aktualisieren, indem Sie Änderungen oder Löschungen vornehmen, wenn sich Ihre Bestellung ändert. Wenn Sie auf eine einzelne Zeile verweisen, können Sie alle Ihre Objekte basierend auf der Reihenfolge in der Arrayspalte zuordnen.

Es ist immer noch ein bisschen abgehackt von einer Lösung, aber es wird wahrscheinlich besser als Option 1 funktionieren, da Option 1 erfordert, die Bestellnummer aller anderen Zeilen bei Bestelländerungen zu aktualisieren.