一口氣說出 4種 LBS “附近的人” 實作方式，面試官笑了

引言

昨天一位公衆号粉絲和我讨論了一道面試題，個人覺得比較有意義，這裡整理了一下分享給大家，願小夥伴們面試路上少踩坑。面試題目比較簡單：“讓你實作一個附近的人功能，你有什麼方案？”，這道題其實主要還是考察大家對于技術的廣度，本文介紹幾種方案，給大家一點思路，避免在面試過程中語塞而影響面試結果，如有不嚴謹之處，還望親人們溫柔指正！

“附近的人”

功能生活中是比較常用的，像外賣app附近的餐廳，共享單車app裡附近的車輛。既然常用面試被問的機率就很大，是以下邊依次來分析基于

mysql資料庫

、

Redis

MongoDB

實作的 “附近的人” 功能。

科普：世界上辨別一個位置，通用的做法就使用經、緯度。經度的範圍在 (-180, 180]，緯度的範圍在(-90, 90]，緯度正負以赤道為界，北正南負，經度正負以本初子午線 (英國格林尼治天文台) 為界，東正西負。比如：望京摩托羅拉大廈的經、緯度（116.49141，40.01229）全是正數，就是因為我國位于東北半球。

一、“附近的人”原理

“附近的人”

也就是常說的

LBS

(Location Based Services，基于位置服務)，它圍繞使用者目前地理位置資料而展開的服務，為使用者提供精準的增值服務。

“附近的人” 核心思想如下：

以 “我” 為中心，搜尋附近的使用者
以 “我” 目前的地理位置為準，計算出别人和 “我” 之間的距離
按 “我” 與别人距離的遠近排序，篩選出離我最近的使用者或者商店等

一口氣說出 4種 LBS “附近的人” 實作方式，面試官笑了

二、什麼是GeoHash算法？

在說

“附近的人”

功能的具體實作之前，先來認識一下

GeoHash

算法，因為後邊會一直和它打交道。定位一個位置最好的辦法就是用

經、緯度

辨別，但

經、緯度

它是二維的，在進行位置計算的時候還是很麻煩，如果能通過某種方法将二維的

經、緯度

資料轉換成一維的資料，那麼比較起來就要容易的多，是以

GeoHash

算法應運而生。

GeoHash

算法将二維的經、緯度轉換成一個字元串，例如：下圖中9個

GeoHash

字元串代表了9個區域，每一個字元串代表了一矩形區域。而這個矩形區域内其他的點（經、緯度）都用同一個

GeoHash

字元串表示。

比如：

WX4ER

區域内的使用者搜尋附近的餐廳資料，由于這區域内使用者的

GeoHash

字元串都是

WX4ER

，故可以把

WX4ER

當作

key

，餐廳資訊作為

value

進行緩存；而如果不使用

GeoHash

算法，區域内的使用者請求餐廳資料，使用者傳來的經、緯度都是不同的，這樣緩存不僅麻煩且資料量巨大。

GeoHash

字元串越長，表示的位置越精确，字元串長度越長代表在距離上的誤差越小。下圖

geohash

碼精度表：

geohash碼長度 | 寬度 | 高度

-------- | ----- | ----- |

1 | 5,009.4km | 4,992.6km

2 |1,252.3km |624.1km

3 |156.5km |156km

4 |39.1km |19.5km

5 |4.9km |4.9km

6 |1.2km |609.4m

7 |152.9m |152.4m

8 |38.2m| 19m

9 |4.8m |4.8m

10 |1.2m |59.5cm

11 |14.9cm |14.9cm

12 |3.7cm |1.9cm

而且字元串越相似表示距離越相近，字元串字首比對越多的距離越近。比如：下邊的經、緯度就代表了三家距離相近的餐廳。

商戶 | 經緯度 | Geohash字元串

串串香 | 116.402843,39.999375 | wx4er9v

火鍋| 116.3967,39.99932 | wx4ertk

烤肉 | 116.40382,39.918118 | wx4erfe

讓大家簡單了解什麼是

GeoHash

算法，友善後邊内容展開，

GeoHash

算法内容比較高深，感興趣的小夥伴自行深耕一下，這裡不占用過多篇幅（其實是我懂得太膚淺，哭唧唧~）。

三、基于Mysql

此種方式是純基于

mysql

實作的，未使用

GeoHash

算法。

1、設計思路

