搜索距离邮政编码最近的5个位置-我应该怎么做？

pwuypxnk  于 2021-06-23  发布在  Mysql
关注(0)|答案(2)|浏览(291)

我想要的是：
用户传入邮政编码或城市名称
我在数据库中搜索最近的5个位置
向用户显示离该位置最近的5个位置
到目前为止我所拥有的：
假设一个包含以下内容的位置表：
（约16000行）

CREATE TABLE `locations` (
 `locationID` int(11) NOT NULL AUTO_INCREMENT,
 `name` varchar(150) NOT NULL,
 `firstname` varchar(100) DEFAULT NULL,
 `lastname` varchar(100) DEFAULT NULL,
 `street` varchar(100) NOT NULL,
 `city` varchar(100) NOT NULL,
 `state` varchar(100) NOT NULL,
 `zipcode` varchar(10) NOT NULL,
 `phone` varchar(20) NOT NULL,
 `web` varchar(255) DEFAULT NULL,
 `machine` enum('Unbekannt','Foo','Bar') DEFAULT 'Unbekannt',
 `surface` enum('Unbekannt','Foo','Bar','') DEFAULT 'Unbekannt',
 PRIMARY KEY (`locationID`)
) ENGINE=InnoDB AUTO_INCREMENT=25 DEFAULT CHARSET=utf8

身份证件
名称
邮政编码
城市
现在我有了第二张table，上面有世界上所有的城镇：
（约340万行）

