存储层次化数据(MySQL)用于推荐营销

7

我需要一个5级层次结构来管理注册到网站的用户。每个用户都是由其他用户邀请的,我需要知道每个用户的所有后代和祖先。

我已经有两种解决方案:

  1. 使用一个关系表来维护这种结构,使用闭包表格:

    ancestor_id  descendant_id  distance
    1            1              0
    2            2              0
    3            3              0
    4            4              0
    5            5              0
    6            6              0
    2            3              1
  1. 拥有这个关系表。在一个表中保存5级祖先。一个“祖先”表:

   user_id ancestor_level1_id ancestor_level2_id ancestor_level3_id ancestor_level4_id ancestor_level5_id
   10      9                  7                  4                  3                  2
   9       7                  4                  3                  2                  1

这些是好的想法吗?

我知道“邻接列表模型”和“修改的前序树遍历算法”,但对于一个“推荐”系统来说,这些是否是好的解决方案呢?

我需要在这棵树上执行以下查询:

  • 频繁地添加新用户
  • 当用户购买物品时,他们的推荐人会获得一定比例的佣金
  • 每个用户都应该能够找出他们推荐的人数(以及由他们推荐的人推荐的人数……)在每个级别上

如果您能定义“好”的标准,那将会很有帮助——您是在寻找速度、灵活性还是易于维护性? - Neville Kuyt
@Neville 我正在寻找速度、易维护性以及一定的灵活性。 - morandi3
@Neville,@morandi3:我们需要确切地知道您想执行哪些类型的查询。 - Ken Bloom
4个回答

10

闭包表

ancestor_id  descendant_id  distance
    1            1              0
    2            2              0
    3            3              0
    4            4              0
    5            5              0
    6            6              0
    2            3              1

要添加由用户3推荐的用户10。(我认为您不需要在这两个插入之间锁定表):

insert into ancestor_table
select ancestor_id, 10, distance+1
from ancestor_table
where descendant_id=3;

insert into ancestor_table values (10,10,0);

查找所有由用户3引荐的用户。

select descendant_id from ancestor_table where ancestor_id=3;

按深度计算那些用户:

select distance, count(*) from ancestor_table where ancestor_id=3 group by distance;
找到用户10的祖先。
select ancestor_id, distance from ancestor_table where descendant_id=10;
这种方法的缺点是这个表所需的存储空间很大。

你的所有解决方案看起来都很好 :D 很难找到最佳方案。我想现在我会选择这个。但是 OQGRAPH 存储引擎似乎也是一个可靠的解决方案。谢谢 - morandi3

4

使用OQGRAPH存储引擎。

您可能希望跟踪任意数量的层级,而不仅仅是5个层级。获取支持QGRAPH引擎(例如MariaDB或OurDelta)的MySQL分支之一,并使用它来存储您的树。它实现了邻接列表模型,但通过使用一个名为latch的特殊列向存储引擎发送命令,告诉它要执行什么类型的查询,您就可以获得闭包表的所有优势,而无需每次有人注册您的网站时进行簿记工作。

以下是在OQGRAPH中使用的查询。请参阅文档:http://openquery.com/graph-computation-engine-documentation

我们将使用origid作为引荐者,destid作为被引荐者。

要添加由用户10引荐的用户11:

insert into ancestors_table (origid,destid) values (10,11)

查找所有由用户3推荐的用户。

SELECT linkid FROM ancestors_table WHERE latch = 2 AND origid = 3;

查找用户10的祖先。
SELECT linkid FROM ancestors_table WHERE latch = 2 AND destid = 10;

要查找由用户3引荐的每个级别的用户数量:

SELECT count(linkid), weight
FROM ancestors_table
WHERE latch = 2 AND origid = 3
GROUP BY weight;

