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 r开发者_开发知识库eferrers 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;

---

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.

---

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.