Storing Hierarchical Data (MySQL) for Referral Marketing

 

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.

I have in mind 2 solution.

  • Keeping a table with relationships this way. A 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
  • Having this table for relationships. Keeping in a table 5 levels ancestors. A "ancestors" table: 
    • 
   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

    • 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): 

    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. 

    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. 

    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.

    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.

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

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

    To add user 11, referred by user 10 

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

    To find all users referred by user 3. 

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

    To find the ancestors of user 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: 

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

    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. 

    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:

    To add user 11, referred by user 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.) 

    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} ancestorscolumn.split(",").map{|x| x.to_i} . There's no good way to break up the string in SQL. 

    select ancestors from ancestors_table where user_id=10;

    To find the number of users at each level, referred by user 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.

    链接地址: http://www.djcxy.com/p/16792.html

    上一篇: Postgresql，使用触发器维护分层数据

    下一篇: 为引荐营销存储分层数据（MySQL）