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

ID:1629148

大小:181.00 KB

页数:9页

时间:2017-11-12

[tree]一种理想的在关系数据库中存储树型结构数据的方法_第1页
[tree]一种理想的在关系数据库中存储树型结构数据的方法_第2页
[tree]一种理想的在关系数据库中存储树型结构数据的方法_第3页
[tree]一种理想的在关系数据库中存储树型结构数据的方法_第4页
[tree]一种理想的在关系数据库中存储树型结构数据的方法_第5页
资源描述:

《[tree]一种理想的在关系数据库中存储树型结构数据的方法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、一种理想的在关系数据库中存储树型结构数据的方法2008-03-0715:49   在各种基于关系数据库的应用系统开发中,我们往往需要存储树型结构的数据,目前有很多流行的方法,如邻接列表模型(TheAdjacencyListModel),在此基础上也有很多人针对不同的需求做了相应的改进,但总是在某些方面存在的各种各样的缺陷。   那么理想中的树型结构应具备哪些特点呢?数据存储冗余小、直观性强;方便返回整个树型结构数据;可以很轻松的返回某一子树(方便分层加载);快整获以某节点的祖谱路径;插入、删除、移动节点效率高等等。带着这些需求我查找了很多资料,发现了

2、一种理想的树型结构数据存储及操作算法,改进的前序遍历树模型(TheNestedSetModel)。一、数据   在本文中,举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下:二、邻接列表模型(TheAdjacencyListModel)在这种模型下,上述数据在关系数据库的表结构数据通常如下图所示:由于该模型比较简单,在此不再详细介绍其算法,下面列出它的一些不足:   在大多数编程语言中,他运行很慢,效率很差。这主要是“递归”造成的。我们每次查询节点都要访问数据库。每次数据库查询都要花费一些时间,这让函数处理庞大的树时会

3、十分慢。造成这个函数不是太快的第二个原因可能是你使用的语言。不像Lisp这类语言,大多数语言不是针对递归函数设计的。对于每个节点,函数都要调用他自己,产生新的实例。这样,对于一个4层的树,你可能同时要运行4个函数副本。对于每个函数都要占用一块内存并且需要一定的时间初始化,这样处理大树时递归就很慢了。三、改进的前序遍历树模型(TheNestedSetModel)原理:   我们先把树按照水平方式摆开。从根节点开始(“Food”),然后他的左边写上1。然后按照树的顺序(从上到下)给“Fruit”的左边写上2。这样,你沿着树的边界走啊走(这就是“遍历”),

4、然后同时在每个节点的左边和右边写上数字。最后,我们回到了根节点“Food”在右边写上18。下面是标上了数字的树,同时把遍历的顺序用箭头标出来了。   我们称这些数字为左值和右值(如,“Food”的左值是1,右值是18)。正如你所见,这些数字按时了每个节点之间的关系。因为“Red”有3和6两个值,所以,它是有拥有1-18值的“Food”节点的后续。同样的,我们可以推断所有左值大于2并且右值小于11的节点,都是有2-11的“Fruit”节点的后续。这样,树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做“改进前序遍历树”算法。表结构设计:

5、常用的操作:下面列出一些常用操作的SQL语句返回完整的树(RetrievingaFullTree)SELECTnode.name  FROMnested_categorynode,nested_categoryparentWHEREnode.lftBETWEENparent.lftANDparent.rgt   ANDparent.name='electronics'ORDERBYnode.lft返回某结点的子树(FindtheImmediateSubordinatesofaNode)SELECTV.*  FROM(SELECTnode.name,(

6、COUNT(parent.name)-(AVG(sub_tree.depth)+1))depth          FROMnested_categorynode,               nested_categoryparent,               nested_categorysub_parent,               (SELECTV.*                  FROM(SELECTnode.name,(COUNT(parent.name)-1)depth                          F

7、ROMnested_categorynode,nested_categoryparent                         WHEREnode.lftBETWEENparent.lftANDparent.rgt                           ANDnode.name='portableelectronics'                         GROUPBYnode.name)V,                       nested_categoryT                 WHERE

8、V.name=T.name                 ORDERBYT.lft)sub_tree   

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《[tree]一种理想的在关系数据库中存储树型结构数据的方法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、一种理想的在关系数据库中存储树型结构数据的方法2008-03-0715:49   在各种基于关系数据库的应用系统开发中,我们往往需要存储树型结构的数据,目前有很多流行的方法,如邻接列表模型(TheAdjacencyListModel),在此基础上也有很多人针对不同的需求做了相应的改进,但总是在某些方面存在的各种各样的缺陷。   那么理想中的树型结构应具备哪些特点呢?数据存储冗余小、直观性强;方便返回整个树型结构数据;可以很轻松的返回某一子树(方便分层加载);快整获以某节点的祖谱路径;插入、删除、移动节点效率高等等。带着这些需求我查找了很多资料,发现了

2、一种理想的树型结构数据存储及操作算法,改进的前序遍历树模型(TheNestedSetModel)。一、数据   在本文中,举一个在线食品店树形图的例子。这个食品店通过类别、颜色和品种来组织食品。树形图如下:二、邻接列表模型(TheAdjacencyListModel)在这种模型下,上述数据在关系数据库的表结构数据通常如下图所示:由于该模型比较简单,在此不再详细介绍其算法,下面列出它的一些不足:   在大多数编程语言中,他运行很慢,效率很差。这主要是“递归”造成的。我们每次查询节点都要访问数据库。每次数据库查询都要花费一些时间,这让函数处理庞大的树时会

3、十分慢。造成这个函数不是太快的第二个原因可能是你使用的语言。不像Lisp这类语言,大多数语言不是针对递归函数设计的。对于每个节点,函数都要调用他自己,产生新的实例。这样,对于一个4层的树,你可能同时要运行4个函数副本。对于每个函数都要占用一块内存并且需要一定的时间初始化,这样处理大树时递归就很慢了。三、改进的前序遍历树模型(TheNestedSetModel)原理:   我们先把树按照水平方式摆开。从根节点开始(“Food”),然后他的左边写上1。然后按照树的顺序(从上到下)给“Fruit”的左边写上2。这样,你沿着树的边界走啊走(这就是“遍历”),

4、然后同时在每个节点的左边和右边写上数字。最后,我们回到了根节点“Food”在右边写上18。下面是标上了数字的树,同时把遍历的顺序用箭头标出来了。   我们称这些数字为左值和右值(如,“Food”的左值是1,右值是18)。正如你所见,这些数字按时了每个节点之间的关系。因为“Red”有3和6两个值,所以,它是有拥有1-18值的“Food”节点的后续。同样的,我们可以推断所有左值大于2并且右值小于11的节点,都是有2-11的“Fruit”节点的后续。这样,树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做“改进前序遍历树”算法。表结构设计:

5、常用的操作:下面列出一些常用操作的SQL语句返回完整的树(RetrievingaFullTree)SELECTnode.name  FROMnested_categorynode,nested_categoryparentWHEREnode.lftBETWEENparent.lftANDparent.rgt   ANDparent.name='electronics'ORDERBYnode.lft返回某结点的子树(FindtheImmediateSubordinatesofaNode)SELECTV.*  FROM(SELECTnode.name,(

6、COUNT(parent.name)-(AVG(sub_tree.depth)+1))depth          FROMnested_categorynode,               nested_categoryparent,               nested_categorysub_parent,               (SELECTV.*                  FROM(SELECTnode.name,(COUNT(parent.name)-1)depth                          F

7、ROMnested_categorynode,nested_categoryparent                         WHEREnode.lftBETWEENparent.lftANDparent.rgt                           ANDnode.name='portableelectronics'                         GROUPBYnode.name)V,                       nested_categoryT                 WHERE

8、V.name=T.name                 ORDERBYT.lft)sub_tree   

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