问题是这样的，有一个故事。

您有一个包含搜索字段的应用程序。当您搜索某些输入时，会弹出一个自动完成组件，显示与您的输入相似的结果。

每个结果都是数据库中的一个位置，这是以下结构location：

id | name                    | lat  | lon
-----------------------------------------
0  | New york street test 51 |34.123| 38.245

每个位置都有lat和lon坐标。

您的系统具有知道如何接收 2 个位置并以km为单位返回距离的功能。

您还有一个名为的表stores，其中包含商店的 id、name、lat、lon。

当您选择一个地点时，您的应用程序会找到离您选择的地点最近的 20 家商店。

问题

一开始一切正常，但现在该应用程序已经发展壮大，并且在许多地方都充满了新商店，并且您在数据库中注册了超过 5 亿家商店。每次搜索都很繁重，系统过载，需要几秒钟到一分钟才能得到结果。

你怎样才能让它变得更好、更高效？

剧透 - 我回答这个问题的想法

我的想法是将世界地图分成大小Constant为 10km x 10km 的区域矩阵。每个地区都会有自己的ID您通过您的平台添加的每个商店都会获得您添加到的区域 id。当你搜索 lat 和 lon 时，系统会遍历所有区域，搜索包含该坐标的区域并返回区域 id，然后你可以抓取该区域 id 的所有商店。但是等等，你有一个问题，如果邻近地区有更近的商店怎么办？很简单，你有4个你所在区域的角点，你可以查找所有相邻区域并比较是否有更近的商店。如果您没有足够的商店并且您必须从所有区域中获得 10 家商店，那么也使用角落的 4 个坐标并在所有区域上递归，直到您到达最近的 10 个。

我很乐意听到每个人的想法。请注意，这不是一个真实的故事，在一些采访中被问到，我觉得它很有趣，看看是否有更好、更有趣的解决方案。