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

I need to have a 5 levels hierarchy for the users registered to a website. Every user is invited by another, and I need to know all descendants for a user. And also ancestors for a user.

我需要为注册到网站的用户设置一个5级层次结构。每个用户都被另一个用户邀请，我需要知道一个用户的所有后代。也是用户的祖先。

I have in mind 2 solution.

我有两个解决方案。

1. Keeping a table with relationships this way. A closure table:
2. 用这种方式保持关系。关闭表:

    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. Having this table for relationships. Keeping in a table 5 levels ancestors. A "ancestors" table:
2. 有这个关系表。在表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

Are these good ideas?

这些是好主意吗?

I know about "the adjacency list model" and "the modified preorder tree traversal algorithm", but are these good solutions for a "referral" system?

我知道“邻接表模型”和“改进的前序树遍历算法”，但是这些是“推荐”系统的好解决方案吗?

The queries that I need to perform on this tree are:

我需要在这棵树上执行的查询是:

• frequently adding a new users
• 经常添加新用户
• when a user buys something, their referrers get a percentage commission
• 当用户购买某样东西时，他们的推荐人会得到一定的佣金
• every user should be able to find out how many people they've referred (and how many people were referred by people who they referred....) at each level
• 每个用户应该能够发现他们被多少人(他们被多少人被人称为....)在每个级别

4 个解决方案

#1

Closure Table

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

To add user 10, referred by user 3. (I don't think you need to lock the table between these two insertions):

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

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);

To find all users referred by user 3.

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

select descendant_id from ancestor_table where ancestor_id=3;

To count those users by depth:

按深度计算这些用户:

select distance, count(*) from ancestor_table where ancestor_id=3 group by distance;

To find the ancestors of user 10.

查找用户10的祖先。

select ancestor_id, distance from ancestor_table where descendant_id=10;

The drawback to this method is amount of storage space this table will take.

这种方法的缺点是该表将占用大量的存储空间。

#2

Use the OQGRAPH storage engine.

You probably want to keep track of an arbitrary number of levels, rather than just 5 levels. Get one of the MySQL forks that supports the QGRAPH engine (such as MariaDB or OurDelta), and use that to store your tree. It implements the adjacency list model, but by using a special column called latch to send a command to the storage engine, telling it what kind of query to perform, you get all of the advantages of a closure table without needing to do the bookkeeping work each time someone registers for your site.

您可能希望跟踪任意数量的级别，而不是仅仅跟踪5个级别。获取一个支持QGRAPH引擎的MySQL分支(如MariaDB或OurDelta)，并使用它来存储树。它实现了邻接表模型,但是通过使用一个专栏叫门闩存储引擎发送命令,告诉它什么样的查询来执行,你会得到所有的好处关闭表,而不需要做簿记工作每次有人注册你的网站。

Here are the queries you'd use in OQGRAPH. See the documentation at http://openquery.com/graph-computation-engine-documentation

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

We're going to use origid as the referrer, and destid as the referree.

我们用origid作为参照，destid作为参照。

To add user 11, referred by user 10

添加用户11，由用户10引用

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

To find all users referred by user 3.

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

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

To find the ancestors of user 10.

查找用户10的祖先。

SELECT linkid FROM ancestors_table WHERE latch = 2 AND destid = 10;

To find the number of users at each level, referred by user 3:

要查找每个级别的用户数量，请参阅用户3:

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

#3

Delimited String of Ancestors

If you're strongly considering the 5-level relationship table, it may simplify things to use a delimited string of ancestors instead of 5 separate columns.

如果您强烈地考虑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)

Here are some SQL commands you'd use with this model:

下面是一些SQL命令，您可以在这个模型中使用:

To add user 11, referred by user 10

添加用户11，由用户10引用

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

To find all users referred by user 3. (Note that this query can't use an index.)

查找所有用户提交的用户3。(注意这个查询不能使用索引。)

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

To find the ancestors of user 10. You need to break up the string in your client program. In Ruby, the code would be ancestorscolumn.split(",").map{|x| x.to_i}. There's no good way to break up the string in SQL.

寻找用户的祖先。您需要在客户端程序中分解字符串。在Ruby中，代码是ancestry .split(“，”)。地图{ x | | x.to_i }。在SQL中没有很好的方法来分解字符串。

select ancestors from ancestors_table where user_id=10;

To find the number of users at each level, referred by user 3:

要查找每个级别的用户数量，请参阅用户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;

You can avoid SQL injection attacks in the like '%,3,%' parts of these queries by using like concat('%,', ?, ',%') instead and binding the an integer for the user number to the placeholder.

您可以使用like concat('%，' ? '， '， '， '， '， '， '，%')来避免SQL注入攻击，并将用户号的整数绑定到占位符。

#4

Managing Hierarchical Data in MySQL

管理MySQL中的分层数据

In general, I like the "nested set", esp. in MySQL which doesn't really have language support for hierarchical data. It's fast, but you'll need to make sure your developers read that article if ease of maintenance is a big deal. It's very flexible - which doesn't seem to matter much in your case.

一般来说，我喜欢“嵌套集”，尤其是在MySQL中，它并没有对分层数据的语言支持。这是快速的，但是如果易于维护的话，您需要确保您的开发人员阅读这篇文章。它是非常灵活的——这对你来说似乎不太重要。

It seems a good fit for your problem - in the referral model, you need to find the tree of referrers, which is fast in the nested set model; you also need to know who are the ~children@ of a given user, and the depth of their relationship; this is also fast.

它似乎很适合您的问题——在推荐模型中，您需要找到引用者的树，这在嵌套集模型中是快速的;你还需要知道谁是一个特定用户的孩子，以及他们关系的深度;这也太快了。