如何用数据库保存多级结构的数据

shukebeita

老有人提这样的问题，还有人不断的展示自己的代码声称支持无限分类等等，为了帮助刚入门的爱好者找到实用的方案，特地贡献一篇。但是文章太长而且有很多的代码这里贴起来不太方便，欢迎大家到下面地址阅读。

http://php.linuxpack.net/show.php?type=studyphp&id=1073542478

如果有什么建议或者疑问，发在这里吧。

mikespook

收获颇多~~~

子孙总数=（左-右-1）/2

虽然一直知道这个事实可是一直都不知道这玩意有什么用~~

打印出来，值得慢慢读！

tonera

收了，支持你写书！

夜猫子

产品分类，多级的树状结构的论坛，邮件列表等许多地方我们都会遇到这样的问题：如何存储多级结构的数据？在PHP的应用中，提供后台数据存储的通常是关系型数据库，它能够保存大量的数据，提供高效的数据检索和更新服务。然而关系型数据的基本形式是纵横交错的表，是一个平面的结构，如果要将多级树状结构存储在关系型数据库里就需要进行合理的翻译工作。接下来我会将自己的所见所闻和一些实用的经验和大家探讨一下：

层级结构的数据保存在平面的数据库中基本上有两种常用设计方法：

1、毗邻目录模式(adjacency list model)

2、预排序遍历树算法(modified preorder tree traversal algorithm)

我不是计算机专业的，也没有学过什么数据结构的东西，所以这两个名字都是我自己按照字面的意思翻的，如果说错了还请多多指教。
这两个东西听着好像很吓人，其实非常容易理解。这里我用一个简单食品目录作为我们的示例数据。

我们的数据结构是这样的

以下是代码：

1. 
   
2. Food
   
3. |
   
4. |---Fruit
   
5. |    |
   
6. |    |---Red
   
7. |    |    |
   
8. |    |    |--Cherry
   
9. |    |
   
10. |    |---Yellow
    
11. |          |
    
12. |          |--Banana
    
13. |
    
14. |---Meat
    
15.      |
    
16.      |--Beef
    
17.      |
    
18.      |--Pork
    

复制代码

为了照顾那些英文一塌糊涂的PHP爱好者
Food:食物
Fruit:水果
Red:红色
Cherry:樱桃
Yellow:黄色
Banana:香蕉
Meat:肉类
Beef:牛肉
Pork:猪肉


毗邻目录模式(adjacency list model)
这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表：

以下是代码：

1. 
   
2. +-----------------------+
   
3. |   parent |    name    |
   
4. +-----------------------+
   
5. |          |    Food    |
   
6. |   Food   |   Fruit    |
   
7. |   Fruit  |    Green   |
   
8. |   Green  |    Pear    |
   
9. |   Fruit  |    Red     |
   
10. |   Red    |    Cherry  |
    
11. |   Fruit  |    Yellow  |
    
12. |   Yellow |    Banana  |
    
13. |   Food   |    Meat    |
    
14. |   Meat   |    Beef    |
    
15. |   Meat   |    Pork    |
    
16. +-----------------------+
    

复制代码

我们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了简单地描述这个问题， 这个例子中只用了name来表示一个记录。 在实际的数据库中，你需要用数字的id来标示每个节点，数据库的表结构大概应该像这样：id, parent_id, name, description。
有了这样的表我们就可以通过数据库保存整个多级树状结构了。

显示多级树
如果我们需要显示这样的一个多级结构需要一个递归函数。

以下是代码：

1. 
   
2. <?php
   
3. // $parent is the parent of the children we want to see
   
4. // $level is increased when we go deeper into the tree,
   
5. //        used to display a nice indented tree
   
6. 
   
7. function display_children($parent, $level)
   
8. {
   
9.    // 获得一个 父节点 $parent 的所有子节点
   
10.    $result = mysql_query('SELECT name FROM tree '.
    
11.                           'WHERE parent="'.$parent.'";');
    
12. 
    
13.    // 显示每个子节点
    
14.    while ($row = mysql_fetch_array($result))
    
15.    {
    
16.        // 缩进显示节点名称
    
17.        echo str_repeat('  ',$level).$row['name']."n";
    
18. 
    
19.        //再次调用这个函数显示子节点的子节点
    
20.       
    
21.        display_children($row['name'], $level+1);
    
22.    }
    
23. }
    
