Storing Hierarchical Data (MySQL) for Referral Marketing

Question

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.

1. 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

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

Answer 1

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}. 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.

Answer 2

Managing Hierarchical Data in 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.

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.