So speichern Sie bestellte Informationen in einer relationalen Datenbank

20

Ich versuche zu verstehen, wie man bestellte Informationen in einer relationalen Datenbank richtig speichert.

Ein Beispiel:

Angenommen, ich habe eine Wiedergabeliste, die aus Songs besteht. In meiner relationalen Datenbank habe ich eine Tabelle Playlistsmit einigen Metadaten (Name, Ersteller usw.). Ich habe auch eine Tabelle mit der Bezeichnung " Songsthe" playlist_idsowie songspezifische Informationen (Name, Künstler, Dauer usw.).

Wenn ein neuer Song zu einer Wiedergabeliste hinzugefügt wird, wird er standardmäßig an das Ende angehängt. Bei Bestellung auf Song-ID (aufsteigend) gilt die Reihenfolge der Hinzufügung. Was aber, wenn ein Benutzer in der Lage sein sollte, Songs in der Wiedergabeliste neu zu ordnen?

Ich hatte ein paar Ideen, jede mit ihren Vor- und Nachteilen:

  1. Eine aufgerufene Spalte order, die eine Ganzzahl ist . Wenn ein Song verschoben wird, wird die Reihenfolge aller Songs zwischen der alten und der neuen Position geändert, um die Änderung widerzuspiegeln. Dies hat den Nachteil, dass jedes Mal, wenn ein Song verschoben wird, viele Abfragen durchgeführt werden müssen und der Algorithmus für das Verschieben nicht so einfach ist wie bei den anderen Optionen.
  2. Eine Spalte genannt order, die eine ist dezimal ( NUMERIC). Wenn ein Song verschoben wird, wird ihm der Gleitkommawert zwischen den beiden benachbarten Zahlen zugewiesen. Nachteil: Dezimalfelder nehmen mehr Platz in Anspruch und es kann vorkommen, dass die Genauigkeit abnimmt, es sei denn, es wird darauf geachtet, dass der Bereich nach einigen Änderungen neu verteilt wird.
  3. Eine andere Möglichkeit wäre, ein previousund ein nextFeld zu haben, das auf andere Songs verweist. (oder sind NULL im Fall des ersten bzw. letzten Songs in der Wiedergabeliste; im Grunde erstellen Sie eine verknüpfte Liste ). Nachteil: Abfragen wie 'finde den X. Song in der Liste' sind nicht mehr zeitlich konstant, sondern zeitlich linear.

Welches dieser Verfahren wird in der Praxis am häufigsten angewendet? Welches dieser Verfahren ist bei mittleren bis großen Datenbanken am schnellsten? Gibt es noch andere Möglichkeiten, dies zu erreichen?

EDIT: Der Einfachheit halber gehört in diesem Beispiel ein Song nur zu einer Playlist (eine Beziehung von vielen zu eins). Natürlich könnte man auch eine Junction-Tabelle verwenden, sodass die Song-Playlist eine Beziehung von vielen zu vielen ist (und eine der oben genannten Strategien auf diese Tabelle anwenden).

Qqwy
quelle
1
Sie können Option eins (Bestellung als Ganzzahl) mit 100 Schritten verwenden. Dann brauchen Sie keine Neuordnung, wenn Sie einen Titel verschieben, sondern nehmen einen Wert zwischen 100. Von Zeit zu Zeit müssen Sie möglicherweise neu nummerieren, um wieder Lücken zwischen den Titeln zu erhalten.
Knut
4
"Der Nachteil dabei ist, dass jedes Mal, wenn ein Song verschoben wird, viele Abfragen durchgeführt werden müssen"?! - update songorder set order = order - 1 where order >= 12 & order <= 42; update songorder set order = 42 where id = 123;- das sind zwei Updates - nicht dreißig. Drei, wenn Sie eine eindeutige Einschränkung für die Bestellung festlegen möchten.
2
Verwenden Sie Option eins, es sei denn, Sie wissen, dass Sie etwas anderes benötigen. Ein Problem, auf das Programmierer, die noch keine Erfahrung mit Datenbanken haben, stoßen, besteht darin, nicht zu verstehen, dass Datenbanken in solchen Dingen sehr, sehr gut sind. Haben Sie keine Angst, Ihre Datenbank zum Laufen zu bringen.
GroßmeisterB
1
Queries like 'find the Xth Song in the list' are no longer constant-timeDies gilt auch für Option 2.
Doc Brown
2
@MikeNakis: Es scheint teuer, aber die ganze Arbeit wird auf dem Server erledigt, der (normalerweise) für diese Art von Arbeit optimiert ist. Ich würde diese Technik nicht für eine Tabelle mit Millionen von Zeilen verwenden, aber ich würde sie nicht für eine Tabelle mit nur ein paar tausend Zeilen rabattieren.
TMN

