27

オブジェクトを分類するためのモデルを作成しようとしています。

私はすでに django-mptt を使用して関連するカテゴリを簡単に取得しようとしましたが、現在、さまざまなソリューションを検索して最適なものを見つけています。

具体化されたパス、隣接リスト、およびネストされたセットの主な違いは何ですか。ウィキペディアは短い答えをくれませんでした。私が知っているのは、おそらく mptt がネストされたセットであるということだけです...

誰かが私にそれを一言で説明できますか?

4

1 に答える 1

60

いくつかの言葉で説明するよりも、例を使って説明する方が簡単です。名前を格納するサンプル ツリーを考えてみましょう。

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) を指すパスがあるためです。11.21.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 は、実際にはネストされたセットと隣接リストを組み合わせて使用​​します。これは、親へのリンクも保持し、それを使用して子をより効率的にクエリし、誰かが台無しにした場合にツリーを再構築するために使用できるためです。

于 2012-04-20T02:45:40.247 に答える