共计 565 个字符，预计需要花费 2 分钟才能阅读完成。
如何在公众点评上找到左近的餐馆？
上周咱们说了应用 GeoHash 的算法宰割地图来存储餐馆的地位，然而这种算法有调配不平衡的问题，在餐馆稠密的中央节约存储资源。这次咱们来摸索另一种数据结构四叉树 (QuadTree)。
四叉树通常用于将二维空间递归细分为四个象限的网格，直到网格内容满足特定条件为止 (见第一张图)。
四叉树是一个内存数据结构，不是数据库解决方案。它在定位服务的实例中运行，整个数据结构在定位服务启动时建设。
第二张图更具体地解释了四叉树的构建过程。根节点代表整个世界地图，被递归地细分为四个象限，直到网格内没有超过 100 个业务的节点为止。
地图构建好了当前如何搜寻餐馆呢？
- 第一步：在内存中构建四叉树。
- 第二步：建设四叉树后，从树根开始搜寻并遍历整个树，直到找到搜寻原点所在的叶节点。
- 第三步：如果该叶节点有 100 个餐馆，则返回该节点。否则，从其邻近节点增加餐馆，直到返回足够多的餐馆。
定位服务启动时如何重建四叉树？
- 第一步：服务器启动时，在内存中建设一个蕴含 2 亿个餐馆的四叉树可能须要几分钟工夫。
- 第二步：在构建四叉树的过程中，服务器无奈响应客户端申请。
- 第三步：因而，咱们须要逐渐分批来公布定位服务的新版本，这样能够防止服务器集群的大部分服务器离线，造成服务中断。
如果你对细节感兴趣，欢送留言通知我。
【关注公众号：ByteByteGo】
正文完