January 1st, 2007 by depesz | Tags: | 2 comments »
Did it help? If yes - maybe you can help me?

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:

  1. pobranie listy elementów głównych (top-levelowych)
  2. pobranie elementu bezpośrednio "nad" podanym elementem
  3. pobranie listy elementów bezpośrednio "pod" podanym elementem
  4. pobranie listy wszystkich elementów "nad" danym elementem (wylosowanym)
  5. pobranie listy wszystkich elementów "pod" danym elementem (wylosowanym)
  6. sprawdzenie czy dany element jest "liściem" (czy ma pod-elementy)
  7. 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.

  1. 2 comments

  2. # sg
    Jan 1, 2007

    A jaki jest średni poziom zagłębienia?

  3. Jan 1, 2007

    okolo 7.

Leave a comment