php - MySQL递归树搜索

Question

我有一个数据库，其中有一棵名称树，可以深入到总共 9 层，我需要能够从树的任何一点搜索树的信号分支。

数据库:

+----------------------+
| 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    |
+----------------------+

树:

tom
 fred
  jay
bob
 tim
  sam
   joe
  leo
   jim

例如:

如果我从用户“bob”搜索“j”，我应该只会得到“joe”和“jim”。如果我从“leo”中搜索“j”，我应该只会得到“jim”。

我想不出有什么简单的方法可以做到这一点，因此不胜感激。

Answer 1

你真的应该考虑使用 Modified Preorder Tree Traversal这使得此类查询变得更加容易。这是用 MPTT 表示的表格。我离开了父字段，因为它使一些查询更容易。

+----------------------+-----+------+
| 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  |
+----------------------+-----+------+

要从用户 bob 中搜索 j，您需要为 使用 lft 和 rght 值鲍勃:

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

实现逻辑来更新 lft 和 rght 以添加、删除和重新排序节点可能是一个挑战(提示:如果可以，请使用现有库)但查询会轻而易举。