Entschuldigung, aber dies ist keine SQL-Antwort, sondern eine Möglichkeit, eine vorhersagbare Leistung zu erhalten, wenn bestimmte Einschränkungen für Ihre Daten vorausgesetzt werden.
Wie oft ändern sich die Daten? Wenn möglich, könnten Sie ein Diagramm von jeder Entität mit den 5 nächsten Nachbarn vorab berechnen und diese verwenden, um Ihre Auswahl zu beschleunigen.?
Wenn diese Daten hauptsächlich schreibgeschützt sind, dann...
Wie gleichmäßig sind diese Punkte verteilt? Wenn die Verteilung ziemlich gleichmäßig und gut bekannt ist, könnten Sie dann Ihre eigene räumliche Zuordnung erstellen, indem Sie jede Koordinate und jeden Index in eine Hash-Tabelle packen.
Wenn Sie die Daten nicht in der Datenbank benötigen, verschieben Sie sie für schnelle Hash-Suchen in eine speicherabgebildete Datei. (70 Millionen Datensätze sollten problemlos in den Speicher passen).
Ich habe diese Architektur verwendet, um Sub-Millisekunden-Lookups für Display-Werbung und Suchmaschinenrelevanz zu generieren.
==Ausarbeitung==
Sie erstellen einfach ein Raster aus Quadraten fester Größe (wie ein Schachbrett), und Sie ordnen jeden Punkt dem Raster zu, und Sie erstellen eine Liste der Objekte, die in jedes der Rasterfelder gehören - wenn Sie die Größe von jedem anpassen Box richtig, sollten Sie durchschnittlich 5-50 Punkte in jedem Quadrat haben -- Dies ist im Prinzip ein Quad-Tree, aber der Einfachheit halber ohne den Baum.
Für jeden Bucket, der leer ist, nachdem Sie alle Daten in Buckets verteilt haben, fügen Sie Informationen darüber hinzu, welche Buckets in der Nähe Daten enthalten.
Sie können jetzt jeden Eimer von links nach rechts nummerieren, sodass jeder Eimer eine eindeutige Nummer hat, die aus den Koordinaten berechnet werden kann – und Sie fügen jeden Eimer in eine Hash-Tabelle ein, oder wenn der Platz es zulässt, genauso eine direkte Nachschlagetabelle.
Wenn Sie jetzt Ihre Abfrage haben, berechnen Sie einfach, auf welchen Bucket sie abgebildet wird, und Sie erhalten entweder eine Liste von Objekten in diesem Bucket oder Sie erhalten einen "leeren" Bucket, der die Zeiger auf den nächsten Bucket mit Inhalt enthält .
Das gibt Ihnen die erste Kandidatenliste von Objekten, nach denen Sie suchen, und jetzt müssen Sie einfach nur noch durchgehen und sehen, welches am nächsten ist.
In 99% der Fälle wäre es das gewesen -- aber wenn Sie sich darüber Sorgen machen, gibt es (a) entweder einige Bedingungen in den nächsten Eimern, die tatsächlich näher sind, dann überprüfen Sie einfach die 8 umliegenden Eimer und sehen Sie, ob Sie können Näher dort finden.
Wenn Sie nun auch eine Liste aller am nächsten gelegenen Objekte erhalten möchten, dann berechnen Sie für jedes Objekt auch ein einfaches Netz von 5 nächsten Nachbarn, sodass Sie am Ende eine Datenstruktur wie A->{B,C,D erhalten ,E,F}, B->{A,D,G,H,I}, C->{A,J,K,G,M}....
Das bildet ein einfaches Netzwerk, das Sie jetzt mit einer Variation von Dijkstra durchqueren können hier, um alle Punkte neben dem nächstgelegenen Punkt zu erhalten.
Das Erstellen der Datenstrukturen wird einige Zeit in Anspruch nehmen, aber sobald dies erledigt ist, kann das Suchen und Zurückgeben eines Datensatzes in weniger als Millisekunden erfolgen (ohne HTTP- oder Off-Box-Kommunikation aus Ursache)
Hoffe das hilft.
