Łatwiej wytłumaczyć z przykładów niż kilka słów. Rozważ drzewo przykładowe, przechowując nazwy:
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
Ścieżka zmaterializowana oznacza, że każdy węzeł przechowuje zakodowaną pełną ścieżkę. Na przykład, można przechowywać swój indeks używając kropki jako separatora
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
So, Adams zna jego pełne imię to William Blake Adams, ponieważ ma ścieżkę 1.2.1, wskazując na węźle na pierwszym poziomie 1 - William - do węzła 1.2 na poziomie 2 - Blake - i 1.2.1 węzeł na poziomie 3 - Adams.
adjacency Lista oznacza drzewo jest przechowywana przez utrzymanie łącza do niektórych sąsiednich węzłów. Na przykład możesz zapisać, kto jest rodzicem i kto jest następnym rodzeństwem.
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
Zauważ, że może to być tak proste, jak tylko przechowywanie rodzica, jeśli nie musimy trzymać dzieci węzła zamówione. Teraz Adams może pobierać rekursywnie wszystkich swoich przodków do zera, aby znaleźć swoje pełne imię.
Zestawy zagnieżdżone oznaczają, że każdy węzeł jest przechowywany z pewnym indeksem, zwykle z lewą i prawą wartością, przypisywanym każdemu z nich podczas przemierzania drzewa w kolejności DFS, dzięki czemu wiadomo, że jego potomkowie mieszczą się w tych wartościach. Oto jak numery byłyby przypisane do przykładowego drzewa:
1 William 10
2 Jones 3
4 Blake 7
5 Adams 6
8 Tyler 9
11 Joseph 16
12 Miller 13
14 Flint 15
i byłoby przechowywane jako:
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
Więc teraz Adams może znaleźć swoich przodków, badając, który ma niższą lewej i wyższą prawą wartość i posortuj je według lewej wartości.
Każdy model ma swoje mocne i słabe strony. Wybór, którego użyć, zależy od aplikacji, używanej bazy danych i najczęściej wykonywanych operacji. Możesz znaleźć dobre porównanie here.
Porównanie wspomina o czwartym modelu, który nie jest bardzo popularny (nie znam żadnej innej implementacji, ale mojej) i bardzo skomplikowany do wyjaśnienia w kilku słowach: Zagnieżdżony interwał poprzez kodowanie Matrix.
Po wstawieniu nowego węzła w zagnieżdżonego zestawu trzeba ponownie wyliczyć wszystkich, którzy przed nim na przechodzenie. Ideą odstępów zagnieżdżonych jest to, że istnieje nieskończona liczba liczb wymiernych między dowolnymi dwiema liczbami całkowitymi, więc możesz zapisać nowy węzeł jako ułamek poprzedniego i następnego węzła.Przechowywanie i odpytywanie frakcji może być kłopotliwe, a to prowadzi do techniki kodowania macierzy, która przekształca te frakcje w matrycę 2x2, a większość operacji może być wykonana za pomocą jakiejś algebry macierzy, która nie jest oczywista na pierwszy rzut oka, ale może być bardzo wydajna.
Drzewko ma bardzo prostą implementację każdego z Zmaterializowanej Ścieżki, Zestawów Zagnieżdżonych i Listy Przyległości, bez nadmiarowości. django-mptt w rzeczywistości używa kombinacji zestawów zagnieżdżonych i list relacji, ponieważ utrzymuje również link do elementu nadrzędnego i może go użyć do skuteczniejszego sprawdzania dzieci i odbudowywania drzewa w przypadku, gdy ktoś je zepsuł.