管理SQL中的层次结构:MPTT/嵌套集vs邻接列表和存储路径
一段时间以来，我一直在思考如何最好地处理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至少可以做的两件事情，存储路径解决方案无法做到：
- 允许计算每个节点的子节点计数，而不需要任何其他查询(上面已经提到)。
- 在给定的级别上对节点施加命令。其他解决方案是无序的。
回答 2
Stack Overflow用户
发布于 2011-11-19 19:18:07
您还可以考虑我在对将平面表解析为树的最有效/最优雅的方法是什么？的答复中描述的闭包表设计
创建/删除/移动节点所需的调用：
- 闭包=1
获取树所需的调用：
- 闭包=1
获取到节点/祖先的路径所需的调用：
- 闭包=1
获取子节点数所需的调用：
- 闭包=1
获取节点深度所需的调用：
- 闭包=1
所需DB字段：
- Adjancency =多一个字段/行
- Path =多一个字段/行
- MPTT =2或3个字段/行
- 闭包=额外表中的2或3个字段。这个表有O(n^2)行最坏的情况，但远小于大多数实际情况下的情况。
还有几个其他考虑因素：
支持无限深度：
- 邻接=是
- MPTT = yes
- 路径= no
- 闭包=是
支持参考完整性：
- 邻接=是
- MPTT = no
- 路径= no
- 闭包=是
我还在我的演示文稿使用SQL和PHP的分层数据模型和我的书SQL Antipatterns第1卷:避免数据库编程的缺陷中介绍了闭包表。
Stack Overflow用户
发布于 2011-11-19 19:18:23
你的结论的问题在于它忽略了与树木打交道所涉及的大部分问题。
通过将一项技术的有效性降低到“调用的数量”，您实际上忽略了所有被充分理解的数据结构和算法试图解决的问题，即执行速度最快、内存和资源足印不足的问题。
对SQL服务器的“调用次数”似乎是一个很好的度量(“尽量少看代码”)，但如果结果是一个程序从未完成、运行缓慢或占用大量空间，那么它实际上是一个无用的度量。
通过将路径与每个节点一起存储，您不会创建树状数据结构。相反，您正在创建一个列表。树被设计为优化的任何操作都会丢失。
这可能很难用小的日期集(在很多情况下，一个小树的列表更好)，尝试一些大小为500,1000，10k的数据集的例子-你会很快明白为什么存储整个路径不是一个好主意。
https://stackoverflow.com/questions/8196175
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号