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

Mister Ad

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.

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--

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.

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--

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.

__________________
--
One pixel is still too big. Please make it smaller. ASAP.

Initiative Mittelstand.
Die wichtigste Gestaltungsregel im Screendesign ist Pi mal Daumen des Arbeitgebers.
--

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.

__________________
Gruss
L

Griffith

Also bisher hatte ich mir so eine Tabelle vorgestellt:

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

__________________
"Nuschel ich?" - "Was?"

Griffith

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.

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?