CREATE TABLE `geoData` (
 `geoID` int(11) NOT NULL AUTO_INCREMENT,
 `countryCode` char(2) NOT NULL,
 `zipCode` varchar(20) NOT NULL,
 `name` varchar(180) NOT NULL,
 `state` varchar(100) NOT NULL,
 `stateCode` varchar(20) NOT NULL,
 `county` varchar(100) NOT NULL,
 `countyCode` varchar(20) NOT NULL,
 `community` varchar(100) NOT NULL,
 `communityCode` varchar(20) NOT NULL,
 `lat` mediumint(6) NOT NULL,
 `lon` mediumint(6) NOT NULL,
 PRIMARY KEY (`lon`,`lat`,`geoID`) USING BTREE,
 KEY `geoID` (`geoID`)
) ENGINE=InnoDB AUTO_INCREMENT=16482 DEFAULT CHARSET=utf8
/*!50100 PARTITION BY RANGE (lat)
(PARTITION p0 VALUES LESS THAN (-880000) ENGINE = InnoDB,
PARTITION p1 VALUES LESS THAN (-860000) ENGINE = InnoDB,
PARTITION p2 VALUES LESS THAN (-840000) ENGINE = InnoDB,
PARTITION p3 VALUES LESS THAN (-820000) ENGINE = InnoDB,
PARTITION p4 VALUES LESS THAN (-800000) ENGINE = InnoDB,
PARTITION p5 VALUES LESS THAN (-780000) ENGINE = InnoDB,
PARTITION p6 VALUES LESS THAN (-760000) ENGINE = InnoDB,
PARTITION p7 VALUES LESS THAN (-740000) ENGINE = InnoDB,
PARTITION p8 VALUES LESS THAN (-720000) ENGINE = InnoDB,
PARTITION p9 VALUES LESS THAN (-700000) ENGINE = InnoDB,
PARTITION p10 VALUES LESS THAN (-680000) ENGINE = InnoDB,
PARTITION p11 VALUES LESS THAN (-660000) ENGINE = InnoDB,
PARTITION p12 VALUES LESS THAN (-640000) ENGINE = InnoDB,
PARTITION p13 VALUES LESS THAN (-620000) ENGINE = InnoDB,
PARTITION p14 VALUES LESS THAN (-600000) ENGINE = InnoDB,
PARTITION p15 VALUES LESS THAN (-580000) ENGINE = InnoDB,
PARTITION p16 VALUES LESS THAN (-560000) ENGINE = InnoDB,
PARTITION p17 VALUES LESS THAN (-540000) ENGINE = InnoDB,
PARTITION p18 VALUES LESS THAN (-520000) ENGINE = InnoDB,
PARTITION p19 VALUES LESS THAN (-500000) ENGINE = InnoDB,
PARTITION p20 VALUES LESS THAN (-480000) ENGINE = InnoDB,
PARTITION p21 VALUES LESS THAN (-460000) ENGINE = InnoDB,
PARTITION p22 VALUES LESS THAN (-440000) ENGINE = InnoDB,
PARTITION p23 VALUES LESS THAN (-420000) ENGINE = InnoDB,
PARTITION p24 VALUES LESS THAN (-400000) ENGINE = InnoDB,
PARTITION p25 VALUES LESS THAN (-380000) ENGINE = InnoDB,
PARTITION p26 VALUES LESS THAN (-360000) ENGINE = InnoDB,
PARTITION p27 VALUES LESS THAN (-340000) ENGINE = InnoDB,
PARTITION p28 VALUES LESS THAN (-320000) ENGINE = InnoDB,
PARTITION p29 VALUES LESS THAN (-300000) ENGINE = InnoDB,
PARTITION p30 VALUES LESS THAN (-280000) ENGINE = InnoDB,
PARTITION p31 VALUES LESS THAN (-260000) ENGINE = InnoDB,
PARTITION p32 VALUES LESS THAN (-240000) ENGINE = InnoDB,
PARTITION p33 VALUES LESS THAN (-220000) ENGINE = InnoDB,
PARTITION p34 VALUES LESS THAN (-200000) ENGINE = InnoDB,
PARTITION p35 VALUES LESS THAN (-180000) ENGINE = InnoDB,
PARTITION p36 VALUES LESS THAN (-160000) ENGINE = InnoDB,
PARTITION p37 VALUES LESS THAN (-140000) ENGINE = InnoDB,
PARTITION p38 VALUES LESS THAN (-120000) ENGINE = InnoDB,
PARTITION p39 VALUES LESS THAN (-100000) ENGINE = InnoDB,
PARTITION p40 VALUES LESS THAN (-80000) ENGINE = InnoDB,
PARTITION p41 VALUES LESS THAN (-60000) ENGINE = InnoDB,
PARTITION p42 VALUES LESS THAN (-40000) ENGINE = InnoDB,
PARTITION p43 VALUES LESS THAN (-20000) ENGINE = InnoDB,
PARTITION p44 VALUES LESS THAN (0) ENGINE = InnoDB,
PARTITION p45 VALUES LESS THAN (20000) ENGINE = InnoDB,
PARTITION p46 VALUES LESS THAN (40000) ENGINE = InnoDB,
PARTITION p47 VALUES LESS THAN (60000) ENGINE = InnoDB,
PARTITION p48 VALUES LESS THAN (80000) ENGINE = InnoDB,
PARTITION p49 VALUES LESS THAN (100000) ENGINE = InnoDB,
PARTITION p50 VALUES LESS THAN (120000) ENGINE = InnoDB,
PARTITION p51 VALUES LESS THAN (140000) ENGINE = InnoDB,
PARTITION p52 VALUES LESS THAN (160000) ENGINE = InnoDB,
PARTITION p53 VALUES LESS THAN (180000) ENGINE = InnoDB,
PARTITION p54 VALUES LESS THAN (200000) ENGINE = InnoDB,
PARTITION p55 VALUES LESS THAN (220000) ENGINE = InnoDB,
PARTITION p56 VALUES LESS THAN (240000) ENGINE = InnoDB,
PARTITION p57 VALUES LESS THAN (260000) ENGINE = InnoDB,
PARTITION p58 VALUES LESS THAN (280000) ENGINE = InnoDB,
PARTITION p59 VALUES LESS THAN (300000) ENGINE = InnoDB,
PARTITION p60 VALUES LESS THAN (320000) ENGINE = InnoDB,
PARTITION p61 VALUES LESS THAN (340000) ENGINE = InnoDB,
PARTITION p62 VALUES LESS THAN (360000) ENGINE = InnoDB,
PARTITION p63 VALUES LESS THAN (380000) ENGINE = InnoDB,
PARTITION p64 VALUES LESS THAN (400000) ENGINE = InnoDB,
PARTITION p65 VALUES LESS THAN (420000) ENGINE = InnoDB,
PARTITION p66 VALUES LESS THAN (440000) ENGINE = InnoDB,
PARTITION p67 VALUES LESS THAN (460000) ENGINE = InnoDB,
PARTITION p68 VALUES LESS THAN (480000) ENGINE = InnoDB,
PARTITION p69 VALUES LESS THAN (500000) ENGINE = InnoDB,
PARTITION p70 VALUES LESS THAN (520000) ENGINE = InnoDB,
PARTITION p71 VALUES LESS THAN (540000) ENGINE = InnoDB,
PARTITION p72 VALUES LESS THAN (560000) ENGINE = InnoDB,
PARTITION p73 VALUES LESS THAN (580000) ENGINE = InnoDB,
PARTITION p74 VALUES LESS THAN (600000) ENGINE = InnoDB,
PARTITION p75 VALUES LESS THAN (620000) ENGINE = InnoDB,
PARTITION p76 VALUES LESS THAN (640000) ENGINE = InnoDB,
PARTITION p77 VALUES LESS THAN (660000) ENGINE = InnoDB,
PARTITION p78 VALUES LESS THAN (680000) ENGINE = InnoDB,
PARTITION p79 VALUES LESS THAN (700000) ENGINE = InnoDB,
PARTITION p80 VALUES LESS THAN (720000) ENGINE = InnoDB,
PARTITION p81 VALUES LESS THAN (740000) ENGINE = InnoDB,
PARTITION p82 VALUES LESS THAN (760000) ENGINE = InnoDB,
PARTITION p83 VALUES LESS THAN (780000) ENGINE = InnoDB,
PARTITION p84 VALUES LESS THAN (800000) ENGINE = InnoDB,
PARTITION p85 VALUES LESS THAN (820000) ENGINE = InnoDB,
PARTITION p86 VALUES LESS THAN (840000) ENGINE = InnoDB,
PARTITION p87 VALUES LESS THAN (860000) ENGINE = InnoDB,
PARTITION p88 VALUES LESS THAN (880000) ENGINE = InnoDB,
PARTITION p89 VALUES LESS THAN MAXVALUE ENGINE = InnoDB) */

