Czy wiesz, na czym polega wzorzec drzewa w MongoDB?
Dane przechowywane w bazie tworzą często większe struktury. Przykładowo, lista pracowników firmy i ich hierarchia, asortyment produktów w podziale na kategorie, miasta wraz z województwami. Wymieniać można długo. Takie relacje są dla nas bardzo naturalne. W MongoDB możemy taką przynależność jednego obiektu do drugiego przedstawić za pomocą wzorca drzewa. W zależności od implementacji zyskujemy łatwiejsze poruszanie się po dokumentach albo ograniczamy liczbę zapytań do bazy. Trzeba jednak mieć na uwadze, że przedstawienie danych w taki sposób ma swoją cenę. Każdy przechowywany dokument będzie musiał posiadać dodatkowe pole z informacją o swoim dziecku i/lub rodzicu albo potomkach. Taka zmiana oznacza rozszerzenie samego dokumentu oraz konieczność utrzymywania nowych pól. Jednak o tym później. Na razie przyjrzyjmy się, jak zaimplementować wzorzec drzewa.
Spróbujmy skupić się na przykładzie ze sklepem i jego asortymentem. Powiedzmy, że struktura dla wybranych produktów wygląda następująco:
Po samym grafie już widać, że dane tworzą strukturę drzewa. W bazie możemy taką strukturę przedstawić na kilka sposobów w zależności od potrzeb.
Drzewo z referencją na dzieci
W tym podejściu każdy obiekt ma dodatkowe pole z powiązanymi do niego kategoriami / produktami. Więc struktura może wyglądać następująco:
{ "_id" : "Super TV", "children" : []}
{ "_id" : "HD TV", "children" : []}
{ "_id" : "Telewizory", "children" : [ "Super TV", "HD TV" ]}
{ "_id" : "TV i Video", "children" : [ "Telewizory" ]}
{ "_id" : "Zimna Lodówka", "children" : []}
{ "_id" : "AGD Wolnostojące", "children" : [ "Zimna Lodówka" ]}
{ "_id" : "RTV i AGD", "children" : [ "AGD Wolnostojące", "TV i Video" ]}
{ "_id" : "Elektronika", "children" : [ "RTV i AGD" ]}
{ "_id" : "Sklep", "children" : [ "Elektronika" ]}
Przechowanie danych w następujący sposób daje nam dodatkową informację o powiązanych podkategoriach dla obiektu, który pobraliśmy.
db.getCollection('categories').find({_id: "RTV i AGD"});
---
{ "_id" : "RTV i AGD", "children" : [ "AGD Wolnostojące", "TV i Video" ] }
Możemy również sprawdzić rodzica dla wybranej kategorii
db.getCollection('categories').find({children: "RTV i AGD"})
---
{ "_id" : "Elektronika", "children" : [ "RTV i AGD" ] }
Drzewo z referencją na rodzica
W poprzednim podejściu, pobierając dokument z wybranym telewizorem niestety nie dostaniemy informacji, do jakiej kategorii należy produkt. Konieczne jest przeszukanie wszystkich kategorii, czy w dzieciach mają nasz telewizor. By zapobiec dodatkowemu zapytaniu, możemy niejako odwrócić strukturę i zamiast referencji na dzieci danego obiektu przechowywać referencję na rodzica.
{ "_id": "Super TV", "parent": "Telewizory" }
{ "_id": "HD TV", "parent": "Telewizory" }
{ "_id": "Telewizory", "parent": "TV i Video" }
{ "_id": "TV i Video", "parent": "RTV i AGD" }
{ "_id": "Zimna Lodówka", "parent": "AGD Wolnostojące" }
{ "_id": "AGD Wolnostojące", "parent": "RTV i AGD" }
{ "_id": "RTV i AGD", "parent": "Elektronika" }
{ "_id": "Elektronika", "parent": "Sklep" }
{ "_id": "Sklep", "parent": null }
Mając obiekt Super TV, bez dodatkowych żądań wiemy, że znajduje się on w kategorii Telewizory.
db.getCollection('categories').find({_id: "Super TV"});
---
{ "_id" : "Super TV", "parent" : "Telewizory" }
Drzewo z listą przodków
Referencja tylko na rodzica może być mało pomocna, jeśli potrzebujemy pełnej ścieżki do danego obiektu.
By rozwiązać ten problem, pole rodzica zastępujemy listą przodków.
{ "_id" : "Super TV", "ancestors" : [ "Telewizory", "TV i Video", "RTV i AGD", "Elektronika", "Sklep" ] }
{ "_id" : "HD TV", "ancestors" : [ "Telewizory", "TV i Video", "RTV i AGD", "Elektronika", "Sklep" ] }
{ "_id" : "Telewizory", "ancestors" : [ "TV i Video", "RTV i AGD", "Elektronika", "Sklep" ] }
{ "_id" : "TV i Video", "ancestors" : [ "RTV i AGD", "Elektronika", "Sklep" ] }
{ "_id" : "Zimna Lodówka", "ancestors" : [ "AGD Wolnostojące", "RTV i AGD", "Elektronika", "Sklep" ] }
{ "_id" : "AGD Wolnostojące", "ancestors" : [ "RTV i AGD", "Elektronika", "Sklep" ] }
{ "_id" : "RTV i AGD", "ancestors" : [ "Elektronika", "Sklep" ] }
{ "_id" : "Elektronika", "ancestors" : [ "Sklep" ] }
{ "_id" : "Sklep", "ancestors" : [] }
Teraz pobierając Super TV wiemy bez dodatkowych zapytań, że znajduje się on pod ścieżką: Sklep → Elektronika → RTV i AGD → TV i Video → Telewizory.
db.getCollection('categories').find({"_id": "Super TV"})
---
{ "_id" : "Super TV", "ancestors" : [ "Telewizory", "TV i Video", "RTV i AGD", "Elektronika", "Sklep"] }
Drzewo z zagnieżdżonymi zbiorami
Specyficzny przykład dla równie specyficznych potrzeb. Drzewo z zagnieżdżonymi zbiorami można zastosować, kiedy zestaw danych jest bardzo rzadko modyfikowany i potrzebujemy wydajnie przeszukiwać i pobierać całe podzbiory struktury. Tym razem rozszerzamy dokument o 3 pola:
parent- definiuje pozycje w strukturze,left- używane do wyszukiwania,right- używane do wyszukiwania.
Pola left i right musimy sami wyliczyć, przechodząc całe drzewo od korzenia przez wszystkie liście i z powrotem do korzenia i nadając kolejne indeksy poszczególnym elementom.
{ "_id" : "Super TV", "parent" : "Telewizory", "left" : 11.0, "right" : 12.0 }
{ "_id" : "HD TV", "parent" : "Telewizory", "left" : 9.0, "right" : 10.0 }
{ "_id" : "Telewizory", "parent" : "TV i Video", "left" : 8.0, "right" : 13.0 }
{ "_id" : "TV i Video", "parent" : "RTV i AGD", "left" : 7.0, "right" : 14.0 }
{ "_id" : "Zimna Lodówka", "parent" : "AGD Wolnostojące", "left" : 4.0, "right" : 5.0 }
{ "_id" : "AGD Wolnostojące", "parent" : "RTV i AGD", "left" : 3.0, "right" : 6.0 }
{ "_id" : "RTV i AGD", "parent" : "Elektronika", "left" : 2.0, "right" : 15.0 }
{ "_id" : "Elektronika", "parent" : "Sklep", "left" : 1.0, "right" : 16.0 }
{ "_id" : "Sklep", "parent" : null, "left" : 0.0, "right" : 17.0 }
Teraz możemy wyszukać cały podzbiór dla kategorii TV i Video:
var kategoria = db.getCollection('categories').findOne( { _id: "TV i Video" } );
db.categories.find( { left: { $gt: kategoria.left }, right: { $lt: kategoria.right } } );
---
{ "_id" : "Super TV", "parent" : "Telewizory", "left" : 11.0, "right" : 12.0 }
{ "_id" : "HD TV", "parent" : "Telewizory", "left" : 9.0, "right" : 10.0 }
{ "_id" : "Telewizory", "parent" : "TV i Video", "left" : 8.0, "right" : 13.0 }
Koszt każdego z rozwiązań
Jak wspomniałem na początku, zastosowanie wzorca drzewa ma swoją cenę. Modyfikacje struktury danych mogą być bardzo kosztowne. Musimy pilnować, by dodane pola były spójne z nową strukturą. Powiedzmy, że musimy rozbić dział RTV i AGD na dwa osobne RTV i AGD. Co musimy dodatkowo zrobić, żeby zachować spójność?
- drzewo z referencją na dzieci - szukamy rodzica dla dawnego
RTV i AGD, usuwamy tę kategorię z dzieci i dodajemy dwie nowe - konieczna będzie modyfikacja jednego dodatkowego dokumentu (rodzica kategoriiRTV i AGD), - drzewo z referencją na rodzica - szukamy dzieci dla dawnego
RTV i AGDi przypisujemy im nowego rodzicaRTVlubAGD- konieczna będzie modyfikacja wszystkich dzieci kategoriiRTV i AGD, - drzewo z listą przodków - szukamy wszystkich potomków i zastępujemy im przodka
RTV i AGDnowymRTVlubAGD- konieczna będzie modyfikacja wszystkich potomków kategoriiRTV i AGD, - drzewo z zagnieżdżonymi zbiorami - należy dokonać zmian jak dla drzewa z referencją na rodzica i przeliczyć wszystkie indeksy oraz zmodyfikować wszystkie elementy kolekcji.
Jak widać, liczba dokumentów dotkniętych zmianą może być bardzo duża. Dlatego wzorzec ten jest używany w przypadkach, gdzie struktura jest niezmienna lub zmienia się bardzo rzadko.
Podsumowanie
Nie ma jednej najlepszej implementacji tego wzorca. Co będzie najlepsze, zależy od naszych potrzeb i od tego, po jakie dane najczęściej sięgamy i jak je wyszukujemy. Nic nie stoi na przeszkodzie, by połączyć rozwiązania i rozszerzyć obiekt zarówno o listę przodków jak i o listę dzieci. Pamiętajmy jednak, że wzorzec ten wymusza dodatkową pracę przy zmianach struktury danych.
Przydatne linki
Podobne wpisy
