常宁市住房和城乡建设局网站,电商入门基础知识,简约个人主页,wordpress 插件 加速问题描述
Proximity Service广泛应用于各种地图相关的服务中比如外卖#xff0c;大众点评#xff0c;Uber打车#xff0c;Google地图中#xff0c;其中比较关键的是我们根据用户的位置来快速找到附近的餐厅#xff0c;司机#xff0c;外卖员也就是就近查询算法。
主流的…问题描述
Proximity Service广泛应用于各种地图相关的服务中比如外卖大众点评Uber打车Google地图中其中比较关键的是我们根据用户的位置来快速找到附近的餐厅司机外卖员也就是就近查询算法。
主流的就近算法
基本的主流就近算法大致就是下图粉色高光的几种,根据实现方式分为两个部分Hash类以及Tree类基本思路都是将地图按照分割成足够小范围的小格来进行就近查询。 1. Even Grid等距分割
顾名思义就是将世界地图按照一个固定的密度分割成固定大小的格子每一个格子代表一小块经纬度范围[lat, long]我们给每一个格子定义一个ID, 这样再查找目标附近满足条件的餐厅时(下面算法讲解都以餐厅为例)我们找到目标所在格子相邻格子内满足条件的餐厅(不断扩大搜索范围直到找到所有满足条件)
优缺点
索引相对比较简单等距分割即可但是缺点就是数据库中范围搜索相对较慢很不高效。而且等距分割对于餐厅高度不平衡的位置 (市中心和农村)进行等距比较浪费资源。
2. Geohash
Geohash算法就可以解决上面even grid的局限性Geohash是将二维地理坐标压缩成base32一维字符作为ID来保存一个区域信息这个Geohash是通过01决策树编码生成根据经纬度范围进行决策编码。geohash长度越长精度越高通常来说geohash长度达到6位格子的范围就差不多在1km直径范围内基本满足精度要求。而且这种geohash编码的优点在于向邻近的区域前缀相同可以通过前缀查找的方式来进行 1001 10110 01001 10000 11011 11010 (base32 in binary) → 9q9hvu (base32) 算法流程
目标位置经纬度 - 进入决策树进行编码 - 根据一个搜索半径对满足条件的格子的相邻格子进行搜索 - 根据前缀搜索相邻的格子 -如果相邻各自餐厅数量不够则继续扩大范围查找直到数量达标为止
优缺点
优点可以处理区域数据不平衡密集的位置就细分更多的层数查找的速度也更快因为先定位到目标grid后根据ID前缀可以快速找到附近的相邻grid. (可以通过ElasticSearch, 也可以直接使用Redis GeoHash API进行查询)
缺点1. 边界问题两个相邻较近的节点可能不在一个同一个前缀中这时如果查询可能就需要对整个数据库进行遍历找到临近的位置。或者把这种corner case缓存起来在下一次查询时可以直接查询。2. Geohash如果hash做更新成本较高如果你的geohash grid需要根据区域内密度进行一定动态合并或者拆分那么geohash存储的话你需要对grid对应的所有数据进行逐一更新。 3. QuadTree 四叉树
四叉树的存储思路类似于二维的线段树每一个节点保存的就是二维区间范围并且在每一个节点中保存对应的餐厅信息。如果某个节点范围内密度超过阈值那么就继续细分这种数据结构存储大大增加了范围设置的灵活性。而且QuadTree本身对于存储大小需求不大根据下面估计这个QuadTree存储大小大约在5GB以内完全可以实现在单机内存中维护这个数据结构而无需使用数据库。并且范围搜索也比较快 O(LogN) 优缺点
优点1. 便于动态分割很好的解决区域密度不平衡问题。2.查询更新操作速度相对较快资源存储相对较小 3. 可以快速合并拆分Quad Tree结构并且范围查询时区间合并不会有GeoHash边界问题。
缺点1. 数据结构实现较为复杂。2. 如果建立在单机来实现快速响应对于分布式系统来说你需要去实现data backup, sharding/partition以及node crash之后数据恢复的问题。 图文引用
Bytebytego: https://bytebytego.com/courses/system-design-interview/proximity-service
