树形结构的数据库设计.docx

树形结构的数据库表Schema设计程序设计过程中，我们常常用树形结构来表征某些数据的关联关系， 如企业上下级部门、栏目结构、商品分类等等，通常而言，这些树状结 构需要借助于数据库完成持久化然而目前的各种基于关系的数据库， 都是以二维表的形式记录存储数据信息，因此是不能直接将Tree存入 DBMS，设计合适的Schema及其对应的CRUD算法是实现关系型数 据库中存储树形结构的关键理想中树形结构应该具备如下特征：数据存储冗余度小、直观性强； 检索遍历过程简单高效；节点增删改查CRUD操作高效无意中在网 上搜索到一种很巧妙的设计，原文是英文，看过后感觉有点意思，于是 便整理了一下本文将介绍两种树形结构的Schema设计方案：一种是 直观而简单的设计思路，另一种是基于左右值编码的改进方案一、基本数据本文列举了一个食品族谱的例子进行讲解，通过类别、颜色和品种组织食品，树形结构图如下：二、继承关系驱动的Schema设计对树形结构最直观的分析莫过于节点之间的继承关系上，通过显示 地描述某一节点的父节点，从而能够建立二维的关系表，则这种方案的 Tree表结构通常设计为：{Node_id,Parent_id},上述数据可以描述为如 下图所示：缺点当然也是非常的突出：由于直接地记录了节点之间的继承关系，因 此对Tree的任何CRUD操作都将是低效的，这主要归根于频繁的“递 归”操作,递归过程不断地访问数据库，每次数据库10都会有时间开销。

当然，这种方案并非没有用武之地，在Tree规模相对较小的情况下， 我们可以借助于缓存机制来做优化，将Tree的信息载入内存进行处理， 避免直接对数据库10操作的性能开销三、基于左右值编码的Schema设计在基于数据库的一般应用中，查询的需求总要大于删除和修改为 了避免对于树形结构查询时的“递归”过程，基于Tree的前序遍历设计一 种全新的无递归查询、无限分组的左右值编码方案,来保存该树的数据Rgt）是如何计算出来的，而且这种表设计似乎并没有保存父子节点 的继承关系但当你用手指指着表中的数字从1数到18,你应该会发 现点什么吧对，你手指移动的顺序就是对这棵树进行前序遍历的顺序， 如下图所示当我们从根节点Food左侧开始，标记为1,并沿前序遍 历的方向，依次在遍历的路径上标注数字，最后我们回到了根节点Food, 并在右边写上了 18第一次看见这种表结构，相信大部分人都不清楚左值（Lft）和右值 （Rgt）是如何计算出来的，而且这种表设计似乎并没有保存父子节点 的继承关系但当你用手指指着表中的数字从1数到18,你应该会发 现点什么吧对，你手指移动的顺序就是对这棵树进行前序遍历的顺序， 如下图所示。

当我们从根节点Food左侧开始，标记为1,并沿前序遍 历的方向，依次在遍历的路径上标注数字，最后我们回到了根节点Food, 并在右边写上了 184| Cherry s a Banana 19-依据此设计，我们可以推断出所有左值大于2,并且右值小于11的 节点都是Fruit的后续节点，整棵树的结构通过左值和右值存储了下来 然而，这还不够，我们的目的是能够对树进行CRUD操作，即需要构 造出与之配套的相关算法四、树形结构CRUD算法(1) 获取某节点的子孙节点只需要一条SQL语句，即可返回该节点子孙节点的前序遍历列表，以 Fruit 为例：SELECT* FROM Tree WHERE Lft BETWEEN 2 AND 11ORDER BY Lft ASC查询结果如下所示：们可以将其子孙节点圈进来，则子孙总数=(右值-左值- 1) / 2,以Fruit为例，其子孙总数为:(11 -2 - 1) / 2 = 4同时，为了更为直观地 展现树形结构，我们需要知道节点在树中所处的层次，通过左、右值的SQL 查询即可实现，以 Fruit 为例：SELECTCOUNT(*) FROM TreeWHERE Lft <= 2 AND Rgt >=11。