24. ?>;
    

复制代码

对整个结构的根节点（Food）使用这个函数就可以打印出整个多级树结构，由于Food是根节点它的父节点是空的，所以这样调用: display_children('',0)。将显示整个树的内容：

1. 
   
2. Food
   
3. Fruit
   
4. Red
   
5.   Cherry
   
6. Yellow
   
7.   Banana
   
8. Meat
   
9. Beef
   
10. Pork
    

复制代码

如果你只想显示整个结构中的一部分，比如说水果部分，就可以这样调用：display_children('Fruit',0);

几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是　"Food >; Fruit >; Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始， 查询得到它的父节点"Red"把它添加到路径中， 然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的"Food"

以下是代码：

1. 
   
2. <?php
   
3. // $node 是那个最深的节点
   
4. function get_path($node)
   
5. {
   
6.    // 查询这个节点的父节点
   
7.    $result = mysql_query('SELECT parent FROM tree '.
   
8.                           'WHERE name="'.$node.'";');
   
9.    $row = mysql_fetch_array($result);
   
10. 
    
11.    // 用一个数组保存路径
    
12.    $path = array();
    
13. 
    
14.    // 如果不是根节点则继续向上查询
    
15.    // (根节点没有父节点)
    
16.    if ($row['parent']!='')
    
17.    {
    
18.        // the last part of the path to $node, is the name
    
19.        // of the parent of $node
    
20.        $path[] = $row['parent'];
    
21. 
    
22.        // we should add the path to the parent of this node
    
23.        // to the path
    
24.        $path = array_merge(get_path($row['parent']), $path);
    
25.    }
    
26. 
    
27.    // return the path
    
28.    return $path;
    
29. }
    
30. ?>;
    

复制代码

如果对"Cherry"使用这个函数：print_r(get_path('Cherry'))，就会得到这样的一个数组了：

1. 
   
2. Array
   
3. (
   
4.   [0] =>; Food
   
5.   [1] =>; Fruit
   
6.   [2] =>; Red
   
7. )
   

复制代码

接下来如何把它打印成你希望的格式，就是你的事情了。

缺点：
这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。

现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm)
这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。

我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的手指）。
这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点

以下是代码：

1. 
   
2.                                 1 Food 18
   
3.                                     |
   
4.                 +-------------------------------------------+
   
5.                 |                                                       |
   
6.             2 Fruit 11                                    12 Meat 17
   
7.                 |                                                       |
   
8.     +------------------------+                   +-----------------------+
   
9.     |                                |                   |                              |
   
10. 3 Red 6               7 Yellow 10         13 Beef 14            15 Pork 16
    
11.     |                                |
    
12. 4 Cherry 5               8 Banana 9
    

复制代码

这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我们看一看下面整理过的数据表。

以下是代码：

1. 
   
2. +-----------------------+-----+-----+
   
3. |   parent |    name  | lft   | rgt |
   
4. +-----------------------+-----+-----+
   
5. |              |    Food    | 1   | 18  |
   
6. |   Food   |   Fruit      | 2   | 11  |
   
7. |   Fruit    |    Red      | 3   |  6  |
   
8. |   Red     |    Cherry  | 4   |  5  |
   
9. |   Fruit    |    Yellow  | 7   | 10  |
   
10. |   Yellow |    Banana | 8   |  9  |
    
11. |   Food   |    Meat     | 12  | 17  |
    
12. |   Meat   |    Beef     | 13  | 14  |
    
13. |   Meat   |    Pork     | 15  | 16  |
    
14. +-----------------------+-----+-----+
    

复制代码

注意：由于"left"和"right"在 SQL中有特殊的意义，所以我们需要用"lft"和"rgt"来表示左右字段。 另外这种结构中不再需要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。

以下是代码：

1. 
   
2. +------------+-----+-----+
   
3. |    name    | lft | rgt |
   
4. +------------+-----+-----+
   
5. |    Food    | 1   | 18  |
   
6. |   Fruit    | 2   | 11  |
   
7. |    Red     | 3   |  6  |
   
8. |    Cherry  | 4   |  5  |
   
9. |    Yellow  | 7   | 10  |
   
10. |    Banana  | 8   |  9  |
    
11. |    Meat    | 12  | 17  |
    
