php - MySQL recursive tree search

Question

I have a database with a tree of names that can go down a total of 9 levels deep and I need to be able to search down a signal branch of the tree from any point on the branch.

Database:

+----------------------+
| id |  name  | parent |
+----------------------+
| 1  |  tom   |   0    |
| 2  |  bob   |   0    |
| 3  |  fred  |   1    |
| 4  |  tim   |   2    |
| 5  |  leo   |   4    |
| 6  |  sam   |   4    |
| 7  |  joe   |   6    |
| 8  |  jay   |   3    |
| 9  |  jim   |   5    |
+----------------------+

Tree:

tom
 fred
  jay
bob
 tim
  sam
   joe
  leo
   jim

For example:

If I search "j" from the user "bob" I should get only "joe" and "jim". If I search "j" form "leo" I should only get "jim".

I can't think of any easy way do to this so any help is appreciated.

Answer 1

You should really consider using the Modified Preorder Tree Traversal which makes such queries much easier. Here's your table expressed with MPTT. I have left the parent field, as it makes some queries easier.

+----------------------+-----+------+
| id |  name  | parent | lft | rght |
+----------------------+-----+------+
| 1  |  tom   |   0    |  1  |   6  |
| 2  |  bob   |   0    |  7  |  18  |
| 3  |  fred  |   1    |  2  |   5  |
| 4  |  tim   |   2    |  8  |  17  |
| 5  |  leo   |   4    | 12  |  15  |
| 6  |  sam   |   4    |  9  |  16  |
| 7  |  joe   |   6    | 10  |  11  |
| 8  |  jay   |   3    |  3  |   4  | 
| 9  |  jim   |   5    | 13  |  14  |
+----------------------+-----+------+

To search j from user bob you'd use the lft and rght values for bob:

SELECT * FROM table WHERE name LIKE 'j%' AND lft > 7 AND rght < 18

Implementing the logic to update lft and rght for adding, removing and reordering nodes can be a challenge (hint: use an existing library if you can) but querying will be a breeze.