`
drinkjava2
  • 浏览: 40670 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

发明了一种新的树结构数据库存储方案

阅读更多
最近在开发jSqlBox过程中,想研究一下树形结构和VO对象树的转换,突然发现一种新的树结构数据库存储方案,在网上搜索了一下,没有找到雷同的(也可能是我花的时间不够)方案,现介绍如下:
目前常见的树形结构数据库存储方案有以下四种,但是都存在一定问题:
1)Adjacency List::记录父节点。优点是简单,缺点是访问子树需要遍历,发出许多条SQL,对数据库压力大。
2)Path Enumerations:用一个字符串记录整个路径。优点是查询方便,缺点是插入新记录时要手工更改此节点以下所有路径,很容易出错。
3)Closure Table:专门一张表维护Path,缺点是占用空间大,操作不直观。
4)Nested Sets:记录左值和右值,缺点是复杂难操作。
以上方法都存在一个共同缺点:操作不直观,不能直接看到树结构,不利于开发和调试。
本文介绍的方法我暂称它为“简单粗暴多列存储法”,它与Path Enumerations有点类似,但区别是用很多的数据库列来存储一个占位符(1或空值),如下图(https://github.com/drinkjava2/Multiple-Columns-Tree/blob/master/treemapping.jpg) 左边的树结构,映射在数据库里的结构见右图表格:



各种SQL操作如下:

1.获取(或删除)指定节点下所有子节点,已知节点的行号为"X",列名"cY":
select *(or delete) from tb where
  line>=X and line<(select min(line) from tb where line>X and  (cY=1 or c(Y-1)=1 or c(Y-2)=1 ... or c1=1))
例如获取D节点及其所有子节点:
select * from tb where line>=7 and line< (select min(line) from tb where line>7 and (c2=1 or c1=1))
删除D节点及其所有子节点:
delete from tb where line>=7 and line< (select min(line) from tb where line>7 and (c2=1 or c1=1))

仅获取D节点的次级所有子节点:
select * from tb where line>=7 and c3=1 and line< (select min(line) from tb where line>7 and (c2=1 or c1=1))

2.查询指定节点的根节点, 已知节点的行号为"X",列名"cY":
select * from tb where line=(select max(line) from tb where line<=X and c1=1)
例如查I节点的根节点:
select * from tb where line=(select max(line) from tb where line<=12 and c1=1)

3.查询指定节点的上一级父节点, 已知节点的行号为"X",列名"cY":
select * from tb where line=(select max(line) from tb where line<X and c(Y-1)=1)
例如查L节点的上一级父节点:
select * from tb where line=(select max(line) from tb where line<11 and c3=1)

4.查询指定节点的所有父节点, 已知节点的行号为"X",列名"cY":
select * from tb where line=(select max(line) from tb where line<X and c(Y-1)=1)
union select * from tb where line=(select max(line) from tb where line<X and c(Y-2)=1)
...
union select * from tb where line=(select max(line) from tb where line<X and c1=1)
例如查I节点的所有父节点:
select * from tb where line=(select max(line) from tb where line<12 and c2=1)
union  select * from tb where line=(select max(line) from tb where line<12 and c1=1)

5.插入新节点:
视需求而定,例如在J和K之间插入一个新节点T:
update tb set line=line+1 where line>=10;
insert into tb (line,id,c4) values (10,'T',1)
这是与Path Enumerations模式最大的区别,插入非常方便,只需要利用SQL将后面的所有行号加1即可,无须花很大精力维护path字串, 
不容易出错。
另外如果表非常大,为了避免update tb set line=line+1 造成全表更新,影响性能,可以考虑增加
一个GroupID字段,同一个根节点下的所有节点共用一个GroupID,所有操作均在groupID组内进行,例如插入新节点改为:
update tb set line=line+1 where groupid=2 and line>=8;
insert into tb (groupid,line,c4) values (2, 8,'T')
因为一个groupid下的操作不会影响到其它groupid,对于复杂的增删改操作甚至可以在内存中完成操作后,一次性删除整个group的内容 
并重新插入一个新group即可。

总结:
以上介绍的这种方法优点有:
1)直观易懂,方便调试,是所有树结构数据库方案中唯一所见即所得,能够直接看到树的形状的方案,空值的采用使得树形结构一目了然。
2)能充分利用SQL,查询、删除、插入非常方便,没有用到like模糊查询语法。
3)只需要一张表。
4)兼容所有数据库。
5)占位符即为实际要显示的内容应出现的地方,方便输出到Grid之类的表格显示控件。

缺点有:
1)不是无限深度树,数据库最大允许列数有限制,通常最多为1000,这导致了树的深度不能超过1000,而且考虑到列数过多对性能也有影响, 使用时建议定一个比较小的深度限制例如100。
2)SQL语句比较长,很多时候会出现c9=1 or c8=1 or c7=1 ... or c1=1这种n阶乘式的查询条件
3)树的节点整体移动操作比较麻烦,需要将整个子树平移或上下移动,当节点须要经常移动时,不建议采用这种方案。对于一些只增减,不常移动节点的应用如论坛贴子和评论倒比较合适。
4)列非常多时,空间占用有点大。

====补充,以下为追加内容,是在前述基础上,一种更简单的无限深度树方案==
突然发现上面的方法还是太笨了,如果不用多列而是只用一个列来存储深度等级,则可以不受数据库列数限制,从而进化为无限深度树,虽然不再具有所见即所得的效果,但是在性能和简单性上要远远优于上述“简单粗暴多列存储法”,暂时给它取名"朱氏深度树V2.0法"(备注:如果已有人发明了这个方法,删掉前面两个字就好了),方法如下:
如下图(https://github.com/drinkjava2/Multiple-Columns-Tree/blob/master/treemappingv2.png)左边的树结构,映射在数据库里的结构见右图表格,注意这种方法是按groupid来分组,每个组的最后一行必须有一个END标记,level设为0,见图:



1.获取指定节点下所有子节点,已知节点的行号为X,level为Y, groupID为Z
select * from tb2 where groupID=Z and
  line>=X and line<(select min(line) from tb where line>X and level<=Y and groupID=Z)
例如获取D节点及其所有子节点:
select * from tb2 where groupID=1 and line>=7 and line< (select min(line) from tb2 where groupid=1 and line>7 and level<=2)
删除和获取相似,只要将sql中select * 换成delete即可。

仅获取D节点的次级所有子节点:(查询条件加一个level=Y+1即可):
select * from tb2 where groupID=1 and line>=7 and level=3 and line< (select min(line) from tb2 where groupid=1 and line>7 and level<=2)

2.查询任意节点的根节点, 已知节点的groupid为Z
select * from tb2 where groupID=Z and line=1 (或level=1)

3.查询指定节点的上一级父节点, 已知节点的行号为X,level为Y, groupID为Z
select * from tb2 where groupID=Z and line=(select max(line) from tb2 where groupID=Z and line<X and level=(Y-1))
例如查L节点的上一级父节点:
select * from tb2 where groupID=1 and line=(select max(line) from tb2 where groupID=1 and line<11 and level=3)

4.查询指定节点的所有父节点, 已知节点的行号为X,level为Y:
select * from tb2 where groupID=Z and line=(select max(line) from tb2 where groupID=Z and line<X and level=(Y-1))
union select * from tb2 where groupID=Z and line=(select max(line) from tb2 where groupID=Z and line<X and level=(Y-2))
...(行数=Y-1)
union select * from tb2 where groupID=Z and line=(select max(line) from tb2 where groupID=Z and line<X and level=1)
例如查I节点的所有父节点:
select * from tb2 where groupID=1 and line=(select max(line) from tb2 where groupID=1 and line<12 and level=2)
union  select * from tb2 where groupID=1 and line=(select max(line) from tb2 where groupID=1 and line<12 and level=1)

5.插入新节点:例如在J和K之间插入一个新节点T:
update tb2 set line=line+1 where  groupID=1 and line>=10;
insert into tb (groupid,line,id,level) values (1,10,'T',4);

总结:
此方法优点有:
1)是无限深度树
2)虽然不象第一种方案那样具有所见即所得的效果,但是依然具有直观易懂,方便调试的特点。
3)能充分利用SQL,查询、删除、插入非常方便,SQL比第一种方案简单多了,也没有用到like模糊查询语法。
4)只需要一张表
5)兼容所有数据库
6)占用空间小

缺点有:
1)树的节点整体移动操作有点麻烦, 适用于一些只增减,不常移动节点的场合如论坛贴子和评论等。当确实需要进行复杂的移动节点操作时,一种方案是在内存中进行整个树的操作并完成排序,操作完成后删除整个旧group再整体将新group一次性批量插入数据库。

2017年1月22日补充:
节点的移动操作有点麻烦,只是相对于查询/删除/插入来说,并不是说难上天了。例如在MySQL下移动整个B节点树到H节点下,并位于J和K之间的操作如下:
update tb2 set tempno=line*1000000 where groupid=1;  
set @nextNodeLine=(select min(line) from tb2 where groupid=1 and line>2 and level<=2);  
update tb2 set tempno=9*1000000+line, level=level+2 where groupID=1 and line>=2 and line< @nextNodeLine;  
set @mycnt=0;  
update tb2 set line=(@mycnt := @mycnt + 1) where groupid=1 order by tempno;

上例需要在表中新增一个名为tempno的整数类型列, 这是个懒人算法,虽然简单明了,但是对整棵树进行了重新排序,所以效率并不高。 在需要频繁移动节点的场合下,用Adjacency List方案可能更合适一些。

1月22日再补充一下:
如果需要频繁移动节点的场合,又想保留方案2高效查询的优点,还有一种方案就是再添加一个父节点pid字段和两个辅助字段tempno和temporder用于排序,(暂时称其为“深度树V3.0法"), 这样相当于V2.0法和Adjacency List模式的合并了,优点是每次移动节点,只需要更改PID即可,不需要复杂的算法,一次可以任意移动、增加、删除多个节点,最后统一调用以下算法简单地进行一下重排序即可,下面这个示例完整演示了一个Adjacency List模式到V2.0模式的转换,这相当于一个重新给树建查询索引的过程:



drop table if exists tb3;

create table tb3 (
id varchar(10),
comments varchar(55),
pid varchar(10),
line integer,
level integer,
tempno bigint,
temporder integer
);

insert into tb3 (id,comments,Pid) values('A','found a bug',null);
insert into tb3 (id,comments,Pid) values('B','is a worm?','A');
insert into tb3 (id,comments,Pid) values('E','no','B');
insert into tb3 (id,comments,Pid) values('F','is a bug','B');
insert into tb3 (id,comments,Pid) values('C','oh, a bug','A');
insert into tb3 (id,comments,Pid) values('G','need solve it','C');
insert into tb3 (id,comments,Pid) values('D','careful it bites','A');
insert into tb3 (id,comments,Pid) values('H','it does not bite','D');
insert into tb3 (id,comments,Pid) values('J','found the reason','H');
insert into tb3 (id,comments,Pid) values('K','solved','H');
insert into tb3 (id,comments,Pid) values('L','uploaded','H');
insert into tb3 (id,comments,Pid) values('I','well done!','D');

set @mycnt=0;
update tb3 set  line=0,level=0, tempno=0, temporder=(@mycnt := @mycnt + 1) order by id;
update tb3 set level=1, line=1 where pid is null;

update tb3 set tempno=line*10000000 where line>0; 
update tb3 a, tb3 b set a.level=2, a.tempno=b.tempno+a.temporder where a.level=0 and 
a.pid=b.id and b.level=1;
set @mycnt=0;
update tb3 set line=(@mycnt := @mycnt + 1) where level>0 order by tempno;

update tb3 set tempno=line*10000000 where line>0; 
update tb3 a, tb3 b set a.level=3, a.tempno=b.tempno+a.temporder where a.level=0 and 
a.pid=b.id and b.level=2;
set @mycnt=0;
update tb3 set line=(@mycnt := @mycnt + 1) where level>0 order by tempno;

update tb3 set tempno=line*10000000 where line>0; 
update tb3 a, tb3 b set a.level=4, a.tempno=b.tempno+a.temporder where a.level=0 and
 a.pid=b.id and b.level=3;
set @mycnt=0;
update tb3 set line=(@mycnt := @mycnt + 1) where level>0 order by tempno;



以上算法利用了SQL的功能,将原来可能需要非常多SQL递归查询的过程转变成了有限次数(=树最大深度)的SQL操作,为了突出算法,以上示例假设只有一个根节点,删除了groupid和endtag,实际使用中要完善一下这个细节, order by id也可改成以其它字段排序。因时间关系我就不给出V2.0模式到Adjacency List模式逆推的算法了(也即pid为空,根据V2.0表格倒过来给pid赋值的过程),不过这个算法倒不重要,因为通常v3.0表中每一行会一直保存着一个pid)。
总结一下:
Adjacency List模式:移/增/删节点方便,查询不方便
深度树V2.0模式:查询方便,增/删节点方便,但存在效率问题,移动节点不方便
深度树V3.0模式:移/增/删节点方便,查询方便,缺点是每次移/增/删节点后要重建line和level值以供查询用。它是结合了上两种模式的合并体,并可以根据侧重,随时在这两种模式(修改模式和查询模式)间切换。v3.0法相当于给Adjacency List模式设计了一个查询索引。
  • 大小: 12.7 KB
  • 大小: 24.5 KB
  • 大小: 39.9 KB
分享到:
评论
5 楼 drinkjava2 2018-05-30  
再补充:为了避免插入新节点时对后续节点进行加1操作影响性能,可以将行号跳号设计,例如按100000跳号,新节点插入在两个节点的空号区中段,这样可以在很大概率上消除加1操作。另外一个表只需一个End标记,可以设为一个很大的常量值(要大于所有行号)即可。

另外,这篇文修修补补,太啰嗦了,不太好看,下面这个链接是精简版:
https://my.oschina.net/drinkjava2/blog/1818631
4 楼 drinkjava2 2017-08-15  
anxin1225 写道
   大大,你果然骨骼精异。我简单考虑了一下,发现这种实现思路,确实能够解决问题,不过还是像是你说的,在整棵树很大的情况下,在修改前面的内容的时候,后边受影响行数很多。

这个没办法,其它三种方法Path Enumerations、Closure Table、Nested Sets也都存在这个问题。想要马儿跑,又要马儿不吃草是不可能的,这是以插入时以有序方式插入(或大的改动后全树或子树的重排序)为代价换取查询性能的提高。
本文算法实际上可以抽象成是一种给多叉树建查询索引的算法,即使在没有数据库存在的情况下,也是有可能在程序中应用到这种算法的,只要将SQL中的查询功能改成手工进行数组遍历即可。
3 楼 anxin1225 2017-07-12  
   大大,你果然骨骼精异。我简单考虑了一下,发现这种实现思路,确实能够解决问题,不过还是像是你说的,在整棵树很大的情况下,在修改前面的内容的时候,后边受影响行数很多。
2 楼 drinkjava2 2017-03-18  
怎么都反映看不懂? 算你狠,拿把尺来: 按"简单粗暴多列存储法"存储的树结构,判断它的所有子结点,只要拿把尺从这个节点开始往下划竖线,竖线右边的全是它的子节点,直到碰到竖线上或竖线左边出现非空值则终止。V2.0和V3.0都是建立在同一个道理上。
你要是做Java的,可以看一下jSqlBox项目(baidu之)中test/examples/orm/TreeORMTest.java这个示例,有很详细的子树查找、子树移动、重排序的演示。
1 楼 gaoyan2011 2017-02-06  
表示看不太懂

相关推荐

    嵌入式数据库中数据恢复的方法和装置

    开了一种嵌入式数据库中数据...本发明提供的一种嵌入式数据库中数据恢复的方法和装置,对数据文件和/或数据文件结构错误的嵌入式数据库中的数据进行恢复,节约了嵌入式系统的存储资源,提高了嵌入式系统中数据库的容错性。

    JDBC技术使用标准的 SQL 语言对数据库表中的数据进行访问,以及增删查改

    是一种用于 SQL 语句的 Java API,由一组类和接口组成,通过调用这些类和接口所提供的方法,可以使用标准的 SQL 语言来存取数据库中的数据,特别是可以访问存储在关系数据库里的数据。JDBC 可以用 Java 语言在各种...

    sql数据库相关加密知识

    三重DES, DES的密码学缺点是密钥长度相对比较短,因此,人们又想出了一个解决其长度的方法,即采用三重DES,三重DES是DES的一种变形。这种方法使用两个独立的56位密钥对交换的信息(如EDI数据)进行3次加密,从而使其...

    一种基于区块链的安全文件存储和共享方法.zip

    本文属于信息检索及数据库结构技术领域,公开了一种基于区块链的安全文件存储和共享方法,利用区块链技术实现文件的安全存储与共享;用户对文件进行加密上传处理,获取文件指针,在记账节点将制定的访问策略与指针等...

    数据分析方案设计7要素.docx

    增强分析 2017年,Rita在Gartner的研究论文中引入了增强分析的概念,并将其描述为一种新的数据分析方法,可使用机器学习和自然语言生成(NLG)自动化见解。增强型数据分析大大提升了数据分析效率,降低数据分析的...

    FriendlyCSharp.Databases:跨平台C#数据结构的库。 用C#编写的通用B树,可以实时替换为放电需求内存中存储的NoSQL数据库(Firebase,Redis缓存,SAP HANA,Exadata,OLTP等)

    基本信息B树可以在N.Wirth的《算法+数据结构=程序》一书中找到,也可以在Wikipedia上找到,即: “在计算机科学中,B树是一种自平衡树数据结构,可对数据进行排序,并允许以对数时间进行搜索,顺序访问,插入和删除...

    java收银系统源码-JSTAR:JSTAR是一种专注于远程网页设计的编程语言,由wilmixjeminj@2017在JAVA和C#中发明

    是一种编程语言,专注于远程网页设计和 它是由 wilmix jemin j @ 2017 在 JAVA 和 C# 中发明的。 Jstar 编程语言简介 定义: “JSTAR(J*)被定义为用于发布专注于网页设计、网站建设等的网络应用程序的网络服务器”。...

    基于JAVA的模拟ATM系统的设计与实现【文献综述】.pdf

    随着 Internet 的蓬勃发展,ATM 网上银行作为电子商务的一种形式正以方便、快捷 的优势,逐步成为新兴的经营模式和理念,人们已经不再满足于排队等待办理各种业务, 而是渴望着能够充分享受网络所带来的更加多的...

    XML高级编程

    扩展标记语言(Extensible Markup Language, XML)作为一种计算技术出现不过是短短几年前的事情。它是一种概念,以其简便性而颇得人心,它驱动了Internet应用程序编写方式的动态改变。本书的覆盖范围本书解释和演示...

    大数据说明文阅读答案.docx

    C、大数据作为一种新的测量工具,将再次引领新的繁荣,提供给人们更多的选择。 D、大数据之"大",仅仅是因为它的容量大,数据大。 1.可以救助更广泛的普通大众;可以帮助人们发现新知,创造新的价值;改变了人们的...

    基于hbase和geohash的矢量数据空间索引方法

    本发明涉及涉及在hbase上进行海量GIS矢量数据空间索引编码及建立的方法,更特定言之,本发明涉及对点、线、面二维矢量数据映射到一维的字符串型rowkey索引,使之能够用hbase存储海量矢量数据,提供高性能空间查询...

    opencv人脸表情识别

    它是由伟大的统计学家RA Fisher爵士发明的,他在1936年发表的论文“在分类学问题中使用多次测量”中成功地将其用于花朵分类(著名的Iris数据集仍可从UCI机器学习存储库中获得。)。但是,如果主成分分析(PCA)表现...

    vRP:FiveM(http:fivem.net)RP addonframework

    它旨在使用OOP减少开销,并提供一种更加直接和结构化的方法。 这可能是最后一个主要版本,可以使用扩展系统为vRP 2更新基于vRP的资源。 请参阅。 特征基本管理工具(踢,禁令,白名单),组/权限,语言,标识系统...

    最新Java面试宝典pdf版

    18、一个用户表中有一个积分字段,假如数据库中有100多万个用户,若要在每年第一天凌晨将积分清零,你将考虑什么,你将想什么办法解决? 107 19、一个用户具有多个角色,请查询出该表中具有该用户的所有角色的其他...

    发明

    我们认为,发展必须是一种令人愉悦的创造力,才能真正实现。 Laravel通过减轻许多Web项目中使用的常见任务来减轻开发工作的痛苦,例如: 。 。 用于和存储的多个后端。 直观的表达 。 数据库不可知。 。 。 ...

    Java面试宝典2012新版

    18、一个用户表中有一个积分字段,假如数据库中有100多万个用户,若要在每年第一天凌晨将积分清零,你将考虑什么,你将想什么办法解决? 107 19、一个用户具有多个角色,请查询出该表中具有该用户的所有角色的其他...

    计算机应用基础知识总结大全.doc

    计算机的特点 从计算机的特点理解计算机的定义,要清楚计算 机的实质是一种信息处理机 计算机是一种能够输入信息,存储信息,并按照人们意志(这些意志就是顺序)对信 息进行加工处理,最后输出人们所需要信息的...

Global site tag (gtag.js) - Google Analytics