gpt4 book ai didi

sql - 管理 SQL 中的层次结构 : MPTT/nested sets vs adjacency lists vs storing paths

转载 作者:行者123 更新时间:2023-12-02 02:30:56 26 4
gpt4 key购买 nike

有一段时间我一直在思考如何最好地处理 SQL 中的层次结构。由于对邻接列表的限制和 MPTT/嵌套集的复杂性感到沮丧,我开始考虑简单地将关键路径存储为简单的 node_key/node_key/... 字符串。我决定整理一下这三种技术的优缺点:

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

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

获取树所需的调用次数:

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

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

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

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

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

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

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

必填数据库字段:

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

结论

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

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

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

更新:

以下是 MPTT 至少可以做的两件事,而存储路径解决方案则无法做到:

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

最佳答案

您还可以考虑我在 What is the most efficient/elegant way to parse a flat table into a tree? 的回答中描述的闭包表设计。

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

  • 关闭 = 1

获取树所需的调用:

  • 关闭 = 1

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

  • 关闭 = 1

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

  • 关闭 = 1

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

  • 关闭 = 1

必填数据库字段:

  • 相邻 = 1 个字段/行
  • 路径 = 另外 1 个字段/行
  • MPTT = 2 或 3 个以上字段/行
  • 闭包 = 额外表中的 2 或 3 个字段。该表在最坏情况下有 O(n^2) 行,但远少于大多数实际情况。

还有其他一些考虑因素:

支持无限深度:

  • 相邻=是
  • MPTT = 是
  • 路径=否
  • 关闭=是

支持引用完整性:

  • 相邻=是
  • MPTT = 否
  • 路径=否
  • 关闭=是

我还在演示中介绍了 Closure Table Models for Hierarchical Data with SQL and PHP ,和我的书,SQL Antipatterns Volume 1: Avoiding the Pitfalls of Database Programming .

关于sql - 管理 SQL 中的层次结构 : MPTT/nested sets vs adjacency lists vs storing paths,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8196175/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com