在SQL中管理层次结构:MPTT /嵌套集与邻接列表与存储路径

Question

有一段时间我一直在努力解决如何最好地处理SQL中的层次结构.由于邻接列表的限制和MPTT /嵌套集的复杂性而感到沮丧,我开始考虑简单地存储密钥路径,作为一个简单的node_key/node_key/...字符串.我决定编译这三种技术的优点和缺点:

创建/删除/移动节点所需的呼叫数:

• 邻接= 1
• MPTT = 3
• Path = 1(用包含该路径的所有节点上的新节点路径替换旧节点路径)

获取树所需的调用次数:

• 邻接= [子级数]
• MPTT = 1
• 路径= 1

获取节点/祖先路径所需的调用次数:

• 邻接= [超级数]
• MPTT = 1
• 路径= 0

获取子节点数所需的调用次数:

• 邻接= [子级数]
• MPTT = 0(可以从右/左值计算)
• 路径= 1

获取节点深度所需的调用次数:

• 邻接= [超级数]
• MPTT = 1
• 路径= 0

需要DB字段:

• 邻接= 1(父)
• MPTT = 3(父,右,左)
• 路径= 1(路径)

结论

除了一个用例之外,存储的路径技术使用与每个用例中的其他技术相同或更少的调用.通过这种分析,存储路径是明显的赢家.更不用说,它实现起来要简单得多,人类可读等等.

所以问题是,不应该将存储路径视为比MPTT更强大的技术吗？为什么存储路径不是更常用的技术,为什么不在给定实例中使用它们而不是MPTT？

另外,如果您认为此分析不完整,请告诉我们.

更新:

这里至少有两件事MPTT可以开箱即用,存储的路径解决方案不会:

1. 允许计算每个节点的子节点数,而无需任何其他查询(如上所述).
2. 在给定级别的节点上强加订单.其他解决方案是无序的.

Answer 1

您可能还会考虑我在回答中所描述的Closure Table设计什么是将平台解析成树的最有效/优雅的方法？

创建/删除/移动节点所需的调用:

• 关闭= 1

获得树所需的电话:

• 关闭= 1

获取节点/祖先路径所需的调用:

• 关闭= 1

获取子节点数所需的调用:

• 关闭= 1

获取节点深度所需的调用:

• 关闭= 1

需要DB字段:

• Adjancency = 1个字段/行
• Path = 1个字段/行
• MPTT = 2或3个字段/行
• Closure =额外表格中的2或3个字段.该表的最坏情况为 O(n ^ 2)行,但远少于大多数实际情况.

还有其他一些注意事项:

支持无限深度:

• 邻接=是
• MPTT =是
• 路径=没有
• 关闭=是的

支持参照完整性:

• 邻接=是
• MPTT =没有
• 路径=没有
• 关闭=是的

我还在我的演示文稿中介绍了Closure Table,其中包括SQL和PHP的分层数据模型,以及我的书,SQL Antipatterns:避免数据库编程的陷阱.