假设我正在设计一个像Yelp这样的餐厅推荐系统。我需要执行的一些基本事项如下:为了在系统设计中快速进行搜索而创建的数据结构是如何实际存储的?
- 用户应该能够添加/删除/更新位置。
- 考虑到它们的位置(经度/纬度),用户应该能够找到给定半径内的所有附近地点。
- 用户应该能够添加关于某个地点的反馈/评论。反馈可以包含图片,文字和评分。
从存储的角度来看,我决定为每个地方的纬度,经度,名称,描述和评分都提供像LocationId这样的字段。假设每个LocationId和纬度和经度的字节数大约为8个字节,如果我为5亿个位置设计系统,那么我就需要〜500 x 10^6 MB的存储空间。到现在为止还挺好。
为了更快获得位置查询结果,我决定使用Quadtree,如图所示,由网格组成,每个网格由500个位置组成。如果一个网格超过500个位置,它将被拆分成另一个网格,每个网格的最大网格数为4.假设我也创建了Quadtree。我不确定创建Quatree后,其中和我们如何存储这棵树?我能想到的
一种可能的方式是,我将序列的四叉树和一些类似的线像我们序列化一个N叉树并将其存储在一个文本文件中。考虑到我在我的树的节点中保留了LocationId,Longitude和Latitude详细信息,如果每个字段都是8个字节,我需要为每个位置存储24kb的数据。对于500个这样的位置,我的树的总内存需求为〜24 * 500M = 12 GB。每当我的机器重新启动时,我只是反序列化存储的树并按服务器的请求执行查询操作。
我用这种方法看到的一个问题是,为了保留有关位置的最新信息,我需要每隔一段时间后更新我的文件。
任何人都可以建议在其他方式可以存储QuadTree,我将在哪里存储它?我相信按照我上面的建议,有更好的方法来存储QuadTree。