The Nested Set Model

原理：

    我们先把树按照水平方式摆开。从根节点开始（“Food”），然后他的左边写上1。然后按照树的顺序（从上到下）给“Fruit”的左边写上2。这样，你沿着树的边界走啊走（这就是“遍历”），然后同时在每个节点的左边和右边写上数字。最后，我们回到了根节点“Food”在右边写上18。下面是标上了数字的树，同时把遍历的顺序用箭头标出来了。

 

    我们称这些数字为左值和右值（如，“Food”的左值是1，右值是18）。正如你所见，这些数字按时了每个节点之间的关系。因为“Red”有3和6两个值，所以，它是有拥有1-18值的“Food”节点的后续。同样的，我们可以推断所有左值大于2并且右值小于11的节点，都是有2-11的“Fruit” 节点的后续。这样，树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做“改进前序遍历树”算法。

表结构设计：

 

常用的操作：

下面列出一些常用操作的SQL语句

返回完整的树（Retrieving a Full Tree）

SELECT node.name
  FROM nested_category node, nested_category parent
 WHERE node.lft BETWEEN parent.lft AND parent.rgt
   AND parent.name = 'electronics'
 ORDER BY node.lft

返回某结点的子树（Find the Immediate Subordinates of a Node）

SELECT V.*
  FROM (SELECT node.name,
               (COUNT(parent.name) - (AVG(sub_tree.depth) + 1)) depth
          FROM nested_category node,
               nested_category parent,
               nested_category sub_parent,
               (SELECT V.*
                  FROM (SELECT node.name, (COUNT(parent.name) - 1) depth
                          FROM nested_category node, nested_category parent
                         WHERE node.lft BETWEEN parent.lft AND parent.rgt
                           AND node.name = 'portable electronics'
                         GROUP BY node.name) V,
                       nested_category T
                 WHERE V.name = T.name
                 ORDER BY T.lft) sub_tree
         WHERE node.lft BETWEEN parent.lft AND parent.rgt
           AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
           AND sub_parent.name = sub_tree.name
         GROUP BY node.name) V,
       nested_category T
 WHERE V.name = T.name
   and V.depth <= 1
   and V.depth > 0
 ORDER BY T.Lft

返回某结点的祖谱路径（Retrieving a Single Path）

SELECT parent.name
  FROM nested_category node, nested_category parent
 WHERE node.lft BETWEEN parent.lft AND parent.rgt
   AND node.name = 'flash'
 ORDER BY node.lft

返回所有节点的深度（Finding the Depth of the Nodes）

SELECT V.*
  FROM (SELECT node.name, (COUNT(parent.name) - 1) depth
          FROM nested_category node, nested_category parent
         WHERE node.lft BETWEEN parent.lft AND parent.rgt
         GROUP BY node.name) V,
       nested_category T
 WHERE V.name = T.name
 ORDER BY T.Lft

返回子树的深度（Depth of a Sub-Tree）

SELECT V.*
  FROM (SELECT node.name,
               (COUNT(parent.name) - (AVG(sub_tree.depth) + 1)) depth
          FROM nested_category node,
               nested_category parent,
               nested_category sub_parent,
               (SELECT V.*
                  FROM (SELECT node.name, (COUNT(parent.name) - 1) depth
                          FROM nested_category node, nested_category parent
                         WHERE node.lft BETWEEN parent.lft AND parent.rgt
                           AND node.name = 'portable electronics'
                         GROUP BY node.name) V,
                       nested_category T
                 WHERE V.name = T.name
                 ORDER BY T.lft) sub_tree
         WHERE node.lft BETWEEN parent.lft AND parent.rgt
           AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
           AND sub_parent.name = sub_tree.name
         GROUP BY node.name) V,
       nested_category T
 WHERE V.name = T.name
 ORDER BY T.Lft

返回所有的叶子节点（Finding all the Leaf Nodes）

SELECT name FROM nested_category WHERE rgt = lft + 1

插入节点（Adding New Nodes）

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category WHERE name = 'TELEVISIONS';

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
  ('GAME CONSOLES', @myRight + 1, @myRight + 2);

UNLOCK TABLES;

删除节点（Deleting Nodes）

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
  FROM nested_category
 WHERE name = 'GAME CONSOLES';

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;

评论

1 楼 liuqq 2011-12-08  

一直用Oracle开发，几乎没有接触过其他数据库。使用Mysql后的确对树的处理变得非常困难。
楼主的文章不错。
但是这个SQL语句没有优化，比如指定深度查询子树这个，我调整了下：
我这里的title等同原SQL的name字段。
/*查询下级节点的同辈元素*/
SELECT V.*
  FROM (SELECT node.title, node.parent,node.lft,
               (COUNT(parent.title) - (AVG(sub_tree.depth) + 1)) depth
          FROM nested_category node,
               nested_category parent,
               (SELECT node.title, (COUNT(parent.title) - 1) depth, node.lft, node.rgt
                          FROM nested_category node, nested_category parent
                         WHERE node.lft BETWEEN parent.lft AND parent.rgt
                           AND node.title = 'Food'
                         GROUP BY node.title) sub_tree
         WHERE node.lft BETWEEN parent.lft AND parent.rgt
           AND node.lft BETWEEN sub_tree.lft AND sub_tree.rgt
         GROUP BY node.title) V
WHERE /* 树的深度*/
V.depth <= 9
   and V.depth >= 0
ORDER BY V.lft