树形结构数据库表设计总结

  • A+
所属分类:数据库

前段时间遇到数据库设计中树形结构设计的问题,今天看了几篇文章,现在来总结下,之前接触到数据库的东西相对较少,但也不至于完全不知道的那种,所以在此拿出这例典型的数据库设计来作为入门是再合适不过的了

理想中树形结构应该具备如下特征:

  1. 数据储存冗余度小、直观性强
  2. 检索遍历过程简单高效
  3. 节点增删查改操作高效。

基本数据

本例通过实物图谱的例子进行讲解,通过类型,颜色和品种组织食品,树形结构图如下:

树形结构数据库表设计总结

一、基于继承关系实现的数据库表设计(AdjacencyList)

对树形结构最直观的分析显而易见的实在节点之间的继承关系上,通过显示地描述某一节点的父节点,从而建立起来的这种二维的关系表,则这种方案的Tree表结构通常设计为:(Node_id,Parent_id),则相应的数据库表为

树形结构数据库表设计总结

优点:从脑子中萌生这种想法到想法落地很自然而然,非常直观和方便,也是我们最首先可以想到的

缺点:直接记录了节点之间的继承关系,因此对Tree的任何CRUD操作都将是低效的,这主要是因为此表中存在频繁的“递归”操作,而递归操作会频繁的访问数据库,每次数据库IO都会有时间开销。

但是,也并不是无用武之地,在Tree规模相对较小的情况下,可以借助缓存来进行优化,将这些较少的Tree信息载入到内存中进行处理,从而避免了直接对数据库的IO操作,节省了性能开支。

二、基于左右值编码的数据库表设计(Nested Sets)

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

树形结构数据库表设计总结

第一眼看到这中表结构,相信大家都是懵比的,因为对这莫名其妙的左值(Lft)和右值(Rgt)感到莫名其妙,但是这种表结构似乎并没有保存父子节点的继承关系,但当你按照这张表的数字从1数到18,你会发现你所数的顺序即为这棵树前序遍历的顺序,我们来画张图可能就比较清晰了

树形结构数据库表设计总结

依次设计,我们可以推断出所有左值大于2,并且右值小于11的节点都是Fruit的后续节点,整棵树的结构通过左值和右值储存下来,然而,这还不够,我们的目的是要对树进行CRUD操作,即需要构造出与之相配套的相关算法。

三、树形结构CRUD算法

1. 获取某节点的子孙节点

只需要一条SQL语句,即可返回该节点子孙节点的前序遍历列表,以Fruit为例,SELECT*FROM Tree WHERE Lft BETWEEN  AND 11 ORDER BY Lft ASC,查询结果如下:

树形结构数据库表设计总结

那么接下来问题又来了,某个节点到底有多少的子孙节点呢?通过该节点的左右值我们可以将其子孙节点点圈进来,则子孙总数 = (右值 - 左值 - 1)/ 2,以Fruit为例,其子孙总数为:(11 - 2 - 1)/ 2 = 4。同时,为了更为直观的展示树形结构,我们需要知道节点在树种所在层数,通过左右值的SQL查询即可实现,以Fruit为例:SELECT COUNT(*) FROM Tree WHERE Lft <= 2 AND Rgt >= 11。 为了更为方便的描述,我们可以为Tree建立一个视图,添加一个层次序列,该列数值可以写一个自定义函数来计算,函数定义如下:

基于层次计算函数,我们创建一个视图,添加了新的记录节点层次的数列

创建储存过程,用于计算给定节点的所有子孙节点及相应的层次

现在,我们使用上面的储存过程来计算节点Fruit所有子孙节点及对应层次,查询结果如下:

树形结构数据库表设计总结

从上面的实现中,我们可以看出采用左右值编码的设计方案,在进行树的查询遍历时,只需要进行2次数据库查询,消除了递归,再加上查询条件都是数字的比较,查询的效率都是很高的随着树规模的不断扩大,基于左右值编码的设计方案将比传统的递归方案查询效率提高更多。

2. 获取某节点的族谱路径

假定我们要获得某节点的族谱路径,则根据左右值分析只需要一条SQL语句即可完成,以Fruit为例,SELECT * FROM Tree WHERE Lft < 2 AND Rgt > 11 ORDER BY Lft ASC,相对完整的储存过程:

3. 为某节点添加子孙节点

假定我们要在节点“Red”下添加一个新的子节点“Apple”,该树将变成如下图所示,其中红色节点为新增节点

树形结构数据库表设计总结

接下来的SQL语句根据之前写的改一改就OK了

4. 删除某节点

