树型数据结构是一种常见的数据结构,如文件目录、公司组织结构等,但是关系型数据库没有相应的原生数据结构来存储和查询这类数据结构。本文介绍几种在关系数据库中实现树形数据存储的方法,供大家参考。前言树形结构是生活中常见的数据结构之一,如公司的组织结构、计算机文件的目录结构、家谱等。本文将以区域为例,介绍数据库中实现树查询的几种常见方式:树结构的关键属性:深度方案1、邻接表模型(adjacencylistmodel)方案原理在每条记录中,记录指向记录parent数据,如下图:数据库中的表结构如下:idnameparent1ShanghaiChina2PudongShanghai查询情况一:当我们需要查询上海的直接parent区域时,使用如下Sqlquery:selectparentfromregiontablewherename='Shanghai'查询情况二:当我们需要查询上海的直属分区时,使用如下Sql查询:selectnamefromregiontablewhereparent='Shanghai'查询情况三:当当我们需要查询上海的二级分区时:selectnamefromregiontablewhereparentin(selectnamefromregiontablewhereparent='Shanghai')查询情况4:当我们需要查询上海的所有分区和不知道地区树的总层数(伪代码):result_set=selectnamefromregiontablewhereparent='Shanghai';current_parent=selectnamefromregiontablewhereparent='Shanghai';whilecurrent_parentisnotnull:current_parent=selectfromnameregionTablewhereparentincurrent_parentresult_set.add_all(current_parent)可以看到,在这个查询案例中,随着树的高度增加,IO的数量也会增加。方案优缺点查询所有子树难度:高查询所有父节点难度:高查询下一层子节点难度:低查询上一层父节点难度:低插入新记录难度:低删除原始记录难度:low占用额外空间少,只需要额外占用一列O(n)空间;适用场景:只包含直接父子查询的场景包含多层查询,但可以将所有数据加载到内存场景2.预排序遍历树算法(改进的预排序树遍历算法)方案原理预排序是指我们执行一个特殊的查询前对数据库中存储的数据进行排序,为每条数据添加两个字段:左索引和右索引。添加方法如下图所示数据库中的表结构如下:idnamelindexrindex1Shanghai16252Pudong1924查询情况一:查找上海有多少个子区域(不含自身):selectrindex-lindexasregion_numfromregion表wherename='Shanghai';说明:编号时,可以发现编号从上海左边递增,回到右边时,所有子节点都编号一次,所以上海节点右索引减去左索引除以2(每个子节点有left和right两个数),是子节点的总数。查询情况二:查询上海所有分区:查询情况二:查询上海所有分区:selectnamefromregiontablewherelindex>16andrindex<25;说明:从编号过程可以发现,上海子区域的编号值必须在(19,24)范围内,非上海子区域的编号范围不能在(19,24),所以where中的lindex和rindex可以在这里互换。比如下面的语句也可以查询ShanghaiSub-regionselectnamefromregiontablewherelindex>16andlindex<25;从rindex>16且rindex<25的区域表中选择名称;从rindex>16且lindex<25的区域表中选择名称;查询情况3:查询浦东地区的父区(上海只有一个父区,不直观):selectnamefromareatablewhererindex<19andlindex>24;说明:从上面的编号过程我们可以知道,只要一个节点的左右编号范围在另一个节点的左右编号范围内(查询2取反),同理,左右19和该查询语句中的24可以互换,例如:selectnamefromregiontablewhererindex<19andlindex>19;selectnamefromregionTablewhererindex<24andlindex>24;selectnamefromareatablewhererindex<24andlindex>19;修改一:删除浦东地区。当树结构发生变化时,需要重新触发预排序。比如删除浦东后,左右索引值在19到24之间的需要减1,左右索引大于24的需要减2.updateregiontablesetrindex=rindex-1whererindex<24andrindex>19;updateregiontablesetlindex=lindex-1wherelindex<24andlindex>19;updateregiontablesetrindex=rindex-2whererindex>24;updateregiontablesetlindex=lindex-2wherelindex>24;修改2:把删除的浦东地区加回来:updateregiontablesetrindex=rindex+1whererindex<24andrindex>=19;updateregiontablesetlindex=lindex+1wherelindex<24andlindex>=19;updateregiontablesetrindex=rindex+2whererindex>=24;updateregiontablesetlindex=lindex+2wherelindex>=24;方案优缺点查询所有子树难度:低查询所有父节点难度:低查询下一层子节点难度:高查询上一层父节点难度:高插入新记录难度:高原始记录删除困难:高占用额外空间少,只需要额外占用一列O(n)空间;适用场景:数据几乎不更新的场景方案三、路径枚举原理该方法在每条数据记录后增加一列,用于存储从根节点到该点的完整路径。idnamepath1ShanghaiChina/2PudongChina/Shanghaiquerycase1:Findhowmanysub-regionsinShanghai(notincludingitself):selectnamefromregiontablewherepathlike'China/Shanghai/%';查询案例2:查询上海地区所有父区域:selectnamefromareatablewherepathlike'%/Shanghai';删除/更改/添加情况:删除/更改/添加上海地区:需要更新所有子节点的路径字符串。方案优缺点查询所有子树难度:低查询所有父节点难度:低查询下一层子节点难度:低查询上一层父节点难度:低插入新记录难度:高删除原始记录难度:高占用额外空间中等,只需要额外占用一列O(n)*O(m)空间(n为节点总数,m为深度)那个树);方案4,ClosureTable方案的原理。给一些记录增加列,然后查询新增加的列,得到父子节点信息关系。ClosureTable是一个新的表,用于记录节点(父节点、子节点、深度)之间的直接关系。对于下图中的孙桥和浦东,会生成如下关系记录;idchildparentdeepth1SunqiaoPudong12SunqiaoShanghai23SunqiaoChina34PudongShanghai15PudongChina26ShanghaiChina1查询情况1:查询上海的下一个子区域:selectchildfromregiontablewhereparent='Shanghai'anddepth=1;查询情况2:查询上海所有分区域:selectchildfromregiontablewhereparent='Shanghai';查询案例3:查询上海上层父区域:selectparentfromregiontablewherechild='Shanghai'anddepth=1;查询案例4:查询上海所有父区:selectparentfromareatablewherechild='Shanghai';删除:删除上海地区:更新上海子节点的深度:parents=selectparentfromareatablewherechild='Shanghai';children=selectchildfromregiontablewhereparent='上海';updateregiontablesetdepth=depth-1whereparentinparentsandchildinchildren.deleteparentfromregiontablewherechild='Shanghai'orparent='上海';方案优缺点查询所有子树难度:低查询所有父节点难度:低查询下一层子节点难度:低查询上一层父节点难度:低插入新记录难度:高删除原始记录难度:高占用额外空间高,需要额外一张表存储O(n)*O(m)条记录(n为节点总数,m为树的深度);先发布到微信公众号,版权所有,禁止转载!
