预排序遍历树算法

嵌套集模型（The Nested Set Model）示意图

上图表现了数据新的层级关系，关系表和数据如下

CREATE TABLE nested_category (
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
lft INT NOT NULL,
rgt INT NOT NULL
);


INSERT INTO nested_category
VALUES(1,'ELECTRONICS',1,20),(2,'TELEVISIONS',2,9),(3,'TUBE',3,4),
(4,'LCD',5,6),(5,'PLASMA',7,8),(6,'PORTABLE ELECTRONICS',10,19),
(7,'MP3 PLAYERS',11,14),(8,'FLASH',12,13),
(9,'CD PLAYERS',15,16),(10,'2 WAY RADIOS',17,18);


SELECT * FROM nested_category ORDER BY category_id;

这里将 left,right 修改为 lft,rgt因为这两个词在MYSQL中属于关键字下面我们将插入的数据标识在图上：

同样，我们将数据标识在原来的结构上：

怎么样，是不是很明确了

下面使我自己标定一种形式，方便理解

[1
      [2
           [3 4]
           [5 6]
           [7 8]
      9]
      [10
           [11
                 [12 13]
           14]
           [15 16]
           [17 18]
      19]
20]

--遍历整个树，查询子集条件：左边 > 父级L，右边 < 父级R

 1 SELECT node.name
 2 FROM nested_category AS node,
 3 nested_category AS parent
 4 WHERE node.lft BETWEEN parent.lft AND parent.rgt
 5 AND parent.name = 'ELECTRONICS'
 6 ORDER BY node.lft;
 7 
 8 +----------------------+
 9 | name                 |
10 +----------------------+
11 | ELECTRONICS          |
12 | TELEVISIONS          |
13 | TUBE                 |
14 | LCD                  |
15 | PLASMA               |
16 | PORTABLE ELECTRONICS |
17 | MP3 PLAYERS          |
18 | FLASH                |
19 | CD PLAYERS           |
20 | 2 WAY RADIOS         |
21 +----------------------+

--查询所有无分支的节点条件：右边 = 左边L + 1

1 SELECT name
2 FROM nested_category
3 WHERE rgt = lft + 1;

--查询某个字节点到根节点的路径

 1 SELECT parent.name
 2 FROM nested_category AS node,
 3 nested_category AS parent
 4 WHERE node.lft BETWEEN parent.lft AND parent.rgt
 5 AND node.name = 'FLASH'
 6 ORDER BY parent.lft;
 7 
 8 
 9 SELECT node.name, (COUNT(parent.name) - 1) AS depth
10 FROM nested_category AS node,
11 nested_category AS parent
12 WHERE node.lft BETWEEN parent.lft AND parent.rgt
13 GROUP BY node.name
14 ORDER BY node.lft;

--查询子节点的深度

 1 SELECT node.name, (COUNT(parent.name) - (sub_tree.depth + 1)) AS depth
 2 FROM nested_category AS node,
 3     nested_category AS parent,
 4     nested_category AS sub_parent,
 5     (
 6         SELECT node.name, (COUNT(parent.name) - 1) AS depth
 7         FROM nested_category AS node,
 8         nested_category AS parent
 9         WHERE node.lft BETWEEN parent.lft AND parent.rgt
10         AND node.name = 'PORTABLE ELECTRONICS'
11         GROUP BY node.name
12         ORDER BY node.lft
13     )AS sub_tree
14 WHERE node.lft BETWEEN parent.lft AND parent.rgt
15     AND node.lft BETWEEN sub_parent.lft AND sub_parent.rgt
16     AND sub_parent.name = sub_tree.name
17 GROUP BY node.name
18 ORDER BY node.lft;

--插入新节点

1 LOCK TABLE nested_category WRITE;
2 SELECT @myRight := rgt FROM nested_category
3 WHERE name = 'TELEVISIONS';
4 UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
5 UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
6 INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1,@myRight + 2);
7 UNLOCK TABLES;

先找到右边的值，例如节点TELEVISIONS右边的值

1 LOCK TABLE nested_category WRITE;
2 SELECT @myRight := rgt FROM nested_category
3 WHERE name = 'TELEVISIONS';

在 R = 9（L8, R9）与 L = 10（L10，R11）节点之间插入一个新节点

那么所有左值和右值 > 9 的节点的左值和右值需要 + 2

1 UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
2 UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;

左值 = 插入位置左边节点记录的右值 + 1，右值 = 插入位置左边节点记录的右值 + 2

1 INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1,@myRight + 2);
2 UNLOCK TABLES;

新节点右边的节点（L10，R11）左值右值都需要 + 2 那么插入后的新值为 L12 R13
新节点的左值为 9 + 1 = 10 右值为 9 + 2 = 11

--删除新节点

删除节点的算法与添加一个节点的算法相反

删除一个没有子节点的节点

1 LOCK TABLE nested_category WRITE;
2 SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
3 FROM nested_category
4 WHERE name = 'GAME CONSOLES';
5 DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
6 UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
7 UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
8 UNLOCK TABLES;

删除一个分支节点和它所有的子节点

1 LOCK TABLE nested_category WRITE;
2 SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
3 FROM nested_category
4 WHERE name = 'MP3 PLAYERS';
5 DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;
6 UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
7 UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;
8 UNLOCK TABLES;

删除一个节点后移动到其他节点

1 LOCK TABLE nested_category WRITE;
2 SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
3 FROM nested_category
4 WHERE name = 'PORTABLE ELECTRONICS';
5 DELETE FROM nested_category WHERE lft = @myLeft;
6 UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND@myRight;
7 UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
8 UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;
9 UNLOCK TABLES;

总结：

预排序遍历树算法的核心就是牺牲了写的性能来换取读取的性能

在你的开发的应用遇到此类问题的时（读压力 > 写压力），尝试下使用预排序遍历树算法来提高你的程序的性能吧。

参考地址：http://be-evil.org/post-168.html

http://www.cnblogs.com/BigIdiot/archive/2013/04/02/2995248.html