Zweidimensionale Karte

[Griffith]

Hallo,

die Karte, von der ich hier spreche, ist im Prinzip eine Bitmap.

Sie hat eine Größe von etwa 1000x1000 und auf jeder Koordinate wird ein einzelner Wert gespeichert. Beispielsweise eine 0 für ein leeres Kartenfeld und eine 1 für ein Hindernis.

Ich kann mich nicht entscheiden, ob ich diese Karte über eine Datei verwalten soll oder über eine Datenbank.

Ich möchte anschließend lediglich einzelne Felder auf ihren Inhalt abfragen können bzw. alle Felder in einem Rechteck auf der Karte.

Pro/Contra Datei
+ schneller Zugriff auf die gewünschte Koordinate (fseek)
+ kleinster Speicherbedarf
- bei jedem Zugriff wird auf die Festplatte zugegriffen.

Pro/Contra Datenbank
Tja, das ist die Frage. Ich erhoffe mir, dass weniger auf die Festplatte zugegriffen wird. Außerdem liegt die Karte dann an einem zentralen Speicherort.

Wie setzt man so eine Karte am besten mit einer Datenbank wie MySQL um?
Und welchen Weg der Speicherung (Datei oder Datenbank) würdet ihr mir empfehlen?

Ich bin für jeden hilfreichen Hinweis dankbar =)


mfg
Griffith

[Flor1an]

Mit Memcache kannst du Abfragen der Datenbank Cachen und im Arbeitsspeicher behalten. So könntest du die größten Abfragen im Cache halten und sie belasten nicht die DB. Wenn es natürlich Abfragen sind die nicht gecached werden dürfen wird es wohl sehr schwer ...

[Chriz]

Was denn eigentlich fuer Binaerdateien? Sind jetzt mit Einsen und Nullen gefuellte Textdateien schon Binaerdateien, oder hab ich wieder nur schlampig gelesen?

[Flor1an]

Naja die größe einer Datenbanktabelle spielt schon eine Rolle. Zwar ist die Menge an sich kein Problem aber irgendwann gehen die Zugriffszeiten so in den Keller dass bestimmte Größen schwer zu handeln werden. Ich denke ich würde vorerst bei einer Datenbank bleiben, alle Zugriffe über eine Klasse abwickeln und dann kann man, bei Performanceproblemen, versuchen mit binär Dateien zu arbeiten etc. Dann müsste nur die Klasse ausgetauscht werden ohne im Skript viel zu ändern.

[Chriz]

Ich meinte mit MyISAM/innoDB mit/ohne Index. Dass die Datei so schnell ist ist schoen, aber sobald du dort zu rechnen anfaengst bekommst du wahrscheinlich die Quittung. Mach doch mal ne Umkreissuche, zaehl die Nachbarn, etc. Ich weiss nicht was du vorhast, aber ich denke mit einer Datenbank bist du einfach auf der sicheren Seite. Ist doch voellig egal wie gross die DB ist und wieviel Platz sie braucht, die Zeiten sind vorbei. Und so lange das ganze deutlich unter einer Sekunde abschneidet ists doch auch egal .. Aber alles was irgendwie mit Browsergames zu tun hat, da straeub ich mich sowieso gegen mitzulesen, weiss garnicht warum, also klink ich mich hierbei mal aus - meine Meinung kennst du ja jetzt

[Griffith]

Merkste was? Die Zeitunterschiede haben keine Aussagekraft

naja, also bei der Variante mit der Datei, die 40x schneller ist, finde ich den Zeitunterschied schon entscheidend

Das InnoDB langsamer ist wundert mich jetzt gar nicht so stark. Nun mal bietet InnoDB eine Transaktionssicherheit. MyISAM hingegen nicht!

Würde es nicht vielleicht Sinn machen die ganzen Daten zum lesen im Cache zu behalten? Ich meine das wenn selten Schreibzugriffe kommen kann dabei ein Teil des Caches erneuert werden und zusätzlich in die DB geschrieben werden. Dafür würden sich Lesezugriffe besser durchführen lassen. Und bei ein paar MB stört das auch nicht im Arbeitsspeicher.

Und wie stelle ich das Cachingverhalten ein für diese Tabelle? Habe leider nur ein Grundlagenwissen :\

Denn diese 0,127 Sekunden sind einfach noch was viel...
Da braucht es nur wenige parallele Zugriffe von außen und schon hängt der Server...

Danke, dass ihr das Thema nochmal aufgegriffen habt

[Flor1an]

Das InnoDB langsamer ist wundert mich jetzt gar nicht so stark. Nun mal bietet InnoDB eine Transaktionssicherheit. MyISAM hingegen nicht!

