nietypowa struktura drzewiasta - indeksowanie Opcje

[dughi]

Mam pytanie dot. ogólnie baz danych - czy warto ogromną tabelę pociąć dodatkowymi kolumnami (około 5cioma) pod względem cech w nich zawartych na klastry o których wyświetlenie najczęściej będzie żądał użytkownik czy zamieścić tylko relację do określonego rekordu będącego niepowtarzalną kombinacją wartości tych 5ciu kolumn. Co tak naprawdę przyśpieszy indeksowanie i odczyt.

Mam przykład - istnieje ogromna tabelę z ścieżkami i nazwami plików gdzie w 5 ciu kolumnach jest zapisana ścieżka w postaci "litera dysku","katalog_1","katalog_2",katalog_3","katalog_4" a następnie "nazwa pliku" i standardowo jakieś "ID" wiersza.

Tego czego chce użytkownik przeważnie to mieć zestawienie plików zawartych w katalogach i wszystkich podkatalogach danej lokalizacji. Zatem dając zapytanie o zawartość "litera dysku" ma od razu wszystkie nazwy plików na wybranym dysku bez przeszukiwania drzewka, podobnie precyzując zapytanie co do katalogów szybko znajduje pasujące rekordy - wystarczy zapytanie o "katalog_2"=cośtam i mam wszystkie nazwy plików w tym katalogu i niżej w podkatalogach bo one też w "katalog_2" mają nazwę cośtam.

Jednak jest to duża nadmiarowość - wiem iż najlepiej byłoby utworzyć niepowtarzalną kombinacje dotycząca danej lokalizacji w osobnej tabeli i id do tego rekordu tzw id_lokalizacji umieścić w wspomnianej ogromnej tabeli z nazwami plików - jednak co wtedy z indeksowaniem i szybkim wyszukiwaniem - dostajemy szybko jedynie zbiór id lokalizacji będących niżej w strukturze od miejsca zapytania z tabeli lokalizacyjnej , aby jednak zwrócić nazwy plików id_lokalizacji należy powiązać z tabelą z nazwami plików co pewnie jest czasochłonne bo takie rozwiązanie nie indeksuje tak tabeli z nazwami plików jak pocięcie jej na klastry poprzez dodanie wspomnianych kolumn z powtarzającymi się cechami umożliwiającymi od razu wyłowienie rekordów z daną cechą - czyli plików znajdujących się w danym katalogu lub podkatalogu danego katalogu.

Przeszukałem internet i za głupi jestem na to aby określić co będzie lepsze, dodam iż struktura drzewa nie będzie nigdy zmieniana - najwyżej dojdą nowe odnogi a limit ilości poziomów nie stanowi utrudnienia co decyduje według mnie o możliwości zastosowania takiej metody, w pozostałych 99% przypadków pasowało by użyć lepszych drzewiastych metod ale na tę okazję ta może być najszybsza a mi o szybkość chodzi.

[cojack]

Powiem Ci tak, z szybkością to na sucho nigdy nie wiesz jak to będzie, dopóki sobie sam tego nie napiszesz i nie sprawdzisz wszystkich założeń to się nie dowiesz. Zgadywać to wiesz można 6 w totka. Twoje założenie trochę ni jak ma się do normalizacji danych przetrzymywanych w bazie. Dlaczego gdy masz 5 kolumn z nazwami katalogów, nie przechowasz tego w jednej kolumnie w postaci tablicy? Nie wiem jak jest z tablicami w mysql, to może po prostu w postaci ciągu ( ale tu z wydajnością będzie gorzej ) i eksplodować string

[erix]

Przeszukałem internet i za głupi jestem na to aby określić co będzie lepsze, dodam iż struktura drzewa nie będzie nigdy zmieniana - najwyżej dojdą nowe odnogi a limit ilości poziomów nie stanowi utrudnienia co decyduje według mnie o możliwości zastosowania takiej metody, w pozostałych 99% przypadków pasowało by użyć lepszych drzewiastych metod ale na tę okazję ta może być najszybsza a mi o szybkość chodzi.

Hmm, z tego co pamiętam, to systemy plików utrzymujące tablice alokacji na bazach utrzymywały coś w deseń relacyjny.

I tu trzeba postąpić dwojako - założyłeś, że pliki mogą należeć tylko do jednego katalogu, a nie uwzględniłeś tego, że w systemie plików mogą pojawić się dowiązania symboliczne. Zostawiam to Tobie.

Zakładając jednak, że jeden plik może należeć do dokładnie jednego katalogu, wystarczy Ci zbudować odpowiednie drzewo na płaskiej strukturze w bazie. Jak dobrze zindeksujesz, to będziesz miał wydajnościowo całkiem przyzwoicie. I proponowałbym tu użycie InnoDB, bo MySQL - w przypadku jakichś wymagających blokowania operacji - blokuje całą tabelę, a nie tylko rekord.

Jakie drzewo? Nie pamiętam konkretnie nazwy, ale był gdzieś algorytm z podziałem na poddrzewa; dzisiaj gdzieś to czytałem, tylko nie bardzo chce mi się już szukać; po keywordzie powinieneś trafić. I drzewo budujesz wg struktury katalogowej. Na liściach zapisujesz sobie identyfikator pliku, a potem zwykłym JOIN-em dociągasz niezbędne o nim informacje.

Summa summarum, wystarczą dwie tabele. Wydajność? Kwestia dobrania odpowiedniego algorytmu zapisu drzewa, masz do wyboru kilka, ale proponowałbym poddrzewa, albo BST, albo zwykłe zapisywanie przez kolumnę order/depth (słowa-klucze, jak coś ).

[Mchl]

Ogólnie jak masz możliwość i rzeczywiście duże drzewa, to doinstaluj sobie to:
http://openquery.com/products/graph-engine