以使用者為中心，假設給定一個500米的距離作為半徑畫一個圓，這個圓型區域内的所有使用者就是符合使用者要求的 “附近的人”。但有一個問題是圓形有弧度啊，直接搜尋圓形區域難度太大，根本無法用經、緯度直接搜尋。

但如果在圓形外套上一個正方形，通過擷取使用者經、緯度的最大最小值（經、緯度 + 距離），再根據最大最小值作為篩選條件，就很容易将正方形内的使用者資訊搜尋出來。

那麼問題又來了，多出來一些面積腫麼辦？

我們來分析一下，多出來的這部分區域内的使用者，到圓點的距離一定比圓的半徑要大，那麼我們就計算使用者中心點與正方形内所有使用者的距離，篩選出所有距離小于等于半徑的使用者，圓形區域内的所使用者即符合要求的

“附近的人”

。

2、利弊分析

純基于

mysql

實作

“附近的人”

，優點顯而易見就是簡單，隻要建一張表存下使用者的經、緯度資訊即可。缺點也很明顯，需要大量的計算兩個點之間的距離，非常影響性能。

3、實作

建立一個簡單的表用來存放使用者的經、緯度屬性。

CREATE TABLE `nearby_user` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL COMMENT '名稱',
  `longitude` double DEFAULT NULL COMMENT '經度',
  `latitude` double DEFAULT NULL COMMENT '緯度',
  `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '建立時間',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

計算兩個點之間的距離，用了一個三方的類庫，畢竟自己造的輪子不是特别圓，還有可能是方的，啊哈哈哈~

<dependency>
     <groupId>com.spatial4j</groupId>
     <artifactId>spatial4j</artifactId>
     <version>0.5</version>
</dependency>

擷取到外接正方形後，以正方形的最大最小經、緯度值搜尋正方形區域内的使用者，再剔除超過指定距離的使用者，就是最終的

附近的人

private SpatialContext spatialContext = SpatialContext.GEO;    
    
    /**
     * 擷取附近 x 米的人
     *
     * @param distance 搜尋距離範圍 機關km
     * @param userLng  目前使用者的經度
     * @param userLat  目前使用者的緯度
     */
    @GetMapping("/nearby")
    public String nearBySearch(@RequestParam("distance") double distance,
                               @RequestParam("userLng") double userLng,
                               @RequestParam("userLat") double userLat) {
        //1.擷取外接正方形
        Rectangle rectangle = getRectangle(distance, userLng, userLat);
        //2.擷取位置在正方形内的所有使用者
        List<User> users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY());
        //3.剔除半徑超過指定距離的多餘使用者
        users = users.stream()
            .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) <= distance)
            .collect(Collectors.toList());
        return JSON.toJSONString(users);
    }
    
    private Rectangle getRectangle(double distance, double userLng, double userLat) {
        return spatialContext.getDistCalc()
            .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat), 
                                 distance * DistanceUtils.KM_TO_DEG, spatialContext, null);
    }

由于使用者間距離的排序是在業務代碼中實作的，可以看到SQL語句也非常的簡單。

<select id="selectUser" resultMap="BaseResultMap">
        SELECT * FROM user
        WHERE 1=1
        and (longitude BETWEEN ${minlng} AND ${maxlng})
        and (latitude BETWEEN ${minlat} AND ${maxlat})
    </select>

四、Mysql + GeoHash

這種方式的設計思路更簡單，在存使用者位置資訊時，根據使用者經、緯度屬性計算出相應的

geohash

字元串。注意：在計算

geohash

字元串時，需要指定

geohash

字元串的精度，也就是

geohash

字元串的長度，參考上邊的

geohash

精度表。

當需要擷取

附近的人

，隻需用目前使用者

geohash

字元串，資料庫通過

WHERE geohash Like 'geocode%

' 來查詢

geohash

字元串相似的使用者，然後計算目前使用者與搜尋出的使用者距離，篩選出所有距離小于等于指定距離（附近500米）的，即

附近的人

利用

 GeoHash

算法實作

“附近的人”

有一個問題，由于

geohash

算法将地圖分為一個個矩形，對每個矩形進行編碼，得到

geohash

字元串。可我目前的點與鄰近的點很近，但恰好我們分别在兩個區域，明明就在眼前的點偏偏搜不到，實實在在的燈下黑。

如何解決這一問題？

為了避免類似鄰近兩點在不同區域内，我們就需要同時擷取目前點（

WX4G0

）所在區域附近

8個

區域的

geohash

碼，一并進行篩選比較。

同樣要設計一張表存使用者的經、緯度資訊，但差別是要多一個

geo_code

字段，存放geohash字元串，此字段通過使用者經、緯度屬性計算出。使用頻繁的字段建議加上索引。

CREATE TABLE `nearby_user_geohash` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL COMMENT '名稱',
  `longitude` double DEFAULT NULL COMMENT '經度',
  `latitude` double DEFAULT NULL COMMENT '緯度',
  `geo_code` varchar(64) DEFAULT NULL COMMENT '經緯度所計算的geohash碼',
  `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '建立時間',
  PRIMARY KEY (`id`),
  KEY `index_geo_hash` (`geo_code`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

首先根據使用者經、緯度資訊，在指定精度後計算使用者坐标的

geoHash

碼，再擷取到使用者周邊8個方位的

geoHash

碼在資料庫中搜尋使用者，最後過濾掉超出給定距離（500米内）的使用者。

private SpatialContext spatialContext = SpatialContext.GEO;

    /***
     * 添加使用者
     * @return
     */
    @PostMapping("/addUser")
    public boolean add(@RequestBody UserGeohash user) {
        //預設精度12位
        String geoHashCode = GeohashUtils.encodeLatLon(user.getLatitude(),user.getLongitude());
        return userGeohashService.save(user.setGeoCode(geoHashCode).setCreateTime(LocalDateTime.now()));
    }


/**
     * 擷取附近指定範圍的人
     *
     * @param distance 距離範圍（附近多遠的使用者） 機關km
     * @param len      geoHash的精度（幾位的字元串）
     * @param userLng  目前使用者的經度
     * @param userLat  目前使用者的緯度
     * @return json
     */
    @GetMapping("/nearby")
    public String nearBySearch(@RequestParam("distance") double distance,
                               @RequestParam("len") int len,
                               @RequestParam("userLng") double userLng,
                               @RequestParam("userLat") double userLat) {


        //1.根據要求的範圍，确定geoHash碼的精度，擷取到目前使用者坐标的geoHash碼
        GeoHash geoHash = GeoHash.withCharacterPrecision(userLat, userLng, len);
        //2.擷取到使用者周邊8個方位的geoHash碼
        GeoHash[] adjacent = geoHash.getAdjacent();

        QueryWrapper<UserGeohash> queryWrapper = new QueryWrapper<UserGeohash>()
            .likeRight("geo_code",geoHash.toBase32());
        Stream.of(adjacent).forEach(a -> queryWrapper.or().likeRight("geo_code",a.toBase32()));

        //3.比對指定精度的geoHash碼
        List<UserGeohash> users = userGeohashService.list(queryWrapper);
        //4.過濾超出距離的
        users = users.stream()
                .filter(a ->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat)<= distance)
                .collect(Collectors.toList());
        return JSON.toJSONString(users);
    }

    
    /***
     * 球面中，兩點間的距離
     * @param longitude 經度1
     * @param latitude  緯度1
     * @param userLng   經度2
     * @param userLat   緯度2
     * @return 傳回距離，機關km
     */
    private double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
        return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
                spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
    }

五、Redis + GeoHash

Redis 3.2

版本以後，基于

geohash

和資料結構

Zset

提供了地理位置相關功能。通過上邊兩種

mysql

的實作方式發現，

附近的人

功能是明顯的讀多寫少場景，是以用

redis

性能更會有很大的提升。

redis

附近的人

功能主要通過

Geo

子產品的六個指令。

GEOADD ：将給定的位置對象（緯度、經度、名字）添加到指定的key;
GEOPOS ：從key裡面傳回所有給定位置對象的位置（經度和緯度）;
GEODIST ：傳回兩個給定位置之間的距離;
GEOHASH ：傳回一個或多個位置對象的Geohash表示;
GEORADIUS ：以給定的經緯度為中心，傳回目标集合中與中心的距離不超過給定最大距離的所有位置對象;
GEORADIUSBYMEMBER ：以給定的位置對象為中心，傳回與其距離不超過給定最大距離的所有位置對象。

以

GEOADD

指令和

GEORADIUS

指令簡單舉例：

GEOADD key longitude latitude member [longitude latitude member ...]

其中，

key

為集合名稱，

member

為該經緯度所對應的對象。

GEOADD

添加多個商戶“火鍋店”位置資訊：

GEOADD hotel 119.98866180732716    30.27465803229662 火鍋店

