MySqlInfiniti分类布局,预排序遍历树算法

MySql无限分类结构

mysql左右值无限分类原理及实现

预排序遍历树算法

 无限分类是我们开发中非常常见的应用,像论坛的的版块,CMS的类别,应用的地方特别多。
  我们最常见最简单的方法就是在MySql里ID ,parentID,name:

 

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

优点是简单,结构简单。
缺点是效率不高,因为每一次递归都要查询数据库,几百条数据库时就不是很快了!

无限分类是我们开发中非常常见的应用,我们最常见最简单的方法就是在MySql里id
,name,f_id。 优点是简单,结构简单。
缺点是效率不高,因为每一次递归都要查询数据库,几百条数据库时就不是很快了!
  www.2cto.com  

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

 
存储树是一种常见的问题,多种解决方案。主要有两种方法:邻接表的模型,并修改树前序遍历算法。
 
我们将探讨这两种方法的节能等级的数据。我会使用树从一个虚构的网上食品商店作为一个例子。这食品商店组织其食品类,通过颜色和类型。这棵树看起来像这样:
必发88手机客户端 1
 
下面我们将用另外一种方法,这就是预排序遍历树算法(modified preorder tree traversal algorithm) 。
 
这种方法大家可能接触的比较少,初次使用也不像上面的方法容易理解,但是由于这种方法不使用递归查询算法,有更高的查询效率。
 
我们首先将多级数据按照下面的方式画在纸上,在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进,
沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结
构。(没有看懂?用你的手指指着数字从1数到18就明白怎么回事了。还不明白,再数一遍,注意移动你的手指)。 
 
这些数字标明了各个节点之间的关系,”Red”的号是3和6,它是 ”Food” 1-18 的子孙节点。 同样,我们可以看到 所有左值大于2和右值小于11的节点 都是”Fruit” 2-11 的子孙节点 
如图所示:
必发88手机客户端 2
 
这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。 
必发88手机客户端 3
 
注意:由于”left”和”right”在 SQL中有特殊的意义,所以我们需要用”lft”和”rgt”来表示左右字段。 另外这种结构中不再需要”parent”字段来表示树状结构。也就是 说下面这样的表结构就足够了。 
  SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
必发88手机客户端 4
 
看到了吧,只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构,我们还需要对这样的查询进行排序。用节点的左值进行排序: 
  SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
  那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2 
descendants = (right – left – 1) / 2 ,如果不是很清楚这个公式,那就去翻下书,我们在上数据结构写的很清楚!
  添加同一层次的节点的方法如下:

存储树是一种常见的问题,多种解决方案。主要有两种方法:邻接表的模型,并修改树前序遍历算法。

以下是代码:                          1 Food 18

 LOCK TABLE nested_category WRITE; 
 
SELECT @myRight := rgt FROM nested_category 
WHERE name = ‘Cherry’; 
 
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight; 
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight; 
 
INSERT INTO nested_category(name, lft, rgt) VALUES(‘Strawberry’,
@myRight + 1, @myRight + 2); 
 
UNLOCK TABLES;

我们将探讨这两种方法的节能等级的数据。我会使用树从一个虚构的网上食品商店作为一个例子。这食品商店组织其食品类,通过颜色和类型。这棵树看起来像这样:
  www.2cto.com  

                             |

  添加树的子节点的方法如下:

必发88手机客户端 5

            +——————————+

LOCK TABLE nested_category WRITE; 
 
SELECT @myLeft := lft FROM nested_category 
 
WHERE name = ‘Beef’; 
 
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft ; 
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft ; 
 
INSERT INTO nested_category(name, lft, rgt) VALUES(‘charqui’, @myLeft +
1, @myLeft + 2); 
 
UNLOCK TABLES; 

下面我们将用另外一种方法,这就是预排序遍历树算法(modified preorder tree
traversal algorithm)
这种方法大家可能接触的比较少,初次使用也不像上面的方法容易理解,但是由于这种方法不使用递归查询算法,有更高的查询效率。
我们首先将多级数据按照下面的方式画在纸上,在根节点Food的左侧写上 1
然后沿着这个树继续向下 在 Fruit 的左侧写上 2
然后继续前进,沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food
右侧的 18。
在下面的这张图中你可以看到整个标好了数字的多级结构。(没有看懂?用你的手指指着数字从1数到18就明白怎么回事了。还不明白,再数一遍,注意移动你的
手指)。 这些数字标明了各个节点之间的关系,”Red”的号是3和6,它是 “Food”
1-18 的子孙节点。 同样,我们可以看到 所有左值大于2和右值小于11的节点
都是”Fruit” 2-11 的子孙节点

            |                              |

  每次插入节点之后都可以用以下SQL进行查看验证:

如图所示:

        2 Fruit 11                     12 Meat 17

SELECT CONCAT( REPEAT( ‘ ‘, (COUNT(parent.name) – 1) ), node.name) AS
name 
FROM nested_category AS node, 
nested_category AS parent 
WHERE node.lft BETWEEN parent.lft AND parent.rgt 
GROUP BY node.name 
ORDER BY node.lft;

