nietypowa struktura drzewiasta - indeksowanie

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.

IMHO
katalogi:

• id
• parentid
• pelna_sciezka np. 'C:\Windows\System'

pliki:

• id
• id_katalogu
• nazwa_pliku

struktura drzewiasta

ID PARENT_ID NAME

odpada ze względu na wydajność

tabela z nazwami pliku ma około 10k rekordów lokalizacji w drzewie około 600 pracujący użytkownicy około 30-50, potrzeba mi prostej i możliwie najszybszej metody.

LOL a co niby jedna wielka tabela z każdym katalogiem w osobnym polu będzie bardziej wydajna?

no właśnie w tym leży problem - pod względem wyszukiwania nazw plików w danej lokalizacji oraz poniżej wydaje mi się iż lepiej jeśli będzie się to odbywało w oparciu o zindeksowaną kolumnę bo pytając przykładowo o kolumnę "katalog_1"=nazwa123 od razu mamy podane wszystkie nazwy plików w katalogu nazwa123 oraz podkatalogach, w przypadku zastosowania struktury drzewiastej rodzić-dziecko najpierw należało by określić które katalogi są poniżej w strukturze a następnie wybrać rekordy z tabeli z nazwami plików po indeksach katalogów. Do tego mnogość identycznych wpisów w kolumnie "katalog_1" zawierających tą samą nazwę - wiem że to duplikowanie i nadmiarowość informacji ale może być to dobre do indeksowania.

No właśnie to o czym napisałeś... Nadmiarowość - co bedzie jak trzeba będzie zmienić nazwę któregoś katalogu? i na której pozycji go szukać? Kat1, Kat2, Kat3 czy Kat4? Do tego pomyśl co będzie, jak nagle trzeba będzie dodać kolejny poziom np Kat5? Korzystając z tego co podał AdamPL nie będzie z tym problemu... Robisz zapytanie, które rekurencyjnie zagłębia się w strukturę katalogów jednocześnie zapisując do jakiejś tablicy/listy id kolejno odwiedzanych katalogów. A potem dajesz drugie zapytanie w ktorym każesz sobie zwrócić listę plików, które znajdują się w którymkolwiek z tych katalogów... do tego moża dodać zeby zwracał także listę podkatalogów w tym katalogu.

poslugiwanie sie schematem id-parentId w bazie i szukanie rekurencyjne/petla to totalne nieporozumienie przy duzej ilosci danych, sa rozwiazania usprawniajace ten proces
prostym i wydajnym jest wprowadzenie dodatkowych pol zwyczajowo nazywanych Left, Right (lub Lt, Rt) typu int, ktore odpowiednio opisuja kazdy wezel w drzewie
umozliwia to poznij szybkie wybieranie poddrzewa danego wezla, lub proste wyszukanie sciezki do root
oczywiscie zawsze sa minusy, tutaj kosztowne jest dodanie, zmiana polozenia, usuniecie wezla, tzn. wymaga to przenumerowania wszystkich rekordow, ale z drugiej strony do modyfikacji sa int'y, jednak trzeba tez pamietac ze update wszystkich rekordow moze blokowac inne operacje
wiec jesli operacie CUD (w kontekscie polozenia wezla) beda zadkie to jest to zdecydawanie bardzo dobry algorytm, poza tym przy 10k rekotdow to i tak powinno migiem sie wykonywac

nie pamietam czy ma to jakas specjalna nazwe, ale znalazlem przyklady
http://articles.sitepoint.com/article/hierarchical-data-database/2
http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/
jesli to za malo, generalnie szukaj hasla"sql hierarchical data"

massther napisał(a)

poslugiwanie sie schematem id-parentId w bazie i szukanie rekurencyjne/petla to totalne nieporozumienie przy duzej ilosci danych, sa rozwiazania usprawniajace ten proces
prostym i wydajnym jest wprowadzenie dodatkowych pol zwyczajowo nazywanych Left, Right (lub Lt, Rt) typu int, ktore odpowiednio opisuja kazdy wezel w drzewie
umozliwia to poznij szybkie wybieranie poddrzewa danego wezla, lub proste wyszukanie sciezki do root
oczywiscie zawsze sa minusy, tutaj kosztowne jest dodanie, zmiana polozenia, usuniecie wezla, tzn. wymaga to przenumerowania wszystkich rekordow, ale z drugiej strony do modyfikacji sa int'y, jednak trzeba tez pamietac ze update wszystkich rekordow moze blokowac inne operacje
wiec jesli operacie CUD (w kontekscie polozenia wezla) beda zadkie to jest to zdecydawanie bardzo dobry algorytm, poza tym przy 10k rekotdow to i tak powinno migiem sie wykonywac

nie pamietam czy ma to jakas specjalna nazwe, ale znalazlem przyklady
http://articles.sitepoint.com/article/hierarchical-data-database/2
http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/
jesli to za malo, generalnie szukaj hasla"sql hierarchical data"

dzięki za odpowiedź,
tak widziałem to rozwiązanie podobnie jak takie z osobna tabelą definicji połączeń
http://www.eioba.pl/a71964/drzewa_w_sql

dodam parę rzeczy, zamiast nazwy katalogu będzie id do tabeli z nazwą (modyfikowalną) nigdy nie będzie potrzeba budowy 5tego poziomu ani przeniesienia - to jest istotne. tabela z nazwą będzie posiadała strukturę ID Parent_ID NAZWA CLASS

gdzie Parent_ID będzie służyła do głównie do bajeranckiego rysowana drzewka -
natomiast właściwe operacje będą wykonywane przez filtrowanie tabeli głównej np. 3ci select bar ="abcdf" i będzie posiadał ID 123 wtedy wczytane będą rekordy z 123 w 3 kolumnie - w/g mnie dużo szybciej. Definicja klasy posłużyć by miała do tego aby wybór 1 selecta zmienił dostępne opcje w drugim etc czyli w drugim pojawia się class+1 i do tego parent_ID ma być równy temu co w pierwszej liście. Zatem zmiana nazwy lokalizacji będzie możliwa a indexowanie po ID podlokalizacji powinno znacznie przyśpieszyć działanie bazy niż tradycyjne przeszukiwanie drzewka i wybór rekordów z drugiej tabeli. Strukturę drzewiastą zostawiamy na etapie wyboru lokalizacji i definicji zapytania. Czy dobrze kombinuję biorąc pod uwagę że nie będzie modyfikacji struktury a co najwyżej same nazwy się zmienią, oraz poziomy się nie rozrosną ??