问题 查找与所选点的特定距离内的所有地址的最佳方法是什么

您可以在查询本身而不是客户端执行计算服务器端计算，从而仅检索计算结果。 这里 （档案链接 对于后代来说，这是一个基于Haversine的SQL实现示例（对不起，这篇文章对我来说太冗长了，我在这里复制+粘贴或总结，虽然它是一篇很棒的文章，很容易阅读）。

或者，您可以将数据库划分为多个区域（例如，具有极坐标的四叉树），并仅检索该点附近的区域，从而为您提供较小的子集以针对客户端进行测试。同样，您可以根据距离计算粗略的经度和经度边界框，使用纬度和经度的数据库索引，并选择该范围内的地址以供计算时考虑。

查询方法虽然更简单，更简洁，但由于初始距离过滤而具有良好的性能。如果前者由于某种原因无法实现，我只会采用区域方法。

我会说数据库方法是最好的，因为你不需要有大量的内存。您可以使用以下代码通过休眠检索它们。

@Transactional
public List<Double> getAllPoisAroundUser(double longitude, double latitude, int page) {

Query query = getSessionFactory().getCurrentSession().createSQLQ uery("SELECT (6371 * 2 * ASIN(SQRT(POWER(SIN((:ulatitude - abs(latitude)) * pi()/180 / 2),2) +" +
"COS(:ulatitude * pi()/180 ) * COS(abs(latitude) * pi()/180) *" +
"POWER(SIN((:ulongitude - longitude) * pi()/180 / 2), 2))))*1000 as distance " +
"FROM poi HAVING distance < 5000 ORDER BY distance");

query.setParameter("ulongitude", longitude);
query.setParameter("ulatitude", latitude);
query.setFirstResult((page-1)*10);
query.setMaxResults(10);

return (List<Double>) query.list();
}

我正在使用hibernate并以这种方式执行此操作：

public List<Tour> searchTours(double lat, double lon, double distance) {

    Session session = getSession();

    Criteria criteria = session.createCriteria(Tour.class, "tour");

    //
    // 1 Grad lat = 111 km
    // 1 grad lon = cos(lat) * 111
    //
    final double KM_IN_ONE_LAT = 111.0;

    double t1 = distance / Math.abs(Math.cos(Math.toRadians(lat)) * KM_IN_ONE_LAT);
    double t2 = distance / KM_IN_ONE_LAT;

    double lonA = lon - t1;
    double lonB = lon + t1;

    double latA = lat - t2;
    double latB = lat + t2;

    Criterion c1 = Restrictions.between("longitude", lonA, lonB);
    Criterion c2 = Restrictions.between("latitude", latA, latB);

    criteria.add(c1);
    criteria.add(c2);

    criteria.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY);

    return criteria.list();
}

查看此文章以获取更多信息： Geo（邻近）使用MySQL搜索

你需要多准确？使用postgres GIS索引或r-tree索引可以作为起点。然后执行边界框查询..然后在客户端上执行径向距离..这样，FP数学不是由中央服务器完成的（窒息可扩展性）。我的问题是GIS和rtree是最慢的索引类型（仅由FTS索引精梳）。所以我通常选择像地理数据一样的一维索引。如果你有点数据，只需将所有内容存储在一个普通的GSD（地面采样距离）中，如10米或1米，或者你有什么......你构建一个' string'（通常是base-64编码），它是lat-long（每个位交替lat和long）。这些点作为简单的字符串索引存储在DB中（对于索引和存储非常有效）。然后对于查询，你必须从你感兴趣的地理散列范围内的搜索点生成一个边界框...除非你有非常大的半径，否则这应该缩小搜索结果...在客户端进行最终过滤（或使用其他人列出的技术之一进行预先计算的三角值）。

然而，问题是通过1M点筛选很快。进行1,000次随机磁盘访问是不可用的。所以即使你有一个很好的地理哈希，如果它有很多随机点;这不会起作用。

我通常做的是在磁盘上存储所有相关的数据块。因此，地理搜索为您提供了一组有限的磁盘位置...然后在最多4个磁盘负载中加载所有数据（数十MB）。然后筛选所有几何体。在最好的情况下（v.s. 1,000磁盘rand访问），这可以快1000倍。但显然对您如何将数据存储到网格中的方式有​​严格的限制（完全重写或固定大小的垃圾箱）。

显然，如果你有足够的RAM来缓存整个数据库，那么从那里开始。该算法并不重要。首先考虑磁盘访问模式。然后CPU访问模式（您可以扩展CPU，但很难维护磁盘数据的重复）。

计划A：由于你有300K行，因此INDEX（lat）在性能方面是非首发的，即使限制为条带： AND lat BETWEEN 65 AND 69。 INDEX(lat, lng) 不是更好，因为优化器会 不 使用两列，即使使用 AND lng BETWEEN...

计划B：下一个选择将涉及lat和lng，以及子查询。版本5.6将是有益的。这是这样的（包括之后） INDEX(lat, lng, id)）：

SELECT ... FROM (
    SELECT id FROM tbl
        WHERE lat BETWEEN... 
          AND lng BETWEEN... ) x
    JOIN tbl USING (id)
    WHERE ...;

由于各种原因，B计划仅略优于计划A.

计划C：如果您需要数百万行，则需要 我的披萨店算法。这涉及一个存储过程来重复探测，寻找足够的行。它还涉及到 PARTITION获得粗略的二维指数。

计划A和B是 O(sqrt(N));计划C是 O(1)。也就是说，对于计划A和B，如果您将行数增加四倍，则会将时间加倍。随着你增加N，计划C不会变慢。

您可以使用原始查询在hibernate中选择表格地址表中的ID列表。

public List<Long> getNearByLocations(float latitude, float longitude,
            float distance) {
        Session sess = getSession();
        String queryString = "SELECT id, (6371 * acos (cos(radians("
                + latitude
                + ")) * cos(radians(latitude)) * cos(radians(longitude) - radians("
                + longitude
                + "))  + sin(radians("
                + latitude
                + ")) * sin(radians(latitude)))) AS distance FROM Address HAVING distance < "
                + distance + " ORDER BY distance";
        Query qry = sess.createSQLQuery(queryString);

        List<Object[]> list = null;
        list = qry.list();
        List<Long> idList = new ArrayList<>();
        for (Object[] obj : list) {
            Long id = (Long) obj[0];
            idList.add(id);
        }
        return idList;
    }

查询整个数据库表不高效或可扩展。考虑使用 R-树 为了更好的表现。