Stellen Sie die Reihenfolge in einer relationalen Datenbank dar

StackOverflow https://stackoverflow.com/questions/21388

Frage

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 Zeile dargestellt.Ich möchte in der Lage sein, diese Bilder willkürlich anzuordnen und diese Reihenfolge in der Datenbank zu speichern, damit sie beim Anzeigen der Objekte in der richtigen Reihenfolge vorliegen.

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

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

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

Einleitung, Form, Funktion, Zugänglichkeit, Konsistenz, Fehler, Schlussfolgerung, Index

Wie kann ich diese Bestellung auf robuste und effiziente Weise in der Datenbank speichern?

Ich hatte die folgenden Ideen, bin aber von keiner davon begeistert:

  1. Array.Jede Zeile hat eine Bestell-ID. Wenn die Bestellung geändert wird (durch Entfernen und anschließendes Einfügen), werden die Bestell-IDs aktualisiert.Dies erleichtert das Abrufen, da es einfach ist ORDER BY, aber es scheint leicht 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.Das Durchqueren scheint hier kostspielig zu sein, obwohl es möglicherweise auf irgendeine Weise nützlich ist ORDER BY Daran denke ich nicht.

  3. Beabstandetes Array.Stellen Sie die Bestell-ID (wie in Nr. 1 verwendet) auf einen großen Wert ein, sodass das erste Objekt 100, das zweite 200 usw. ist.Wenn dann eine Einfügung erfolgt, platzieren Sie sie einfach an (objectBefore + objectAfter)/2.Natürlich müsste dies gelegentlich neu ausbalanciert werden, damit die Dinge nicht zu nah beieinander liegen (selbst bei Gleitkommazahlen würde es irgendwann zu Rundungsfehlern kommen).

Nichts davon erscheint mir besonders elegant.Hat jemand eine bessere Möglichkeit, das zu machen?

War es hilfreich?

Lösung 9

Da ich das meiste mit Django erlebt habe, habe ich es herausgefunden diese Lösung um am praktikabelsten zu sein.Es scheint, dass es in einer relationalen Datenbank keinen „richtigen Weg“ gibt, dies zu tun.

Andere Tipps

Eine andere Alternative wäre (sofern Ihr RDBMS dies unterstützt) die Verwendung von Spalten vom Typ Array.Obwohl dies gegen die Normalisierungsregeln verstößt, kann es in solchen Situationen nützlich sein.Eine mir bekannte Datenbank mit Arrays ist PostgreSQL.

Das Mixin „acts_as_list“ in Rails handhabt dies im Grunde so, wie Sie es in Nr. 1 beschrieben haben.Es sucht nach einer INTEGER-Spalte mit dem Namen position (die Sie natürlich mit dem Namen überschreiben können) und verwendet diese, um ein ORDER BY auszuführen.Wenn Sie Dinge neu anordnen möchten, aktualisieren Sie die Positionen.Es hat mir jedes Mal gute Dienste geleistet, wenn ich es verwendet habe.

Als Randbemerkung: Sie können die Notwendigkeit beseitigen, bei INSERTS/DELETES immer eine Neupositionierung vorzunehmen, indem Sie eine spärliche Nummerierung verwenden – ähnlich wie damals einfach …Sie können Ihre Positionen mit 10, 20, 30 usw. nummerieren.und wenn Sie etwas zwischen 10 und 20 einfügen müssen, fügen Sie es einfach an der Position 15 ein.Ebenso können Sie beim Löschen einfach die Zeile löschen und die Lücke lassen.Sie müssen die Nummerierung nur dann neu vornehmen, wenn Sie tatsächlich die Reihenfolge ändern oder wenn Sie versuchen, eine Einfügung vorzunehmen und es keine passende Lücke zum Einfügen gibt.

Natürlich abhängig von Ihrer individuellen Situation (z.B.Unabhängig davon, ob die anderen Zeilen bereits in den Speicher geladen sind oder nicht), kann es sinnvoll sein, den Gap-Ansatz zu verwenden oder auch nicht.

Nur eine Überlegung Option Nr. 1 vs. Nr. 3:Verschiebt die Option für beabstandete Arrays (#3) nicht nur das Problem des normalen Arrays (#1)?Welchen Algorithmus Sie auch wählen, entweder ist er kaputt und Sie werden später mit Nr. 3 auf Probleme stoßen, oder er funktioniert, und dann sollte Nr. 1 genauso gut funktionieren.

Wenn die Objekte nicht stark durch andere Tabellen verschlüsselt sind und die Listen kurz sind, ist es am einfachsten, alles in der Domäne zu löschen und einfach die richtige Liste erneut einzufügen.Dies ist jedoch nicht praktikabel, wenn die Listen groß sind und Sie viele Einschränkungen haben, die den Löschvorgang verlangsamen.Ich denke, Ihre 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 mitten in der Aktualisierung befinden und die Bestellung vermasseln könnten.

Ich habe dies in meinem letzten Projekt gemacht, aber es war für einen Tisch, der nur gelegentlich speziell bestellt werden musste und auf den nicht allzu oft zugegriffen wurde.Ich denke, das beabstandete Array wäre die beste Option, da die Neuordnung im Durchschnitt am günstigsten wäre, da nur ein Wert geändert und zwei abgefragt werden müssten.

Außerdem würde ich mir vorstellen, dass ORDER BY von Datenbankanbietern ziemlich stark optimiert würde, sodass die Nutzung dieser Funktion im Vergleich zur Implementierung verknüpfter Listen von Vorteil für die Leistung wäre.

Verwenden Sie eine Gleitkommazahl, um die Position jedes Elements darzustellen:

Punkt 1 -> 0,0

Punkt 2 -> 1.0

Punkt 3 -> 2.0

Punkt 4 -> 3.0

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

Punkt 1 -> 0,0

Punkt 4 -> 0,5

Punkt 2 -> 1.0

Punkt 3 -> 2.0

(Punkt 4 zwischen Punkt 1 und 2 verschoben).

Der Halbierungsvorgang kann aufgrund der Art und Weise, wie Gleitkommazahlen in einem Computersystem codiert werden, nahezu unbegrenzt fortgesetzt werden.

Punkt 4 -> 0,5

Punkt 1 -> 0,75

Punkt 2 -> 1.0

Punkt 3 -> 2.0

(Verschieben Sie Element 1 an die Position direkt nach Element 4)

Ich würde eine fortlaufende Nummer erstellen, mit einem Auslöser auf der Tabelle, der „Platz schafft“ für eine Priorität, falls diese bereits vorhanden ist.

Ich hatte dieses Problem auch.Ich stand unter großem Zeitdruck (das gilt nicht für uns alle) und habe mich für Option 1 entschieden und nur die Zeilen aktualisiert, die sich geändert haben.

Wenn Sie Artikel 1 mit Artikel 10 austauschen, führen Sie einfach zwei Aktualisierungen durch, um die Bestellnummern von Artikel 1 und Artikel 10 zu aktualisieren.Ich weiß, dass es algorithmisch einfach ist und der schlimmste Fall O(n) ist, aber der schlimmste Fall ist, wenn man eine vollständige Permutation der Liste hat.Wie oft wird das passieren?Die Antwort liegt bei Ihnen.

Ich hatte das gleiche Problem und habe mich wahrscheinlich mindestens eine Woche lang mit der richtigen Datenmodellierung beschäftigt, aber ich glaube, ich habe es endlich geschafft.Mithilfe des Array-Datentyps in PostgreSQL können Sie den Primärschlüssel jedes bestellten Artikels speichern und dieses Array durch Einfügungen oder Löschungen entsprechend aktualisieren, wenn sich Ihre Bestellung ändert.Wenn Sie auf eine einzelne Zeile verweisen, können Sie alle Ihre Objekte basierend auf der Reihenfolge in der Array-Spalte zuordnen.

Die Lösung ist immer noch etwas holprig, funktioniert aber wahrscheinlich besser als Option 1, da Option 1 beim Bestellen von Änderungen die Aktualisierung der Bestellnummer aller anderen Zeilen erfordert.

Schema Nr. 1 und Schema Nr. 3 haben in jeder Operation die gleiche Komplexität, außer INSERT schreibt.Schema Nr. 1 enthält O(n) Schreibvorgänge INSERT und Schema Nr. 3 enthält O(1)-Schreibvorgänge INSERT.

Bei jeder anderen Datenbankoperation ist die Komplexität gleich.

Schema Nr. 2 sollte nicht einmal in Betracht gezogen werden, weil es so ist DELETE erfordert O(n) Lese- und Schreibvorgänge.Schema Nr. 1 und Schema Nr. 3 haben O(1) DELETE sowohl zum Lesen als auch zum Schreiben.

Neue Methode

Wenn Ihre Elemente ein eindeutiges übergeordnetes Element haben (d. h.sie teilen sich eine Fremdschlüsselzeile), dann können Sie Folgendes versuchen ...

Django bietet eine datenbankunabhängige Lösung zum Speichern von Listen mit Ganzzahlen darin CharField().Ein Nachteil besteht darin, dass die maximale Länge der gespeicherten Zeichenfolge nicht größer sein kann max_length, was DB-abhängig ist.

In Bezug auf die Komplexität würde dies Schema Nr. 1 ergeben, für das O(1) schreibt INSERT, da die Bestellinformationen als einzelnes Feld in der Zeile des übergeordneten Elements gespeichert würden.

Ein weiterer Nachteil besteht darin, dass a JOIN Zur Aktualisierung der Reihenfolge ist nun ein Eintrag in die übergeordnete Zeile erforderlich.

https://docs.djangoproject.com/en/dev/ref/validators/#django.core.validators.validate_comma_separated_integer_list

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top