为了方便描述，我们可以为Tree建立一个视图，添加一个层次数列，该列数值可以写一个自定义函数来计算，函数定义如下：[sql] view plaincopy1. CREATE FUNCTION dbo.CountLayer2. (3. @node_id int4. )5. RETURNS int6. AS7. begin8. declare @result int9. set @result = 010. declare @lft int11. declare @rgt int12. if exists(select Node_id from Tree where Node_id = @node_id)13. begin14. select @lft = Lft, @rgt = Rgt from Tree where node_id = @node_id15. select @result = count(*) from Tree where Lft <= @lft and Rgt >= @rg t16. end17. return @result18. end19. GO基于层次计算函数，我们创建一个视图，添加了新的记录节点层次的数列：[sql] view plaincopy1.CREATE VIEW dbo.TreeView2.AS3.SELECT Node_id, Name, Lft, Rgt, dbo.CountLayer(Node_id) AS Layer FROM dbo.Tree ORDER BY Lft4.GO创建存储过程，用于计算给定节点的所有子孙节点及相应的层次:[sql] view plaincopy1. CREATE PROCEDURE [dbo].[GetChildrenNodeList]2. (3.@node_id int4.)5.AS6.declare @lft int7.declare @rgt int8. if exists(select Node_id fromTree where node_id = @node_id)9. begin10. select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id11. select * from TreeView where Lft between @lft and @rgt order by LftASC12. end13. GO现在，我们使用上面的存储过程来计算节点Fruit所有子孙节点及对应层次，查询结果如下：行树的查询遍历时，只需要进行2次数据库查询，消除了递归，再加上 查询条件都是数字的比较，查询的效率是极高的，随着树规模的不断扩 大，基于左右值编码的设计方案将比传统的递归方案查询效率提高更多。

当然，前面我们只给出了一个简单的获取节点子孙的算法，真正地使用 这棵树我们需要实现插入、删除同层平移节点等功能2) 获取某节点的族谱路径假定我们要获得某节点的族谱路径，则根据左、右值分析只需要一 条SQL语句即可完成，以Fruit为例：SELECT* FROM Tree WHERE Lft < 2 AND Rgt > 11 ORDER BY Lft ASC，相对完整的存储过程：1. CREATE PROCEDURE [dbo].[GetParentNodePath]2. (3. @node_id int4. )5. AS6. declare @lft int7. declare @rgt int8. if exists(select Node_id from Tree where Node_id = @node_id)9. begin10. select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id11. select * from TreeView where Lft < @lft and Rgt > @rgt order by LftASC12. end13. GO(3) 为某节点添加子孙节点假定我们要在节点“Red”下添加一个新的子节点“Apple”，该树将变成 如下图所示，其中红色节点为新增节点。

仔细观察图中节点左右值变化，相信大家都应该能够推断出如何写SQL脚本了吧我们可以给出相对完整的插入子节点的存储过程：[sql] view plaincopy1. CREATE PROCEDURE [dbo].[AddSubNode]2. (3. @node_id int,4. @node_name varchar(50)5. )6. AS7. declare @rgt int8. if exists(select Node_id from Tree where Node_id = @node_id)9. begin10. SET XACT_ABORT ON11. BEGIN TRANSCTION12. select @rgt = Rgt from Tree where Node_id = @node_id13. update Tree set Rgt = Rgt + 2 where Rgt >= @rgt14. update Tree set Lft = Lft + 2 where Lft >= @rgt15. insert into Tree(Name, Lft, Rgt) values(@node_name, @rgt, @rgt + 1)16. COMMIT TRANSACTION17. SET XACT_ABORT OFF18. end19. GO(4) 删除某节点如果我们想要删除某个节点，会同时删除该节点的所有子孙节点， 而这些被删除的节点的个数为：(被删除节点的右值-被删除节点的左 值+ 1) / 2而剩下的节点左、右值在大于被删除节点左、右值的情况下 会进行调整。

来看看树会发生什么变化，以Beef为例，删除效果如下 图所示则我们可以构造出相应的存储过程:[sql] view plaincopy1. CREATE PROCEDURE [dbo].[DelNode]2. (3. @node_id int4. )5. AS6. declare @lft int7. declare @rgt int8. if exists(select Node_id from Tree where Node_id = @node_id)9. begin10. SET XACT ABORT ON8.9.10.11.BEGIN TRANSCTION12.select @lft = Lft, @rgt = Rgt from Tree where Node_id = @node_id13.14.15.16.delete from Tree where Lft >= @lft and Rgt <= @rgtupdate Tree set Lft = Lft - (@rgt - @lft + 1) where Lft > @lftupdate Tree set Rgt = Rgt - (@rgt 。