Ich möchte eine große sortierte Liste (Millionen von Elementen) im Google App Engine-Datenspeicher aufbewahren. Schnelles Einstecken ist erforderlich.
Der einfachste Weg wäre das Hinzufügen einer indizierten Eigenschaft (oder Spalte) "order_num", die die Reihenfolge darstellt. Zum Beispiel würde eine Liste [A, B, C] wie folgt gespeichert:
%Vor%Dies führt jedoch nicht zu einem schnellen Einfügen. Zum Beispiel, wenn ich X nach A einfügen möchte, muss ich B und C neu nummerieren, um Platz für X zu schaffen, dh B wird 3, C wird 4 und X ist 2. Das wäre eine Katastrophe, wenn ich habe Millionen von Elementen.
Ich fand eine praktikable Lösung namens "gap approach" beschrieben hier . Dieser Ansatz hält eine Lücke zwischen benachbarten Elementen. So:
%Vor%Wenn ich X nach A einfügen will, kann ich einfach X hinzufügen, wobei seine Ordnungsnummer auf (1000 + 2000) / 2 = 1500 gesetzt wird, keine Neunummerierung erforderlich.
Wenn diese Lücken jedoch kleiner werden, kann eine Neunummerierung erforderlich sein. Meine Frage ist, gibt es eine bekannte Strategie zur Neunummerierung? Und über die Größe der Lücken entscheiden?
Danke!
AKTUALISIEREN
Hier ist mehr Detail. Angenommen, ich habe eine Liste von Elementen in der Datenbank und jedes Element hat eine ganzzahlige Eigenschaft namens my_num. Der Wert von my_num ist eine beliebige positive Ganzzahl. Angenommen, ich habe eine Liste [A, B, C, D] und ihre my_num sind
%Vor%Definieren wir nun einen accum () Operator:
%Vor%Also sind die Akkumulationswerte für jedes Element
%Vor%Aber akkumulierte Werte sollten wahrscheinlich NICHT in der Datenbank gespeichert werden, da die Liste ständig aktualisiert wird. Es ist besser, die Einfügung schnell zu halten.
Ich möchte eine Abfrage entwerfen, deren Eingabe eine Ganzzahl x ist:
%Vor%Abfrage (11) ist beispielsweise C und Abfrage (3) ist A.
Ist es möglich, ein Datenspeicherschema zu entwerfen, um diese Abfrage schnell zu machen? Oder der einzige Weg ist, es einzeln zur Abfragezeit zu akkumulieren, was ich vorhabe?
Alternativ könnten Sie Dezimalzahlen oder eine Zeichenfolge verwenden?
%Vor% Um D zwischen a und b einzufügen, geben Sie den Wert 'aa'
Ein Algorithmus zum Erzeugen der Strings wird am besten für eine binäre Zeichenkette gezeigt: Wenn Sie etwas zwischen "1011" und "1100" einfügen möchten, gehen Sie folgendermaßen vor:
Durchschnitt, neuer Wert = 1 + 0 * (1/2) + 1 * (1/4) + 1 * (1/8) + 1 * (1/16) neuer String="10111"
%Vor%Da Sie immer 2 Werte mitteln, wird der Durchschnitt immer eine endliche binäre Entwicklung und eine endliche Zeichenkette haben. Es definiert effektiv einen binären Baum.
Wie Sie wissen, werden binäre Bäume nicht immer gut ausbalanciert, mit anderen Worten, einige Strings werden nach ausreichendem Einfügen viel länger sein als andere. Um sie kurz zu halten, könnte man jede gerade Zahlenbasis verwenden - sie muss gerade sein, weil dann die Entwicklung eines Durchschnitts von zwei Werten endlich ist.
Aber was auch immer Sie tun, Strings werden wahrscheinlich lang, und Sie müssen zu einem gewissen Zeitpunkt etwas aufräumen, indem Sie die Werte aufräumen, damit der String-Platz effizient genutzt wird. Was dieser Algorithmus Ihnen gibt, ist die Gewissheit, dass zwischen den Aufräumarbeiten das System weiterläuft.
Sie möchten wahrscheinlich die App-Engine-Rangliste verwenden, die einen Baum verwendet Struktur, um eine Rangfolge im Datenspeicher aufrechtzuerhalten.
Oder, wenn Sie Ihre Anforderungen detaillierter beschreiben können, können wir Ihnen vielleicht eine Alternative vorschlagen, die weniger Overhead erfordert.
Du könntest eine riesige verlinkte Liste erstellen .... mit jeder Entität, die auf die nächste in der Liste zeigt .
Es wäre extrem langsam, die Liste später zu durchlaufen, aber das ist vielleicht abhängig davon, wie Sie die Daten verwenden, und das Einfügen in die Liste würde immer nur zwei Datenspeicherschreibvorgänge sein (einen zum Aktualisieren des Einfügepunkts und einen für deine neue Entität).
In der Datenbank kann Ihre verknüpfte Liste wie folgt aussehen:
%Vor%Wenn Sie neue Daten einfügen, ändern Sie den Vorgänger:
%Vor%Das Einfügen ist schnell, aber das Verlegen ist in der Tat langsam!
Tags und Links database list google-app-engine google-cloud-datastore order