首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 今日面试被鄙视的第二题：mp3搜索的问题 [已结帖,结帖人:loops]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 结帖率：
    发表于：2007-12-13 20:02:24 楼主
    谈到后来，我都觉得自己快“朽木不可雕”了，估计自己跟面试人员的思想差距太大了，虽然他提示我好多，可是我依然不能领悟。
    题目是：
    “
    假设一个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;
    };
    我当时想到的是这样的方法。但是面试官挑一堆错，比如桶的增长和缩小，采用链式结构又多费空间，我实在是想不到其他更好的方法，不知道有啥其他方法可以再更加优化。
    200  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • arfi
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 20:10:491楼 得分:5
    好像是百度的面试题，要是面试通过的话，月薪两万呢！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ttlyfast
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 20:28:342楼 得分:5
    挖！
    没接触过类似算法
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • langya54
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 20:36:193楼 得分:5
    看着这题目我真的没信心学下去了 哎 何时才能达到那样的高度
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • whycom
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 20:37:114楼 得分:5
    btree?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ttlyfast
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 20:37:435楼 得分:0
    查看下搜索引擎相关书再去面试估计会好些
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • silencezhujianhua
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 21:32:006楼 得分:5
    祝福你能通过
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tanmeining
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 22:18:527楼 得分:5
    除略的算了一下,1G大约是个1024*1024字节,我想是不是可以这样.
    将SONG_ID和URL_ID的对应map放到一个文件中去,然后在内存区内开辟空间存放此map内每一项的可用的URL_ID的ID(因为这个是拿来搜索的,所以要可用的URL_ID也就是那2^10个URL_ID,所以常驻内存中的就只存放它),搜索的时候采用移位或者与的方式进行(速度较快),至于URL_ID不可用，直接找出相应的ID与掉就可以了,因可用的URL_ID为2^10这么多个,所以ID可以只存放这么大,那就相当的小了4k左右吧(好象是,一个int32位4个字节,2^10个int4k个字节,没算错吧?).
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • NKLoveRene
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 22:21:368楼 得分:5
    不会
    谢谢
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • mLee79
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 22:38:039楼 得分:30
    随便搞搞,这样行不..

    硬盘数据:
    记录 < SONG_ID , URL_ID > 信息需要 16M * 1K * 4 字节, 在逻辑上构成一个64G的文件, 存储时分割为64G/2G==32个文件, SONG_ID 对应的URL_ID信息位于逻辑文件的 4K * SONG_ID 处.
    内存使用:
    记录 SONG_ID 是否使用的 bitmap , 共需要 16M/8 == 2M , 记录 URL_ID 是否可用的bitmap, 共需要 1G/8==128M , 其他内存作为缓存

    在数据量增大时, 建立 ( M = ceil( SONG_ID_MAX / 16M ) ) * ( N = ceil( URL_ID_MAX / 1G ) ) 台服务器, 如128M SONG_ID , 4G URL_ID 共需要 8*4 台服务器,分别编号为:
    <1,1> <2,1>.... <M,1>
    <1,2> <2,2>.... <M,2>
    . . . . . . . .
    <1,N> <2,N>.... <M,N>
    在逻辑上, 服务器 <X,Y> 处理 SONG_ID in [4K*X ,4K*(X+1) ) , URL_ID in [1G * Y , 1G*(Y+1) ) 的请求.

    1) X = SONG_ID / 16M + 1 , 由服务器 <X,1> <X,2>... <X,N> 响应.
    2) 由服务器 < SONG_ID/16M + 1 , URL_ID/1G + 1> 响应
    3) X = SONG_ID / 16M + 1 , 由服务器 <X,1> <X,2>... <X,N> 响应.
    4) Y = URL_ID / 1G + 1  , 由服务器 <1,Y> <2,Y>... <M,Y> 响应.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • gzlucky
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 22:55:5110楼 得分:5
    其实面对这些题目，我觉得一点也不可怕。

    首先这些题，对于考官来说，可能他们也不会是一时半刻能想周全的，而且他们在考虑这个问题前还会有很多这方面的积累。所以要求一个面试者对这些题目也不会期望应试者能够在短短时间内有完美的答案。关键是你的思考过程，以及思路的严密性。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cpp20071101
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-13 23:13:3511楼 得分:5
    up 努力 !
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ltc_mouse
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2
    发表于：2007-12-14 00:22:4912楼 得分:5
    只能继续埋头学习了...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhangystc
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:21:2913楼 得分:5
    估计面试官自己都没怎么弄明白
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jmulxg
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:25:0414楼 得分:5
    mark first
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • firemcu123
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:32:1115楼 得分:5

      继续关注。谢谢。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • awperpvip
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:32:2116楼 得分:5
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhulinpptor
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:33:5717楼 得分:5
    面试官瞎闹
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • bigpin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:34:5018楼 得分:5
    恩，这种面试题基本上没有完全正确的答案，主要是他有来言，你有去语，思维能跟的上就OK
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • michney
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:46:5219楼 得分:5
    b+树，稀疏矩阵
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • starshift
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 09:48:5120楼 得分:10
    Bloom Filter嘛，这个显然是这个
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Tiger_Zhao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 5

      4

      3
    发表于：2007-12-14 10:23:2421楼 得分:10
    ①用位标记每个URL_ID可用性，类似.Net的BitArray，该文件/对象大小：2^30/8=128M；
    ②一个URL_ID只属于一个SONG_ID，URL_ID为数组下标，SONG_ID为数组元素值，该文件/对象大小：2^30*4=4G，可以分成16份每份512M；
    ③属于每个SONG_ID的URL_ID，用小根堆的方式存放，该文件/对象大小上限：2^10*4=4K；
    　此类文件要分目录，如果128的限定对目录也有效，需要分成8\128\128\128共4层存放。

    需求
    1)直接按目录载入文件③，数组个数为计数，内容为列表；
    2)根据URL_ID更新①的位标志；载入对应文件②，更新数组元素；载入对应文件③，用堆操作添加URL_ID；
    3)创建一个空白的文件③；
    4)根据URL_ID更新①的位标志；载入对应文件③，用堆操作删除URL_ID；

    注：以上文件①②③各载入一个，或者减小②的大小对②③进行缓存。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 10:31:5222楼 得分:0
    arfi
    好像是百度的面试题，要是面试通过的话，月薪两万呢！
    ~~~~~~~~~对，题目是来自百度的面试题

    ttlyfast
    没接触过类似算法
    ~~~~~~~~~呵呵，看完你的《Computer.Systems.A.Programmer's.Perspective.》没？看完了学学搜索方面的东西吧。真正的高手大约应该是从头通到尾巴的。

    langya54
    看着这题目我真的没信心学下去了  哎  何时才能达到那样的高度
    ~~~~~~~~~~其实，没啥的，你多接触一下此类问题，再加上实践和基础扎实，稍微点拨一下就会明白了。


    silencezhujianhua
    祝福你能通过
    ~~~~~~~~~~哦，谢谢，不过肯定通不过，我昨天表现太差了，跟面试的人想的根本就不是同一条线路，确切的说，现在还是没有想在同一条线路上。


    tanmeining
    除略的算了一下,1G大约是个1024*1024字节,我想是不是可以这样.
    将SONG_ID和URL_ID的对应map放到一个文件中去,然后在内存区内开辟空间存放此map内每一项的可用的URL_ID的ID(因为这个是拿来搜索的,所以要可用的URL_ID也就是那2^10个URL_ID,所以常驻内存中的就只存放它),搜索的时候采用移位或者与的方式进行(速度较快),至于URL_ID不可用，直接找出相应的ID与掉就可以了,因可用的URL_ID为2^10这么多个,所以ID可以只存放这么大,那就相当的小了4k左右吧(好象是,一个int32位4个字节,2^10个int4k个字节,没算错吧?).
    ~~~~~~~~~~~~~~~~~~~~
    URL_ID有2^30个，是一个unsigned int型，占用4个字节，因此2^30*4=2^32(字节)就已经占用4G空间，所以URL_ID肯定不能放到内存中去。


    mLee79
    记录  <  SONG_ID  ,  URL_ID  >  信息需要  16M  *  1K  *  4  字节,  在逻辑上构成一个64G的文件,  存储时分割为64G/2G==32个文件,  SONG_ID  对应的URL_ID信息位于逻辑文件的  4K  *  SONG_ID  处.
    记录  SONG_ID  是否使用的  bitmap  ,  共需要  16M/8  ==  2M  ,  记录  URL_ID  是否可用的bitmap,  共需要  1G/8==128M  ,  其他内存作为缓存
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    SONG_ID取值范围是整个unsigned int型的，因此是0-2^32-1，BITMAP怎么也得使用4G/8=500MB的吧? 当时我特地问面试官是不是SONG_ID是从0编到2^24-1的，他说是一个整型。
    同理URL_ID也得要4G/8=500MB。
    我上面的分析应该没错吧？
    所以，为了记录SONG_ID，还是需要在磁盘上开辟4G*4k=16000G的逻辑空间，8000个2G的小文件吧？（俺用惯小硬盘了，当时这种方法都没敢去想，太奢侈了）

    gzlucky
    其实面对这些题目，我觉得一点也不可怕。
    首先这些题，对于考官来说，可能他们也不会是一时半刻能想周全的，而且他们在考虑这个问题前还会有很多这方面的积累。所以要求一个面试者对这些题目也不会期望应试者能够在短短时间内有完美的答案。关键是你的思考过程，以及思路的严密性。
    ~~~~~~~~~~~
    此话倒是对，不过基础不扎实的话，或者跟面试官想不到一条线上的时候，也没戏。
    我这次的主要问题是无法领悟面试官的提示，云里雾里的。
    还有一点，他也没把他的解决方案告诉我，我也不信他的方案有那么强悍，可以既省时间又省空间。
    他只是让我回去考虑考虑，我到现在还是不能领悟（貌似“朽木不可雕”了），所以只好来求助大家的智慧。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 10:55:5323楼 得分:0
    StarShift
    Bloom  Filter嘛，这个显然是这个
    ~~~~~~~~~~~~~~~~~~
    SongID是4个字节32位，那8个随机数的seed就是每个都使用SongID的4位了？
    然后开个200MB的bitmap来映射0-1600000000的自然数？
    不过还需要把映射的bitmap对应到每个SONGID所对应的URL_ID的文件存放空间呢。
    就是说
    struct
    {
      int FILE_ID;
      int FILE_ADDR;//文件头的偏移
    };
    这个结构是少不了的吧？
    怎么从200MB的bitmap映射到这个结构呢？
    我就是这儿至今还想不通。
    此外Bloom Filter这儿也就是省了300MB的空间，还要冒着很小概率的误识别的风险。

    Tiger_Zhao
    ①用位标记每个URL_ID可用性，类似.Net的BitArray，该文件/对象大小：2^30/8=128M；
    ~~~~~~~~~
    URL_ID取值是整型的，就是0~2^32-1的，这样的话，BitArray就应该是512MB了吧？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Tiger_Zhao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 5

      4

      3
    发表于：2007-12-14 11:07:1824楼 得分:0
    >并记录了可收听这些歌曲的2^30条URL
    这不是限定数量了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • flyingscv
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 11:28:4525楼 得分:5
        1)                  通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表     
      select  .. from ..where ..=  SONG_ID
        2)                  给定一个SONG_ID，为其添加一个新的URL_ID
    insert into ...         
        3)                  添加一个新的SONG_ID         
    insert into ...         
        4)                  给定一个URL_ID，将其置为不可用
    update or delete ...

    呵呵,开个玩笑，这么回答不知会不会被轰出来

    回答这个问题之前是不是应该先看看数据库管理系统之类的东西,打打基础

           
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • flyingscv
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 11:29:4826楼 得分:0
        1)                  通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表     
      select  .. from ..where ..=  SONG_ID
        2)                  给定一个SONG_ID，为其添加一个新的URL_ID
    insert into ...         
        3)                  添加一个新的SONG_ID         
    insert into ...         
        4)                  给定一个URL_ID，将其置为不可用
    update or delete ...

    呵呵,开个玩笑，这么回答不知会不会被轰出来

    回答这个问题之前是不是应该先看看数据库管理系统之类的东西,打打基础

           
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 11:33:0727楼 得分:0
    michney
    b+树，稀疏矩阵
    ~~~~~~~~~~~~~~~~~~~~~

    B+树咋实现？
    就一个整型的SourcID，最多建立一个平衡二叉排序树就够了，何必B+？？不懂。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • think4
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 11:55:2228楼 得分:5
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • guojianbao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 12:32:0929楼 得分:5
    xx
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • flyingscv
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 12:39:3930楼 得分:0
    歌曲4M
    4*64(歌曲名,songid)=256M 
    根据歌曲名建立B-树应该足够了

    4M歌曲分3级，叶子4M个，第二级约2k个

    以上为内存结构


    --------------
    每首歌的URL不超过2^10(1k)个
    一个叶子1k*1k(url长度1k足够了吧，这个无关紧要)
    每个2级节点1m×2k约 2G

    过2G，一个目录下的文件数不超过128个
    2k/128= 8

    建8个目录，每个128个×2G文件
    ----------
    硬盘存储,根据2级节点也3级点点索引，直接存取，保证速度


    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • flyingscv
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 12:43:0831楼 得分:0
    4*64(歌曲名,songid)=256M  估计要  4M*128=512M
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • flyingscv
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 12:44:2732楼 得分:0
    2叉平衡数是不适合做这种事的
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ihpl_love
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 12:56:2233楼 得分:5
    只能先顶一下了，看来数据结构我真的要好好学了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • rlj021
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 13:03:1134楼 得分:5
    强！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • langya54
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 13:15:3635楼 得分:0
    数据结构是要回头好好看看了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • mLee79
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 13:52:1436楼 得分:0
    偶下面不是写了么, 当SONG_ID超出16M, URL_ID超出1G , 就建立 ( M=SONG_ID_MAX/16M ) * (N=URL_ID/1G ) 的逻辑上的服务器阵列, 每台服务器都需要 64+G 硬盘和 200M 左右的内存, 对 <SID,UID> 的请求被分配到服务器 <SID/16M , UID/1G > 上, 每台服务器 <X,Y>处理的 <SID'=SID-X*16M,UID'=UID-Y*1G> 范围都不会超过 <16M,1G>.
    按现在的服务器的能力, 每台服务器运行8个这样的进程是没问题地, 所以对 <1G,4G>的规模的服务需要约32台服务器.

    SID,UID 显然应该是相当稠密的, 因为想不到任何理由在里面留下大量的未使用的ID.

    在规模增大的情况下, 更好地办法是让每台逻辑的服务器处理 <SID,UID> :: <16M,4G> 的服务, 这样就需要512M内存做 UID的bitmap , 每个逻辑服务器需要大约600M的内存,同样是64+G的硬盘空间,每台服务器运行2个这样的进程该没问题. 对同样 <1G,4G>规模的服务同样需要32台服务器, 但硬盘的需求只要原来的1/4...

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • CoffeeCN
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 14:07:1537楼 得分:5
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhangyanli
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 14:22:5938楼 得分:5
    怎么看不到他们几个星星啊 ，我发现这里的星星们就会扯淡玩，真正遇到问题就看不到影子了。

    尤其是有几个，哎。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • gming2003
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 14:27:0539楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • liu_zhaoqf
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 15:45:3340楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • malligator
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 18:04:5641楼 得分:30
    内存不够存储这些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对应的位，表示为不可用。


    搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，希望在这些数据的基础上，能够开发这样一种功能：针对一个用户的检索串，能够向用户提示和该检索串关联度最大的10个其他检索串。（1）请描述你解决这个问题的思路；（2）请给出主要的处理流程、算法，以及算法的复杂度。


    对于用户的查询请求，根据其输入的检索串中关键词或者分词以后的关键词数可分为单查询词请求和多查询词请求。
    单查询词请求，顾名思义用户输入检索串的是一个单个的词，比如“中国”，对于这种查询不计入相关度计算中。
    另一种是多查询词请求，亦即用户在一次查询中输入了多个词语，比如“中国 北京”，或者输入的是一个查询词，但是经过分词以后分为了多个词语，比如用户输入“中国北京”，经过分词程序分词以后变成了“中国 北京”两个词语。对于这种查询，认为同一个检索串中的多个词语之间是具有相关性的，比如这里认为“中国”和“北京”具有一定的相关度。
    百度的题目估计是要根据用户输入的检索串中的多个查询词来计算这种这些查询词之间的相关度。

    根据以上分析，我的解决问题的思路是，建立一个查询词到与之相关的其他查询词之间的映射表，即对任意一个查询词 s1,存储与之相关的其他查询词序列s3,s9 ……sn，并且记录与之相关的相关度。同样，对于s2,s3……也都有这样的表项。对于每一个查询检索串Q=（sa, sb,……），其中sa,sb是独立的词语，我们认为sa,sb相关，那么查询上面的那个记录相关度的表，找到sa表项中的sb,将其相关度加1，同样也找sb项，将其中sa的相关度加1.同样对于同一检索串中的其他查询词亦是如此操作。
    以上的算法是建立一个相关度的映射表，那么当有一个新的检索串，如何的到它的最相关的查询词呢?思路如下：以有三个词的检索串为例，对于检索串Q=(sa,sb,sc)，取任意其他的词语s,则认为s与检索串Q的相关度为V(s，Q) = V（s,sa)+V(s,sb)+V(s,sc),V（）表示相关度;所以找出V(s,Q)最大的十个词语即可。

    数据结构：
    由于存储每个词语比较占内存，所以需要建立一个词典（ID <->word）,以hashmap形式来存储。ID从0往上累加，所以是连续的，因此可以整个相关的的映射表用动态数组来存储，数组的每个元素是：{ID，{ID1，degree}，{ID2，degree}……}表示词以及与之相关的 (词/相关度) 列表。在每个表项{ID，{ID1，degree}，{ID2，degree}……}中，ID1,ID2 … IDn的组织也是有序的。这样，对于任意一个词，首先通过词典找到他的ID,在通过ID找到相关度映射表中的项，即可查找相关度，或修改相关度（通常是加1）.

    另外，由于任意两个词之间的相关度是相等的，据此可以优化这个映射表，减少内存使用。比如对于每个表象{ID，{ID1，degree}，{ID2，degree}……{IDn，degree}},后面的相关度列表中的IDm（1 <= m <=n）,要求IDm>ID。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • malligator
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 18:05:4042楼 得分:0
    上文引用自 百度问题
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • guirong2007
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 18:24:2543楼 得分:0
    想你们学习啊 ，我还在读大一呢/我希望自己努力，哦，加油
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wgsasd311
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 18:26:5644楼 得分:0
    学习:)
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • pingchap
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 21:03:2145楼 得分:0
    what can I do for you?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ckt1120
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 21:59:5346楼 得分:0
    不会百度 大学白读
    果然
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 22:54:5547楼 得分:0
    文件的总大小大约为2^24*2^10*4  =2^36  =64GB.根据SongID即可计算出在哪个文件的哪个位置，那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    我晕，SONG_ID题目中没说编号是在[0,2^24-1]吧？
    如果SONG_ID的编号是在上述区间，那么可以这么做。但是题目中只指出了SONG_ID是个整型，所以如果SONG_ID是一个unsigned int，即[0,2^32-1]的取值范围，那么上述方案就是不对的。题目中没有明确指出这一点，我不明白为啥这么多人默认了SONG_ID的取值范围在[0,2^24-1]之间？

    同理URL_ID也是如此，凭什么认为URL_ID编号范围也是在[0,2^20-1]之间的呢？题目中读不出来。

    不过如果从这个假设来考虑的话，面试官提示的话现在想起来是豁然开朗了。
    我一直觉得2^32-1的空间太大，内存又只能占用1G，所以一直没有考虑。
    估计面试官也没闹明白我问他SONG_ID取值范围的意思。
    所以整个过程就是各想各的，天忘我也！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kings_zqz
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 23:00:5548楼 得分:0
    只能慢慢学习啦，好强悍啊
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 23:08:0949楼 得分:0
    这题总算弄清楚了，主要是对题目理解有误，或者说题目出的不严密也行。
    难怪那天下午我拼命跟着面试官的提示想，都想不出来，好狼狈。面试官又故作神秘，不告诉我答案，否则我也就无需想不通了。
    话说回来，居然拿这种流传的相当广泛的百度的面试老题来考人，这简直是考rp啊。

    感谢各位捧场，改天加分到200，再结贴。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ERR0RC0DE
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-14 23:35:5750楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • lishiyong110
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-15 00:23:3451楼 得分:0
    学习路还长啊
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yuyunliuhen
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-15 00:26:5452楼 得分:0
    算是见识到了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tanmeining
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-15 01:07:3453楼 得分:0
    呵呵，我也明白了，先前还以为只将可用的URL_ID常驻内存中(内存直接读取较快)呢,寒,原来题意都没搞懂就在下笔了,8好意思...狂汗一个!~~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Treazy
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-15 01:30:0454楼 得分:0
    百度的老玩意~~~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-15 10:12:0055楼 得分:0
    文件的总大小大约为2^24*2^10*4      =2^36      =64GB.根据SongID即可计算出在哪个文件的哪个位置，那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。 
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    我晕，SONG_ID题目中没说编号是在[0,2^24-1]吧？
    如果SONG_ID的编号是在上述区间，那么可以这么做。但是题目中只指出了SONG_ID是个整型，所以如果SONG_ID是一个unsigned  int，即[0,2^32-1]的取值范围，那么上述方案就是不对的。题目中没有明确指出这一点，我不明白为啥这么多人默认了SONG_ID的取值范围在[0,2^24-1]之间？
    同理URL_ID也是如此，凭什么认为URL_ID编号范围也是在[0,2^30-1]之间的呢？题目中读不出来。


    ~~~~~~~~~~~
    我上面的想法对吗？

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhouwei2
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-15 19:15:1256楼 得分:0
    路过 ,.....
    难拉
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cjls1
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 08:47:0257楼 得分:0
    我晕，SONG_ID题目中没说编号是在[0,2^24-1]吧？ 
    如果SONG_ID的编号是在上述区间，那么可以这么做。但是题目中只指出了SONG_ID是个整型，所以如果SONG_ID是一个unsigned      int，即[0,2^32-1]的取值范围，那么上述方案就是不对的。题目中没有明确指出这一点，我不明白为啥这么多人默认了SONG_ID的取值范围在[0,2^24-1]之间？ 
    同理URL_ID也是如此，凭什么认为URL_ID编号范围也是在[0,2^30-1]之间的呢？题目中读不出来。
    ==============================================================================
    unsigned int与int类型有很大区别？它的这个区间（其实没啥区间，只是算出SONG_ID和URL_ID总共需要的空间，以划分文件而已）是根据歌的数目来算的，就算是unsigned int，仍然是4个byte（32位机子），2^24*2^10*4仍然=64G,同样没有改变。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • silencezhujianhua
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 08:52:1658楼 得分:0
    建立  (  M  =  ceil(  SONG_ID_MAX  /  16M  )  )  *  (  N  =  ceil(  URL_ID_MAX  /  1G  )  )  台服务器,  如128M  SONG_ID  ,  4G  URL_ID  共需要  8*4  台服务器,分别编号为:
    <1,1> <2,1> .... <M,1>
    <1,2> <2,2> .... <M,2>
      .  .  .  .  .  .  .  .
    <1,N> <2,N> .... <M,N>
    在逻辑上,  服务器  <X,Y>  处理  SONG_ID  in  [4K*X  ,4K*(X+1)  )  ,  URL_ID  in  [1G  *  Y  ,  1G*(Y+1)  )  的请求.

    1)  X  =  SONG_ID  /  16M  +  1  ,  由服务器  <X,1> <X,2> ... <X,N>  响应.
    2)  由服务器  <  SONG_ID/16M  +  1  ,  URL_ID/1G  +  1>  响应
    3)  X  =  SONG_ID  /  16M  +  1  ,  由服务器  <X,1> <X,2> ... <X,N>  响应.
    4)  Y  =  URL_ID  /  1G  +  1      ,  由服务器  <1,Y> <2,Y> ... <M,Y> 
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 10:01:1459楼 得分:0
    unsigned  int与int类型有很大区别？它的这个区间（其实没啥区间，只是算出SONG_ID和URL_ID总共需要的空间，以划分文件而已）是根据歌的数目来算的，就算是unsigned  int，仍然是4个byte（32位机子），2^24*2^10*4仍然=64G,同样没有改变。
    ~~~~~~~~~~~~~~~~~~~
    对，实际文件大小是只需64GB，但是问题在于如果SONG_ID 可以取值[0,2^32-1]的话，你怎么从硬盘中直接定位你所需要的部分？？？
    也就是说此时SONG_ID [0,2^32-1]与连续存放4k内容的64GB文件之间存在一个映射的问题，你怎么映射？

    同理，URL_ID如果也是在[0,2^32-1]之间取值的话，开1G/8个字节来进行BITMAP怎么能够满足要求？


    所以，我认为这道题目没说清楚URL_ID和SONG_ID的取值范围。


    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • gimse7en
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 12:28:2960楼 得分:0
    云里雾里了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • langya54
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 12:39:0561楼 得分:0
    哎 今天不看改天在来弄清楚
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • visame
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 13:49:2762楼 得分:0
    学习学习！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xxxatt
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 13:50:1363楼 得分:0
    好强悍 都是牛人！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hanb99
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 15:12:0564楼 得分:0
    如果是我，就直接选用数据库，这样大概就不会这么费事了，好象本题也没说不得用数据库
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • mgtcllxl
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 15:22:0465楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yan63
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 15:51:5166楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • nifengfeiyang2
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 16:22:0067楼 得分:0
    哎,感觉自己要走的路还长着呢!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wh_peng
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 16:27:5868楼 得分:0
    niu
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • starshift
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 16:45:1769楼 得分:0
    StarShift
    Bloom      Filter嘛，这个显然是这个
    ~~~~~~~~~~~~~~~~~~
    SongID是4个字节32位，那8个随机数的seed就是每个都使用SongID的4位了？
    然后开个200MB的bitmap来映射0-1600000000的自然数？
    不过还需要把映射的bitmap对应到每个SONGID所对应的URL_ID的文件存放空间呢。
    就是说
    struct
    {
        int  FILE_ID;
        int  FILE_ADDR;//文件头的偏移
    };
    这个结构是少不了的吧？
    怎么从200MB的bitmap映射到这个结构呢？
    我就是这儿至今还想不通。
    此外Bloom  Filter这儿也就是省了300MB的空间，还要冒着很小概率的误识别的风险。

    Tiger_Zhao 
    ①用位标记每个URL_ID可用性，类似.Net的BitArray，该文件/对象大小：2^30/8=128M； 
    ~~~~~~~~~
    URL_ID取值是整型的，就是0~2^32-1的，这样的话，BitArray就应该是512MB了

    --------------------------------------------------------------------------------------------------
    问得好細啊，试着答一下哈！！！：）

    1， 首先不管你是多少位的ID，用bloomfilter都是没有关系的吧。
    2， 一共收录的2^24方个歌曲，存储 bloom filter的数组就是需要2^24方个位吧？ ：）
        2^24 个bit = 2^21 byte 是 2^11 K 2M 也就是说要是只需要判断有还是没有的话，只需要2M就好了。
        当然，如果你要存储一个在硬盘中的位置的话，这个位置只能是小于64位的，这个应该还是比较容易做到的吧。
        那么也只需要 2×64 = 128M的内存空间。
        也就是说你的song ID 是一个24位的数就好了，当然也可以是32位的。
    3，这里还有一个URL存储的问题，存储当然不能在内存中，硬盘顺序存储就好了。
    4，存储的时候根据歌曲名好好设计hash函数的到最后的歌曲ID，存储在bloomfilter中，就可以知道有没有这个歌曲了
      然后再根据你hash得到的位置（注意这个位置是一个0～2^24之间的数）去硬盘中检索就好了。


    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • oldmanzhao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 17:10:4470楼 得分:0
    LZ可以浩然正气的对面试官说，“在网上下载MP3是违法的！”然后拂袖而去。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • datuhao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-17 22:15:3871楼 得分:0
    ie7下居然不能回帖？
    来整两句：
    1）2^24首歌，被频繁搜索的只占很小一部分，局部性原则-最热文件在内存cache，保证最快被搜到，余者写磁盘
    2）每个文件2^10个url，局部性原则-最优的url在内存cache，保证优先被搜到，余着写磁盘
    3）按文件散列开存储最容易做分布处理

    该题数据结构不是关键，也根本不需要用到很复杂的数据结构，越简单越好，数据结构带来的性能差异根本可以忽略不记，因为海量资源的索引和查找瓶颈在读写磁盘的频率，如何将最好的资源调度给最热的内容的算法才是问题的关键。

    一、内存中建两张全局表，用于索引及热度排序
    1.一张songid->song的url列表的映射表，最简单的数组，下标直接作为songid，内容为该song对应的url列表的引用
    2.一张song的热度排序表，红黑树，AVL树都可，做为cache交换依据，热度表前2%（可调整）的歌曲对应的url列表cache在内存，由搜索热度的改变触发相应的交换算法，保证最热搜索一直被cache在内存中

    二、硬盘上count(songid)个文件，用于存放url列表
    每个文件对应一个url的排序表，该表不能全部cache在内存中，且需要按url质量排序。由于查找速度优先于删除，插入，和排序的速度（由一守护进程每2-3天，或更长时间执行一次对所有url列表文件进行排序，删除无效url，添加新url，更新url的总记数动作即可），所以根本不用考虑B-或B+树这样复杂的存储方式，直接使用最简单的顺序文件存储，每行一条记录，按质量好坏顺序排列，文件的前2%（可调整）直接cache在内存，若cache不命中的话，直接按顺序往下读，效率非常高。

    三、硬盘上一全局url质量统计列表，或直接放数据库
    用于采集所有url的质量状况，每2-3天，守护进程根据该表对所有song的url文件进行重新排序

    四、方便硬件升级扩展，如加内存，则可提高内存中的cache比例

    五、方便文件增加扩展，可按文件id分布到不同机器，例如1-1000完在a机器，1001万-2000万在b机器。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • loops
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-12-24 20:07:4772楼 得分:0
    真是不好意思，分不够分了，后来回帖的兄弟就没了。
    修改 删除 举报 引用 回复
    公司简介| 广告服务| 银行汇款帐号| 联系方式| 版权声明| 问题报告
    北京创新乐知广告有限公司 版权所有, 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    文明办网文明上网举报电话：13552009689
    Copyright © 1999-2009, CSDN.NET, All Rights Reserved
    GongshangLogo