[TREE]一种理想的在关系数据库中存储树型结构数据的方法

一种理想的在关系数据库中存储树型结构数据的方法2008-03-0715:49在各种基于关系数据库的应用系统开发中，我们往往需要存储树型结构的数据，目前有很多流行的方法，如邻接列表模型（TheAdjacencyListModel），在此基础上也有很多人针对不同的需求做了相应的改进，但总是在某些方面存在的各种各样的缺陷。那么理想中的树型结构应具备哪些特点呢？数据存储冗余小、直观性强；方便返回整个树型结构数据；可以很轻松的返回某一子树（方便分层加载）；快整获以某节点的祖谱路径；插入、删除、移动节点效率高等等。带着这些需求我查找了很多资料，发现了一种理想的树型结构数据存储及操作算法，改进的前序遍历树模型（TheNestedSetModel）。一、数据在本文中，举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下：二、邻接列表模型（TheAdjacencyListModel）在这种模型下，上述数据在关系数据库的表结构数据通常如下图所示：由于该模型比较简单，在此不再详细介绍其算法，下面列出它的一些不足：在大多数编程语言中，他运行很慢，效率很差。这主要是“递归”造成的。我们每次查询节点都要访问数据库。每次数据库查询都要花费一些时间，这让函数处理庞大的树时会十分慢。造成这个函数不是太快的第二个原因可能是你使用的语言。不像Lisp这类语言，大多数语言不是针对递归函数设计的。对于每个节点，函数都要调用他自己，产生新的实例。这样，对于一个4层的树，你可能同时要运行4个函数副本。对于每个函数都要占用一块内存并且需要一定的时间初始化，这样处理大树时递归就很慢了。三、改进的前序遍历树模型（TheNestedSetModel）原理：我们先把树按照水平方式摆开。从根节点开始（“Food”），然后他的左边写上1。然后按照树的顺序（从上到下）给“Fruit”的左边写上2。这样，你沿着树的边界走啊走（这就是“遍历”），然后同时在每个节点的左边和右边写上数字。最后，我们回到了根节点“Food”在右边写上18。下面是标上了数字的树，同时把遍历的顺序用箭头标出来了。我们称这些数字为左值和右值（如，“Food”的左值是1，右值是18）。正如你所见，这些数字按时了每个节点之间的关系。因为“Red”有3和6两个值，所以，它是有拥有1-18值的“Food”节点的后续。同样的，我们可以推断所有左值大于2并且右值小于11的节点，都是有2-11的“Fruit”节点的后续。这样，树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做“改进前序遍历树”算法。表结构设计：常用的操作：下面列出一些常用操作的SQL语句返回完整的树（RetrievingaFullTree）SELECTnode.nameFROMnested_categorynode,nested_categoryparentWHEREnode.lftBETWEENparent.lftANDparent.rgtANDparent.name='electronics'ORDERBYnode.lft返回某结点的子树（FindtheImmediateSubordinatesofaNode）SELECTV.*FROM(SELECTnode.name,(COUNT(parent.name)-(AVG(sub_tree.depth)+1))depthFROMnested_categorynode,nested_categoryparent,nested_categorysub_parent,(SELECTV.*FROM(SELECTnode.name,(COUNT(parent.name)-1)depthFROMnested_categorynode,nested_categoryparentWHEREnode.lftBETWEENparent.lftANDparent.rgtANDnode.name='portableelectronics'GROUPBYnode.name)V,nested_categoryTWHEREV.name=T.nameORDERBYT.lft)sub_treeWHEREnode.lftBETWEENparent.lftANDparent.rgtANDnode.lftBETWEENsub_parent.lftANDsub_parent.rgtANDsub_parent.name=sub_tree.nameGROUPBYnode.name)V,nested_categoryTWHEREV.name=T.nameandV.depth=1andV.depth0ORDERBYT.Lft返回某结点的祖谱路径（RetrievingaSinglePath）SELECTparent.nameFROMnested_categorynode,nested_categoryparentWHEREnode.lftBETWEENparent.lftANDparent.rgtANDnode.name='flash'ORDERBYnode.lft返回所有节点的深度（FindingtheDepthoftheNodes）SELECTV.*FROM(SELECTnode.name,(COUNT(parent.name)-1)depthFROMnested_categorynode,nested_categoryparentWHEREnode.lftBETWEENparent.lftANDparent.rgtGROUPBYnode.name)V,nested_categoryTWHEREV.name=T.nameORDERBYT.Lft返回子树的深度（DepthofaSub-Tree）SELECTV.*FROM(SELECTnode.name,(COUNT(parent.name)-(AVG(sub_tree.depth)+1))depthFROMnested_categorynode,nested_categoryparent,nested_categorysub_parent,(SELECTV.*FROM(SELECTnode.name,(COUNT(parent.name)-1)depthFROMnested_categorynode,nested_categoryparentWHEREnode.lftBETWEENparent.lftANDparent.rgtANDnode.name='portableelectronics'GROUPBYnode.name)V,nested_categoryTWHEREV.name=T.nameORDERBYT.lft)sub_treeWHEREnode.lftBETWEENparent.lftANDparent.rgtANDnode.lftBETWEENsub_parent.lftANDsub_parent.rgtANDsub_parent.name=sub_tree.nameGROUPBYnode.name)V,nested_categoryTWHEREV.name=T.nameORDERBYT.Lft返回所有的叶子节点（FindingalltheLeafNodes）SELECTnameFROMnested_categoryWHERErgt=lft+1插入节点（AddingNewNodes）LOCKTABLEnested_categoryWRITE;SELECT@myRight:=rgtFROMnested_categoryWHEREname='TELEVISIONS';UPDATEnested_categorySETrgt=rgt+2WHERErgt@myRight;UPDATEnested_categorySETlft=lft+2WHERElft@myRight;INSERTINTOnested_category(name,lft,rgt)VALUES('GAMECONSOLES',@myRight+1,@myRight+2);UNLOCKTABLES;删除节点（DeletingNodes）LOCKTABLEnested_categoryWRITE;SELECT@myLeft:=lft,@myRight:=rgt,@myWidth:=rgt-lft+1FROMnested_categoryWHEREname='GAMECONSOLES';DELETEFROMnested_categoryWHERElftBETWEEN@myLeftAND@myRight;UPDATEnested_categorySETrgt=rgt-@myWidthWHERErgt@myRight;UPDATEnested_categorySETlft=lft-@myWidthWHERElft@myRight;UNLOCKTABLES;类别：Sql|添加到搜藏|浏览(12)|评论(1)