近くにいる人の数はどのように計算されますか?

例: Ele.me は近くのレストラン、QQ、WeChat に接続されている人々を検索します。バックエンドはどのように検索しますか?
ユーザーが接続されたレストランを開くと、ユーザーのレストランの座標レコードが 10,000 件あります。座標は、たとえば、ある店舗の場合、2 点の座標を計算するのは簡単です。問題は、10,000 店舗ある場合、500 メートル、1000 メートルのアタッチメントをどのように見つけるかです。 2000 メートル....

返信内容:

多くの実装ソリューションがあります:
mysql 空間データベース: Mysql gis 空間データベース関数の詳細な調査
2. Solr 空間インデックスは緯度および経度インデックス、場所によるクエリ、距離による並べ替え。

3. Redis の新しいバージョンは geohash もサポートします。Redis GEO 機能の概要 一般に、Geohash アルゴリズムが使用され、文字列を使用して 2 次元座標を表します。2 つの点が近ければ近いほど、2 つの Geohash 文字列プレフィックスに共通する桁数が多くなります (この文は厳密ではない可能性があります)。そのため、クエリは次のようになります。効率ははるかに高くなります。 ジオハッシュ 一般的には Geohash アルゴリズムですが、このアルゴリズムの問​​題点は、非常に近いグリッドでも、周囲の 8 つのグリッドを選択して計算することです。 ○○メートル付近など、範囲に応じて検索するのは簡単ではありません。 2つ目のアルゴリズムは、xxメートルの近くに円があり、その円に外接する正方形の経度、緯度の範囲を計算します。これは、中心辺の長さが次の正方形の経度、緯度の範囲です。現在位置のxx*2をデータベースに保存します。大なり小なりの条件を使用して四角形に該当するPOI（店舗）を検索し、厳密にしたい場合は四隅のデータを削除します。 (距離を計算するだけです。現時点では、データ量が非常に少ないため、テーブル全体をスキャンする必要はありません。非常に高速です) 精度の要件が高くない場合は、そのまま使用できます。この方法では、データベース内の経度と緯度のフィールドにインデックスを付けるだけで済み、一般的なデータ量に対処するのに十分です。
質問の主題には 10,000 個のデータしかありません。データなので、この方法が適切です。
3 番目の方法は、データベースの空間インデックスを使用する方法で、MySQL 自体がこれをサポートしており、R Tree で実装されているため、より効率的です。 1. 緯度と経度を整数に変換します。
2. 円形をカウントせずに正方形を計算し、平方根演算を避け、経度間と緯度間を直接使用します。 3. この四角形内の人々を決定した後、指数で並べ替えるだけです (ルート記号は開かずに)。 1000 メートル以内にいる人を見つけるには、データベースの設計とクエリでこの機能をどのように実装できるでしょうか? - データベース設計 オープン ソース ツールをすぐに使用してください、おいおい、おい、ソース コードを開いてください、おいおい。 この種のアルゴリズムが付属する mongodb を使用してください 全員の座標を保存し、自分の座標と他の全員の座標の間の距離を見つけます。 ジオハッシュ | 解決策: geohash + redis set
時間計算量: O(1)
空間計算量: O(n)、redis のキーは非常に短いため、非常に経済的です。を参照してください。以下の表: