Ini adalah pertanyaan pertama saya di sini, jadi bersabarlah!
Saya menerapkan ujung belakang untuk aplikasi seluler yang harus melakukan pencarian kedekatan untuk menemukan POI terdekat (poin yang menarik). Saya tahu ini adalah skenario yang sangat umum dan terlihat sangat sederhana, tetapi ada banyak cara saya dapat mengimplementasikannya, jadi saya akan senang melihat bagaimana profesional yang lebih berpengalaman menerapkan pencarian spasial sederhana ini.
Karena POI hanyalah POINT, kami tidak memerlukan perhitungan rumit yang melibatkan persimpangan atau sejenisnya. Itulah sebabnya saya awalnya berpikir bahwa menggunakan kolom GEOGRAFI dan indeks spasial bisa jadi lebih banyak atau bahkan lebih lambat daripada strategi lainnya. Jadi saya mempersempitnya menjadi 3 pendekatan:
1) kolom GEOGRAFI + Indeks Spasial
Ini mungkin solusi de facto untuk masalah ini. Karena kami memiliki indeks spasial dan kolom geografi, kami cukup menggunakannya dan mencari berdasarkan jarak. Sesuatu seperti ini.
SELECT * FROM POIs WHERE Loc.STDistance(@radius) <= @distance;
Karena kami memiliki indeks spasial pada Loc, itu harus sangat cepat.
2) Menggunakan "kotak pembatas" di atas kolom Lintang dan Bujur
Ini adalah pendekatan sepele tanpa melibatkan indeks spasial. Kami menemukan kotak pembatas untuk titik dan jari-jari kami kemudian cukup mencari pada kolom Lintang dan Bujur. Jika keduanya diindeks pencarian ini harus sangat cepat. Kita harus menerapkan fungsi jarak untuk menyaring beberapa nilai di luar "lingkaran" tetapi dengan kotak pembatas. Tapi itu harusnya cukup cepat. Ide ini lebih baik dijelaskan di sini: http://www.movable-type.co.uk/scripts/latlong-db.html
Sesuatu seperti ini:
DECLARE @lat float
DECLARE @lon float
SET @lat = -23.001029
SET @lon = -43.328422
DECLARE @maxLat float, @minLat float, @maxlon float, @minLon float
DECLARE @R float
DECLARE @distance FLOAT = 100 -- A distance in meters
SET @R = 6378137 -- Earth
SET @maxLat = @lat + DEGREES(@distance/@R)
SET @minLat = @lat - DEGREES(@distance/@R)
SET @maxLon = @lon + DEGREES((@distance/@R/COS(RADIANS(@lat))))
SET @minLon = @lon - DEGREES((@distance/@R/COS(RADIANS(@lat))))
SELECT * from POIs
WHERE
Lat Between @minLat And @maxLat
And Lng Between @minLon And @maxLon
3) Gunakan GEOHASH integral yang disimpan pada kolom yang diindeks
Pendekatan ini sangat menarik dan merupakan sesuatu yang digunakan orang bersama dengan set yang diperintahkan REDIS untuk melakukan pencarian kedekatan. Prinsipnya dapat dialihkan ke SQL Server dengan menggunakan kolom yang diindeks yang menyimpan GEOHASH integral.
Saya mendapat ide ini dari Ardb: https://github.com/yinqiwen/ardb/wiki/Spatial-Index
Ini juga dijelaskan dengan sedikit ramah di sini: Menggunakan geohash untuk pencarian kedekatan?
Dengan kata lain seseorang akan menghitung GEOHASH dengan kedalaman-bit yang sesuai dengan radius pencarian yang diinginkan, kemudian menghitung 8 tetangga geohash dan akhirnya mengirimkan pencarian menggunakan geohashs ini sebagai kotak pembatas pada kolom yang diindeks. Ini akan menjadi 9 ANTARA operator pada klausa WHERE SQL ... Hasilnya harus disaring karena beberapa POI palsu dikembalikan.
Tetapi tampaknya ini akan lebih lambat daripada metode 2 karena klausa di mana akan lebih kompleks meskipun hanya akan meminta lebih dari satu kolom, bukan dua.
Adakah yang punya pengalaman untuk berbagi tentang ini? Apakah ada pendekatan yang lebih baik / benar untuk ini?
sumber
Jawaban:
Alasan mengapa database mengimplementasikan indeks R-tree untuk spasial adalah karena mereka lebih cepat daripada geohash atau pencarian pada indeks x dan y yang terpisah. Masalah dengan geohash, adalah Anda harus mencari 9 kuadran, bukan hanya 1, untuk melakukan pencarian tipe kedekatan - lihat batasan geohash . Mereka berguna dalam database yang tidak memiliki R-tree, untuk memungkinkan ekspresi objek dengan rentang 2-D, dalam satu dimensi, yang kemudian dapat diindeks dengan B-tree. Memiliki indeks terpisah (atau gabungan) pada x dan y juga akan lebih lambat, karena Anda perlu memindai lebih banyak indeks ke nol pada bidang yang Anda minati, sedangkan dengan R-tree, pencarian indeks Anda berada di kotak pembatas.
Penggunaannya akan bervariasi, tetapi tidak berlebihan untuk menggunakan spasial hanya karena Anda hanya memiliki poin. Anda tidak kehilangan apa pun dengan menggunakan tipe geometri dan berpotensi memperoleh banyak (tidak hanya dalam hal kecepatan), tetapi dalam pemeriksaan di masa mendatang. Bagaimana jika Anda ingin menambahkan penyangga atau persimpangan poligon di kemudian hari? Pada akhirnya, satu-satunya cara untuk mengetahuinya adalah dengan menguji use case Anda, tetapi 2c saya menggunakan pendekatan 1.
sumber