12. |    Beef    | 13  | 14  |
    
13. |    Pork    | 15  | 16  |
    
14. +------------+-----+-----+
    

复制代码

好了我们现在可以从数据库中获取数据了，例如我们需要得到"Fruit"项下的所有所有节点就可以这样写查询语句：
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
这个查询得到了以下的结果。

以下是代码：

1. 
   
2. +------------+-----+-----+
   
3. |    name    | lft | rgt |
   
4. +------------+-----+-----+
   
5. |   Fruit    | 2   | 11  |
   
6. |    Red     | 3   |  6  |
   
7. |    Cherry  | 4   |  5  |
   
8. |    Yellow  | 7   | 10  |
   
9. |    Banana  | 8   |  9  |
   
10. +------------+-----+-----+
    

复制代码

看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;


剩下的问题如何显示层级的缩进了。

以下是代码：

1. 
   
2. <?php
   
3. function display_tree($root)
   
4. {
   
5.    // 得到根节点的左右值
   
6.    $result = mysql_query('SELECT lft, rgt FROM tree '.'WHERE name="'.$root.'";');
   
7.    $row = mysql_fetch_array($result);
   
8. 
   
9.    // 准备一个空的右值堆栈
   
10.    $right = array();
    
11. 
    
12.    // 获得根基点的所有子孙节点
    
13.    $result = mysql_query('SELECT name, lft, rgt FROM tree '.
    
14.                           'WHERE lft BETWEEN '.$row['lft'].' AND '.
    
15.                           $row['rgt'].' ORDER BY lft ASC;');
    
16. 
    
17.    // 显示每一行
    
18.    while ($row = mysql_fetch_array($result))
    
19.    {
    
20.        // only check stack if there is one
    
21.        if (count($right)>;0)
    
22.    {
    
23.            // 检查我们是否应该将节点移出堆栈
    
24.            while ($right[count($right)-1]<$row['rgt'])
    
25.    {
    
26.                array_pop($right);
    
27.            }
    
28.        }
    
29. 
    
30.        // 缩进显示节点的名称
    
31.        echo str_repeat('  ',count($right)).$row['name']."n";
    
32. 
    
33.        // 将这个节点加入到堆栈中
    
34.        $right[] = $row['rgt'];
    
35.    }
    
36. }
    
37. ?>;
    

复制代码

如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些，因为只有2次数据库查询。

要获知一个节点的路径就更简单了，如果我们想知道Cherry 的路径就利用它的左右值4和5来做一个查询。

SELECT name FROM tree WHERE lft < 4 AND rgt >; 5 ORDER BY lft ASC;

这样就会得到以下的结果：

以下是代码：

1. 
   
2. +------------+
   
3. |    name    |
   
4. +------------+
   
5. |   Food     |
   
6. |   Fruit    |
   
7. |    Red     |
   
8. +------------+
   

复制代码

那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2
descendants = (right – left - 1) / 2
不相信？自己算一算啦。
用这个简单的公式，我们可以很快的算出"Fruit 2-11"节点有4个子孙节点，而"Banana 8-9"节点没有子孙节点，也就是说它不是一个父节点了。

很神奇吧？虽然我已经多次用过这个方法，但是每次这样做的时候还是感到很神奇。

这的确是个很好的办法，但是有什么办法能够帮我们建立这样有左右值的数据表呢？这里再介绍一个函数给大家，这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。

以下是代码：

1. 
   
2. <?php
   
3. function rebuild_tree($parent, $left) {
   
4.    // the right value of this node is the left value + 1
   
5.    $right = $left+1;
   
6. 
   
7.    // get all children of this node
   
8.    $result = mysql_query('SELECT name FROM tree '.
   
9.                           'WHERE parent="'.$parent.'";');
   
10.    while ($row = mysql_fetch_array($result)) {
    
11.        // recursive execution of this function for each
    
12.        // child of this node
    
13.        // $right is the current right value, which is
    
14.        // incremented by the rebuild_tree function
    
15.        $right = rebuild_tree($row['name'], $right);
    
16.    }
    
17. 
    
18.    // we've got the left value, and now that we've processed
    
19.    // the children of this node we also know the right value
    
20.    mysql_query('UPDATE tree SET lft='.$left.', rgt='.
    
21.                 $right.' WHERE name="'.$parent.'";');
    
22. 
    
23.    // return the right value of this node + 1
    
24.    return $right+1;
    
25. }
    
