本文介绍的方法基于多叉树的前序遍历序列,是所有数据库树结构存储方案中查询子树速度最快的方案。最早发表在这里"http://drinkjava2.iteye.com/blog/2353983",但那篇文章太啰嗦了,这是整理后的精简版,其实原理很简单,几句话就能说完。
目前常见的树形结构数据库存储方案有以下四种,但是都存在一定问题:
1)Adjacency List(邻接表):每个节点仅记录父节点主键。优点是简单,缺点是访问子树需要递归遍历,对数据库压力大(即使是支持递归SQL的数据库)。
2)Path Enumerations( 路径枚举):用一个字符串记录当前节点所在路径。优点是查询方便,缺点是占用空间大,查询需要使用like模糊方法,效率低,插入新记录时要手工更改此节点以下所有路径,维护不便。
3)Closure Table(闭包表):专门一张表维护Path,缺点是占用空间大,操作不直观。
4)Nested Sets (嵌套集):记录左值和右值,优点是查询子树无需递归,缺点是非常复杂、难操作。
本文介绍的基于树形结构的前序遍历序列方法,示意图如下:
如上图左边的树结构,映射在数据库里的结构见右图表格,注意整个表格是一个排好序的树结构的前序遍历序列,相同节点深度的排序以line为准。 表格的最后一行(或每个根节点)必须有一个END标记,level设为0,上表中的ID为主键,Level为树节点的深度。在以上基础上,只要一句SQL,就可以无递归查询出任意节点的所有子树节点, 比某些数据自带的基于递归原理的查询更高效。 假设节点的行号为X,level为Y,则查询整个子树的SQL为:
select * from tb where line>=X and line<(select min(line) from tb where line>X and level<=Y)
例如获取D节点及其所有子节点:
select * from tb where line>=7 and line< (select min(line) from tb where line>7 and level<=2)
它依据的原理很简单:按树结构的前序遍历序列存储的树结构,判断它的所有子结点,只要从这个节点开始往下划竖线,竖线右边的全是它的子节点,直到碰到竖线上或竖线左边出现非空值则终止,原理图如下:
这种方案的优点是查询高效,删除高效(只需要删除当前行即可,虽然会造成line字段的跳号,但是不影响使用),插入节点也很简单,只需要2行简单的SQL即可,例如要在line=9和line=10的两个节点之间插入一个新节点,则新节点行号应为10,原行号为10的将变为11, SQL操作为:
update tb2 set line=line+1 where line>=10; //把10以后的所有行号加1
insert into tb (line,id,level) values (10,'T',4); //执行插入新节点操作
虽然影响的行数非常多,但是理解和维护都非常简单。 如果担心插入操作对性能的影响,还可以将行号跳号设计(如按100000跳号),新的节点可以插入在两个节点的空号区中段(如果节点间存在空号区),这样可以很大程序上消除进行加1操作的概率。另外一个表只需要一个End标记,可以设为一个固定的非常大的数值(要大于所有line值)。
这种方案的缺点是当需要移动节点时,必须维护整张表的前序遍历排序顺序,必要时要进行整张表或子树的重排序, 这是一个很耗时的工作(其它三种方案Path Enumerations/Closure Table/Nested Sets也有这个缺点),这是不可避免的,是以始终维护一个索引为代价换取查询性能的提高。因此它最适合只有增删查操作,但是很少有移动节点的场合。
总结:这种方案最适合的场合是树的深度很深(可以超过上百万),不经常移动节点、对查询速度要求极高的场合(因为无递归)。
本文实际上可以抽象成一种利用前序遍历给多叉树建查询索引的方案,即使在没有数据库存在的情况下,也是有可能在程序中应用到这种方案的,只要将SQL中的查询功能改成手工进行数组遍历即可。
另外,数据库开发者也可以考虑,对于邻接表模式(即只有id和pid两个关键字段)存储的树结构, 可以用这种方法创建一个内部索引,将level和line作为数据库表的隐藏字段,这样用户就可以不用手工维护level、line以及维护前序遍历排序这些与业务无关的操作,这才是最人性化的使用方式。
- 大小: 90.8 KB
- 大小: 11 KB
分享到:
相关推荐
C语言实现二叉树的前序遍历(非递归),下载下来看看哦!
常见的二叉树遍历,分为前序、中序、后续和层次遍历4种。 层次遍历相对比较好理解,对于前3种遍历方式概念的记忆方式应该是这样的:左和右的顺序始终是固定的—先左后右,所谓的前序、中序和后序是针对根来说的。...
先序遍历非递归算法(C语言) 多种遍历方法
首先把根节点入栈,因为根节点是前序遍历中的第一个节点。随后每次我们从栈顶取出一个节点 u,它是我们当前遍历到的节点,并把 u的所有子节点逆序推入栈中。例如 u
链式二叉树的前序创建、递归遍历、利用堆栈的非递归遍历、前序销毁以及求二叉树的深度
C语言二叉树遍历前序非递归算法,简单易懂,正确无误
二叉树的基本操作,包括前序、中序、后序遍历的递归和非递归算法,不得不下的资源
一棵n个结点的完全二叉树用向量作存储结构,用非递归算法实现对该二叉树进行前序遍历。
数据结构中非递归前序遍历 VC6.0 包括源程序和CPP文件
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
C语言实现二叉树的前序、中序、后续遍历(递归法),大家可以看看哈。。。
/*选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等) 【实验内容】 必做内容 程序的菜单功能项如下: 1----...
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
因此,满二叉树的前序遍历、中序遍历和后序遍历均可以通过递归方式实现。 以前序遍历为例,满二叉树的前序遍历顺序为:根、左、右。 在具体实现过程中,我们可以通过构造一个满二叉树,然后进行前序遍历来获取遍历...
先序遍历的非递归算法C语言 二叉树前序、中序、后序三种遍历的非递归算法和递归算法最精悍版
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
springJpa单标递归树形结构
用递归实现C#树形结构 ,用递归实现C#树形结构 ,
二叉树的创建与三种遍历的递归与非递归实现 包括二叉树的动态创建,前序遍历,中序遍历,后续遍历的递归与非递归方法的实现。
主要介绍了二叉树前序遍历的非递归算法,需要的朋友可以参考下