[前端面试题: 请求/显示千万级别数量的任务]

题目: 设计一个在地图（谷歌地图）上显示千万级别数量的任务的前端单页应用程序

任务被分组到项目中。项目/任务被存储在后端 RDBMS 系统中.  每个任务所在的记录存有该任务的经纬度位置。

前端请求后端 API, 拿到特定项目的任务数据, 并显示在前端谷歌地图上。
一次请求可以返回千万级条任务

**问题: 您将使用哪些关键概念/技术来实现在前端显示上千万级别数量的任务?**

我的思路:
1. Throttling / Debouncing, 避免短时间内重复请求
2. 按需请求/加载: 网页滚动到哪里, 先请求/加载当前视口能看得到的内容.  视口外的看不见的内容,不请求不加载
3. 本地缓存

请大佬提供思路!


谢谢!

@shadowyue 万一他面的就是百度地图，腾讯地图，高德地图嘞🤣

这个东西往深入挺复杂，不知道面试官需要的是能回答到什么程度。
如果是工作中遇到这个，现在随便一个地图的 sdk 都支持海量数据展示处理，上面几位提到的算法都自带了，去查查文档就行。

关于数据加载：请求完数据后，构建四叉树，四叉树的数据使用分块存储。根据视角所处的位置和 level 动态加载对应 level 的分块数据。同时可以预加载相邻的分块和相邻的 level 数据。

关于显示：因为前端不可能同时显示 1000 万个对象，整个屏幕也就 100 万像素左右。根据需求，看最大需要同时显示多少个对象，来确定使用什么方式来显示这些对象。如果要尽可能密集，那只好绘制像素，如果只要显示 1 万个，那就可以简单些了。

感觉面试官卡在这个问题很久了。

按缩放级别加载？然后限制单次请求的数据量，优先加载中心坐标近的该缩放等级的数据。

我记得现在的地图插件都可以拿到缩放层级的，该聚合就聚合，算法都不需要，缩放太低了直接就显示粗略信息

面试：
使用 KD-tree 算法聚合坐标
使用 Web Worker 避免阻塞主线程
使用 Emscripten c++ 加快计算速度

干活：
npm install supercluster

这是来面试客户端吧，什么四叉树管理经纬度之类的算法。

多学学 google earth ，web 直接上 wasm ，用客户端的思路开发前端。JS 代码再花里胡哨，也阻挡不了时代的步伐。

1. geo fencing,  只拉取并显示当前 map zoom level 和 geo boundary 内的 task 。
2. clustering ， 显示的时候只显示当前 level 的 clustered marker,  zoom in/out 的时候再去拉更详细的数据。
3. 如果这些 task 需要以列表的形式做展示，virtual scrolling