面对一个包含100万商户的数据集，你会采用什么数据结构和算法来高效地找出距离给定位置最近的5家商户？请阐述你的设计方案、核心机制和复杂度分析。

回答思路

1. 【回答框架 1】核心思路是利用空间索引将二维搜索转化为高效的剪枝查询。常用方案为基于网格或地理哈希的粗粒度分区，配合KD树或R树进行精细查找，最终通过优先队列取距离最近的前K个结果。
2. 【回答框架 2】具体设计：第一步，将商户经纬度映射到统一坐标系，构建GeoHash索引，将区域划分为大小适中的格子，每个格子对应一个商户ID列表。第二步，根据目标点所在格子，逐层向外扩展搜索邻近格子，剪枝掉距离明显超过当前第5近候选的格子。
3. 【回答框架 3】在候选格内，可使用KD树或四叉树组织商户坐标，以支持快速范围查询。对于每个候选商户，计算与目标点的球面距离（如Haversine公式），并维护一个大小为5的最大堆，堆顶为当前最远候选，新点若更近则替换堆顶。
4. 【回答框架 4】复杂度方面，索引构建为O(N log N)，单次查询在理想均匀分布下为O(log N + K)，最坏情况下（商户集中）需扫描较多区域，但实际通过多级索引和缓存可达到毫秒级响应。此外，可对热门区域建立常驻内存索引，并利用分布式集群分片处理100万级数据。
5. 【回答框架 5】备选方案包括直接使用PostgreSQL的PostGIS或Elasticsearch的地理查询，但需权衡引入外部组件的成本。最终方案应结合查询频率、更新频率和可用性要求进行选择。
6. 【关键点 1】空间索引（GeoHash、KD树、R树）是解决大规模最近邻查询的核心。
7. 【关键点 2】利用最大堆（大小为5）维护当前最近的5个候选，实现高效Top-K筛选。
8. 【关键点 3】复杂度：构建索引O(N log N)，查询近似O(log N + K)，依赖于数据分布。
9. 【关键点 4】需考虑数据更新、冷热数据和容灾，必要时引入分布式缓存与分片。
10. 【易错点 1】不能对所有商户实时全量计算距离，必须依赖空间索引进行剪枝。
11. 【易错点 2】距离计算须用球面距离公式，避免平面直角坐标在跨经纬度时误差过大。
12. 【易错点 3】数据倾斜时（如市中心商户密集），单一索引可能性能退化，需设计多级或动态网格。