mp3搜索的问题

谈到后来，我都觉得自己快“朽木不可雕”了，估计自己跟面试人员的思想差距太大了，虽然他提示我好多，可是我依然不能领悟。
题目是：
“
假设一个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个。          
    为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？      
”

我所能想到的是：首先的500MB献给URL_ID，做个大的bitmap，用来重置不可用的URL_ID
SONG_ID和URL_ID的对应关系大约是只能放在磁盘上了，因此，以2^10*4=4k为一个分块的大小，存入文件，
其次，
如果磁盘空间是无限的话，那么可以把SONG_ID的索引结构都放到磁盘上，就是说建立：4G*4k/2G=8000个文件来索引整个SONG_ID（感觉很有魄力），如此一来，对于任何SONG_ID，SONG_ID*4k/2G就是表示第几个文件，SONG_ID%2G就是在该文件中的位移。

如果磁盘空间是有限的话，那就Hash整个SONG_ID，用桶来处理冲突。
结构是：
struct   SongIndex
{
      int   song_id;
      int   file_id;
      int   file_addr;
};
我当时想到的是这样的方法。但是面试官挑一堆错，比如桶的增长和缩小，采用链式结构又多费空间，我实在是想不到其他更好的方法，不知道有啥其他方法可以再更加优化。

 

 

这是百度的一道面试题,据说过关后,2W一月!看来得加把劲学习了...同时该作者也推荐了一本书《Computer.Systems.A.Programmer》，以前看了一点。。。有机会再瞧瞧

 

转自：