私はいくつかのオブジェクトを分類するためのモデルを作ろうとしています。Django treebeard AL、NS、MPの違いは何ですか
django-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
だから、区切り文字としてドットを使用して、そのインデックスを格納することができ、アダムスは、それが最初のレベルで1ノードを指す、1.2.1パスを持っているため、完全な名前は、ウィリアム・ブレイク・アダムスであることを知っている - ウィリアム - レベル2のノード1.2に - ブレイク - レベル3のノード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
ノードの子を注文しないようにする必要がある場合は、単に親を格納するだけでよいことに注意してください。アダムスは、彼のフルネームを見つけるためにヌルまで再帰的に彼のすべての祖先を得ることができます。
ネストされたセットとは、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
ここでの数字は、例えばツリーに割り当てられる方法です右の値を大きくし、左の値でソートします。
各モデルには長所と短所があります。どちらを使用するかは、アプリケーション、使用しているデータベース、最も頻繁に行う操作の種類によって異なります。あなたは良い比較hereを見つけることができます。
比較ではあまり一般的ではない（私は他の実装についてはわかりませんが、私自身の）第4のモデルについて言及し、いくつかの言葉で説明するのは非常に複雑です：マトリックスエンコーディングによる入れ子の間隔。
ネストされたセットに新しいノードを挿入するときに、そのノードを先行するすべてのノードをトラバーサルで再列挙する必要があります。ネストされた間隔の背後にあるアイデアは、任意の2つの整数の間に無限の有理数があるので、新しいノードをその前後のノードの一部として格納できるということです。分数の保存と照会は厄介なことがあり、これは2x2行列でこれらの分数を変換する行列エンコーディング技術につながります。ほとんどの演算は一見では分かりませんが非常に効率的ないくつかの行列代数によって行うことができます。
ツリービートは、冗長性のないマテリアライズド・パス、ネストしたセットおよび隣接リストのそれぞれの非常に簡単な実装を備えています。 django-mpttは実際にはネストセットと隣接リストを組み合わせて使用しています。親へのリンクも保持しているため、子をより効率的に照会することができ、誰かが台無しになった場合に備えてツリーを再構築できます。