嵌套关联的数据结构

Question

First, please do not flame me as I am new to programming and PHP. I am a student trying to step outside of the comfort of foundation in a classroom and work on my first project. I have performed a search, my problem is I am not even sure how to word what I am looking for and am curious if I am overlooking a simple solution. I have tried searching for every variation of 'nested' or 'tree' that I think would associate with this problem but am having problems finding something that answers my question.

I am trying to list members that were referred by other members in a nested tree i.e. if John sponsored Mary, Mike, and Tom and Mike sponsored Megan and Susan, and Susan sponsored Betty and Michelle I want to be able to display something like:

1. John
   • Mary
   • Mike
     • Megan
     • Susan
       • Betty
       • Michelle
   • Tom

I would like to be able to specify the depth to search for example I only needed to display 5 levels deep if needed. For this I was thinking of a for (i=0;i<=4;i++)

$query = "SELECT fname, lname, user_id FROM USER WHERE sponsor_id = (SELECT user_id FROM USER WHERE username = '$_SESSION[username]')";
$result = mysqli_query($con, $query); 

while ($row = mysqli_fetch_row($result)) {
  echo "<ul><li>$row[0] $row[1]</li>";
  $subquery = "SELECT fname, lname, user_id FROM USER WHERE sponsor_id = '$row[2]'";
  $subresult = mysqli_query($con, $subquery);
  while ($row2 = mysqli_fetch_row($subresult)) {
    echo "<ul><li>$row2[0] $row2[1]</li></ul>";
  }     
}

This was my last attempt to figure out the general required structure which didn't exactly work. I am pretty sure I can make this work at any level desired if I want to keep making this deeper and nest further but what if I wanted to return 100 levels... seems there is a simple structure that I am just overlooking.

Any guidance would be appreciated, even a link to help explain this if you know how to search for what I am looking for I would be happy to read and learn myself, thanks!!

---

I found the answer after reading everyone's comments and doing a lot of searching. What I am looking for is an adjacency list or closure table. The best information I found on this is at http://www.slideshare.net/billkarwin/models-for-hierarchical-data. Thanks for the information everyone!

Answer 1

What you need is usually referred to as a B+ tree. Each node has children, but the number of children is not preset. So one node may have 5 children while another has 3 and another 1. To understand what not preset means, contrast with an n-ary tree. An n-ary tree is a tree where the number of children per node is already known (i.e. preset). Example, Bin-ary means each node has two children. In your case, you can decide to use an n-ary tree, which means you would use an array of children of a preset size. Your structure may end up being sparse. It that happens, change to B+ so that each children array has its own size.

Note that you don't need a graph for this since each person may only have one sponsor (i.e. one parent).