map3搜索与存储的一道面试题

假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用

限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？

TODO:
确定磁盘文件里存放什么？需要多少个文件？

 

怎么通过song_id来定位该song所在的文件的url列表？

 

如何存储URL_ID计数？

 

 

 http://tech.techweb.com.cn/thread-222923-3-1.html写道

内存不够存储这些url，所以将数据写入若干个文件中。 

每一首歌曲对应的存储在文件中的信息格式为（url1, url2……）。

文件的总大小大约为2^24*2^10*4 =2^36 =64GB.根据SongID即可计算出在哪个文件的哪个位置，那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。

将每首歌曲的信息存入文件中，由于每首歌的url不超过2^10个，所以在文件中每首歌的存储结构是2^10个int数，每个int数字标识着一个url。-1表示url不存在。初始化时将文件中每个int数初始化为-1.
这样每个SongID对应的信息占用的空间为2^10*4=4KB，设每个文件大小1G，那么每个文件可存储2^18=256K个Song的信息。总共需要64个文件，把这些文件编号从0-63.

对于任意一个SongID，他所对应的url信息所在的文件编号是：SongID> > 18,在文件中的位置是：(SongID&0x3FFFF) < <12.

另外内存中用一个2^24大小的short int型数组来保存每一首歌曲对应的url的个数，计数组名为urlCount[]，初始化时值为-1,表示对应的Song_ID不存在。此数组占用空间2^25Byte=32MB;

url是否可用的信息用位图来标识。位图保存在内存中，占用的空间为2^30/8=2^27 Byte=128MB.


对所要求的操作：
:1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
通过SONG_ID计算出文件号和对应在文件中的位置，从urlCount[]中读取url个数，读出所有的url,并对每个url_ID查询位图看是否可用，若可用，将此url加入返回列表。

:2) 给定一个SONG_ID，为其添加一个新的URL_ID
通过SONG_ID计算出文件号和对应在文件中的位置，设为start，在通过urlCount[]得到url个数，假设有n个url,那么将新的URL_ID写入文件的start+sizeof(int)*n处。修改urlCount[SONG_ID]的值。

:3) 添加一个新的SONG_ID
检查将对应的urlCount[SONG_ID]，若为-1，则修改为0,若大于等于0，则表明改Song_ID已经存在。

:4) 给定一个URL_ID，将其置为不可用
修改url位图，标识URL_ID对应的位，表示为不可用。