必发88手机客户端 6

            |                              |

  删除节点的方法,稍微有点麻烦是有个中间变量,如下:

这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。 必发88手机客户端 7

    +————-+                 +————+

LOCK TABLE nested_category WRITE;  
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt – lft + 1 
FROM nested_category 
WHERE name = ‘Cherry’;  
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;  
UPDATE nested_category SET rgt = rgt – @myWidth WHERE rgt >
@myRight;  
UPDATE nested_category SET lft = lft – @myWidth WHERE lft >
@myRight; 
 
UNLOCK TABLES;

注意:由于”left”和”right”在
SQL中有特殊的意义,所以我们需要用”lft”和”rgt”来表示左右字段。
另外这种结构中不再需要”parent”字段来表示树状结构。也就是
说下面这样的表结构就足够了。 SELECT * FROM tree WHERE lft BETWEEN 2 AND
11;

    |             |                 |            |

 
这种方式就是有点难的理解,但是适合数据量很大规模使用,查看所有的结构只需要两条SQL语句就可以了,在添加节点和删除节点的时候略显麻烦,不过相对于
效率来说还是值得的,这次发现让我发现了数据库结构真的很有用,但是我在学校学的树基本上都忘记了,这次遇到这个问题才应用到项目中!

必发88手机客户端 8

3 Red 6      7 Yellow 10       13 Beef 14   15 Pork 16

无限分类是我们开发中非常常见的应用,像论坛的的版块,CMS的类别,应用的地方特别多。
我们最常见最简单的方法就是…

只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构,我们还需要对这样的查询进行排序。用节点的左值进行排序:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2
descendants = (right – left – 1) / 2
,如果不是很清楚这个公式,那就去翻下书,我们在上数据结构写的很清楚!

    |             |

添加同一层次的节点的方法如下: Sql代码 1. LOCK TABLE nested_category
WRITE; 
2. 
3. 

4 Cherry 5    8 Banana 9
复制代码这样整个树状结构可以通过左右值来存储到数据库中。继续之前,我们看一看下面整理过的数据表。

  1. SELECT @myRight := rgt FROM nested_category 
  2. WHERE name = ‘Cherry’; 
    6. 
    7. 
    8. 
  3. UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight; 
  4. UPDATE nested_category SET lft = lft + 2 WHERE lft >
    @myRight; 
    11. 
  5. INSERT INTO nested_category(name, lft, rgt) VALUES(‘Strawberry’,
    @myRight + 1, @myRight + 2); 
    13. 
  6. UNLOCK TABLES;

以下是代码: +———-+————+—–+—–+

添加树的子节点的方法如下: Sql代码 1. LOCK TABLE nested_category
WRITE; 
2. 

|  parent  |    name    | lft | rgt |

  1. SELECT @myLeft := lft FROM nested_category 
    4. 
  2. WHERE name = ‘Beef’; 
    6. 
  3. UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myLeft ; 
  4. UPDATE nested_category SET lft = lft + 2 WHERE lft > @myLeft ; 
    9. 
  5. INSERT INTO nested_category(name, lft, rgt)
    VALUES(‘charqui’, @myLeft + 1,@myLeft + 2); 
    11. 
  6. UNLOCK TABLES;

必发88手机客户端,+———-+————+—–+—–+

每次插入节点之后都可以用以下SQL进行查看验证: Sql代码 1. SELECT CONCAT(
REPEAT( ‘ ‘, (COUNT(parent.name) – 1) ), node.name) AS name 

|          |    Food    | 1   | 18  |

  1. FROM nested_category AS node, 
  2. nested_category AS parent 
  3. WHERE node.lft BETWEEN parent.lft AND parent.rgt 
  4. GROUP BY node.name 
  5. ORDER BY node.lft;

|   Food   |   Fruit    | 2   | 11  |

删除节点的方法,稍微有点麻烦是有个中间变量,如下: Sql代码 1. LOCK TABLE
nested_category WRITE; 
2. 
3. 

|   Fruit  |    Red     | 3   |  6  |

  1. SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt – lft + 1 
  2. FROM nested_category 
  3. WHERE name = ‘Cherry’; 
    7. 
    8. 
  4. DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND
    @myRight; 
    10. 
    11. 
  5. UPDATE nested_category SET rgt = rgt – @myWidth WHERE rgt >
    @myRight; 
  6. UPDATE nested_category SET lft = lft – @myWidth WHERE lft >
    @myRight; 
    14. 
  7. UNLOCK TABLES; 
    这种方式就是有点难的理解,但是适合数据量很大规模使用,查看所有的结构只需要两条SQL语句就可以了,在添加节点和删除节点的时候略显麻烦,不过相对于效率来说还是值得的

|   Red    |    Cherry  | 4   |  5  |

无限分类是我们开发中非常常见的应用,我们最常见最简单的方法就是在MySql里id
,name,f_id。 优点是简单,结…

