那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

[算法]如何根据数据的多种属性来查找数据

今天下午,使用新浪微博的查找好友功能查找好友时,突然想起这样的一个功能,应该说这个问题我之前也考虑过,但是一直没有很好的答案,这里做一个描述.

其实问题说白了也很简单,查找好友的时候,可以根据用户的一个或者多个属性来定位数据.比如一个用户有用户名,性别,地址三个属性,如何做到可以根据其中的一个或者多个属性来定位用户呢?

首先来看存储端的设计,我个人认为这个功能虽然可能用的次数不多,但是不应该是直接去访问查找数据库的,否则量如果大了起来响应会很慢.好了,如果不是直接查找数据库的话,那么挡在数据库前面应该有cache服务器了.第二个问题来了,cache总是有限的,不能缓存所有的数据,那么在这里查找就可能会丢失一些数据,这个问题又怎么解决呢?嗯,我个人的猜测是,这里有一个平衡点的问题,即有一个准则,比如说经常登录的活跃用户信息才会留在cache中,不常访问的用户,找不到也不打紧了.

接下来,如果数据真的在cache中,即使如此,那么要实现这里提到的可以根据多个属性来查找数据也不是很容易实现的.

现在大部分的cache系统,比如memcached,还有我之前写的ccache,本质上都是key-value形式的cache,也就是仅能针对一个key值进行搜索查找.

考虑如下的两种实现:
1) 缓存中数据key是用户名,而value是用户的其它信息如性别,城市,主页等,那么这里就存在一个key值不唯一的问题.好了,如果把所有相同key值的数据组织在一起,比如用一个链表串起来,如果找到这个用户名,再遍历这个链表根据其余的参数来定位数据.但是,如果用户不是根据用户名也就是key值来查找数据的,如何是好呢?难道说,要建立一个多key的数据结构用于查找,就我现在对cache设计的了解,还没有这种多key设计的cache,基本上都是单key的cache.

2) 缓存中数据key不仅包括用户名,还包括了其它可以定位到用户的属性,也就是,与前面的实现不同的是,这个实现把多个属性都放在key里面了.但是,如果这样组织数据,又如何定位数据呢?假设key里面有三个属性,某次使用了其中的一个属性来查找,下一次使用其中的两个属性来查找....这种设计实现起来还是很难的.

以上几个问题,我今天考虑了一下,没有太好的思路,这也越发激起我去研究数据库实现的想法.疑问未除,做个纪念.


=========== 分割线 ==================
这个问题似乎我想的复杂了,问了一下朋友,说是应该直接搜索数据库,因为一般这样的搜索量不会很多.




posted on 2009-10-23 20:11 那谁 阅读(4997) 评论(4)  编辑 收藏 引用 所属分类: 算法与数据结构服务器设计

评论

# re: [算法]如何根据数据的多种属性来查找数据  回复  更多评论   

按照数据库实现,应该是数据存储起来,然后分别建立不同的索引吧.索引做的复杂了,就是搜索引擎了 :)
2009-10-23 22:00 | dogstar

# re: [算法]如何根据数据的多种属性来查找数据  回复  更多评论   

一般都会按照 ID和用户名做key的

你那个需求 直接查找数据库好点
2009-10-27 15:12 | wangfan1985@gmail.com

# re: [算法]如何根据数据的多种属性来查找数据  回复  更多评论   

分层索引呢 相当于key值查找key值,最后查找到数据
2012-06-07 15:37 | hai

# re: [算法]如何根据数据的多种属性来查找数据  回复  更多评论   

这个可以用多叉树
2013-10-21 17:49 | xiaolong

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理