GEORADIUS

根據給定的經緯度為中心，擷取目标集合中與中心的距離不超過給定最大距離（500米内）的所有位置對象，也就是

“附近的人”

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key]

範圍機關：

km

ft

mi

--> 米 | 千米 | 英尺 | 英裡。

WITHDIST ：在傳回位置對象的同時，将位置對象與中心之間的距離也一并傳回。距離的機關和使用者給定的範圍機關保持一緻。
WITHCOORD ：将位置對象的經度和次元也一并傳回。
WITHHASH ：以 52 位有符号整數的形式，傳回位置對象經過原始 geohash 編碼的有序集合分值。這個選項主要用于底層應用或者調試，實際中的作用并不大。
ASC | DESC ：從近到遠傳回位置對象元素 | 從遠到近傳回位置對象元素。
COUNT count ：選取前N個比對位置對象元素。（不設定則傳回所有元素）
STORE key ：将傳回結果的地理位置資訊儲存到指定key。
STORedisT key ：将傳回結果離中心點的距離儲存到指定key。

例如下邊指令：擷取目前位置周邊500米内的所有飯店。

GEORADIUS hotel 119.98866180732716    30.27465803229662 500 m WITHCOORD

Redis

内部使用有序集合(

zset

)儲存使用者的位置資訊，

zset

中每個元素都是一個帶位置的對象，元素的

score

值為通過經、緯度計算出的52位

geohash

值。

redis

附近的人

效率比較高，內建也比較簡單，而且還支援對距離排序。不過，結果存在一定的誤差，要想讓結果更加精确，還需要手動将使用者中心位置與其他使用者位置計算距離後，再一次進行篩選。

以下就是

Java

redis

實作版本，代碼非常的簡潔。

@Autowired
    private RedisTemplate<String, Object> redisTemplate;
    
    //GEO相關指令用到的KEY
    private final static String KEY = "user_info";

    public boolean save(User user) {
        Long flag = redisTemplate.opsForGeo().add(KEY, new RedisGeoCommands.GeoLocation<>(
                user.getName(), 
                new Point(user.getLongitude(), user.getLatitude()))
        );
        return flag != null && flag > 0;
    }

    /**
     * 根據目前位置擷取附近指定範圍内的使用者
     * @param distance 指定範圍 機關km ，可根據{@link org.springframework.data.geo.Metrics} 進行設定
     * @param userLng 使用者經度
     * @param userLat 使用者緯度
     * @return
     */
    public String nearBySearch(double distance, double userLng, double userLat) {
        List<User> users = new ArrayList<>();
        // 1.GEORADIUS擷取附近範圍内的資訊
        GeoResults<RedisGeoCommands.GeoLocation<Object>> reslut = 
            redisTemplate.opsForGeo().radius(KEY, 
                        new Circle(new Point(userLng, userLat), new Distance(distance, Metrics.KILOMETERS)),
                        RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs()
                                .includeDistance()
                                .includeCoordinates().sortAscending());
        //2.收集資訊，存入list
        List<GeoResult<RedisGeoCommands.GeoLocation<Object>>> content = reslut.getContent();
        //3.過濾掉超過距離的資料
        content.forEach(a-> users.add(
                new User().setDistance(a.getDistance().getValue())
                .setLatitude(a.getContent().getPoint().getX())
                .setLongitude(a.getContent().getPoint().getY())));
        return JSON.toJSONString(users);
    }

六、MongoDB + 2d索引

MongoDB

實作附近的人，主要是通過它的兩種地理空間索引

2dsphere

和

2d

。兩種索引的底層依然是基于

Geohash

來進行建構的。但與國際通用的

Geohash

還有一些不同，具體參考

官方文檔

2dsphere

索引僅支援球形表面的幾何形狀查詢。

2d

索引支援平面幾何形狀和一些球形查詢。雖然

2d

索引支援某些球形查詢，但

2d

索引對這些球形查詢時，可能會出錯。是以球形查詢盡量選擇

2dsphere

索引。

盡管兩種索引的方式不同，但隻要坐标跨度不太大，這兩個索引計算出的距離相差幾乎可以忽略不計。

2、實作

首先插入一批位置資料到

MongoDB

，

collection

為起名

hotel

，相當于

MySQL

的表名。兩個字段

name

名稱，

location

為經、緯度資料對。

