树形结构数据存储方案(四):左右值编码

栏目: 数据库 · 发布时间: 6年前

内容简介:在基于数据库的一般应用中,查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程,基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案,来保存该树的数据。

在基于数据库的一般应用中,查询的需求总要大于删除和修改。为了避免对于树形结构查询时的“递归”过程,基于Tree的前序遍历设计一种全新的无递归查询、无限分组的左右值编码方案,来保存该树的数据。

树形结构数据存储方案(四):左右值编码

第一次看见这种表结构,相信大部分人都不清楚左值(Lft)和右值(Rgt)是如何计算出来的,而且这种表设计似乎并没有保存父子节点的继承关系。但当你用手指指着表中的数字从1数到18,你应该会发现点什么吧。对,你手指移动的顺序就是对这棵树进行前序遍历的顺序,如下图所示。当我们从根节点Food左侧开始,标记为1,并沿前序遍历的方向,依次在遍历的路径上标注数字,最后我们回到了根节点Food,并在右边写上了18。

树形结构数据存储方案(四):左右值编码

依据此设计,我们可以推断出所有左值大于2,并且右值小于11的节点都是Fruit的后续节点,整棵树的结构通过左值和右值存储了下来。然而,这还不够,我们的目的是能够对树进行CRUD操作,即需要构造出与之配套的相关算法。按照深度优先,由左到右的原则遍历整个树,从1开始给每个节点标注上left值和right值,并将这两个值存入对应的name之中。

如何查询?

1、获取某个节点下的所有子孙节点,以Fruit为例:

2、获取子孙节点总数

子孙总数 = (右值–左值–1)/2,以Fruit为例,其子孙总数为:(11–2–1)/2 = 4

3、 获取节点在树中所处的层数,以Fruit为例:

4、 获取当前节点所在路径,以Fruit为例:

在日常的处理中我们经常还会遇到的需要获取某一个节点的直属上级、同级、直属下级。为了更好的描述层级关系,我们可以为Tree建立一个视图,添加一个层次列,该列数值可以编写一个自定义函数来计算:

在添加完函数以后,我们创建一个a视图,添加新的层次列:

5、 获取当前节点父节点,以Fruit为例:

6、 获取所有直属子节点,以Fruit为例:

7、 获取所有兄弟节点,以Fruit为例:

8、 返回所有叶子节点

如何创建树?如何新增数据?

上面已经介绍了如何检索结果,那么如何才能增加新的节点呢?Nested set 最重要是一定要有一个根节点作为所有节点的起点,而且通常这个节点是不被使用的。为了便于控制查询级别,在建表的时候建议添加parent_id配合之联结列表方式一起使用。

添加子节点(子节点起始处),以在Food下添加子节点Fruit为例:

如需在末尾追加就需要以下方式进行(以在Red下添加Apple为例):

在节点A后面添加同级节点(以在Yellow后面添加Green为例)

以上讨论的添加节点指的都是添加末端节点,即插入的这个节点不是当前已存在节点的父节点。如果需要插入非末端节点要怎么办呢?

这个过程可以将流程分为2步,首先新增节点,接下里再将需要的节点移到新增的节点下级。节点移动方法(以将Apple移到Yellow中为例):

删除节点(包含子节点)

如果需要只删除该节点,子节点自动上移一级如何处理?

以上为Nested Set的CURD操作,具体在使用时建议结合事务和存储过程一起使用。本方案的优点时查询非常的方便,缺点就是每次插入删除数据涉及到的更新内容太多,如果树非常大,插入一条数据可能花很长的时间。

参考链接:


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

社会再平衡

社会再平衡

[加] 亨利·明茨伯格 / 陆维东、鲁强 / 东方出版社 / 2015-9 / 38.00元

明茨伯格曾坦言:我虽然不是律师,但我觉得有必要质疑法律的失效;我也不算是经济学家,但我觉得有义务来挑战一切事物以经济为指标的标准;我也不是人类学家、社会学家、心理学家,或者政治科学,更不是活动分子,但是在我的讨论中,文化、行为、权力、社会运动都扮演了重要的角色。我是一个合成者,我最成功的书都囊括了不同来源的想法。 明茨伯格创作《社会再平衡》这本书的初衷是因为关注身边的趋势:环境的恶化、民主的......一起来看看 《社会再平衡》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具