这个数据集的最佳数据库是什么？

Question

我有一个应用程序(对于给定的Twitter用户),它获取您关注的Twitter用户列表但不关注您.它这样做:

• 比较两个列表,一个来自时间x和时间y,也看看是否有更多的人跟着你或更少.
• 看看twitter用户x需要多长时间跟进你.
• 查看用户x关注您的转推/评论数量

我想出的简单方法就是拥有一个很多属于关系的用户和没有关注你的人,例如:

User table
-id

TwitterUser table
-user_id 
-timestamp
-isFollowing

因此,对于给定用户,我可以获得所有非跟随用户的SQL模式,并且可以通过时间戳比较它们以匹配上述要求.

但是,我希望有一个更好的数据库后端代表这个数据集而不是一个sql数据库.我一直在尝试使用redis,但不知道如何将它拉下来.

我想也许是文档存储 - b/c我想要做的就是采用两个数据集的差异.或者更准确地说:我想区分两个twitter用户ID列表.

有任何想法吗？

Answer 1

比较两个阵列的Bruteforce方法将具有O(N*M)的时间复杂度,其中N和M是阵列的大小.因此,我们应该使用一些智能数据结构来存储它们以有效地执行此操作.

我想出了以下方法:

1. twitter ids列表是一个集合,因为ID是唯一的.Redis支持集合并允许执行差异等集合操作.假设你有2套钥匙ids_at_time_x和ids_at_time_y.使用SADD 如下方法向它们添加元素:

   SADD ids_at_time_x "15424"
   

   当你准备执行diff执行时

   SDIFF ids_at_time_x ids_at_time_y
   

   这将返回一个ids_at_time_x不存在的ID列表ids_at_time_y.如果你想做反向操作,即检索一个不存在的id列表ids_at_time_x,只需交换参数:

   SDIFF ids_at_time_y ids_at_time_x
   

   关于SDIFF的最好的事情是它非常有效地运行 - 时间复杂度是O(N),其中N是这两组中元素的总数.即使您进行2次差异操作,时间复杂度仍然是线性的.

2. 将它们存储为排序列表.Redis支持有序集.添加id时,你必须包含一个元素分数(Redis将根据分数进行排序),它等于你的id中的id:

   ZADD ids_at_time_x 15424 "15424"
   

   列表准备就绪后,我们检索它们并在代码中进行比较.这是伪代码:

   n = size of A
   m = size of B
   i = 0
   j = 0
   setA = [] // List of elements that present only in A
   setB = [] // List of elements that present only in B
   intersection = [] // List of elements that present in A and B
   
   while i < n or j < m {
     if j == m {
       setA.add(A[i])
       i = i + 1
     } else if i == n {
       setB.add(B[j])
       j = j + 1
     } else if A[i] < B[j] {
       setA.add(A[i])
       i = i + 1
     } else if B[j] < A[i] {
       setB.add(B[j])
       j = j + 1
     } else {
       intersection.add(A[i])
       i = i + 1
       j = j + 1
     }
   }
   

   说明:我们使用A和B排序的事实.我们有两个索引,都从零开始.比较A和B的两个第一元件如果A [0]是小于B [0],我们知道,A [0]是只存在于A,使我们将其添加到列表中组A和由一个增加A的索引.如果B [0]小于A [0],我们将B [0]添加到列表setB并将B的索引增加1.如果A [0] == B [0],我们将A [0]添加到交叉点列表中并递增两个索引.此代码也适用于线性时间O(N),其中N是A和B中元素的总数.

   请注意,此方法适用于任何可以返回排序列表的数据库,这意味着您可以将其存储在传统的SQL数据库中并使用ORDER BY twitter_id)检索列表.

看看Redis支持的所有数据类型及其命令的完整列表,它们都有很好的文档记录.Redis还有许多语言的官方客户,所以这应该不是问题.您仍然可以将重要数据存储在SQL数据库中,并让Redis处理ID列表.