关于附近的XXX
1
近来的一个需求——附近的XXX。
google一下，
最方便的解决方案是MongoDB的geoNear命令。
无奈我司的DBA属于老成持重型的，所以只能使用MySQL……
怎么办呢？
2
假设表：
+-------------+------------+------+-----+---------+-------+
| Field | Type | Null | Key | Default | Extra |
+-------------+------------+------+-----+---------+-------+
| xxx_id | bigint(20) | NO | PRI | NULL | |
| lat | double | NO | | NULL | |
| lon | double | NO | | NULL | |
+-------------+------------+------+-----+---------+-------+
想找某半径范围内，按照距离远近排序的xxx_id列表，如何写SQL语句呢?
其实我也不会写…… （笑）
不过找到了一个相关的PPT Geo (proximity) Search with MySQL
其中给出了SQL语句：
set @orig_lat=121.9763; set @orig_lon=37.40445;
set @dist=10;
SELECT *, 3956 * 2 * ASIN(SQRT(
POWER(SIN((@orig_lat - abs(dest.lat)) * pi()/180 / 2),
2) + COS(@orig_lat * pi()/180 ) * COS(abs(dest.lat) *
pi()/180) * POWER(SIN((@orig_lon - dest.lon) *
pi()/180 / 2), 2) )) as distance
FROM hotels dest
having distance < @dist
ORDER BY distance limit 10\G
这么复杂…… 数据量大的话肯定性能低下。
其中给出了一个解决方案，就是通过计算距离缩小探索空间：
1° of latitude ~= 69 miles
1° of longitude ~= cos(latitude)*69
To calculate lon and lat for the rectangle:
当然这个PPT是某个DBA写的……
我们通常不会把这么多计算的逻辑放在mysql上。
3
沿着上述缩小探索范围的思路，就很容易想到一个叫做Geohash的算法。
该算法简而言之就是将地图一半一半地切分成一个个小区域，每个小区域计算出一个一维的编码。
Github上有个很不错的项目——geohash-java——可以直接拿来用。
计算Geohash的核心算法如下：
private GeoHash(double latitude, double longitude, int desiredPrecision) {
point = new WGS84Point(latitude, longitude);
desiredPrecision = Math.min(desiredPrecision, 64);
boolean isEvenBit = true;
double[] latitudeRange = { -90, 90 };
double[] longitudeRange = { -180, 180 };
while (significantBits < desiredPrecision) {
if (isEvenBit) {
divideRangeEncode(longitude, longitudeRange);
} else {
divideRangeEncode(latitude, latitudeRange);
}
isEvenBit = !isEvenBit;
}
setBoundingBox(this, latitudeRange, longitudeRange);
bits <<= (64 - desiredPrecision);
}
private void divideRangeEncode(double value, double[] range) {
double mid = (range[0] + range[1]) / 2;
if (value >= mid) {
addOnBitToEnd();
range[0] = mid;
} else {
addOffBitToEnd();
range[1] = mid;
}
}
所以就在表中多个一个字段：
+-------------+------------+------+-----+---------+-------+
| geo_hash_32 | bigint(20) | NO | MUL | NULL | |
+-------------+------------+------+-----+---------+-------+
32表示geohash的bit长度，也就是维度之间大约300米的范围。
另外这还有个好处，如果数据量上来了还可以通过geo_hash_32字段散表。
4
最后串一下整个流程：
某用户在A点，半径m米，
首先计算出覆盖这个半径的geo_hash_32列表，
然后从数据库中查询出数据，
最后计算距离、排序
5
记得之前看过一篇介绍uber架构的文章——Uber Unveils its Realtime Market Platform，
其中提到了一个称为s2-geometry-library的类库。
The S2 Geometry Library is a spherical geometry library, very useful for manipulating regions on the sphere (commonly on Earth) and indexing geographic data.
具体细节、暂且留坑。