Einmal ist interessant, ob deine DB "lebt" oder ob sie konstant bleibt? Je konstanter, desto mehr kannst du mit verberechneten Werten arbeiten.

Wenn du in einem High-Performance Umfeld arbeitest, kann ich Oracle empfehlen. Deren Spatial-Erweiterungen sind sehr ausgereift. Allerdings ist die Lizenz nicht gerade billig und du müsstest deine DB wechseln.

Wenn du die Berechnung per Hand machen möchtest, gibt es noch mehr als das schon angesprochene Gitter (nennt sich auch UniformGrid), welches aber sehr schlecht skaliert. Hast du z.B. eine starke Häufung deiner Punkte in einem Quadranten, gewinnst du kaum etwas.
Es wäre jetzt etwas aufwendig, alle Optimierungsstrukturen aufzuzeigen, viele werden übrigens auch in der Computergrafik (mit einer Tiefendimension mehr) erfolgreich verwendet. Ich nenn hier nur mal einige:

UniformGrid, AdaptiveGrid, BoundingBoxes, kd-Trees, QuadTrees, R-Trees und Varianten, mehrdimensionales Hashing und alle BinaryTrees.


Auch wenn das jetzt viel klingt, schau mal in die Doku deiner DB, normalerweise sind da schon einige vorimplementiert und für die DB optimiert. Wenn du es selber machen willst, empfehle ich dir einen BoundingBoxes-Ansatz mit einem beliebiges Tree kombiniert. Damit wirst du schon recht effektiv.

Einmal ist interessant, ob deine DB "lebt" oder ob sie konstant bleibt? Je konstanter, desto mehr kannst du mit verberechneten Werten arbeiten.

Wenn du in einem High-Performance Umfeld arbeitest, kann ich Oracle empfehlen. Deren Spatial-Erweiterungen sind sehr ausgereift. Allerdings ist die Lizenz nicht gerade billig und du müsstest deine DB wechseln.

Wenn du die Berechnung per Hand machen möchtest, gibt es noch mehr als das schon angesprochene Gitter (nennt sich auch UniformGrid), welches aber sehr schlecht skaliert. Hast du z.B. eine starke Häufung deiner Punkte in einem Quadranten, gewinnst du kaum etwas.
Es wäre jetzt etwas aufwendig, alle Optimierungsstrukturen aufzuzeigen, viele werden übrigens auch in der Computergrafik (mit einer Tiefendimension mehr) erfolgreich verwendet. Ich nenn hier nur mal einige:

UniformGrid, AdaptiveGrid, kd-Trees, QuadTrees, R-Trees und Varianten, mehrdimensionales Hashing und alle BinaryTrees.


Auch wenn das jetzt viel klingt, schau mal in die Doku deiner DB, normalerweise sind da schon einige vorimplementiert und für die DB optimiert.