オブジェクトを分類するためのモデルを作成しようとしています。
私はすでに django-mptt を使用して関連するカテゴリを簡単に取得しようとしましたが、現在、さまざまなソリューションを検索して最適なものを見つけています。
具体化されたパス、隣接リスト、およびネストされたセットの主な違いは何ですか。ウィキペディアは短い答えをくれませんでした。私が知っているのは、おそらく mptt がネストされたセットであるということだけです...
誰かが私にそれを一言で説明できますか?
オブジェクトを分類するためのモデルを作成しようとしています。
私はすでに django-mptt を使用して関連するカテゴリを簡単に取得しようとしましたが、現在、さまざまなソリューションを検索して最適なものを見つけています。
具体化されたパス、隣接リスト、およびネストされたセットの主な違いは何ですか。ウィキペディアは短い答えをくれませんでした。私が知っているのは、おそらく mptt がネストされたセットであるということだけです...
誰かが私にそれを一言で説明できますか?
いくつかの言葉で説明するよりも、例を使って説明する方が簡単です。名前を格納するサンプル ツリーを考えてみましょう。
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
マテリアライズド パスとは、各ノードがエンコードされたフル パスを格納することを意味します。たとえば、ドットを区切り文字として使用してインデックスを保存できます
Name Path
William 1
Jones 1.1
Blake 1.2
Adams 1.2.1
Tyler 1.3
Joseph 2
Miller 2.1
Flint 2.2
したがって、Adams はそのフルネームが William Blake Adams であることを知っています。これは、最初のレベルのノード (William) からレベル 2 のノード (Blake)、およびレベル 3 のノード (Adams 1.2.1
) を指すパスがあるためです。1
1.2
1.2.1
隣接リストとは、いくつかの隣接ノードへのリンクを維持することによってツリーが格納されることを意味します。たとえば、誰が親で誰が次の兄弟かを保存できます。
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 null
ノードの子を順序付けたままにしておく必要がない場合は、親を格納するだけでよいことに注意してください。これで、Adams は null になるまですべての祖先を再帰的に取得して、フルネームを見つけることができます。
入れ子になったセットとは、ツリーを DFS 順にトラバースする際に各ノードにインデックス (通常は左と右の値) を割り当てて各ノードを格納することを意味するため、その子孫がそれらの値の範囲内にあることがわかります。サンプル ツリーに番号を割り当てる方法は次のとおりです。
1 William 10
2 Jones 3
4 Blake 7
5 Adams 6
8 Tyler 9
11 Joseph 16
12 Miller 13
14 Flint 15
そして、次のように保存されます。
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 15
そのため、Adams は、左下の値と右の値が高い人をクエリすることで祖先を見つけ、左の値で並べ替えることができます。
各モデルには長所と短所があります。どちらを使用するかは、アプリケーション、使用しているデータベース、および最も頻繁に行う操作の種類によって異なります。ここで良い比較を見つけることができます。
この比較では、あまり一般的ではなく (私自身の実装以外は知りません)、簡単に説明すると非常に複雑な 4 番目のモデルについて言及しています: マトリックス エンコーディングによるネストされた間隔。
ネストされたセットに新しいノードを挿入すると、トラバーサルでその前にいるすべての人を再列挙する必要があります。ネストされた間隔の背後にある考え方は、任意の 2 つの整数の間に無数の有理数があるため、新しいノードを前のノードと次のノードの分数として格納できるということです。分数の格納とクエリは面倒な場合があり、これは行列エンコード手法につながります。これは、これらの分数を 2x2 行列に変換し、ほとんどの操作は、一見すると明らかではありませんが非常に効率的な行列代数によって実行できます。
Treebeard には、具体化されたパス、ネストされたセット、および隣接リストのそれぞれが非常に簡単に実装されており、冗長性はありません。django-mptt は、実際にはネストされたセットと隣接リストを組み合わせて使用します。これは、親へのリンクも保持し、それを使用して子をより効率的にクエリし、誰かが台無しにした場合にツリーを再構築するために使用できるためです。