ancestor

树形结构存储⽅案对⽐分析

在程序开发中，我们常遇到⽤树型结构来表⽰某些数据间的关系，如企业的组织架构、商品的分类、操作栏⽬等，⽬前的关系型数据库都是以⼆维表的形式

记录存储数据，⽽树型结构的数据如需存⼊⼆维表就必须进⾏Schema设计。最近对此⽅⾯⽐较感兴趣，专门做下梳理，如下为常见的树型结构的数据：

⼀、邻接表

其中最简单的⽅法是：AdjacencyList（邻接列表模式）。简单的说是根据节点之间的继承关系，显现的描述某⼀节点的⽗节点，从⽽建⽴⼆位的关系表。表

结构通常设计为{Node_id,Parent_id}，如下图：

这种⽅案的优点很明显：结构简单易懂，由于互相之间的关系只由⼀个parent_id维护，所以增删改都是⾮常容易，只需要改动和他直接相关的记录就可以。

缺点当然也是⾮常的突出：由于直接地记录了节点之间的继承关系，因此对Tree的任何CRUD操作都将是低效的，这主要归根于频繁的“递归”操作，递归过程

不断地访问数据库，每次数据库IO都会有时间开销。举个例⼦，如果想要返回所有⽔果，也就是⽔果的所有⼦孙节点，看似很简单的操作，就需要⽤到⼀堆递

归。

当然，这种⽅案并⾮没有⽤武之地，在树的层级⽐较少的时候就⾮常实⽤。这种⽅法的优点是存储的信息少，查直接上司和直接下属的时候很⽅便，缺点是

多级查询的时候很费劲。所以当只需要⽤到直接上下级关系的时候，⽤这种⽅法还是不错的，可以节省很多空间。

⼆、物化路径

物化路径其实更加容易理解，其实就是在创建节点时，将节点的完整路径进⾏记录。以下图为例：

此种⽅案借助了unix⽂件⽬录的思想，主要时以空间换时间。

//查询某⼀节点下的所有⼦节点:（以Fruit为例）

SET@path=(SELECTpathFROMpathTreeWHEREnode_name='Fruit');

SELECT*FROMpathTreeWHEREpathlikeCONCAT(@path,'/%');

//如何查询直属⼦节点？需要采⽤MySQL的正则表达式查询：

SET@path=(SELECTpathFROMpathTreeWHEREnode_name='Fruit');

SELECT*FROMpathTreeWHEREpathREGEXPCONCAT(@path,'/','[0-9]$');

//查询任意节点的所有上级：（以Yellow为例）：

SET@path=(SELECTpathFROMpathTreeWHEREnode_name='Yellow');

SELECT*FROMpathTreeWHERE@pathLIKECONCAT(path,'%')ANDpath<>@path;

//插⼊新增数据：

SET@parent_path=(SELECTpathFROMpathTreeWHEREnode_name='Fruit');

INSERTINTOpathtree(path,node_name)VALUES(CONCAT(@parent_path,'/',LAST_INSERT_ID()+1),'White')

此⽅案的缺点是树的层级太深有可能会超过PATH字段的长度，所以其能⽀持的最⼤深度并⾮⽆限的。

如果层级数量是确定的，可以再将所有的列都展开，如下图，⽐较适⽤于于类似⾏政区划、⽣物分类法（界、门、纲、⽬、科、属、种）这些层级确定的内

容。

三、左右值编码

在基于数据库的⼀般应⽤中，查询的需求总要⼤于删除和修改。为了避免对于树形结构查询时的“”过程，基于Tree的前序遍历设计⼀种全新的⽆递归查询、⽆

限分组的左右值编码⽅案，来保存该树的数据。

第⼀次看见这种表结构，相信⼤部分⼈都不清楚左值（Lft）和右值（Rgt）是如何计算出来的，⽽且这种表设计似乎并没有保存⽗⼦节点的继承关系。但当你

⽤⼿指指着表中的数字从1数到18，你应该会发现点什么吧。对，你⼿指移动的顺序就是对这棵树进⾏前序遍历的顺序，如下图所⽰。当我们从根节点Food左侧

开始，标记为1，并沿前序遍历的⽅向，依次在遍历的路径上标注数字，最后我们回到了根节点Food，并在右边写上了18。

依据此设计，我们可以推断出所有左值⼤于2，并且右值⼩于11的节点都是Fruit的后续节点，整棵树的结构通过左值和右值存储了下来。然⽽，这还不够，我

们的⽬的是能够对树进⾏CRUD操作，即需要构造出与之配套的相关算法。按照深度优先，由左到右的原则遍历整个树，从1开始给每个节点标注上left值和right

