jakiś czas temu zainteresowała mnie metoda przechowywania wszelkiego rodzaju struktur drzewiastych w bazach danych.
dla wyjaśnienia – struktura drzewiasta jest to taki uporządkowany zbiór danych gdzie każdy element ma swój element nadrzędny, chyba, że jest elementem najwyższego rzędu.
dając przykłady z życia – drzewami są opisane wszelkiego rodzaju hierarchie – służbowe, kategorie (np. w sklepie internetowym), różnego rodzaju podziały. drzewami są też wiadomości na forach dyskusyjnych – a dokładniej – w drzewa są poukładane wątki z tych wiadomości.
ogólnie – struktury drzewiaste mają sporo zastosowań.
z tego powodu stały się one obiektem mojego zainteresowania, testów i badań. o struktury drzewiaste pytam potencjalnych pracowników na rozmowie kwalifikacyjnej.
w czasie swojej pracy z "drzewami" wyodrębniłem kilka metod które kiedyś już opisałem (link do http://www.dbf.pl/faq/tresc.html?rozdzial=1#o1_9), ale tu postaram się opisać je dokładniej i podając przy okazji wyniki pewnych testów na wydajność.
ze względu na obfitość materiału tekst ten podzielę na kilka wpisów: wstęp (to co czytacie), następnie po jednym wpisie na każdą z opisywanych metod, potem jakieś podsumowanie i na koniec kilka uwag praktycznych do wybranej przeze mnie metody.
ponieważ testowanie wydajności powinno odbywać się na sporych zestawach danych, a jednocześnie pokazywanie "o co mi chodzi" powinno być na możliwie małych ilościach – na potrzeby tego tematu przygotowałem 2 zupełnie różne zestawy danych:
1. małe drzewko w celach dydaktycznych:
to drzewko, zgodnie z konwencjami stosowanymi w tym dokumencie, ma następujące elementy:
- sql
- sql.oracle
- sql.oracle.linux
- sql.oracle.linux.glibc2
- sql.oracle.linux.glibc1
- sql.oracle.solaris
- sql.oracle.windows
- sql.postgresql
- sql.postgresql.linux
2. spory zestaw danych pobrany z katalogu dmoz – lista kategorii
dane z dmoza poddałem obróbce usuwając z nich znaki spoza zestawu A-Za-z0-9_, i ustawiając separator elementów drzewa na ".".
powstała lista elementów ma 478,870 elementów.
ścieżki z dmoz zawierają od 3 do 247 znaków, największe zagłębienie w drzewo jest w elemencie Regional.North_America.United_States.New_York.Localities.N.New_York_City.Brooklyn.Society_and_Culture.Religion.Christianity.Catholicism.Eastern_Rites.Maronite
w celu porównania wydajności różnych metod zapisu drzew będę testował następujące scenariusze testowe:
- pobranie listy elementów głównych (top-levelowych)
- pobranie elementu bezpośrednio "nad" podanym elementem
- pobranie listy elementów bezpośrednio "pod" podanym elementem
- pobranie listy wszystkich elementów "nad" danym elementem (wylosowanym)
- pobranie listy wszystkich elementów "pod" danym elementem (wylosowanym)
- sprawdzenie czy dany element jest "liściem" (czy ma pod-elementy)
- pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element
dodatkowo zostanie sprawdzona wielkość tabel i indeksów na założonej strukturze danych.
dla porównania – zapis w postaci takiej jak w pliku źródłowym zajmuje:
– tabela dmoz: 57,319,424 bajtów
– index pkey: 8,609,792 bajtów
– unikalny indeks ścieżki: 51,888,128 bajtów
tak więc – w ciągu najbliższego czasu będę pokazywał kolejne metody oraz wyniki ich testów.
A jaki jest średni poziom zagłębienia?
okolo 7.