Antworten:

29

Datenbanken sind für bestimmte Dinge optimiert. Das schnelle Aktualisieren vieler Zeilen ist eine davon. Dies gilt insbesondere dann, wenn Sie die Datenbank arbeiten lassen.

Erwägen:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

Und wenn Sie zum Beat ItEnde gehen möchten, hätten Sie zwei Fragen:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

Und das ist es. Dies lässt sich sehr gut mit sehr großen Zahlen skalieren. Versuchen Sie, ein paar tausend Titel in eine hypothetische Wiedergabeliste in Ihrer Datenbank aufzunehmen, und sehen Sie, wie lange es dauert, einen Titel von einem Ort an einen anderen zu verschieben. Da diese sehr standardisierte Formen haben:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

Sie haben zwei vorbereitete Anweisungen, die Sie sehr effizient wiederverwenden können.

Dies bietet einige bedeutende Vorteile - die Reihenfolge der Tabelle ist etwas, über das Sie nachdenken können. Das dritte Lied hat immer eine order3. Die einzige Möglichkeit, dies zu gewährleisten, besteht darin, aufeinanderfolgende ganze Zahlen als Reihenfolge zu verwenden. Durch die Verwendung von Pseudolisten, Dezimalzahlen oder Ganzzahlen mit Lücken können Sie diese Eigenschaft nicht garantieren. In diesen Fällen besteht die einzige Möglichkeit, den n-ten Titel zu erhalten, darin, die gesamte Tabelle zu sortieren und den n-ten Datensatz abzurufen.

Und das ist viel einfacher, als Sie denken. Es ist einfach herauszufinden, was Sie tun möchten, um die beiden Aktualisierungsanweisungen zu generieren, und damit andere Personen sich diese beiden Aktualisierungsanweisungen ansehen und erkennen können, was gerade getan wird.

vedant
quelle
2
Ich fange an, diesen Ansatz zu mögen.
Mike Nakis
2
@ MikeNakis es funktioniert gut. Es gibt auch einen Binärbaum, der auf einer ähnlichen Idee basiert - den modifizierten Vorbestellbaum . Es dauert ein bisschen länger, bis Sie sich zurechtfinden, aber Sie können damit einige sehr schöne Abfragen für hierarchische Daten durchführen. Ich hatte noch nie Leistungsprobleme damit, auch bei großen Bäumen. Über den Code nachdenken zu können, ist etwas, worauf ich großen Wert lege, bis sich herausstellt, dass dem einfachen Code die erforderliche Leistung fehlt (und das nur in extremen Situationen).
Wird es Probleme mit der Verwendung geben, orderda dies order byein Schlüsselwort ist?
Kojow7
@ kojow7 Wenn Ihre Felder Namen haben, die mit Schlüsselwörtern in Konflikt stehen, sollten Sie sie in Häkchen "` "setzen.
Andri
Dieser Ansatz ist sinnvoll, aber was ist der beste Weg, um den orderWert beim Hinzufügen eines neuen Songs zu einer Wiedergabeliste zu erhalten. Angenommen, es ist der 9. Song. Gibt es eine bessere Möglichkeit, 9 in den Song einzufügen, orderals eine COUNTvor dem Hinzufügen der Platte?
Delashum
3

Zunächst ist aus Ihrer Beschreibung nicht ersichtlich, was Sie getan haben, aber Sie benötigen eine PlaylistSongsTabelle, die a PlaylistIdund a enthält und SongIdbeschreibt, welche Songs zu welchen Wiedergabelisten gehören.

In dieser Tabelle müssen Sie Bestellinformationen hinzufügen.

