想用这个算法的缘由起源于一个帖子：http://bbs.csdn.net/topics/392012391node

预排序遍历树算法(modified preorder tree traversal algorithm) 这种方法你们可能接触的比较少，初次使用也不像上面的方法（邻接表）容易理解，可是因为这种方法不使用递归查询算法，有更高的查询效率。算法

咱们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 而后沿着这个树继续向下 在 Fruit 的左侧写上 2 而后继续前进，沿着整个树的边缘给每个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你能够看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的手指）。 sql

这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 一样，咱们能够看到 全部左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点数据库

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

注意：因为"left"和"right"在 SQL中有特殊的意义，因此咱们须要用"lft"和"rgt"来表示左右字段。 另外这种结构中再也不须要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。 函数

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;ui

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

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

那么某个节点到底有多少子孙节点呢？很简单，子孙总数=(右值-左值-1)/2 code

descendants = (right – left - 1) / 2 ，若是不是很清楚这个公式，那就去翻下书，咱们在上数据结构写的很清楚！

添加同一层次的节点的方法以下：

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;

添加树的子节点的方法以下： 

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;

每次插入节点以后均可以用如下SQL进行查看验证： 

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;

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

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;

这种方式就是有点难的理解，可是适合数据量很大规模使用，查看全部的结构只须要两条SQL语句就能够了，在添加节点和删除节点的时候略显麻烦，不过相对于效率来讲仍是值得的。

文章转载自http://my.oschina.net/XYleung/blog/99604