分层数据模型：邻接表与嵌套集
我有一个产品目录。 每个类别由不同数量（深度）的子类别组成。 层数（深）未知，但我很确定不会超过 5,6 层。 数据更改比读取少得多。
问题是：哪种类型的层次数据模型更适合这种情况。 该项目基于 Django 框架，应考虑其特殊性（管理 i-face、模型处理...）。
非常感谢！
I have a product catalog. Each category consists of different number (in deep) of subcategories. The number of levels (deep) is unknown, but I quite sure that it will not be exceed of 5,6 levels. The data changes are much more rarely then reads.
The question is: what type of hierarchical data model is more suitable for such situation. The project is based on Django framework and it's peculiarities (admin i-face, models handling...) should be considered.
Many thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果您不需要频繁更新或分层排序，
嵌套集的性能会更好。如果您需要树更新或分层排序，最好使用
parent-child数据模型。它可以在
Oracle和SQL Server 2005+中轻松构建，但在MySQL中则不那么容易（但仍然可行）。Nested setsare better for performance, if you don't need frequent updates or hierarchical ordering.If you need either tree updates or hierarchical ordering, it's better to use
parent-childdata model.It's easily constructed in
OracleandSQL Server 2005+, and not so easily (but still possible) inMySQL.对于此类分层数据，我将使用改进的先序树遍历算法 MPTT。 如果您不介意对结构的更改进行一些惩罚，那么这可以在遍历树和查找子树方面提供出色的性能。
幸运的是，Django 有一个很棒的库可以实现此目的，django-mptt。 我已经在许多项目中使用了它，并取得了很大的成功。 还有 django-treebeard 它提供了几种替代算法，但我没有使用过它（而且它似乎不像 mptt 那样流行）。
I would use the Modified Preorder Tree Traversal algorithm, MPTT, for this sort of hierarchical data. This allows great performance on traversing the tree and finding children, if you don't mind a bit of a penalty on changes to the structure.
Luckily Django has a great library available for this, django-mptt. I've used this in a number of projects with a lot of success. There's also django-treebeard which offers several alternative algorithms, but I haven't used it (and it doesn't seem as popular as mptt anyway).
根据这些文章：
http://explainextend。 com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/
http://explainextend.com/2009/09 /29/adjacency-list-vs-nested-sets-mysql/
“MySQL 是四大系统（MySQL、Oracle、SQL Server、PostgreSQL）中唯一一个嵌套集模型表现出不错的性能并且可以被视为存储的分层数据。”
According to these articles:
http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/
http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/
"MySQL is the only system of the big four (MySQL, Oracle, SQL Server, PostgreSQL) for which the nested sets model shows decent performance and can be considered to stored hierarchical data."
http://www.sqlsummit.com/AdjacencyList.htm
http://www.sqlsummit.com/AdjacencyList.htm
邻接列表更容易维护，嵌套集的查询速度更快。
问题一直是，由于加载了 RBAR 的非常讨厌的“推栈”方法，将邻接列表转换为嵌套集花费了太长的时间。 因此，人们最终会在嵌套集中进行一些非常困难的维护，或者不使用它们。
现在，你也可以鱼与熊掌兼得了！ 您可以在不到 4 秒的时间内完成 100,000 个节点的转换，并在不到一分钟的时间内完成一百万行的转换！ 顺便说一句，一切都在 T-SQL 中！ 请参阅以下文章。
类固醇层次结构 #1：将邻接列表转换为嵌套集
类固醇层次结构 #2：嵌套集计算的替代品
The Adjacency List is much easier to maintain and Nested Sets are a lot faster to query.
The problem has always been that converting an Adjacency List to Nested Sets has taken way too long thanks to a really nasty "push stack" method that's loaded with RBAR. So people end up doing some really difficult maintenance in Nested Sets or not using them.
Now, you can have your cake and eat it, too! You can do the conversion on 100,000 nodes in less than 4 seconds and on a million rows in less than a minute! All in T-SQL, by the way! Please see the following articles.
Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets
Hierarchies on Steroids #2: A Replacement for Nested Sets Calculations