Month: January 2007

drzewa w sql’u – wstęp

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.

two for the money / podwójna gra

obejrzałem sobie tę (dosyć nową (2005) w sumie) produkcję.
ocena ogólna – około 7/10. film nie jest zły. jest nawet dobry. ogląda sie go przyjemnie.
jedynym problemem tego filmu jest to, że spodziewałem się więcej. w roli głównej al pacino. człowiek legenda. heat (gorączka) oglądam co jakiś czas by zobaczyć kawał wspaniałego kina. ojciec chrzestny, adwokat diabła (film zebrał takie sobie oceny, ale rola ala w nim jest niesamowita).
tu – oczywiście nadal jest tym samym diabłem. świetnym. tyle, że trochę jednak starszym. mającym swoje problemy.
na dokładkę do ala w filmie jest rene russo – z mojego punktu widzenia znana głównie z zabójczej broni 3 i 4, ale zdarzyło jej się zagrać też w innych, nie najgorszych, filmach.
no i trzeci aktor pierwszoplanowy – matthew mcconaughey. ciekawe ile z was kojarzy nazwisko. mnie sie on głównie kojarzy z rolą w świetnym kontakcie (contact) z jodie foster.
i rene i matthew zagrali poprawnie. w/g mnie przemiana brandona w john'a jest mało przekonująca (spokojnie, nie zdradzam tu nic tajnego). russo jest zdecydowanie bardziej przekonująca – może dlatego, że ta rola powstała dla niej i z myślą o niej jako odtwórczyni 🙂
kończąc – co by się nie rozpisywać i nie zdradzać nic z fabuły – film jest przyjemny. nie jest to arcydzieło kina światowego, ale spędziłem miłe 2 godzinki oglądając go. drugi raz nie zamierzam, ale żałować, nie żałuję.