Würde es nicht vielleicht Sinn machen die ganzen Daten zum lesen im Cache zu behalten? Ich meine das wenn selten Schreibzugriffe kommen kann dabei ein Teil des Caches erneuert werden und zusätzlich in die DB geschrieben werden. Dafür würden sich Lesezugriffe besser durchführen lassen. Und bei ein paar MB stört das auch nicht im Arbeitsspeicher.

[Chriz]

Merkste was? Die Zeitunterschiede haben keine Aussagekraft

[Griffith]

[...] Du kannst auch den Wert aus der Tabelle raus schmeissen (den brauchst du sowieso nicht) [...]

Den Wert brauche ich schon. Er beschreibt, welches Objekt sich dort befindet (Baum, Felsen, was auch immer).

Ich habe gerade eine Klasse geschrieben mit der man die Karte als Datei verwalten kann (nur Einlesen bisher).
Um einen Bereich von 300x300 Feldern über MySQL einzulesen (MEMORY) brauche ich ca. 0,1272 Sekunden.
Um einen Bereich von 300x300 Feldern aus der Datei einzulesen (Keine Textdatei, sondern Binärdaten) brauche ich ca. 0,003 Sekunden.

Sollen die eingelesenen Daten in Integer-Werte umgewandelt werden braucht die Klasse ca. 0.0827 Sekunden. (fread liefert ja leider immer einen String). Allerdings ist die Umwandlung gar nicht notwendig.

Sogesehen ist die Variante mit der Textdatei 40x bzw. 1,5x so schnell.

Es finden hauptsächlich Lesezugriffe statt.
Direkt aufeinanderfolgende Schreibzugriffe sehr sehr selten.
Aber Angst macht es mir schon, dass es beim Schreiben zu Problemen kommen kann.
Und solange ich nicht weiß wie man das verhindert, ist mir die MySQL-Variante definitiv lieber.

Allerdings: Wenn die Datei in einer Ramdisk liegt und ich bei Schreibzugriff > 1 Byte die Datei per flock() verriegel, sollte es doch eigtl keine Probleme geben, oder?

Edit:
Hmm, InnoDB müsste ich erstmal nachrüsten. Konnte ich noch nicht testen.

Edit 2:
MyISAM ohne Index: 430 KiB und ca. 0,127 Sekunden
MyISAM mit Index (x,y): 1,0 MiB und ca. 0,127 Sekunden
InnoDB ohne Index: 2,5 MiB und ca. 0.18 Sekunden
InooDB mit Index (x,y): 2,5 MiB und ca. 0.132 Sekunden

Wobei InnoDB scheinbar ein klitzekleines bisschen langsamer als MyISAM ist *wunder*
Hat auch zwischendurch deutlich höhere Peaks ins der Ausführungszeit als bei MyISAM.

Also ob InnoDB oder MyISAM macht eigtl kein Unterschied.

[Flor1an]

MyIsam würde ich, wenn es sich um kritische Daten handelt, meiden. Wir hatten selbst das Problem. Wenn der Server mal abstürzt dann sind die MyIsam Tabellen alle kaputt und konnten nur teilweise repariert werden. Mit InnoDB war das gar kein Problem.

Handelt es sich hier auch um viele Schreibzugriffe oder nur Lesezugriffe? Denn wenn noch Schreibzugriffe dazu kommen würde ich bei einer Textdatei auch aufpassen. Wenn es da zu gleichzeitigen Schreibzugriffen kommt ...

[lazydog]

Warum ist jeder Datensatz 7 byte groß, wenn es doch nur 2 SMALLINT und 1 TINYINT sind. Sollten es nicht 5 Byte sein?

Das kann ich dir auch nicht sagen. Du kannst auch den Wert aus der Tabelle raus schmeissen (den brauchst du sowieso nicht), es bleibt trotzdem bei 7 Byte. Bei ENGINE MEMORY sind es 8.
Es hängt auch sonst noch vom Tabellentyp ab. MyIsam braucht fast keinen Platz für Daten, dfür umso mehr für den Index. Auch InnoDB scheint zu merken, dass Daten und Index identisch sind. Benutzt wird hier nur der Platz der Daten. Memory scheint alles doppelt zu führen

[Griffith]

In der Datenbank hast du den Vorteil, 0 Werte garnicht auffuehren zu muessen, wodurch sich die Datenmenge erheblich reduzieren koennte. Ausserdem kannst du die Tabelle als MEMORY anstatt MyISAM anlegen, dann liegt sie im Arbeitsspeicher des Datenbankservers. Aber ich bezweifle, dass MySQL damit Probleme hat ..

Die Tabelle hat die 4-fache Größe der Datei.
Pro Feld benötige ich in der Datenbank 7/4 Byte (da nur jedes 4. Feld belegt ist und ein Datensatz 7 Byte groß ist).
Pro Feld benötige ich in der Datei 1 Byte.

