一个关于数据结构的问题

pygzx 发布于 2014/10/24 19:13
阅读 129
收藏 0

设计一个数据结构;

数量级是百万;

描述是:支持插入删除查找,并且更新其插入的时间。如果数据集中已经有相同的元素,那就更新其时间。另外要维护数据集中的数据,如果与当前时间超过一个伐值,就清理那些数据。

望各位前辈指导一下思路.

加载中
0
jingdor
jingdor
你是要重新设计一个 memcache吗?
p
pygzx
我也不知道,听同学说的,对这方面的问题有兴趣.当做是面试题吧(应该是实际应用的)
0
中山野鬼
中山野鬼
哈,不知道你怎么搞。实际应用,我的搞发是切成块,每块整体数据存储量再4k,然后索引确定每块。另外对象如果是字符串,则使用hash方式做存储和比较。
p
pygzx
那超过阀值删除的问题呢?
0
Dracula777
Dracula777

可以参考redis,对于数据淘汰而言,有主动和被动淘汰策略,设定一个定时器去随机pick若干数据出来,然后检查key的时间矬,超过的则删除之,如果需要淘汰的key超过一定的比例,redis则会被迫强制把数据删除到这个比例之下后再接收请求.可以看看redis里面serverCron的代码

mongodb也有一个key淘汰机制,不过是开了一个线程去做,每分钟去scan,然后删除(TTL实际是分钟级,无法精确到秒级别)

查找删除的话,具体还是应该看插入的数据到底是什么,多个value?还是文件?还是别的之类.redis里面是用了ziplist存储元素,然后内部也实现了一个hashtable,不过对于有一类别元素而言,是用了快表.

我觉得还是应该把具体应用场景说说看吧.

p
pygzx
thx
返回顶部
顶部