Omlouváme se, ale toto není odpověď SQL, ale způsob, jak získat předvídatelný výkon za předpokladu určitých omezení vašich dat.
Jak často se údaje mění? Pokud je to možné, mohli byste předem vypočítat graf každé entity 5 nejbližších sousedů a použít to k urychlení výběru?
Pokud jsou tato data většinou pouze pro čtení, pak...
Jak rovnoměrně jsou tyto body rozděleny? Pokud distribuci znáte poměrně rovnoměrně a dobře, můžete vytvořit vlastní prostorové mapování seskupením každé souřadnice a indexu do hašovací tabulky.
Pokud data v databázi nepotřebujete, přesuňte je do souboru mapovaného v paměti pro rychlé vyhledávání hashů. (70 m záznamů by se mělo snadno vejít do paměti).
Tuto architekturu jsem použil ke generování submilisekundových vyhledávání pro obsahovou reklamu a relevanci pro vyhledávače.
==Zpracování==
Jednoduše vytvoříte mřížku čtverců pevné velikosti (jako šachovnici), namapujete každý bod do mřížky a vytvoříte seznam objektů, které patří do každého z polí mřížky – pokud upravíte velikost každého z nich. správně, měli byste mít v průměru 5-50 bodů v každém čtverci -- Toto je v principu čtyřstrom, ale pro jednoduchost bez stromu.
Ke každému segmentu, který je prázdný poté, co jste rozházeli všechna data do segmentů, přidáte informace o tom, které nejbližší segmenty obsahují data.
Nyní můžete očíslovat každý segment zleva doprava-řádek-ny-řádek, takže každý segment bude mít jedinečné číslo, které lze vypočítat ze souřadnic – a každý segment vložíte do hashovací tabulky, nebo pokud to prostor dovolí, přímou vyhledávací tabulku.
Nyní, když máte svůj dotaz, jednoduše spočítáte, ke kterému segmentu se bude mapovat, a získáte buď seznam objektů v tomto segmentu, nebo získáte „prázdný“ segment, který obsahuje ukazatele na nejbližší segment, který má obsah .
To vám dá první kandidátní seznam objektů, které hledáte, a teď už stačí jen běžet a zjistit, který z nich je nejblíže.
V 99 % případů by to tak bylo – ale pokud se obáváte toho, že (a) jsou buď nějací kondidáti v příštích kbelících, kteří jsou ve skutečnosti blíže, pak stačí zkontrolovat 8 okolních kbelíků a zjistit, zda můžete najděte tam něco blíž.
Pokud nyní chcete také získat seznam všech objektů, které jsou nejblíže, pak také vypočítejte jednoduchou síť 5 nejbližších sousedů pro každý objekt, takže skončíte s datovou strukturou jako A->{B,C,D ,E,F}, B->{A,D,G,H,I}, C->{A,J,K,G,M}....
To vytvoří jednoduchou síť, kterou nyní můžete procházet s variací Dijkstra zde, abyste získali všechny body sousedící s vaším nejbližším bodem.
Vytváření datových struktur bude nějakou dobu trvat, ale jakmile je hotovo, a správné vyhledání a vrácení datové sady může být provedeno během několika milisekund (nezahrnuje případnou komunikaci http nebo off-box)
Doufám, že to pomůže.