值，并将这两个值存⼊对应的name之中。

本⽅案的优点是查询⾮常的⽅便，缺点就是每次插⼊删除数据涉及到的更新内容太多，如果树⾮常⼤，插⼊⼀条数据可能花很长的时间。所以不推荐，了解

下就⾏，也不打算深⼊研究，想研究的可以查其他资料。

四、闭包表

将ClosureTable翻译成闭包表不知道是否合适，闭包表的思路和差不多，都是空间换时间，ClosureTable，⼀种更为彻底的全路径结构，分别记录路径上相

关结点的全展开形式。能明晰任意两结点关系⽽⽆须多余查询，级联删除和结点移动也很⽅便。但是它的存储开销会⼤⼀些，除了表⽰结点的Meta信息，还需要

⼀张专⽤的关系表。

//主表

CREATETABLEnodeInfo(

node_idINTNOTNULLAUTO_INCREMENT,

node_nameVARCHAR(255),

PRIMARYKEY(`node_id`)

)DEFAULTCHARSET=utf8;

//关系表

CREATETABLEnodeRelationship(

ancestorINTNOTNULL,

descendantINTNOTNULL,

distanceINTNOTNULL,

PRIMARYKEY(ancestor,descendant)

)DEFAULTCHARSET=utf8;

其中

Ancestor代表祖先节点

Descendant代表后代节点

Distance祖先距离后代的距离

添加数据（创建存储过程）

CREATEDEFINER=`root`@`localhost`PROCEDURE`AddNode`(`_parent_name`varchar(255),`_node_name`varchar(255))

BEGIN

DECLARE_ancestorINT;

DECLARE_descendantINT;

DECLARE_parentINT;

IFNOTEXISTS(SELECTnode_idFromnodeinfoWHEREnode_name=_node_name)

THEN

INSERTINTOnodeinfo(node_name)VALUES(_node_name);

SET_descendant=(SELECTnode_idFROMnodeinfoWHEREnode_name=_node_name);

INSERTINTOnoderelationship(ancestor,descendant,distance)VALUES(_descendant,_descendant,0);

IFEXISTS(SELECTnode_idFROMnodeinfoWHEREnode_name=_parent_name)

THEN

SET_parent=(SELECTnode_idFROMnodeinfoWHEREnode_name=_parent_name);

INSERTINTOnoderelationship(ancestor,descendant,distance)SELECTancestor,_descendant,distance+1fromnoderelationshipwheredescendant=_parent;

ENDIF;

ENDIF;

END;

完成后2张表的数据⼤致是这样的：（注意：每个节点都有⼀条到其本⾝的记录。）

//查询Fruit下所有的⼦节点

SELECT

_name

FROM

nodeinfon1

_id=or

dant=_id

WHERE

_name='Fruit'

ce!=0

//查询Fruit下直属⼦节点：

SELECT

_name

FROM

nodeinfon1

_id=or

dant=_id

WHERE

_name='Fruit'

ce=1

//查询Fruit所处的层级：

SELECT

n2.*,_name

FROM

nodeinfon1

_id=dant

or=_id

WHERE

_name='Fruit'

ORDERBY

ceDESC

然后是新增节点：即为给某⼀个节点新增⼦节点，假设该节点还是B，现在给B节点新增⼀个⼦节点E

⾸先，把⾃⼰新增进去，SQL：inrtintoreleationvalues('E','E',0);，然后找到E的祖先，那么现在E的祖先是B的祖先加上B⾃⼰，然后告诉这些祖先们，他

们新增了⼀个后代。通过找祖先的SQL，我们找到了B的祖先，A，那么E的祖先就是B和A：inrtintoreleationvalues('A','E',2);inrtintoreleation

values('B','E',1);那么我们可以看出，新增⼦节点，除了新增⾃⼰以外，还需要通知祖先，并让祖先保存⾃⼰，下⾯提供⼀个伪码，实现该功能

publicinrt(Nodea,Nodeb){

//1.将⾃⼰记录下来

Sql(inrtintoreleationvalues(a,a,0));

//2.查找a的祖先和⾃⼰，并告知他们，他们新增的⼦孙b

Listancestors=Sql(dant=aorderbydistacne);

for(Releationr:ancestors){

Sql(inrtintoreleationvalues(or,b,ne+1))

}

}

缺点很显⽽易见，他的存储和更新开销太⼤。

以上所述存储⽅案，并没有绝对的优劣之分，适⽤场合不同⽽已。可以根据情况⾃⼰选⽤。