|   Fruit  |    Yellow  | 7   | 10  |

|   Yellow |    Banana  | 8   |  9  |

|   Food   |    Meat    | 12  | 17  |

|   Meat   |    Beef    | 13  | 14  |

|   Meat   |    Pork    | 15  | 16  |

+———-+————+—–+—–+
复制代码注意:由于”left”和”right”在
SQL中有特殊的意义,所以我们需要用”lft”和”rgt”来表示左右字段。
另外这种结构中不再需要”parent”字段来表示树状结构。也就是
说下面这样的表结构就足够了。

以下是代码: +————+—–+—–+

|    name    | lft | rgt |

+————+—–+—–+

|    Food    | 1   | 18  |

|    Fruit   | 2   | 11  |

|    Red     | 3   |  6  |

|    Cherry  | 4   |  5  |

|    Yellow  | 7   | 10  |

|    Banana  | 8   |  9  |

|    Meat    | 12  | 17  |

|    Beef    | 13  | 14  |

|    Pork    | 15  | 16  |

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

以下是代码: +————+—–+—–+

|    name    | lft | rgt |

+————+—–+—–+

|    Fruit   | 2   | 11  |

|    Red     | 3   |  6  |

|    Cherry  | 4   |  5  |

|    Yellow  | 7   | 10  |

|    Banana  | 8   |  9  |

+————+—–+—–+
复制代码看到了吧,只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构,我们还需要对这样的查询进行排序。用节点的左值进行排序:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
复制代码剩下的问题如何显示层级的缩进了。
以下是代码:
<?php

function display_tree($root) {

    // 得到根节点的左右值

    $result = mysql_query(“

        SELECT lft, rgt

        FROM tree

        WHERE name = ‘” . $root . “‘

        ;”

    );

    $row = mysql_fetch_array($result);

    // 准备一个空的右值堆栈

    $right = array();

    // 获得根基点的所有子孙节点

    $result = mysql_query(“

        SELECT name, lft, rgt

        FROM tree

        WHERE lft BETWEEN ‘” . $row[‘lft’] . “‘ AND ‘” . $row[‘rgt’]
.”‘

        ORDER BY lft ASC

        ;”

    );

    // 显示每一行

    while ($row = mysql_fetch_array($result)) {

        // only check stack if there is one

        if (count($right) > 0) {

            // 检查我们是否应该将节点移出堆栈

            while ($right[count($right) – 1] < $row[‘rgt’]) {

                array_pop($right);

            }

        }

        // 缩进显示节点的名称

        echo str_repeat(‘  ‘,count($right)) . $row[‘name’] . “n”;

        // 将这个节点加入到堆栈中

        $right[] = $row[‘rgt’];

    }

}

?>

复制代码如果你运行一下以上的函数就会得到和递归函数一样的结果。只是我们的这个新的函数可能会更快一些,因为只有2次数据库查询。
要获知一个节点的路径就更简单了,如果我们想知道Cherry
的路径就利用它的左右值4和5来做一个查询。 SELECT name FROM tree WHERE lft
< 4 AND rgt >; 5 ORDER BY lft ASC;
复制代码这样就会得到以下的结果:

以下是代码: +————+

|    name    |

+————+

|    Food    |

|    Fruit   |

|    Red     |

+————+
复制代码那么某个节点到底有多少子孙节点呢?很简单,子孙总数=(右值-左值-1)/2
descendants = (right – left – 1) / 2
复制代码不相信?自己算一算啦。
用这个简单的公式,我们可以很快的算出”Fruit
2-11″节点有4个子孙节点,而”Banana
8-9″节点没有子孙节点,也就是说它不是一个父节点了。
很神奇吧?虽然我已经多次用过这个方法,但是每次这样做的时候还是感到很神奇。
这的确是个很好的办法,但是有什么办法能够帮我们建立这样有左右值的数据表呢?这里再介绍一个函数给大家,这个函数可以将name和parent结构的表自动转换成带有左右值的数据表。
以下是代码:
<?php

function rebuild_tree($parent, $left) {

    // the right value of this node is the left value + 1

    $right = $left+1;

    // get all children of this node

    $result = mysql_query(“

        SELECT name

        FROM tree

        WHERE parent = ‘” . $parent . “‘

        ;”

    );

    while ($row = mysql_fetch_array($result)) {

        // recursive execution of this function for each

        // child of this node

        // $right is the current right value, which is

        // incremented by the rebuild_tree function

        $right = rebuild_tree($row[‘name’], $right);

    }

    // we’ve got the left value, and now that we’ve processed

    // the children of this node we also know the right value

    mysql_query(“

        UPDATE tree

        SET

            lft = ‘” . $left . “‘,

            rgt= ‘” . $right . “‘

        WHERE name = ‘” . $parent . “‘

        ;”

    );

    // return the right value of this node + 1

    return $right + 1;

}

?>

复制代码当然这个函数是一个递归函数,我们需要从根节点开始运行这个函数来重建一个带有左右值的树
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语句会变得更加简单。