如何有效地find一个给定位置附近最近的位置
我正在做一个脚本，一个负载的业务加载到一个经度和纬度的MySQL数据库。 然后，我提供该脚本的经度（最终用户的经度），脚本必须计算从提供的经纬度到从数据库获得的每个条目的距离，并按照距离最近的顺序对它们进行sorting。
我只实际需要大约10或20个“最接近”的结果，但我不能想到，除了从数据库中获取所有结果并在每个结果上运行函数，然后进行数组sorting之外，无法做到这一点。
这是我已经：
<?php function getDistance($point1, $point2){ $radius = 3958; // Earth's radius (miles) $pi = 3.1415926; $deg_per_rad = 57.29578; // Number of degrees/radian (for conversion) $distance = ($radius * $pi * sqrt( ($point1['lat'] - $point2['lat']) * ($point1['lat'] - $point2['lat']) + cos($point1['lat'] / $deg_per_rad) // Convert these to * cos($point2['lat'] / $deg_per_rad) // radians for cos() * ($point1['long'] - $point2['long']) * ($point1['long'] - $point2['long']) ) / 180); $distance = round($distance,1); return $distance; // Returned using the units used for $radius. } include("../includes/application_top.php"); $lat = (is_numeric($_GET['lat'])) ? $_GET['lat'] : 0; $long = (is_numeric($_GET['long'])) ? $_GET['long'] : 0; $startPoint = array("lat"=>$lat,"long"=>$long); $sql = "SELECT * FROM mellow_listings WHERE active=1"; $result = mysql_query($sql); while($row = mysql_fetch_array($result)){ $thedistance = getDistance($startPoint,array("lat"=>$row['lat'],"long"=>$row['long'])); $data[] = array('id' => $row['id'], 'name' => $row['name'], 'description' => $row['description'], 'lat' => $row['lat'], 'long' => $row['long'], 'address1' => $row['address1'], 'address2' => $row['address2'], 'county' => $row['county'], 'postcode' => strtoupper($row['postcode']), 'phone' => $row['phone'], 'email' => $row['email'], 'web' => $row['web'], 'distance' => $thedistance); } // integrate google local search $url = "http://ajax.googleapis.com/ajax/services/search/local?"; $url .= "q=Off+licence"; // query $url .= "&v=1.0"; // version number $url .= "&rsz=8"; // number of results $url .= "&key=ABQIAAAAtG" ."Pcon1WB3b0oiqER" ."FZ-TRQgsWYVg721Z" ."IDPMPlc4-CwM9Xt" ."FBSTZxHDVqCffQ2" ."W6Lr4bm1_zXeYoQ"; // api key $url .= "&sll=".$lat.",".$long; // sendRequest // note how referer is set manually $ch = curl_init(); curl_setopt($ch, CURLOPT_URL, $url); curl_setopt($ch, CURLOPT_RETURNTRANSFER, 1); curl_setopt($ch, CURLOPT_REFERER, /* url */); $body = curl_exec($ch); curl_close($ch); // now, process the JSON string $json = json_decode($body, true); foreach($json['responseData']['results'] as $array){ $thedistance = getDistance($startPoint,array("lat"=>$array['lat'],"long"=>$array['lng'])); $data[] = array('id' => '999', 'name' => $array['title'], 'description' => '', 'lat' => $array['lat'], 'long' => $array['lng'], 'address1' => $array['streetAddress'], 'address2' => $array['city'], 'county' => $array['region'], 'postcode' => '', 'phone' => $array['phoneNumbers'][0], 'email' => '', 'web' => $array['url'], 'distance' => $thedistance); } // sort the array foreach ($data as $key => $row) { $id[$key] = $row['id']; $distance[$key] = $row['distance']; } array_multisort($distance, SORT_ASC, $data); header("Content-type: text/xml"); echo '<?xml version="1.0" encoding="UTF-8"?>'."\n"; echo '<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">'."\n"; echo '<plist version="1.0">'."\n"; echo '<array>'."\n"; for($i = 0; isset($distance[$i]); $i++){ //echo $data[$i]['id']." -> ".$distance[$i]."<br />"; echo '<dict>'."\n"; foreach($data[$i] as $key => $val){ echo '<key><![CDATA['.$key.']]></key>'."\n"; echo '<string><![CDATA['.htmlspecialchars_decode($val, ENT_QUOTES).']]></string>'."\n"; } echo '</dict>'."\n"; } echo '</array>'."\n"; echo '</plist>'."\n"; ?> 现在，这个数据库中只有2到3家企业运行得非常快，但是我现在正在将5k个企业加载到数据库中，我担心这个数据库运行速度会非常慢。 你怎么看？
它不是我可以caching的那种数据，因为两个用户具有相同经纬度的可能性很可能非常小，因此不会有帮助。
我能做些什么呢？
感谢您的任何帮助和任何build议。 他们都非常感激。
选项1：通过切换到支持GeoIP的数据库来对数据库进行计算。
选项2：对数据库进行计算：您正在使用MySQL，因此以下存储过程应该有所帮助
CREATE FUNCTION distance (latA double, lonA double, latB double, LonB double) RETURNS double DETERMINISTIC BEGIN SET @RlatA = radians(latA); SET @RlonA = radians(lonA); SET @RlatB = radians(latB); SET @RlonB = radians(LonB); SET @deltaLat = @RlatA - @RlatB; SET @deltaLon = @RlonA - @RlonB; SET @d = SIN(@deltaLat/2) * SIN(@deltaLat/2) + COS(@RlatA) * COS(@RlatB) * SIN(@deltaLon/2)*SIN(@deltaLon/2); RETURN 2 * ASIN(SQRT(@d)) * 6371.01; END//
编辑
如果您的数据库中有经度和纬度的索引，则可以通过在PHP中创build初始边界框（$ minLat，$ maxLat，$ minLong和$ maxLong）来减less需要计算的计算次数，并限制（WHERE latitude BETWEEN $ minLat AND $ maxLat和经度BETWEEN $ minLong AND $ maxLong）的行的子集。 那么MySQL只需要执行该行子集的距离计算。
进一步的编辑 （作为对之前编辑的解释）
如果您只是使用Jonathon提供的SQL语句（或存储过程来计算距离），那么SQL仍然需要查看数据库中的每条logging，并在数据库中的每条logging计算距离是否返回该行或丢弃它。
因为执行计算相对较慢，所以如果您可以减less需要计算的行集，那么排除明显超出所需距离的行将会更好，因此我们只执行昂贵的计算更less的行数。
如果你认为你所做的事情基本上是在地图上画一个圆圈，以你的初始点为中心，并以距离为半径， 那么该公式只是确定哪些行落在该圆圈内……但仍需要检查每一行。
使用边界框就像先在地图上画一个正方形，左边，右边，顶部和底部边距离我们中心点的适当距离。 然后，我们的圈子将在该框内被绘制，圆圈上的最北端，最东端，最南端和最西端点接触框的边界。 一些行将落在该框之外，所以SQL甚至不打算计算这些行的距离。 它只计算落在边界框内的那些行的距离，以查看它们是否落在圆内。
在PHP中，我们可以使用一个非常简单的计算，根据我们的距离计算最小和最大经度和纬度，然后将这些值设置在SQL语句的WHERE子句中。 这实际上是我们的盒子，任何超出这个范围的东西都会被自动丢弃，而不需要真正计算它的距离。
Movable Type网站对此有一个很好的解释（使用PHP代码），对于任何计划在PHP中执行任何GeoPositioning工作的人来说，这应该是必不可less的。
我认为你在SQL中使用Haversine公式可以做得更好。 Google有一个关于如何在MySQL数据库中find最近的位置的教程，但总体思路是这个SQL：
SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;
然后，您需要做的所有工作都是在数据库上完成的，因此，您甚至在检查距离之前，不必将所有业务都放到PHP脚本中。
如果您有很多点，那么使用距离公式的查询会非常慢，因为它没有使用索引进行search。 为了提高效率，您必须使用矩形边界框来加快速度，或者您可以使用内置GISfunction的数据库。PostGIS是免费的，这里有一篇关于做最近邻search的文章：
http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor_generic
这个工作有更简单的方法。
-
我们知道在相同经度的纬度上的0.1的差值等于11.12公里的距离。 （1.0拉特将使距离111.2公里）
-
经纬度为0.1度，纬度为3.51公里（lon为1.0，距离为85.18公里），转换成英里，乘以1.60934。
注意。 请注意，经度从-180到180，所以-180到179.9之间的差值是0.1，这是3.51公里。
我们现在需要知道的是所有带有lon和lat的邮编列表（你已经有了）
所以现在要把你的search范围缩小90％，例如，你只需要删除所有绝对不会在100公里以内的结果。 我们的坐标$ lat1和$ lon2对于100千米相差2的经纬度和纬度将是绰绰有余的。
$lon=...; $lat=...; $dif=2; SELECT zipcode from zipcode_table WHERE latitude>($lan-$dif) AND latitude<($lan+$dif) AND longitude>($lon-$dif) AND longitude<($lon+$dif)
就是这样 当然，如果您需要覆盖更小或更大的区域，您将需要相应地更改$ dif。
这样Mysql只会考虑非常有限的储蓄资源。
