Django treebeard AL，NS，MP之间有什么区别？ [英] Django treebeard what are differences between AL, NS, MP
问题描述
我已经尝试使用django-mptt轻松检索相关类别，现在我正在搜索不同的解决方案，找到最好的。
我找不到物化路径，邻接列表和嵌套集之间的主要区别。维基百科没有给我一个简短的答案，所有我知道的是mptt可能是嵌套集...
任何人都可以用几句话向我解释吗？ >
使用示例更容易解释，而不是用几个字。考虑样本树，存储名称：
William
Jones
Blake
亚当斯
泰勒
约瑟夫
米勒
弗林特
物化路径每个节点存储其完整路径编码。例如，您可以使用点作为分隔符来存储其索引
名称路径
William 1
琼斯1.1
布莱克1.2
亚当斯1.2.1
泰勒1.3
约瑟夫2
米勒2.1
弗林特2.2
所以，亚当斯知道它的完整路径是Wiliam Blake Adams，因为它有1.2.1，指向第一级的第一个级别 - William - 第2级的第二个节点 - 布莱克 - 第3节的第1个节点 - 亚当斯。
邻接列表表示通过保留与某些相邻节点的链接来存储树。例如，您可以存储谁是父母，谁是下一个兄弟姐妹。
姓名父母下一张
William null Joseph
琼斯William Blake
布莱克·威廉·泰勒
亚当斯布莱克null
泰勒William null
约瑟夫null null
米勒约瑟夫弗林特
弗林特约瑟夫null
请注意，如果我们不需要保留一个节点的子节点，它可能只是存储父节点的简单。现在亚当斯可以递归得到他的所有祖先，直到null找到他的全名。
嵌套集意味着你存储每个节点一些索引，通常是一个左右的值，当您以DFS顺序遍历树，因此您知道其后代属于这些值。数字将分配给示例树：
1 William 10/ pre>
2琼斯3
4布莱克7
5亚当斯6
8泰勒9
11约瑟夫16
12米勒13
14 Flint 15
它将被存储为：
右
威廉1 10
琼斯2 3
布莱克4 7
亚当斯5 6
泰勒8 9
约瑟夫11 16
米勒12 13
Flint 14 15
所以，现在亚当斯可以通过查询谁的下一个left和一个较高的正确值，并按左边的值排序。
每个模型都有其优缺点。选择使用哪一个取决于您的应用程序，您正在使用的数据库以及您最常使用什么样的操作。您可以找到一个很好的比较这里。
比较提到了第四个不是很常见的模型（我不知道任何其他实现，但我不知道自己的），非常复杂用几个字来解释：通过矩阵编码的嵌套间隔。
当您在嵌套集中插入新节点时，必须重新枚举所有在其中的人在遍历中。嵌套间隔背后的想法是，任何两个整数之间都有无数个有理数，所以您可以将新节点存储为其前一个和下一个节点的一小部分。存储和查询分数可能是麻烦的，这导致矩阵编码技术，其转换了2x2矩阵中的分数，并且大多数操作可以通过一些不明显但可以非常有效的矩阵代数来完成。 / p>
Treebeard具有物化路径，嵌套集和邻接列表中每一个的非常简单的实现，没有冗余。 django-mptt实际上使用了嵌套集合和邻接列表的混合，因为它还保留到父级的链接，并且可以使用它来更有效地查询孩子，并重建树，以防其被某人弄乱。 p>
I'm trying to make a model for categorizing some objects.
I already tried using django-mptt to easily retrieve related categories, and now I'm searching different solutions to find the best one.
I can't find out though what are main differences between Materialized Path, Adjacency List and Nested Set. Wikipedia didn't give me a short answer, all I know is mptt is probably Nested Set...
Can anyone explain it to me in few words ?
解决方案It's easier to explain with examples than with a few words. Consider the sample tree, storing names:
William Jones Blake Adams Tyler Joseph Miller FlintMaterialized Path means each node stores its full path encoded. For instance, you can store its index using a dot as a delimiter
Name Path William 1 Jones 1.1 Blake 1.2 Adams 1.2.1 Tyler 1.3 Joseph 2 Miller 2.1 Flint 2.2So, Adams know its full path is Wiliam Blake Adams, because it has 1.2.1, pointing to the 1st node at first level — William — to the 2nd node at level 2 — Blake — and 1st node at level 3 — Adams.
Adjacency List means the tree is stored by keeping a link to some adjacent nodes. For instance, you can store who is the parent and who is the next sibling.
Name Parent Next William null Joseph Jones William Blake Blake William Tyler Adams Blake null Tyler William null Joseph null null Miller Joseph Flint Flint Joseph nullNotice that it could be as simple as just storing the parent, if we don't need to keep the children of a node ordered. Now Adams can get all his ancestors recursively until null to find his full name.
Nested sets means you store each node with some index, usually a left and right value, assigned to each one as you traverse the tree in DFS order, so you know its descendants are within those values. Here's how the numbers would be assigned to the example tree:
1 William 10 2 Jones 3 4 Blake 7 5 Adams 6 8 Tyler 9 11 Joseph 16 12 Miller 13 14 Flint 15And it would be stored as:
Name left right William 1 10 Jones 2 3 Blake 4 7 Adams 5 6 Tyler 8 9 Joseph 11 16 Miller 12 13 Flint 14 15So, now Adams can find its ancestors by querying who has a lower left AND a higher right value, and sort them by the left value.
Each model has its strengths and weaknesses. Choosing which one to use really depends on your application, the database you're using and what kind of operations you'll be doing most often. You can find a good comparison here.
The comparison mentions a fourth model that isn't very common (I don't know of any other implementation but my own) and very complicated to explain in a few words: Nested Interval via Matrix Encoding.
When you insert a new node in a nested set you have to re-enumerate everyone who is ahead of it in the traversal. The idea behind nested intervals is that there's an infinite number of rational numbers between any two integers, so you could store the new node as a fraction of its previous and next nodes. Storing and querying fractions can be troublesome, and this leads to the matrix encoding technique, which transforms those fractions in a 2x2 matrix and most operations can be done by some matrix algebra that isn't obvious at first sight but can be very efficient.
Treebeard has very straightforward implementations of each one of Materialized Path, Nested Sets and Adjacency Lists, with no redundancy. django-mptt actually uses a mix of Nested Sets and Adjacency Lists, since it also keeps a link to the parent and can use it to both query children more efficiently, and to rebuild the tree in case it gets messed up by someone.
这篇关于Django treebeard AL，NS，MP之间有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