db.hotel.insertMany([
 {'name':'hotel1',  location:[115.993121,28.676436]},
 {'name':'hotel2',  location:[116.000093,28.679402]},
 {'name':'hotel3',  location:[115.999967,28.679743]},
 {'name':'hotel4',  location:[115.995593,28.681632]},
 {'name':'hotel5',  location:[115.975543,28.679509]},
 {'name':'hotel6',  location:[115.968428,28.669368]},
 {'name':'hotel7',  location:[116.035262,28.677037]},
 {'name':'hotel8',  location:[116.024770,28.68667]},
 {'name':'hotel9',  location:[116.002384,28.683865]},
 {'name':'hotel10', location:[116.000821,28.68129]},
])

接下來我們給

location

字段建立一個

2d

索引，索引的精度通過

bits

來指定，

bits

越大，索引的精度就越高。

db.coll.createIndex({'location':"2d"}, {"bits":11111})

用

geoNear

指令測試一下，

near

目前坐标（經、緯度），

spherical

是否計算球面距離，

distanceMultiplier

地球半徑，機關是米，預設6378137，

maxDistance

過濾條件（指定距離内的使用者），開啟弧度需除

distanceMultiplier

distanceField

計算出的兩點間距離，字段别名（随意取名）。

db.hotel.aggregate({
    $geoNear:{
        near: [115.999567,28.681813], // 目前坐标
        spherical: true, // 計算球面距離
        distanceMultiplier: 6378137, // 地球半徑,機關是米,那麼的除的記錄也是米
        maxDistance: 2000/6378137, // 過濾條件2000米内，需要弧度
        distanceField: "distance" // 距離字段别名
    }
})

看到結果中有符合條件的資料，還多出一個字段

distance

剛才設定的别名，代表兩點間的距離。

{ "_id" : ObjectId("5e96a5c91b8d4ce765381e58"), "name" : "hotel10", "location" : [ 116.000821, 28.68129 ], "distance" : 135.60095397487655 }
{ "_id" : ObjectId("5e96a5c91b8d4ce765381e51"), "name" : "hotel3", "location" : [ 115.999967, 28.679743 ], "distance" : 233.71915803517447 }
{ "_id" : ObjectId("5e96a5c91b8d4ce765381e50"), "name" : "hotel2", "location" : [ 116.000093, 28.679402 ], "distance" : 273.26317035334176 }
{ "_id" : ObjectId("5e96a5c91b8d4ce765381e57"), "name" : "hotel9", "location" : [ 116.002384, 28.683865 ], "distance" : 357.5791936927476 }
{ "_id" : ObjectId("5e96a5c91b8d4ce765381e52"), "name" : "hotel4", "location" : [ 115.995593, 28.681632 ], "distance" : 388.62555058249967 }
{ "_id" : ObjectId("5e96a5c91b8d4ce765381e4f"), "name" : "hotel1", "location" : [ 115.993121, 28.676436 ], "distance" : 868.6740526419927 }

總結

本文重點并不是在具體實作，旨在給大家提供一些設計思路，面試中可能你對某一項技術了解的并不深入，但如果你的知識面寬，可以從多方面說出多種設計的思路，能夠侃侃而談，那麼會給面試官極大的好感度，拿到offer的機率就會高很多。而且

“附近的人”

功能使用的場景比較多，尤其是像電商平台應用更為廣泛，是以想要進大廠的同學，這類的知識點還是應該有所了解的。

代碼實作借鑒了一位大佬的開源項目，這裡有前三種實作方式的demo，感興趣的小夥伴可以學習一下，GitHub位址：

https://github.com/larscheng/larscheng-learning-demo/tree/master/NearbySearch

，。

最近身邊很多小夥伴都在面試，我整了一些Java方面的架構、面試資料，還有一些付費課程，噓~，免費送給小夥伴們。需要的小夥伴可以關注我的公号，無套路自行領取

一口氣說出 4種 LBS “附近的人” 實作方式，面試官笑了

引言

一、“附近的人”原理

二、什麼是GeoHash算法？

三、基于Mysql

1、設計思路

2、利弊分析

3、實作

四、Mysql + GeoHash

五、Redis + GeoHash

六、MongoDB + 2d索引

2、實作

總結

繼續閱讀

艱難安裝LDAP,SSL認證

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

MySQL的4種隔離級别？出現問題

資料結構與算法（27）——排序（二）

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

mysql使用source指令導入.sql檔案

登入plsql 報錯 the account is locked --使用者被鎖

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希