FiFo Datenstrukurt mit MySql
lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess
code
datenbank
datensatz
eintrag
feuer
limit
objekt
position
prinzip
queue
reihenfolge
spiel
standard
struktur
system
tabelle
tip
url
zeile
ziel
-
Hallo,
und wieder eine Frage, Diesesmal zu MySql. Undzwar benötige ich eine FiFo Datenstruktur, also Queue. Damit meine ich keinen Ringspeicher, wie ich ihn bei meiner Recherche zu Hauf gefunden habe. Meine Einzige Idee ist es die Datensätze(Bloß die ID und ein boolscher Wert) untereinander anzulegen und bei einer Abfrage immer den Datensatz mit der ID1 zu entnehmen. Dafür müssen die Datensätze aber nach jeder Entnahme um eine ID Position nach oben verschoben werden um die Struktur wieder herzustellen.
Hat jemand von euch Erfahrung mit ähnlichen Datenstrukturen gesammelt und kann mir einen Hinweis zur Laufzeit geben? Jede Tabelle wird maximal 10 Werte enthalten. Jedoch fürchte ich mich davor, dass das umsortieren die Laufzeit erheblich beeinflusst. Ich muss im Prinzip nach 0.5 Sekunden wieder auf die Tabelle zugreifen können ohne in der Warteschlange zu landen.
Oder gibt es bereits vorgefertigte Skripte und/oder Datenstrukturen nur bin ich zu blöde sie zu finden? Oder gibts es gar eine für meine Ansprüche besser umgesetzte Datenbank?
Grüße
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
wieso die ganzen ID's updaten und so unnötigew Last erzeugen? Ein Query das Order by ID enthält tut es doch auch. Um nur einen DS zu bekommen fügts du am besten auch noch Limit=1 an, danach löschst du diesen Datensatz.
Beitrag zuletzt geändert: 29.2.2012 8:00:59 von motoernie -
Das ist natürlich ne elegante Alternative. Mich stört nur der Gedanke, dass ich dann ja immer nach unten durch die Tabelle wander. Ich kenn MySql nicht so super, daher die jetzt vllt. etwas dumme Frage: Wenn ich den ersten Eintrag lösche, wird die Tabellenzeile komplett entfernt, also bei einer Tabelle mit ehemals 3 Zeilen bleiben nurnoch 2 übrig, oder wird sie einfach leer an ihrer Position belassen? Ich mag halt keinen Datenmüll haben :P.
Vielen Dank aber für den Tip, so leicht hab ich nicht gedacht.:P -
smartrail schrieb:
Das ist natürlich ne elegante Alternative. Mich stört nur der Gedanke, dass ich dann ja immer nach unten durch die Tabelle wander. Ich kenn MySql nicht so super, daher die jetzt vllt. etwas dumme Frage: Wenn ich den ersten Eintrag lösche, wird die Tabellenzeile komplett entfernt, also bei einer Tabelle mit ehemals 3 Zeilen bleiben nurnoch 2 übrig, oder wird sie einfach leer an ihrer Position belassen? Ich mag halt keinen Datenmüll haben :P.
Vielen Dank aber für den Tip, so leicht hab ich nicht gedacht.:P
Wenn du sie löscht dann verschwindet sie ganz, du kannst sie aber in mysql mit Platzhaltern füllen ( ) um dann beim Auslesen eine leere Zeile zu erzeugen ;) -
kill-a-teddy schrieb:
Wenn du sie löscht dann verschwindet sie ganz
Das mag nach außen hin so aussehen aber im Sinne der Frage ist es nicht immer richtig.
Richtig ist, dass dir die Zeile nicht mehr mit ausgegeben wird (da sie ja gelöscht ist).
Aber da Datenbanksysteme hoch optimiert sind, werden solche Dinge nach Heuristiken entschieden.
Das heißt es kann durchaus vorkommen, dass das System entscheidet es wäre zu viel aufwand die Zeile zu löschen und alle anderen eins nachrücken zu lassen und stattdessen lieber die Zeile einfach als gelöscht markiert.
Wenn später eine Zeile eingefügt werden müsste, die gerade an diese Stelle passt, kann sie unter umständen ersetzt werden.
Eigentlich ist das aber alles halb so wild, weil sich diese Sache meistens nur im kleinen Rahmen abspielt.
Wenn du allerdings den verdacht hast, dass die Datenbank langsam ist, weil du so viel "Müll" drin hast, dann kannst du sie optimieren lassen (Stichwort Optimize Table). Dies veranlasst das System solche lücken wieder zu schließen und noch an anderen Stellen Aufräumarbeiten vorzunehmen.
Um mal noch auf die eigentliche Frage zurückzukommen:
Warum brauchst du die FiFo gerade in der Datenbank?
Du kannst sie natürlich relativ einfach hinbekommen, indem du eine Tabelle mit fortlaufendem automatisch inkrementiertem Index baust. Dieser bildet dann automatisch eine zeitliche Ordnung (also in der Reihenfolge des Einfügens). Außerdem werden Schlüssel vom Datenbanksystem meist automatisch sortiert, sodass der Zugriff in Reihenfolge wesentlich schneller laufen sollte.
Beitrag zuletzt geändert: 29.2.2012 19:48:29 von sektor -
Also im Prinzip ist es sehr einfach. Man braucht nicht einmal irgendwelche ids oder indices. Das wichtigste ist einfach der LIMIT-Modifier.
Eintrag in die Tabelle einfügen:
INSERT INTO fifo (a,b) VALUES(1,2);
ältesten Eintrag aus der Tabelle aulesen:
SELECT * FROM fifo LIMIT 1;
Und den ältesten Eintrag löschen.
DELETE FROM fifo LIMIT 1;
Und MySQL wird dir ohnehin die Einträge in fifo-Reihenfolge liefern. Du musst also nichts sortieren ect.
Und sich hier jetzt über Performance den Kopf zu zerbrechen ist auch nur begrenzt sinnvoll. Schau erstmal, wie gut das läuft (lässt sich ja schnell umsetzen) und dann kannst du dir immer noch überlegen, ob es da notwendigen Verbesserungsbedarf gibt.
Beitrag zuletzt geändert: 29.2.2012 21:30:06 von bladehunter -
bladehunter schrieb:
Also im Prinzip ist es sehr einfach. Man braucht nicht einmal irgendwelche ids oder indices.
Ist das auch garantiert?
Wenn es nicht vom Standard vorgeschrieben ist, dann würde ich mich auf dieses Verhalten nicht verlassen.
Natürlich kann es sein, dass es alle Systeme so machen werden, weil es die einfachste Implementation ist aber ohne Garantie ist das ein Spiel mit dem Feuer, wenn updates rauskommen, die dieses Verhalten ändern. -
@sektor: Ich schreibe an einer Art Distrubutionsprogramm. Das ganze soll innerhalb eines Spiels Verwendung finden, welches mir nur die Möglichkeit gibt über php Skripte nach aussen zu interagieren. Ich sende Quasi ein Objekt auf eine bestimme Route über ein System von Wegen. Dabei wird, je nach Ziel ,für entsprechende Checkpoints ein Datensatz in der Tabelle des Checkpoints angelegt. Wenn das Objekt einen Checkpoint passiert, und das muss es um an seinem Ziel anzukommen, wird der zuerst angelegte Eintrag der Tabelle entnommen, entsprechen des Zieles das Routing an dem Checkpoint festgelegt und der Eintrag gelöscht. Somit ist immer garantiert, dass jedes Objekt nur mit den für ihn bestimmten Daten verarbeitet wird. Daher die FiFo Struktur der Datenbank, oder eben als ADT über das Skript.
Ich danke euch allen für die Tipps. Ich denke mit der Hilfe und ein bisschen Trial&Error werd ich da etwas für meine Anforderungen mit zaubern können.
Gruß
-
Wenn man das ganze theoretisch betrachtet brauchst du nur noch einen Zeiger, der auf den Head der Queue zeigt.
Ideen dazu:
* Flag in jedem Datensatz, ob der Datensatz der Head ist oder nicht => n Overhead
* einen Dummydatensatz: dieser wird vor den Head gesetzt und referenziert auf den Head, er hat dann einen festgelegeten Namen den nur er bekommen kann, worüber man ihn dann auslesen kann => bisschen unhandlich
* extra Tabelle mit einem Datensatz der direkt auf den Kopf referenziert => 1 Overhead, dafür eine extra Tabelle -
sektor schrieb:
bladehunter schrieb:
Also im Prinzip ist es sehr einfach. Man braucht nicht einmal irgendwelche ids oder indices.
Ist das auch garantiert?
Ich bin mir keineswegs sicher, das es so ist. Ich habe mal ein Script geschrieben um das ganze zu testen:
<?php $handle = mysql_connect( 'localhost', 'dbuser', 'das_ist_so_ein_doofes_passwort_da_kommt_keiner_drauf' ); mysql_select_db( 'test' ); mysql_query( 'CREATE TABLE IF NOT EXISTS fifo ( a INT, b INT )' ); for( $i = 0; $i < 5; $i++ ) { //dafür sorgen, dass schon nen bisl drin ist mysql_query( 'INSERT INTO fifo (a,b) VALUES ('.$i.',42)' ); } $smallest_idx = -1; for( $i = 5; $i < 5000; $i++ ) { $choice = rand( 0, 2 ); //zufällig pushen oder poppen if( $choice ) { //push mysql_query( 'INSERT INTO fifo (a,b) VALUES ('.$i.',42)' ); } else { //pop $query = mysql_query( 'SELECT * FROM fifo LIMIT 1' ); $res = mysql_fetch_row( $query ); $res = intval( $res[ 0 ] ); if( $res < $smallest_idx ) { echo 'FAIL for '.$res.' vs '.$smallest_idx; exit( 1 ); } $smallest_idx = $res; //grow smallest_idx mysql_query( 'DELETE FROM fifo LIMIT 1' ); } } ?>
Und es lief ohne FAIL durch.
Wenn es nicht vom Standard vorgeschrieben ist, dann würde ich mich auf dieses Verhalten nicht verlassen.
Natürlich kann es sein, dass es alle Systeme so machen werden, weil es die einfachste Implementation ist aber ohne Garantie ist das ein Spiel mit dem Feuer, wenn updates rauskommen, die dieses Verhalten ändern.
Das ist natürlich richtig. Ich habe jetzt auch keine offizielle Bestätigung für dieses Verhalten finden können. -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