@Ken 我不知道保留“任意”数量的级别是否是一个好主意,假设我们将有大约100个级别。在数据库中保留所有这些级别是否是一个好主意? - morandi3
@morandi3:仅从技术限制的角度来看(不讨论隐私影响),这取决于你如何做。您的祖先表使用的存储空间与您要跟踪的最大级别数量成比例。OQGRAPH是一种存储引擎,专门用于执行图形算法。它旨在通过在表中具有一个特殊列以向存储引擎发出命令来执行像Dijkstra的最短路径算法之类通常在SQL数据库中很难或不可能的操作。它没有相同的空间惩罚。 - Ken Bloom
@Ken,我不确定我能否在我的服务器上使用MariaDB或OurDelta。是否可以仅针对数据库中的一个表使用此引擎,还是需要更改所有表的存储方式?在您的意见中,哪种想法看起来最快/可靠? - morandi3
@morandi3:你不需要为所有的表更改存储方式。在MySQL中,存储引擎是用于创建和管理特定类型表的插件。MySQL的默认表类型是MyISAM,而默认分发还允许您使用InnoDB存储引擎创建特定的表(以获得更好的事务并发性)。当需要时,OQGRAPH只是另一种可以创建的表类型。它不会更改默认设置,也不会更改现有表使用的存储引擎,也不会替换默认存储引擎。 - Ken Bloom
@morandi3:我现在有两个答案,分别详细说明了如何执行你的每个查询。这些模型都不是很复杂。 - Ken Bloom
显示剩余3条评论

2

在MySQL中管理分层数据

一般来说,我喜欢“嵌套集”,尤其是在MySQL中,因为它没有对分层数据进行语言支持。它很快,但如果易于维护对你很重要,你需要确保你的开发人员阅读那篇文章。它非常灵活,但在你的情况下似乎并不重要。

在引荐模型中,嵌套集模型似乎非常适合你的问题——你需要找到引荐者的树形结构,在嵌套集模型中这很快;你还需要知道给定用户的“子代”以及他们之间的关系深度,这也很快。


我认为这不是我的系统的好方法,因为每当有新用户注册时,嵌套集都需要更新,不是吗?! - morandi3

1

祖先的分隔字符串

如果您正在考虑使用5级关系表,那么使用祖先的分隔字符串而不是5个单独的列可能会简化事情。

user_id  depth   ancestors
10       7       9,7,4,3,2,1
9        6       7,4,3,2,1
...
2        2       1
1        1       (empty string)

以下是一些与此模型相关的 SQL 命令:

添加用户 11,由用户 10 推荐

insert into ancestors_table (user_id, depth, ancestors)
select 11, depth+1, concat(10,',',ancestors)
from ancestors_table
where user_id=10;

查找所有由用户3推荐的用户。(请注意,此查询无法使用索引。)

select user_id
from ancestors_table
where ancestors like '%,3,%' or ancestors like '3,%' or ancestors like '%,3';

要查找用户10的祖先,您需要在客户端程序中分解字符串。 在Ruby中,代码是ancestorscolumn.split(",").map{|x| x.to_i}。 在SQL中没有很好的方法来分解字符串。

select ancestors from ancestors_table where user_id=10;

查找由用户3引荐的每个级别的用户数量:

select
   depth-(select depth from ancestors_table where user_id=3),
   count(*)
from ancestors_table
where ancestors like '%,3,%' or ancestors like '3,%' or ancestors like '%,3'
group by depth;

你可以通过使用like concat('%,', ?, ',%')替代like '%,3,%',并绑定用户数字的整数到占位符来避免这些查询中的SQL注入攻击。

@Ken 是的,但是一个用户只有一个祖先/级别。 - morandi3
@morandi3:我认为你把parentancestor混淆了。用户10只有一个parent(用户9)。而用户9只有一个parent(用户7)。用户7也只有一个parent(用户4)。所有这些父级以及父级的父级都被称为用户10的“ancestors”。因此,深度是指您必须经过几次跳转才能到达没有通过朋友推荐(通过广告或随机搜索找到您的网站的人)的人。 - Ken Bloom
@Ken 好的,现在我明白了,深度是链的长度。嗯,但是用这种方法很难找到用户的后代。 - morandi3
@morandi:查找后代是第二个查询。 (记住,就像祖先一样,后代是子孙和子孙的子孙等)你是指只查找子代吗? - Ken Bloom
@morandi3:嗯,是的。这就是这个模型的缺点。(你可以在“深度”字段上放置索引,但我怀疑这不会有太大帮助。)这基本上就是为什么SQL和图形/树形结构不能混合使用的要点,也是为什么OQGRAPH存储引擎被发明的原因。 - Ken Bloom
显示剩余7条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接