身份证件
城市
邮政编码
纬度
经度
基于这篇文章和其他一些关于这个问题的阅读，我有一个存储过程，它给我一个点（纬度/经度）附近最近城镇的n个位置/邮政编码。
我的存储过程：

BEGIN
    DECLARE _deg2rad DOUBLE DEFAULT PI()/1800000;

    SET @my_lat := _my_lat,
        @my_lon := _my_lon,
        @deg2dist := 0.0111325,  
        @start_deg := _start_dist / @deg2dist,  
        @max_deg := _max_dist / @deg2dist,
        @cutoff := @max_deg / SQRT(2),  
        @dlat := @start_deg,  
        @lon2lat := COS(_deg2rad * @my_lat),
        @iterations := 0;        

    SET @sql = CONCAT(
        "SELECT COUNT(*) INTO @near_ct
            FROM geoData
            WHERE lat    BETWEEN @my_lat - @dlat
                             AND @my_lat + @dlat   
              AND lon    BETWEEN @my_lon - @dlon
                             AND @my_lon + @dlon");
    PREPARE _sql FROM @sql;
    MainLoop: LOOP
        SET @iterations := @iterations + 1;
        SET @dlon := ABS(@dlat / @lon2lat);  
        SET @dlon := IF(ABS(@my_lat) + @dlat >= 900000, 3600001, @dlon);  
        EXECUTE _sql;
        IF ( @near_ct >= _limit OR         
             @dlat >= @cutoff ) THEN       
            LEAVE MainLoop;
        END IF;
        SET @dlat := LEAST(2 * @dlat, @cutoff);   
    END LOOP MainLoop;
    DEALLOCATE PREPARE _sql;

    SET @dlat := IF( @dlat >= @max_deg OR @dlon >= 1800000,
                @max_deg,
                GCDist(ABS(@my_lat), @my_lon,
                       ABS(@my_lat) - @dlat, @my_lon - @dlon) );
    SET @dlon := IFNULL(ASIN(SIN(_deg2rad * @dlat) /
                             COS(_deg2rad * @my_lat))
                            / _deg2rad 
                        , 3600001);    

    IF (ABS(@my_lon) + @dlon < 1800000 OR    
        ABS(@my_lat) + @dlat <  900000) THEN 
        SET @sql = CONCAT(
            "SELECT *,
                    @deg2dist * GCDist(@my_lat, @my_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat   
                  AND lon BETWEEN @my_lon - @dlon
                              AND @my_lon + @dlon   
                HAVING dist <= ", _max_dist, "
                ORDER BY dist
                LIMIT ", _limit
                        );
    ELSE
        SET @west_lon := IF(@my_lon < 0, @my_lon, @my_lon - 3600000);
        SET @east_lon := @west_lon + 3600000;
        SET @sql = CONCAT(
            "( SELECT *,
                    @deg2dist * GCDist(@my_lat, @west_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat 
                  AND lon BETWEEN @west_lon - @dlon
                              AND @west_lon + @dlon   
                HAVING dist <= ", _max_dist, " )
            UNION ALL
            ( SELECT *,
                    @deg2dist * GCDist(@my_lat, @east_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat   
                  AND lon BETWEEN @east_lon - @dlon
                              AND @east_lon + @dlon   
                HAVING dist <= ", _max_dist, " )
            ORDER BY dist
            LIMIT ", _limit
                        );
    END IF;

    PREPARE _sql FROM @sql;
    EXECUTE _sql;
    DEALLOCATE PREPARE _sql;
END

我的问题是：
我想输入一个城市的邮政编码或名称，然后从那里开始搜索。所以我的想法是，我要求这些信息，并查找我的表中的所有城镇/邮政编码从世界各地。之后，如果只找到一个结果，我就有了lat/lon的信息，或者在有多个结果的情况下，我会要求用户选择正确的选项。
之后，我开始寻找离我现在位置最近的城镇。假设我想要一份50个城镇的名单。然后，我会去查一下，看看包含位置的表是否匹配其中的5个结果。
仔细想想，这听起来是个坏主意。。。
方法1：
我仔细阅读了存储过程、sql和monster查询，并尝试获得以下内容：
输入一个邮政编码/城市名称，我会查找它，从巨大的表中获取lat/lon（可能是mysql中的函数），然后根据它查找最近的城镇，然后在那里加入locations表，得到我的5个最近的位置。
问题：
如何避免同一城市/邮政编码的同一名称有多个匹配项？
为了得到5个最近的位置，用一个简单的连接听起来可能吗？
方法2：
获取我所在位置的所有纬度/经度值，然后在此表上运行该过程。就用那张大table来找回我现在的位置？
有了这些，我就需要收集我所在地的所有纬度/经度。但这也许是最好的办法。
不过，拥有庞大的城市/邮政编码数据库只是为了获取地理位置，似乎有点过头了。我希望有其他的选择，也许。。。不知怎的。。。
方法3
老实说，我想要的这个函数好像以前写过无数次。那我为什么要费心重新发明轮子呢？但我不知道如何找到合适的文章或书籍，以实现我的目标。
你们中有没有其他人对这种事情的最佳实践有什么想法？

sqlmysqlstored-proceduresinnodb

2条答案

按热度按时间
tpxzln5u

tpxzln5u1#

16k排其实没那么多。
我有一个 cities 3.1m行的表格（数据取自https://www.maxmind.com/de/free-world-cities-database). 我创造了一个“赝品” locations 具有16k个不同随机cityid和一些虚拟数据的表。我用一列 POINT 数据类型而不是 latitude 以及 longitude . 这是我从MySQL5.7.18上非常简单的查询中得到的：

select l.*, c.*, st_distance(point(-0.127758, 51.507351), c.geoPoint) dist
from locations l
join cities c using (cityId)
order by dist
limit 5

执行时间约为70ms。
可以通过子查询进行改进：

select l.*, c.*, x.dist
from (
    select l.locationId, st_distance(point(-0.127758, 51.507351), c.geoPoint) dist
    from locations l
    join cities c using (cityId)
    order by dist
    limit 5
) x
join locations l using(locationId)
join cities c using(cityId)

执行时间：~40ms
如果你储存 geoPoint （多余的）在 locations 表中，可以避免与 cities table。

select l.*, st_distance(point(-0.127758, 51.507351), l.geoPoint) dist
from locations l
order by dist
limit 5

执行时间：~17ms
你仍然可以加入 cities 在不损失性能的情况下将表添加到子查询。
请注意，所有这些查询都将计算所有16k行的距离并对它们进行排序。不过，这场表演对你来说已经足够了。
如果速度不够快或者 locations 表将随着时间的推移而增长，或者如果您想在大表中搜索，您仍然可以使用 SPATIAL INDEX 在 geoPoint 以及 MBRWithin() 或者 MBRContains() .
算法：
在用户位置周围定义一个小多边形。
增加循环中多边形的大小，直到它至少包含5个位置。
使用多边形中的位置选择5个最近的。
请注意，根据所使用的多边形类型，在找到一个具有5个位置的多边形后，可能需要再次增大其大小。例如，如果您使用一个正方形（简单的实现），您应该将大小增加一倍（将长度增加因子sqrt（2）），以绝对确保您不会错过正方形外的位置，该位置比正方形内的第五个位置更近。这是因为正方形不是圆。但是如果你用一个八角形，你可能会说-这已经够圆了-然后跳过最后一步。
这可能不是最好的算法。但它的实现非常简单，而且应该扩展得足够好。

赞(0）分享  回复(0）举报  2021-06-23
mefy6pfw

mefy6pfw2#

首先是一些评论。。。
我在这里和其他论坛上看到了几十个（不是几百万个）的实现；你的比大多数人都好。
根据一个数据来源（我碰巧下载的），世界上大约有320万个城市。
为了提高性能，您需要避免检查所有3m行。你已经有了一个良好的开端与不断增长的边界框。请注意，您应该

INDEX(lat, lon),
INDEX(lon, lat)

优化器将在这些查询和第一个查询之间进行选择（使用 COUNT(*) )会把它看作是“掩护”。它将是环绕地球的条纹或楔形物；超过3米的行距确实有所改善。最差的纬度（+34度）有9.6万个城市(1度=69英里/111公里）对于十分之一度，34.4度是最差的，有10公里的城市。
（是的，我喜欢这种数据拼图。）
而且，我看到你处理日期线和波兰人。我认为你不能把它们当作特例来改进。
（我只看了一眼公式和常数。）
geohash和z顺序索引帮助。但是它们有一个小问题，那就是你需要检查目标周围的4个区域——就像没有意识到199999和200000两个整数彼此非常接近一样，尽管它们的第一个数字是不同的。
“用户传入邮政编码或城市名称”--这是指向两个简单表之一的点查询(除了可能有DUP——圣何塞和圣安东尼奥各有320多个。排名靠后的是第一个非西班牙名字：“维多利亚”，只有144个城市。）
第二，我的实现(它和你的有些相似。）
http://mysql.rjweb.org/doc.php/latlng
这通过使用 PARTITIONing 使边界框大致保持为正方形，而不是条形或楔形。如果您要查找最接近的5行，我的算法将很少触及几十行以上的行，并且这些行将“聚集”在少量块中，从而将磁盘命中数保持在很低的水平。
在我的设计中，关键的一点是在一个表中包含所有必要的列。一旦你找到了最接近的5个，你就可以到其他table去拿一些辅助的东西（电话号码等）。
至于邮政编码，先将其转换为lat/lon，然后再开始搜索最近的5个。
算法内部的连接很可能会破坏性能。

赞(0）分享  回复(0）举报  2021-06-23
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com