如果我们要删除某节点,则要删除该节点的所有子孙节点,而被删除的节点的个数为:(被删除的节点的右值 - 被删除的节点的左值 + 1)/ 2,而剩下的节点的左右值在大于删除节点的左右值的情况下进行调整,那么调整之后的树形结构为

树形结构数据库表设计总结

5. 总结嵌套集的优缺点:

通过左右值编码实现无线分组的树形结构Schema设计方案做一个总结

优点:在消除了递归操作的前提下,实现了无限分组,而且查询条件是基于整形数字的比较,效率很高

缺点:节点的添加,删除及修改的成本高,将会涉及到多方面数据的改动

四、基于路径枚举的数据库表设计(Path Enumerations)

在数据库表中,我们使用类型varchar的path字段来替代原来的parent_id字段,这个path字段所储存的内容为当前节点的最顶层祖先到它的自己的序列,就像UNIX的路径一样,你甚至可以使用'/'作为路径的分隔符。

树形结构数据库表设计总结

你可以通过比较每个节点的路径来查询一个节点祖先,比如:要找到Beef,路径是1/3/6,可以这么做:

一旦你可以很简单地获取一颗子树或者从子孙节点到祖先节点的路径,你就可以很简单地实现查询,如查询一颗子树所有节点上值得总和,插入一个节点也可以像使用邻接表一样的简单,你所需要做的只是复制一份要插入节点的父节点的路径,并建这个新节点的ID追加到路径末尾即可。

路径枚举也存在一些缺点,比如数据库不能确保路径的格式总是正确或者路径中的节点确实存在。依赖于应用程序的逻辑代码来维护路径的字符串,并且验证字符串的正确性开销很大。无论将varchar的长度设定为多大,依旧存在长度的限制,因而不能支持树结构的无限扩展。

五、基于闭包表的数据库表实际(Closure Table)

闭包表是解决分级储存的一个简单而优雅的解决方案,它记录了树中所有节点间的关系,而不仅仅只有那些直接的父子节点。

在这个食物系统里,我们不在使用Node_id来储存树的结构,而是将树中任何具有(祖先-后代)关系的节点储存在treepaths表里,即使这两个节点之间不是直接的父子关系;同时,我们还增加一行指向节点自己。

通过treepaths表来获取祖先和后代比使用嵌套集更加的直接。例如要获取Meat的后代,只需要在treepaths表中搜索祖先是Food的行就行了,同样获取后代也是这样。

要插入一个新的叶子节点,比如Meat的一个子节点,应首先插入一条自己到自己的关系,然后搜索treepaths表中是评论Meat的节点,增加该节点和新插入节点的“祖先后一代”关系(新节点ID应该为8)

要删除一个叶子节点,比如pork,应删除所有treepaths表中后代为8的行:

要删除一个完成的子树,比如Meat和他的所有的后代,可删除所有在treepaths表中后代Meat的行,以及那些以meat后代为后代的行

闭包表的设计比嵌套集更加的直接,两者都能快捷地查询给定节点的祖先和后代,但是闭包表能更加简单地维护分层信息。这两个设计都比使用邻接表或者路径枚举更方便地查询给定节点的直接后代和祖先。

然而你可以优化闭包表来使它更方便地查询直接父亲节点或者子节点: 在 treepaths 表中添加一个 path_length 字段。一个节点的自我引用的path_length 为0,到它直接子节点的path_length 为1,再下一层为2,以此类推。这样查询起来就方便多了。

总结:所以到底该用哪种设计

每种设计都各有优劣,如何选择设计,依赖于应用程序的哪种操作是你最需要性能上的优化

树形结构数据库表设计总结

层级设计比较
  1. 邻接表是最方便的设计,因为最简单最容易想到
  2. 如果使用的数据库支持WITH或者CONNECT BY PRIOR的递归查询,那能使得邻接表的查询效率更高效
  3. 枚举路径能够很直观的展示出祖先到后代之间的路径,但同时由于不能确保引用完整性,使得这个设计变得非常脆弱。枚举路径也使得数据的储存变得冗余。
  4. 嵌套集是一个聪明的解决方案,但可能是过于的聪明了吧,同样也不能确保引用的完整性,做好在一个查询性能要求很高而对其他要求一般的场合来使用它。
  5. 闭包表是最通用的设计,并且已上的方案也只有它能允许一个节点属于多棵树,他要求一张额外的表来储存关系,使用空间换时间的方案减少操作过程中由冗余的计算造成的消耗。

 

这几种方案只是我们日常设计中的一部分,开发中肯定会到更多的选择方案。选择哪一种方案,是需要切合实际,根据自己项目的需求,选择最合适的一种。

 

 

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: