专栏首页.NET企业级解决方案应用与咨询SQL反模式学习笔记3 单纯的树

SQL反模式学习笔记3 单纯的树

2014-10-11

在树形结构中,实例被称为节点。每个节点都有多个子节点与一个父节点。

最上层的节点叫做根(root)节点,它没有父节点。

最底层的没有子节点的节点叫做叶(leaf)

中间的节点简单地称为非叶节点(nonleaf)

目标:分成存储于查询,比如:系统字典、组织机构、省份区域等树形结构数据或者以层级方式组织的数据。

反模式:总是依赖父节点,邻接表。

最简单的实现方式是添加ParentId字段,引用同一张表的主键ID。

邻接表维护树比较方便,但是查询很笨拙,如果要找一个节点下的所有子节点,要关联很多次,这个关联次数取决于树的深度,

所以,邻接表不能用于存储比较深的树。

如何识别反模式:当出现以下情况时,可能是反模式

(1)我们的数结构要支持多少层

(2)我们总是很害怕接触那些管理树结构的代码

   (3)我需要一个脚本来定期的清理树中的孤立节点数据

合理使用反模式:

邻接表设计的优势在与能快速地获取一个给定节点的直接父子节点,也很容易插入新节点、维护节点、删除节点。

如果树的分层结构不是很深,可以使用这种模式。

【 使用CTE通用表表达式来递归查询树形结构数据比较方便,详见“SQL中的CTE通用表表达式” 】

解决方案:使用其他树模型

  路径枚举:

    用一个path字段保存当前节点的最顶层的祖先到自己的序列(路径)

    优点:查询方便;

    缺点:1、不能保证存储的值的有效性。

2、增、删时,要考虑对原位置下的子节点如何处理,比较麻烦。

3、如果还要维护一个排序path,那就更麻烦了。

  嵌套集:

    存储子孙节点的相关信息,而不是节点的直接祖先。用nsleft存储所有后台的nsleft中最小的数-1,

用nsright存储所有后台的nsright中最大的数+1。

    优点:删除时,原来子节点的关系自动上移。

    缺点:1、查询一个节点的直接上级或下级,很困难。

2、增、删,困难。

  闭包:记录了树中所有节点间的关系,而不仅仅是只有那些直接的父子关系。

将树中任何具有“祖先-后代”关系的节点对都存储在TreePath表中的一行,同时增加一行指向节点自己。

优点:1、能快速的查询给定节点的祖先与后代;

2、能更加简单的维护分层信息;

3、如果删除了TreePath表中的一条记录,那么并不是真正的删除具体信息表中的记录。这样设计有时候很有用:

比如在产品目录的分类或者员工组织架构的图标中,当你改变了节点关系的时候,并不是真的想要删除一个节点。

我们把关系路径存储在一个分开独立的表中,使得设计更加灵活。

缺点:查询直接父节点或子节点,需要在表中增加Path_Length字段来维护。

结论:

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

邻接表:简单,但不适用于很深的表;

   枚举路径:无法保证引用完整性;

   嵌套集:无法保证引用完整性,太复杂;

   闭包:需要一个额外的表存储关系;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C#开发BIMFACE系列35 服务端API之模型对比6:获取模型构建对比分类树

      BIMFACE平台提供了服务端“获取模型对比构件分类树”API。目录树返回结果以树状层级关系显示了增删改的构件信息,里面无法区分哪些构建是新增、修改或者删除...

    张传宁老师
  • DevExpress 开发经验总结3 制作项目安装包

      使用DevExpress控件包开发C/S项目完成后,部署前需要制作本地安装包。本文还是使用“SetupFactory”安装工厂来制作安装包。在以前的系列文章...

    张传宁老师
  • C#开发BIMFACE系列11 服务端API之源文件删除

    通过BIMFACE控制台或者调用服务接口上传文件成功后,如果不再需要该文件,则可以通过BIMFACE平台提供的“源文件删除”服务接口删除具体的文件。下面详细介绍...

    张传宁老师
  • 一万字详解 Redis Cluster Gossip 协议

    大家好,我是历小冰,今天来讲一下 Reids Cluster 的 Gossip 协议和集群操作,文章的思维导图如下所示。

    程序员历小冰
  • (2)MongoDB副本集自动故障转移 全流程原理

    前文我们搭建MongoDB三成员副本集,了解集群基本特性,今天我们围绕下图聊一聊背后的细节。

    小码甲
  • 动画 | 什么是2-3-4树?

    画了一系列树的动画,从二分搜索树,到AVL树,再到2-3树,再到基于2-3树的红黑树,都可以发现这些树都跟二叉查找树很像啊。

    我脱下短袖
  • 【从二叉树到红黑树】清晰理解红黑树的演变---红黑的含义

    网上关于红黑树的博文很多,但是多是上来即讲定义,未说其所以然,难以理解且无所营养,甚者示例图有误且概念模糊的比比即是;

    云服务器最新
  • 动画 | 什么是2-3树?

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是2-3树?(修改删除操作方式)

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是红黑树?(基于2-3树)

    学习过2-3树之后就知道应怎样去理解红黑树了,如果直接看「算法导论」里的红黑树的性质,是看不出所以然。我们也看看一颗二分搜索树满足红黑的性质:

    我脱下短袖

扫码关注云+社区

领取腾讯云代金券