Wenn der Index bei der Datenbank noch dazu kommt, kommt man auf die 4-fache Größe der Datei.
Den Index brauche ich um doppelte Einträge zu verhindern (Primary Key).

Die MEMORY-Engine kann ich nicht verwenden, weil es sich um sehr kritische Daten handelt. Sollte der Server abstürzen und die Daten sind weg, wäre das fatal.

PS: Jetzt erst gelesen. Die Tabelle ist ja praktisch nur ein Index, da wuerde ich den Overhead Index-Spalte wohl eher weglassen. War Postgresql nicht die grosse Integer-Datenbank, die dafuer so gut geeignet ist? Vielleicht kannst du auch die verwenden ..

Nun, die Tabelle könnte doch auch ungeordnet sein. Füge ich ein neues Feld hinzu (dort wo vorher ein leeres Feld war) wird der Datensatz ans Ende der Tabelle gespeichert und schon ist die Tabelle selbst kein Index mehr, sondern nur noch ne Anhäufung von Rohdaten.

Man müsste sicherstellen, dass die Datenbank immer sortiert ist.
Immerhin ändert sich die Karte nur ganz selten.

Edit:
Warum ist jeder Datensatz 7 byte groß, wenn es doch nur 2 SMALLINT und 1 TINYINT sind. Sollten es nicht 5 Byte sein?

[Chriz]

In der Datenbank hast du den Vorteil, 0 Werte garnicht auffuehren zu muessen, wodurch sich die Datenmenge erheblich reduzieren koennte. Ausserdem kannst du die Tabelle als MEMORY anstatt MyISAM anlegen, dann liegt sie im Arbeitsspeicher des Datenbankservers. Aber ich bezweifle, dass MySQL damit Probleme hat ..

PS: Jetzt erst gelesen. Die Tabelle ist ja praktisch nur ein Index, da wuerde ich den Overhead Index-Spalte wohl eher weglassen. War Postgresql nicht die grosse Integer-Datenbank, die dafuer so gut geeignet ist? Vielleicht kannst du auch die verwenden ..

[Griffith]

Also bisher hatte ich mir so eine Tabelle vorgestellt:

CREATE  TABLE  `karte` (
   `x` SMALLINT  UNSIGNED NOT  NULL ,
   `y` SMALLINT  UNSIGNED NOT  NULL ,
   `wert` TINYINT  UNSIGNED NOT  NULL ,
   PRIMARY  KEY (  `x` ,  `y`  ) 
) ENGINE  =  MYISAM ;

Damit der Zugriff auf ein X-Y-Paar schnell ist, wird der PRIMARY-KEY für beide Spalten x und y angelegt. Ist das so korrekt?

Oder sollte ich die Tabelle doch anders aufbauen? Wie würde der Zugriff auf die einzelnen Koordinaten am schnellsten sein?

Und ja, gespeichert würden dann nur die Felder, in denen der Wert != 0 ist.
Dabei würden nur ca. die Hälfte der Felder in der Datenbank rumliegen.

Der Nachteil an der Datebank im Gegensatz zur Datei ist aber, dass zusätzlich noch die X-Y-Koordinaten und der passende Index dazu erstellt und verwaltet werden muss.

Allerdings ist die Datenbank dadurch auch etwas flexibler, falls ich die Karte mal erweitern möchte in ihrer Dimension. Aber das wird eh nie der Fall sein.

Edit:
Habe mal eine Tabelle mit 60.000 zufälligen Werten erstellt.
X-Y-Koordinaten zwischen (0|0) und (499|499).

Wenn ich jetzt den Bereich zwischen (100|100) und (200|200) anfordere, macht es scheinbar keinen unterschied, ob ich x und y als PRIMARY-KEY definiere oder nicht. Es dauert genauso lange. (Obwohl die Tabelle nciht mehr soritert war, habe einfach mal aufsteigend nach "wert" soritert).

Ich habe folgende Queries probiert, wobei das zweite mit BETWEEN ein bisschen schneller ist.

SELECT x, y, wert FROM `karte` WHERE x >= $untergrenze_x AND x <= $obergrenze_x AND y >= $untergrenze_y AND y <= $obergrenze_y

SELECT x, y, wert FROM `karte` WHERE x BETWEEN $untergrenze_x AND $obergrenze_x AND y BETWEEN $untergrenze_y AND $obergrenze_y

Insgesamt habe ich für den kleinen Bereich 0,043 Sekunden gebraucht. (ca. 2500 Datensätze)

Aber dass das mit den PRIMARY-KEY keine Auswirkung hat verwundert mich doch...

[lazydog]

Es gäbe auch die Möglichkeit, ausschliesslich die gesetzten (oder falls weniger, die nicht gesetzten) Punkte zu speichern und diese als x/y Paare in die DB zu schreiben. Das kann die Tabelle u.U massiv verkleinern. Diese können dann in einen zweidimensionalen Array gelesen werden.