结构树 树表设计 二叉树.doc

The Nested Model 树形结构先把树按水平的方式摆开，如下图 然后按前序遍历的方法，为每一个结点编号，每一个结点都有左、右的编号，根结点从1开始开始计算。我们分别把左右编号称为左值和右值。 根据前序遍历的规律，我们可以知道，每一个结点的子结点的左值比父结点左值大而比父结点的右值小。例如 Fruit(2,11) 的子结点 Red(3,6)、Cherry(4,5)、 Yellow(7,10)、Banana(8,9) ，可以看到Red、Cherry、Yellow、Banana的左值均比Fruit大，而右值均比Fruit小。数据库设计如下：Java代码 1. CREATETABLEnested_category( 2. idint(11)NOTNULLAUTO_INCREMENT, 3. namevarchar(16)DEFAULTNULL, 4. parentint(11)DEFAULTNULL, 5. lftint(11)DEFAULTNULL, 6. rgtint(11)DEFAULTNULL, 7. PRIMARYKEY(id) 8. ) CREATE TABLE nested_category ( id int(11) NOT NULL AUTO_INCREMENT, name varchar(16) DEFAULT NULL, parent int(11) DEFAULT NULL, lft int(11) DEFAULT NULL, rgt int(11) DEFAULT NULL, PRIMARY KEY (id) ) 常用到的SQL语句:返回完整的树（Retrieving a Full Tree） Java代码 1. SELECT 2. 3. FROMnested_categorynode,nested_categoryparent 4. WHEREnode.lftBETWEENparent.lftANDparent.rgt 5. AND=Food6. ORDERBYnode.lftSELECT FROM nested_category node, nested_category parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND = Food ORDER BY node.lft返回某结点的祖谱路径（Retrieving a Single Path） Java代码 1. SELECT 2. FROMnested_categorynode,nested_categoryparent 3. WHEREnode.lftBETWEENparent.lftANDparent.rgt 4. AND=Yellow5. ORDERBYnode.lftSELECT FROM nested_category node, nested_category parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND = Yellow ORDER BY node.lft返回所有节点的深度（Finding the Depth of the Nodes） 提示：所有父结点的个数即为深度,最外面那层select 是为了对node.lft进行排序，而between and 操作是相当于= and =，所以会包括结点本身，所以要减一Java代码 1. SELECTV.* 2. FROM(SELECT,(COUNT()-1)depth 3. FROMnested_categorynode,nested_categoryparent 4. WHEREnode.lftBETWEENparent.lftANDparent.rgt 5. GROUPBY)V, 6. nested_categoryT 7. WHEREV.name=T.name 8. ORDERBYT.LftSELECT V.* FROM (SELECT , (COUNT() - 1) depth FROM nested_category node, nested_category parent WHERE node.lft BETWEEN parent.lft AND parent.rgt GROUP BY ) V, nested_category T WHERE V.name = T.name ORDER BY T.Lft返回子树的深度（Depth of a Sub-Tree） 提示：首先，第一步，找到父结点的深度，在前面的SQL中加一个限制条件=Yellow,得到了父结点的全局深度后，便与node、parent、subParent进行条件比较，找到指定父结点的所有子结点（包括父结点本身)，然后用子结点的全局深度减去父结点的全局深度，就可以得到子结点相对于父结点的深度，而父结点本身的深度为0parent 是为了找到子结点的全局深度，而subParent是为了得到父结点的lft,rgt的结点信息，node就是子结点本身,最外面那层是为了对lft进行排序。Java代码 1. SELECTV.* 2. FROM(SELECT, 3. (COUNT()-(AVG(sub_tree.depth)+1)depth 4. FROMnested_categorynode, 5. nested_categoryparent, 6. nested_categorysub_parent, 7. (SELECTV.* 8. FROM(SELECT,(COUNT()-1)depth 9. FROMnested_categorynode,nested_categoryparent 10. WHEREnode.lftBETWEENparent.lftANDparent.rgt 11. AND=Yellow12. GROUPBY)V, 13. nested_categoryT 14. WHEREV.name=T.name 15. ORDERBYT.lft)sub_tree 16. WHEREnode.lftBETWEENparent.lftANDparent.rgt 17. ANDnode.lftBETWEENsub_parent.lftANDsub_parent.rgt 18. ANDsub_=sub_ 19. GROUPBY)V, 20. nested_categoryT 21. WHEREV.name=T.name 22. ORDERBYT.Lft SELECT V.* FROM (SELECT , (COUNT() - (AVG(sub_tree.depth) + 1) depth FROM nested_category node, nested_category parent, nested_category sub_parent, (SELECT V.* FROM (SELECT , (COUNT() - 1) depth FROM nested_category node, nested_category parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND = Yellow GROUP BY ) 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_ = sub_ GROUP BY ) V, nested_category T WHERE V.name = T.name ORDER BY T.Lft返回某结点的直接子树（Find the Immediate Subordinates of a Node） 提示：某结点A的所有子结点的深度(depth)减去A结点的深度等于1的所有结点即为A的直接结点Java代码 1. SELECTV.* 2. FROM(SELECT, 3. (COUNT()-(AVG(sub_tree.depth)+1)depth 4. FROMnested_categorynode, 5. nested_categoryparent, 6. nested_categorysub_parent, 7. (SELECTV.* 8. FROM(SELECT,(COUNT()-1)depth 9. FROMnested_categorynode,nested_categoryparent 10. WHEREnode.lftBETWEENparent.lftANDparent.rgt 11. AND=Yellow 12. GROUPBY)V, 13. nested_categoryT 14. WHEREV.name=T.name 15. ORDERBYT.lft)sub_tree 16. WHEREnode.lftBETWEENparent.lftANDparent.rgt 17. ANDnode.lftBETWEENsub_parent.lftANDsub_parent.rgt 18. ANDsub_=sub_ 19. GROUPBY)V, 20. nested_categoryT 21. WHEREV.name=T.name 22. andV.depth0 24. ORDERBYT.LftSELECT V.* FROM (SELECT , (COUNT() - (AVG(sub_tree.depth) + 1) depth FROM nested_category node, nested_category parent, nested_category sub_parent, (SELECT V.* FROM (SELECT , (COUNT() - 1) depth FROM nested_category node, nested_category parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND = Yellow GROUP BY ) 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_ = sub_ GROUP BY ) V, nested_category T WHERE V.name = T.name and V.depth 0 ORDER BY T.Lft 返回所有的叶子节点（Finding all the Leaf Nodes） 提示：左值与右值相减为1的所有结点即为叶子结点Java代码 1. SELECTnameFROMnested_categoryWHERErgt=lft+1SELECT name FROM nested_category WHERE rgt = lft + 1插入节点（Adding New Nodes） 即所有的后续的子结点都相应的加2Java代码 1. LOCKTABLEnested_categoryWRITE; 2. SELECTmyRight:=rgtFROMnested_categoryWHEREname=TELEVISIONS; 3. UPDATEnested_categorySETrgt=rgt+2WHERErgtmyRight; 4. UPDATEnested_categorySETlft=lft+2WHERElftmyRight; 5. INSERTINTOnested_category 6. (name,lft,rgt) 7. VALUES 8. (GAMECONSOLES,myRight+1,myRight+2); 9. UNLOCKTABLES;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） 提示：所有后续的结点都相应的减去结点删除后的左右值的偏差Java代码 1. LOCKTABLEnested_categoryWRITE; 2. SELECTmyLeft:=lft,myRight:=rgt,myWidth:=rgt-lft+13. FROMnested_category 4. WHEREname=GAMECONSOLES; 5. DELETEFROMnested_categoryWHERElftBETWEENmyLeftANDmyRight; 6. UPDATEnested_categorySETrgt=rgt-myWidthWHERErgtmyRight; 7. UPDATEnested_categorySETlft=lft-myWidthWHERElftmyRight; 8. UNLOCKTABLES;IntroductionMost users at one time or another have dealt with hierarchical data in a SQL database and no doubt learned that the management of hierarchical data is not what a relational database is intended for. The tables of a relational database are not hierarchical (like XML), but are simply a flat list. Hierarchical data has a parent-child relationship that is not naturally represented in a relational database table.For our purposes, hierarchical data is a collection of data where each item has a single parent and zero or more children (with the exception of the root item, which has no parent). Hierarchical data can be found in a variety of database applications, including forum and mailing list threads, business organization charts, content management categories, and product categories. For our purposes we will use the following product category hierarchy from an fictional electronics store:These categories form a hierarchy in much the same way as the other examples cited above. In this article we will examine two models for dealing with hierarchical data in MySQL, starting with the traditional adjacency list model.The Adjacency List ModelTypically the example categories shown above will be stored in a table like the following (Im including full CREATE and INSERT statements so you can follow along):CREATE TABLE category(category_id INT AUTO_INCREMENT PRIMARY KEY,name VARCHAR(20) NOT NULL,parent INT DEFAULT NULL);INSERT INTO categoryVALUES(1,ELECTRONICS,NULL),(2,TELEVISIONS,1),(3,TUBE,2),(4,LCD,2),(5,PLASMA,2),(6,PORTABLE ELECTRONICS,1),(7,MP3 PLAYERS,6),(8,FLASH,7),(9,CD PLAYERS,6),(10,2 WAY RADIOS,6);SELECT * FROM category ORDER BY category_id;+-+-+-+| category_id | name | parent |+-+-+-+| 1 | ELECTRONICS | NULL | 2 | TELEVISIONS | 1 | 3 | TUBE | 2 | 4 | LCD | 2 | 5 | PLASMA | 2 | 6 | PORTABLE ELECTRONICS | 1 | 7 | MP3 PLAYERS | 6 | 8 | FLASH | 7 | 9 | CD PLAYERS | 6 | 10 | 2 WAY RADIOS | 6 |+-+-+-+10 rows in set (0.00 sec)In the adjacency list model, each item in the table contains a pointer to its parent. The topmost element, in this case electronics, has a NULL value for its parent. The adjacency list model has the advantage of being quite simple, it is easy to see that FLASH is a child of mp3 players, which is a child of portable electronics, which is a child of electronics. While the adjacency list model can be dealt with fairly easily in client-side code, working with the model can be more problematic in pure SQL.Retrieving a Full TreeThe first common task when dealing with hierarchical data is the display of the entire tree, usually with some form of indentation. The most common way of doing this is in pure SQL is through the use of a self-join:SELECT AS lev1, as lev2, as lev3, as lev4FROM category AS t1LEFT JOIN category AS t2 ON t2.parent = t1.category_idLEFT JOIN category AS t3 ON t3.parent = t2.category_idLEFT JOIN category AS t4 ON t4.parent = t3.category_idWHERE = ELECTRONICS;+-+-+-+-+| lev1 | lev2 | lev3 | lev4 |+-+-+-+-+| ELECTRONICS | TELEVISIONS | TUBE | NULL | ELECTRONICS | TELEVISIONS | LCD | NULL | ELECTRONICS | TELEVISIONS | PLASMA | NULL | ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH | ELECTRONICS | PORTABLE ELECTRONICS | CD PLAYERS | NULL | ELECTRONICS | PORTABLE ELECTRONICS | 2 WAY RADIOS | NULL |+-+-+-+-+6 rows in set (0.00 sec)Finding all the Leaf NodesWe can find all the leaf nodes in our tree (those with no children) by using a LEFT JOIN query:SELECT FROMcategory AS t1 LEFT JOIN category as t2ON t1.category_id = t2.parentWHERE t2.category_id IS NULL;+-+| name |+-+| TUBE | LCD | PLASMA | FLASH | CD PLAYERS | 2 WAY RADIOS |+-+Retrieving a Single PathThe self-join also allows us to see the full path through our hierarchies:SELECT AS lev1, as lev2, as lev3, as lev4FROM category AS t1LEFT JOIN category AS t2 ON t2.parent = t1.category_idLEFT JOIN category AS t3 ON t3.parent = t2.category_idLEFT JOIN category AS t4 ON t4.parent = t3.category_idWHERE = ELECTRONICS AND = FLASH;+-+-+-+-+| lev1 | lev2 | lev3 | lev4 |+-+-+-+-+| ELECTRONICS | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH |+-+-+-+-+1 row in set (0.01 sec)The main limitation of such an approach is that you need one self-join for every level in the hierarchy, and performance will naturally degrade with each level added as the joining grows in complexity.Limitations of the Adjacency List ModelWorking with the adjacency list model in pure SQL can be difficult at best. Before being able to see the full path of a category we have to know the level at which it resides. In addition, special care must be taken when deleting nodes because of the potential for orphaning an entire sub-tree in the process (delete the portable electronics category and all of its children are orphaned). Some of these limitations can be addressed through the use of client-side code or stored procedures. With a procedural language we can start at the bottom of the tree and iterate upwards to return the full tree or a single path. We can also use procedural programming to delete nodes without orphaning entire sub-trees by promoting one child element and re-ordering the remaining children to point to the new parent.The Nested Set ModelWhat I would like to focus on in this article is a different approach, commonly referred to as the Nested Set Model. In the Nested Set Model, we can look at our hierarchy in a new way, not as nodes and lines, but as nested containers. Try picturing our electronics categories this way:Notice how our hierarchy is still maintained, as parent categories envelop their children.We represent this form of hierarchy in a table through the use of left and right values to represent the nesting of our nodes: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_categoryVALUES(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;+-+-+-+-+| category_id | name | lft | rgt |+-+-+-+-+| 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 |+-+-+-+-+We use lft and rgt because left and right are reserved words in MySQL, see /doc/mysql/en/reserved-words.html for the full list of reserved words.So how do we determine left and right values? We start numbering at the leftmost side of the outer node and continue to the right:This design can be applied to a typical tree as well:When working with a tree, we work from left to right, one layer at a time, descending to each nodes children before assigning a right-hand number and moving on to the right. This approach is called the modified preorder tree traversal algorithm.Retrieving a Full TreeWe can retrieve the full tree through the use of a self-join that links parents with nodes on the basis that a nodes lft value will always appear between its parents lft and rgt values:SELECT FROM nested_category AS node,nested_category AS parentWHERE node.lft BETWEEN parent.lft AND parent.rgtAND = ELECTRONICSORDER BY node.lft;+-+| name |+-+| ELECTRONICS | TELEVISIONS | TUBE | LCD | PLASMA | PORTABLE ELECTRONICS | MP3 PLAYERS | FLASH | CD PLAYERS | 2 WAY RADIOS |+-+Unlike our previous examples with the adjacency list model, this query will work regardless of the depth of