1

Imagine a tree. I would like to trace back to the trunk of the tree given any branch on that tree, with the number of branches within branches being unlimited. There are no many-to-many connections.

I am logging customers and have set up a table to show which existing customer recommended a new customer to us, so this has spread out to somewhat of a "family tree".

Every time a new customer comes on board, I need to know the original customer at the origin of the tree that started everything.

Here is a mock-up of my table to show 2 "families", with 1 and 11 being the top of the tree for each. Each parent has 2 children in this example and each number is a foreign key for a customer's contract number.

parents children
1       2
1       3
2       4
2       5
3       6
3       7
11      12
11      13
12      14
12      15
13      16
13      17

So far, I have been using MySQL and a PHP loop to SELECT a parent WHERE the child has a specific contract number, then looking to see if that parent is a child itself in the same table. I keep this loop going until no rows are returned and I get the answer.

My question is, is this the most efficient way to do this, or is there a solution outside of PHP, or by redesigning the table? I can see there being hundreds of "generations" soon and I don't want it to start getting too slow.

DaveHolt
  • 119
  • 1
  • 3
  • 13

2 Answers2

1

What you're looking for is the Nested set model. It allows to store hierarchical data in a relational database.

Have a look at this answer, it will give you the idea of how to find the origin of any record.

Community
  • 1
  • 1
Alexander Guz
  • 1,334
  • 12
  • 31
  • The nested set model deserves to be looked at whenever tree traversal operations are more speed critical than updates. The article you referenced is a good summary. – Walter Mitty Jul 22 '15 at 10:25
0

Bill Karwin made a nice slideshow called SQL Antipatterns Strike Back. The topic turns to techniques for handling trees starting at slide 48.

Personally, I like the closure table technique. It's easy to query, efficient and with the right triggers, it's maintenance-free.

reaanb
  • 9,806
  • 2
  • 23
  • 37