26. ?>;
    

复制代码

当然这个函数是一个递归函数，我们需要从根节点开始运行这个函数来重建一个带有左右值的树

rebuild_tree('Food',1);

这个函数看上去有些复杂，但是它的作用和手工对表进行编号一样，就是将立体多层结构的转换成一个带有左右值的数据表。

那么对于这样的结构我们该如何增加，更新和删除一个节点呢？

增加一个节点一般有两种方法：

第一种，保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。

第二种，效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果"Strawberry"（草莓）它将成为"Red"节点的最后一个子节点。首先我们需要为它腾出一些空间。"Red"的右值应当从6改成8，"Yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点 （5 是"Red"最后一个子节点的右值） 加上2。 所以我们这样进行数据库操作：

UPDATE tree SET rgt=rgt+2 WHERE rgt>;5;
UPDATE tree SET lft=lft+2 WHERE lft>;5;

这样就为新插入的值腾出了空间，现在可以在腾出的空间里建立一个新的数据节点了， 它的左右值分别是6和7

INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';

再做一次查询看看吧！怎么样？很快吧。

好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。

另外，如果数据库支持的话 你还可以将rebuild_tree()和 腾出空间的操作写成数据库端的触发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加新节点的SQL语句会变得更加简单。

shukebeita

能不能把那些图表对对齐，尤其是那个代标号的树状图，否则大家看不懂了。

shukebeita

原帖由 "longnetpro" 发表：
2、modified preorder tree traversal algorithm - 修改过的先序遍历树算法（亦即先根遍历树算法）
注：modified 意为“修改过的”
preorder tree traversal 专业术语“先序遍历树”，preorder是“先于...的顺序”的意思，pre- 是词前缀，意为“先”，order 意为“顺序”；

多谢支持，这些方法也是我从外国的书里学到的，我的确不太懂这些术语，不过我对 modified preorder tree traversal algorithm 这一句还是有我的想法。

1、我不是计算级或者数学专业的，单是从字面上理解我想大概有一种算法叫做preorder tree traversal algorithm ，而这里用到的是它的一个修改版本，所以称其为modified。

2、pre是先的意思没错，但是order在这里更准确地说应该是排序，排定顺序的意思。所以就是说这个树是“预先排好序号“的树。

最主要的是目前暂只适用于二叉树，不适合于多叉树。

不知道你说的多叉树是不是说像下面的样子

1. 
   
2.                                 1 Food 20
   
3.                                     |
   
4.                 +-------------------------------------------+
   
5.                 |                         |                             |
   
6.             2 Fruit 11     12  Vegetable 13    14 Meat 19
   
7.                 |                                                       |
   
8.     +------------------------+                   +-----------------------+
   
9.     |                                |                   |                              |
   
10. 3 Red 6               7 Yellow 10         15 Beef 16            17 Pork 18
    
11.     |                                |
    
12. 4 Cherry 5               8 Banana 9
    

复制代码

如果是这样的话，你完全可以放心，这种办法没有问题，一样适用。我已经试过多次。

但建树的时候还要用到递归

所以这种方法对于经常需要查询，但是很少增加和更新的数据（比如产品，书籍的多级分类）更为合适，一旦建立很少变动。

有时也会影响到计算所有子节点的数目，因为数据库操作写入可能会写错。

这就是需要transaction(事务处理)的地方了。

tonera

今天终于遇到关于多级分类查询和数据设计的问题了。再次认真看了一遍楼主的文章，真是恍然大悟、茅塞顿开啊。我没读多少书，没学过离散数学，呵呵。我觉得这个问题实在讨论得太有意义了。

这个问题其实并不只是PHP的问题，更多的是数据设计的问题，精巧的数据结构实在太重要了。

我开始也只想到用递归来处理，但效率实在太差。层次越多，效率越低。如果用先序遍历树算法(modified preorder tree traversal algorithm) 。则相对来说，层次越多，表现越好。呵呵呵呵。

唯一不爽的就是在编辑节点时比较麻烦。
shuke，能不能抽空写个树构造类，以后大家都用这个算啦。呵呵。
我试试看能不能完成，等我搞好了再贴。