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

[nikosch]

Bei 1000x1000 und einem Flag pro Koordinate kommst Du bereits auf 1MB bzw. 1 Million Tableeinträge. Vielleicht solltest Du Dir eine Strategie überlegen, die Gesamt-Karte weiter zu unterteilen.

Vielleicht reicht Dir auch ein BIT, dann sparst Du etwas.

[Griffith]

Ein Byte pro Feld trifft es eigentlich sehr gut. Ein Nibble mit 16 Möglichkeiten wäre bereits zu wenig.

Am schönsten wäre es glaube ich, wenn die Karte ununterbrochen im Arbeitsspeicher liegt.

Angenommen ich würde den HTTP-Server per Hand in C schreiben, so wäre die ideale Lösung ein ByteArray im Arbeitsspeicher, dass vom Start des Servers bis zum Herunterfahren des Servers im Arbeitsspeicher bleibt.

Nur würde ich gerne wissen, ob es auch eine Lösung für PHP gibt :\

[nikosch]

Wie gesagt: resultierend 1MB. Als Datei ist's das eine, aber als Array im Speicher? Ich spekuliere mal: Das geht nicht gut. Unterteile die Karte in kleinere Quadranten und lade immer nur die in PHP nach. Vielleicht brauchst Du gar nicht so oft unterteilen, weil die Speicherauslastung ja quadratisch abhängig von der Kantenlänge ist.

[Griffith]

Naja, wenn ichs als Datei mache, dann bringen mich Quadranten auch nicht weiter.

Immerhin reicht bei der Datei ein einziges fseek() und fread() um das gewünschte Feld einzulesen. Bzw. beim Einlesen eines Rechtecks auf der Karte ein fseek() und ein fread(Breite) pro Zeile.

Mit Quadranten würde es da nur unnötig komplizierter.

Aber was bringt es mir im Bezug auf die Datenbank?
Ich verstehe noch nicht ganz, wie du das mit den Quadranten meinst :\

Edit:
Ich sollte evtl noch anmerken, dass auf meinem Webserver sehr sehr oft auf diese Karte zugegriffen wird.
Fast bei jedem 4. Auruf schätze ich, wird auf die Karte zugeriffen. Von einem Feld bis hin zu einem Quadrat von 10 Feldern pro Aufruf.

Auch sind die Zugriffe sehr zufällig. Mal ist es ein Feld oben links auf der Karte, mal ein Feld völlig woanders. (Von Aufruf zu Aufruf)

[nikosch]

Doch bringt was.
Wenn Du bspw. einen Zugriff auf Feld 400/800 hast (was auch immer Deine Anwendung genau macht) dann kannst Du vorher berechnen, in welchem Quadranten das Feld liegt und nur die Koordinaten dieses Quadranten einlesen. (Auch wenn der Vergleich mächtig hinkt: so ähnlich, wie das Google Maps veranstaltet...) Natürlich vorausgesetzt, Du speicherst die Quadranten in verschiedenen Dateien ab.
Bei einer Datenbank ist das wohl eher unerheblich.

Aber bitte: Ich habe so etwas noch nie versucht. Meine Antworten sind im Endeffekt Spekulation.

[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.

[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...

[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]

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?

[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

[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 ...

[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.

[Chriz]

Merkste was? Die Zeitunterschiede haben keine Aussagekraft

[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.