logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

十分钟内学会：存储在二维表的树结构如何进行指定深度节点的查询

 贾朋亮博客 2014-09-30

Question

在设计ASP.NET网站时，无限分级的商品分类或者论坛板块都可以使用树结构表示，存放到关系型数据库时大家也懂得用Id和ParentId两个字段来表示节点间的关系。

然而这种最省存储空间的表示方法却不是最有效率的，在需要查询指定深度节点时就会遇到问题。我们需要通过递归来逐层展开才能获取到所有该层的节点，然后再在其中进行查询实在既浪费时间又浪费空间。那么有没有更好的做法呢？

Answer

通常在设计表示树结构的数据表时，我们会增加两个字段：

  • Depth - 表示当前节点的深度的整数
  • Path - 表示从根节点到当前节点的路径的字符串，采用节点名称不可能出现的字符作为分隔符

在对树进行操作时，我们还是如平常一样对表执行CRUD操作，要维护这两个字段并不需要费多少力气，然而在查询时却会为我们带来极大的便利。例如要查询第3层的节点，则只需要使用"WHERE Depth = 3"；又例如要查询A1节点下B3节点下C2节点下的所有子节点，则可以使用"WHERE Path LIKE 'A1/B3/C2%'"。

这样做的道理就在于，通过增加冗余信息来提高检索速度，同时这些冗余信息非常容易维护所以不容易因为操作不慎而导致信息不一致。设想一下你要对树增加/移动/删除一个节点，原本一条SQL语句就能完成的事情现在还是一条SQL语句就能完成，就算不依赖事务也绝对不会导致信息不一致。

明白了这个道理，我们就可以进行推广，例如我们既可能需要根据Id字段的路径来查询，又可能需要根据Name字段的路径来查询，那就分开IdPath和NamePath两个字段来表示两组路径字符串。

1
0
(请您对文章做出评价)
上一篇：十分钟内学会：无刷新的页面间导航
下一篇：英语阅读推荐：海明威写作技巧 & UpdatePanel为何失灵
Add your comment

  1. #1楼 袁永福 电子病历，医疗信息化 2006-12-12 00:42
    顶，支持，但写这种程序得考虑容错，最怕的就是其他菜鸟程序修改不当导致无限递归，然后是删除某个节点时，要删除子孙节点时不幸发生错误，产生“记录泄漏”
    支持(0)反对(0)
  2. #2楼 Henry Liang 2006-12-12 04:45
    楼上说的非常有道理。因为这样的设计其实是一种redundant，不符合3nf的要求。当然3nf不是绝对的，很多时候设计要为“使用”服务。
    支持(0)反对(0)
  3. #3楼 Kevin Zou 2006-12-12 07:40
    謝謝樓主分享
    的確是一個好辦法
    支持(0)反对(0)
  4. #4楼 wang-seraph[未注册用户] 2006-12-12 08:29
    eBay的产品类别结构就是这个样子的
  5. #5楼 Clark Chan 2006-12-12 09:18
    在我的NToggery开发之旅，数据库中，有一个表，Sort表结构如下：
    2 SortId int 4 0
    0 SortName varchar 50 0
    0 ParentId int 4 0
    1 Layer varchar 50 0

    字段中的值如下：
    SortId SortName ParentId Layer
    0 所有类别 0
    1 爱得堡 0 00001
    2 金百利 0 00002
    3 卡尔丹顿 0 00003
    4 高尔夫(南韩) 0 00004
    5 金苹果 0 00005
    6 老人头 0 00006
    7 法国鳄鱼 0 00007
    8 T恤 1 0000100001
    9 牛仔裤 1 0000100002
    10 男 8 000010000100001
    11 皮靴 7 0000700001
    12 女士 11 000070000100001
    13 男士 11 000070000100002


    在这个设计中，无需递归！仅仅order by 就可以生成树了。

    但是添加，删除，移动节点是写了3个存储过程做的：
    sp_Sort_Delete
    sp_Sort_Insert
    sp_Sort_Update

    ps：设计原理和楼主的差不多。再有就是说一点个人感觉：不要死抓3nf，关键是数据库的设计，让程序和软件简单就好，适当的冗余对于，统计查询也会有好处。
    当然这里冗余是为了不再递归。
    支持(0)反对(0)
  6. #6楼 Clark Chan 2006-12-12 09:37
    乘这个机会ps一下，觉得说的不好就丢砖吧~
    ：

    如果园子里面有高手愿意建立一个数据库设计的团队就好了(感觉园子中写数据库设计的太少，就算google搜索出来的数据库设计也少，而且很乱，如果能做归纳整理将是很有用的)。
    我觉得好的数据库会让代码简单多，实用多。
    数据库中好的结构设计，其实已经很多了，只是我们广大的程序员都不知道，
    不了解。
    如果能有个这样的团队来和大家一起积累数据库的优秀设计，那是相当有好处的。对于个人，对于团队，对于园子，是共赢。可惜我没有这个实力~
    写作路线可以是满足某一类业务功能的数据库表结构设计：如传统的组织结构，
    如传统的功能权限，如数据权限，如产品分类，如业务单证，如系统日志，等等。
    这样可以帮助我们这些想学习数据库设计的新手，少走弯路。（就像楼主的文章，看的人以前也做过主-子级的树，设计可能没有楼主的好，那么以前就是走了相对的弯路。）

    请大家拍砖吧，说说自己的意见！

    Cat Chen，咱都姓陈，借你的宝地讨论哈，不介意吧：）
    支持(0)反对(0)
  7. #7楼 Dream.Lee 2006-12-12 10:12
    有必要有数据库设计方面的,最近有个项目需要类似百度竞价排名的功能,数据库设计搞昏了头
    支持(0)反对(0)
  8. #8楼[楼主] Cat Chen 2006-12-12 10:55
    @Henry Liang
    所以我也强调了，这些冗余必须要是非常容易维护的，不容易导致信息不一致的。

    如果增加一个ChildCount字段，维护起来就麻烦了，反而对查询提供不了多少便利（本来COUNT()可以做的事情），所以是一个不好的设计。
    支持(0)反对(0)
  9. #9楼 小隐[匿名][未注册用户] 2006-12-12 11:53
    这种方法维护并不难，但楼主说的“原本一条SQL语句就能完成的事情现在还是一条SQL语句就能完成”恐怕未必罢。我们看一下
    Path - 表示从根节点到当前节点的路径的字符串，采用节点名称不可能出现的字符作为分隔符
    假如一条记录的Path字段的值为：
    A1/B3/C2
    显然也存在一条ID为B3的记录，那么，当你删除B3这条记录的时候
    首先你需要：
    1、DELETE B3
    然后需要：
    2、UPDATE 那些Path字段包含B3的记录
    比如A1/B3/C2，你要改成A1/C2（根据业务不同，可能也会改成A1，或者其他样子）
    这显然是2步工作，怎么能用一条语句完成呢？
    比较好的方法是将这2步写成一个存储过程。
    这就是冗余带来的代价，当然，这种代价我们是可以承受的。
  10. #10楼[楼主] Cat Chen 2006-12-12 12:30
    @小隐[匿名]
    假设硬盘上的目录结构：
    C:\A1\B3\C2

    删除B3后只有两种可能：
    1.删除C:\A1\B3\*，然后删除C:\A1\B3
    2.由于约束，C:\A1\B3不为空，不允许删除
    但是不会出现C:\A1\B3\C2移动到C:\A1\C2的情况。

    你按这种逻辑去想想，是不是还是一条SQL？符合情况1的话，那就用"WHERE Path LIKE 'A1/B3%'"把B3整个支剪掉了。
    支持(0)反对(0)
  11. #11楼 580k[未注册用户] 2006-12-12 15:32
    使用580k.com帮您关注此blog更新
    580k是一种WEB形式的网页监控工具(网址:http://***/).所谓网页监控工具,用其首页的描述,就是:您关注的网页内容发生变化时,580k会将变化的内容用邮件通知您.

    580K作为WEB工具,其提供的功能是有实际应用的,相信一些需要每天关注大量信息的人,如公司老总、炒股者、网络编辑、情报员、论坛灌水爱好者、新闻评论员等,会非常喜欢使用它的.
  12. #12楼 580k[未注册用户] 2006-12-12 15:33
    使用580k.com帮您关注此blog更新,580k是一种WEB形式的网页监控工具(网址:http://***/).所谓网页监控工具,用其首页的描述,就是:您关注的网页内容发生变化时,580k会将变化的内容用邮件通知您.
    580K作为WEB工具,其提供的功能是有实际应用的,相信一些需要每天关注大量信息的人,如公司老总、炒股者、网络编辑、情报员、论坛灌水爱好者、新闻评论员等,会非常喜欢使用它的.
  13. #13楼 lu[匿名][未注册用户] 2006-12-12 16:23
    “这事情告诉我们，学好数据结构与算法设计是有必要的，很多时候我们设计算法无非就是玩时间换空间或者空间换时间的把戏，这把戏玩得多了你自然就熟悉怎么玩了。”

    这最后一句简直就是败笔啊，说明搂主都根本没有理解什么叫算法。那么请谈谈在NP－Complete问题中，你拿多少空间换时间？搞笑。

    不是想得罪人，实在是看不惯某些懂点皮毛却摆出一些教育别人的模样，简直是误己误人。
  14. #14楼 Amnoh 2006-12-12 16:46
    sp_Sort_Delete
    sp_Sort_Insert
    sp_Sort_Update
    ----------------
    自己写的存储过程，不要以sp_开头
    支持(0)反对(0)
  15. #15楼[楼主] Cat Chen 2006-12-12 22:41
    @lu[匿名]
    我确实是把事情扯远了，然后就说错了，我现在把最后一句删掉。
    支持(0)反对(0)
  16. #16楼 ditto0723[未注册用户] 2006-12-12 23:52
    LZ好像没有考虑在 A\B\C中B更名的时候，如将B更名为B1
    这个时候如何如用一条语句实现，敬请赐教。
  17. #17楼 Clark Chan 2006-12-13 09:17
    @Amnoh
    这几个存储过程是朋友05年帮我写的，现在新写的都是
    usp_xxxxx
    uv_xxxxx
    谢谢指正。
    支持(0)反对(0)
  18. #18楼 柠檬[匿名][未注册用户] 2006-12-13 14:50
    这样的设计，会在移动节点和重命名节点的时候非常麻烦。

    事实上，事物有好有坏，除非特殊情况，否则一般不会采用这样的设计方法。
  19. #19楼 MSFT:waywa 韦恩卑鄙 2006-12-13 15:46
    移动的时候 通过update语句批量处理还算可以 我2000年给一个传销公司写的系统就是这样
    支持(0)反对(0)
  20. #20楼 锦瑟[未注册用户] 2006-12-13 22:46
    移动和重命名节点，其他节点的路径肯定要受影响，不可能一句sql完成。

  21. #21楼[楼主] Cat Chen 2006-12-14 00:04
    @ditto0723
    @柠檬[匿名]
    @锦瑟
    可以用REPLACE语句来修改Path，这样Path字符串要加一个前缀表明开头，例如"ROOT\A1\B3\C2"。如果B3改名为B4了，那就Path = REPLACE(Path, 'ROOT\A1\B3', 'ROOT\A1\B4')。

    Depth也可以用类似的方式来批量增减。
    支持(0)反对(0)
  22. #22楼 ivan[匿名][未注册用户] 2006-12-30 11:03
    楼主的设计不错.@Clark Chan 的设计更进了一步.个人觉得还能继续优化.
    首先每一层的自有编码是固定长度,这对直接使用SQL查询非常方便.以@Clark Chan的例子为基础, 比如:使用 "WHERE Path LIKE '00007_____'" 可以仅查出00007以下的子节点,使用 "WHERE Path LIKE '00007%'"可以查出所有00007以下的子节点.在截取其中一层的编码时,也不用去找分隔符,只要你知道是第几层然后直接截取就行了.即便是计算它的所在层数也是直接取字符长度除以一个编码长度,不用老是拆字符.

    但是在移动的时候可能发生这样的情况:
    10 男 000010000100001
    12 女士 000070000100001
    第12 女士节点移动到第10 男士节点同一个父节点之下,由于女士节点最后5位自有编码和男士的后5位相同,那么这个移动就没那么简单了.首先需要查找父节点下节点的最高节点号编码,然后把父节点的编码加上最高节点号编码.在此你还不能忽略并发的可能,多个用户同时把其他位置的节点移动到同一个父节点下.
    所以我们可以直接用节点的ID号作为自己所在层的编码.比如:
    10 男 id=12345 000010000112345
    12 女士 id=54321 000070000154321
    由于每个节点的ID不会重复,所以移动节点的SQL可以这样写:
    移动节点 update tabname set Path='新父节点编码' || id where path= '节点编码'
    移动子树 update tabname set Path='新父节点编码' || substr(Path,length('旧父节点编码'),length(Path) -length('旧父节点编码') ) where path like '节点编码' || '%'
    这样做也有其弱点,id一般不会只有5位,可能是8位或者10位以上.
  23. #23楼 海边的风 2007-04-10 12:02
    如果分类不是太多的话，就用XML吧，它生下来就是做这个的。用XPath来查询要方便得多。
    支持(0)反对(0)
  24. #24楼 游客[未注册用户] 2007-05-08 23:42
    如果节点层次超深，还得用clob来储存这个path字段，LZ有没有考虑过由此带来的其它问题？
  25. #25楼 tomshow 2007-10-25 15:06
    不是吧,这个需要clob来储存！
    支持(0)反对(0)
  26. #26楼 RookieStar 2007-11-06 19:36
    没必要这样吧，非关系型数据为什么不考虑XML数据源+XQuery/XPath呢？
    支持(0)反对(0)
  27. #27楼 智思网[未注册用户] 2008-01-19 00:52
    显示系统实际应用中，查询是大部分工作，更新/删除之类的只是小部分工作，不可能对分类经常进行修改的，这样不合常理，除非特殊，那么特殊处理了。所以楼主的方法其实是足够不错的了。
  28. #28楼 vwvjvwv 2013-08-15 22:04
    不明白
    "查询A1节点下B3节点下C2节点下的所有子节点"
    @ WHERE Path LIKE 'A1/B3/C2%'
    这个%是什么?
    支持(0)反对(0)
  29. #29楼[楼主] Cat Chen 2013-08-16 01:28
    @vwvjvwv
    那个是 LIKE 的通配符，相当于常见的 * 通配符。

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： 贾朋亮博客 > 《Asp.net》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多