Mein Lieblingsmechanismus ist mit reellen Zahlen. Ich habe es kürzlich implementiert und es hat wie ein Zauber funktioniert. Wenn Sie ein Lied an eine bestimmte Position verschieben möchten, berechnen Sie den neuen OrderingWert als Durchschnitt der OrderingWerte des vorherigen und des nächsten Lieds. Wenn Sie eine reelle 64-Bit-Zahl verwenden, wird Ihnen die Genauigkeit ungefähr zur gleichen Zeit ausgehen, zu der die Hölle zufriert. Wenn Sie jedoch Ihre Software für die Nachwelt schreiben, sollten Sie erwägen Ordering, allen Titeln in jedem Titel schöne gerundete Ganzzahlenwerte zuzuweisen Wiedergabeliste hin und wieder.

Als zusätzlichen Bonus ist hier der Code, den ich geschrieben habe, der dies implementiert. Natürlich können Sie es nicht so verwenden, wie es ist, und es wäre im Moment zu viel Arbeit für mich, es für Sie zu bereinigen. Deshalb poste ich es nur, damit Sie Ideen daraus erhalten.

Die Klasse ist ParameterTemplate(was auch immer, fragen Sie nicht!). Die Methode ruft die Liste der Parametervorlagen ab, zu denen diese Vorlage von ihrem übergeordneten Element gehört ActivityTemplate. (Was auch immer, fragen Sie nicht!) Der Code enthält einige Schutzmaßnahmen gegen mangelnde Präzision. Der Divisor wird zum Testen verwendet: Beim Komponententest wird ein großer Divisor verwendet, um die Genauigkeit schnell zu verringern und somit den Präzisionsschutzcode auszulösen. Die zweite Methode ist öffentlich und "nur für den internen Gebrauch; nicht aufrufen", damit der Testcode sie aufrufen kann. (Es kann nicht paket-privat sein, da mein Testcode nicht im selben Paket enthalten ist wie der Code, den er testet.) Das Feld, das die Bestellung steuert, wird aufgerufen Orderingund über getOrdering()und aufgerufen setOrdering(). Sie sehen kein SQL, da ich die objektrelationale Zuordnung über den Ruhezustand verwende.

/**
 * Moves this {@link ParameterTemplate} to the given index in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * The index must be greater than or equal to zero, and less than or equal to the number of entries in the list.  Specifying an index of zero will move this item to the top of
 * the list. Specifying an index which is equal to the number of entries will move this item to the end of the list.  Any other index will move this item to the position
 * specified, also moving other items in the list as necessary. The given index cannot be equal to the current index of the item, nor can it be equal to the current index plus
 * one.  If the given index is below the current index of the item, then the item will be moved so that its new index will be equal to the given index.  If the given index is
 * above the current index, then the new index of the item will be the given index minus one.
 *
 * NOTE: this method flushes the persistor and refreshes the parent node so as to guarantee that the changes will be immediately visible in the list of {@link
 * ParameterTemplate}s of the parent {@link ActivityTemplate}.
 *
 * @param toIndex the desired new index of this {@link ParameterTemplate} in the list of {@link ParameterTemplate}s of the parent {@link ActivityTemplate}.
 */
public void moveAt( int toIndex )
{
    moveAt( toIndex, 2.0 );
}

/**
 * For internal use only; do not invoke.
 */
public boolean moveAt( int toIndex, double divisor )
{
    MutableList<ParameterTemplate<?>> parameterTemplates = getLogicDomain().getMutableCollections().newArrayList();
    parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
    assert parameterTemplates.getLength() >= 1; //guaranteed since at the very least, this parameter template must be in the list.
    int fromIndex = parameterTemplates.indexOf( this );
    assert 0 <= toIndex;
    assert toIndex <= parameterTemplates.getLength();
    assert 0 <= fromIndex;
    assert fromIndex < parameterTemplates.getLength();
    assert fromIndex != toIndex;
    assert fromIndex != toIndex - 1;

    double order;
    if( toIndex == 0 )
    {
        order = parameterTemplates.fetchFirstElement().getOrdering() - 1.0;
    }
    else if( toIndex == parameterTemplates.getLength() )
    {
        order = parameterTemplates.fetchLastElement().getOrdering() + 1.0;
    }
    else
    {
        double prevOrder = parameterTemplates.get( toIndex - 1 ).getOrdering();
        parameterTemplates.moveAt( fromIndex, toIndex );
        double nextOrder = parameterTemplates.get( toIndex + (toIndex > fromIndex ? 0 : 1) ).getOrdering();
        assert prevOrder <= nextOrder;
        order = (prevOrder + nextOrder) / divisor;
        if( order <= prevOrder || order >= nextOrder ) //if the accuracy of the double has been exceeded
        {
            parameterTemplates.clear();
            parameterTemplates.addAll( getParentActivityTemplate().getParameterTemplates() );
            for( int i = 0; i < parameterTemplates.getLength(); i++ )
                parameterTemplates.get( i ).setOrdering( i * 1.0 );
            rocs3dDomain.getPersistor().flush();
            rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
            moveAt( toIndex );
            return true;
        }
    }
    setOrdering( order );
    rocs3dDomain.getPersistor().flush();
    rocs3dDomain.getPersistor().refresh( getParentActivityTemplate() );
    assert getParentActivityTemplate().getParameterTemplates().indexOf( this ) == (toIndex > fromIndex ? toIndex - 1 : toIndex);
    return false;
}
Mike Nakis
quelle
Ich würde eine ganzzahlige Reihenfolge verwenden, und wenn ich der Meinung wäre, dass die Nachbestellung zu teuer ist, würde ich einfach die Anzahl der Nachbestellungen verringern, indem jeder Sprung um X erfolgt, wobei X der Betrag ist, um den ich die Nachbestellung reduzieren muss, z sollte als Vorspeise in Ordnung sein.
Warren P
1
@WarrenP Ja, ich weiß, es kann auch so gemacht werden, deshalb habe ich diesen Ansatz einfach "mein Favorit" anstatt "der beste" oder "der eine" genannt.
Mike Nakis
0

Was für mich bei einer kleinen Liste in der Größenordnung von 100 Artikeln funktionierte, war ein hybrider Ansatz:

  1. Spalte Decimal SortOrder, jedoch mit einer Genauigkeit, mit der 0,5 Differenzen gespeichert werden können (z. B. Decimal (8,2) oder etwas anderes).
  2. Ergreifen Sie beim Sortieren die PKs der Zeile über und unter der aktuellen Zeile, in die sie verschoben wurden, sofern vorhanden. (Oben wird keine Zeile angezeigt, wenn Sie den Artikel beispielsweise an die erste Position verschieben.)
  3. Stellen Sie die PKs der aktuellen, vorherigen und nächsten Zeile auf dem Server bereit, um die Sortierung durchzuführen.
  4. Wenn Sie eine vorherige Zeile haben, setzen Sie die Position der aktuellen Zeile auf vorherige + 0,5. Wenn Sie nur eine nächste haben, setzen Sie die Position der aktuellen Zeile auf next - 0.5.
  5. Als nächstes habe ich einen gespeicherten Proc, der alle Positionen mit der SQL Server-Funktion Row_Number aktualisiert und nach der neuen Sortierreihenfolge sortiert. Dadurch wird die Reihenfolge von 1,1,5,2,3,4,6 in 1,2,3,4,5,6 geändert, da die Funktion row_number ganzzahlige Ordnungszahlen liefert.

Sie erhalten also eine Ganzzahlreihenfolge ohne Lücken, die in einer Dezimalspalte gespeichert ist. Es ist ziemlich sauber, ich fühle. Wenn Sie Hunderttausende von Zeilen auf einmal aktualisieren müssen, ist die Skalierung möglicherweise nicht besonders gut. Aber wenn ja, warum verwenden Sie überhaupt eine benutzerdefinierte Sortierung? (Hinweis: Wenn Sie eine große Tabelle mit Millionen von Benutzern haben, aber jeder Benutzer nur ein paar hundert Elemente zum Sortieren hat, können Sie den oben beschriebenen Ansatz verwenden, da Sie ohnehin eine where-Klausel verwenden, um die Änderungen auf nur einen Benutzer zu beschränken )

John
quelle