Witam

Załóżmy że mamy duże drzewo poszukiwań, niekoniecznie chodzi o
drzewa binarne, ani o idealnie zrównoważone, może być to 'dowolne
sensowne' drzewo poszukiwań. Załóżmy dalej, że na jednym komputerze nie
mieści się w pamięci RAM, trzeba użyć wielu komputerów. W dodatku,
komputery można dynamicznie dostawiać lub usuwać. Drzewko
powinno samo rozpoznać że jakiś komputer zginął i trzeba jego
dane zreplikować na innym komputerze, albo że jakiś komputer
przybył i można go wykorzystać.

Dobre zaprojektowanie i implementacja takiej struktury wydaje się
bardzo trudna. Co myślicie na ten temat?

Pozdrawiam

do góry

On Sunday, April 3, 2016 at 5:26:46 PM UTC+2, M.M. wrote:
> Witam
>
> Załóżmy że mamy duże drzewo poszukiwań, niekoniecznie chodzi o
> drzewa binarne, ani o idealnie zrównoważone, może być to 'dowolne
> sensowne' drzewo poszukiwań. Załóżmy dalej, że na jednym komputerze nie
> mieści się w pamięci RAM, trzeba użyć wielu komputerów. W dodatku,
> komputery można dynamicznie dostawiać lub usuwać. Drzewko
> powinno samo rozpoznać że jakiś komputer zginął i trzeba jego
> dane zreplikować na innym komputerze, albo że jakiś komputer
> przybył i można go wykorzystać.
>
> Dobre zaprojektowanie i implementacja takiej struktury wydaje się
> bardzo trudna. Co myślicie na ten temat?

Czasochłonna na pewno. Pomyśl o istniejącym, sprawdzonym rozwiązaniu.
Np. http://redis.io/topics/partitioning

w.

do góry

On Monday, April 4, 2016 at 8:55:32 AM UTC+2, Wojciech Muła wrote:
> On Sunday, April 3, 2016 at 5:26:46 PM UTC+2, M.M. wrote:
> > Witam
> >
> > Załóżmy że mamy duże drzewo poszukiwań, niekoniecznie chodzi o
> > drzewa binarne, ani o idealnie zrównoważone, może być to 'dowolne
> > sensowne' drzewo poszukiwań. Załóżmy dalej, że na jednym komputerze nie
> > mieści się w pamięci RAM, trzeba użyć wielu komputerów. W dodatku,
> > komputery można dynamicznie dostawiać lub usuwać. Drzewko
> > powinno samo rozpoznać że jakiś komputer zginął i trzeba jego
> > dane zreplikować na innym komputerze, albo że jakiś komputer
> > przybył i można go wykorzystać.
> >
> > Dobre zaprojektowanie i implementacja takiej struktury wydaje się
> > bardzo trudna. Co myślicie na ten temat?
>
> Czasochłonna na pewno. Pomyśl o istniejącym, sprawdzonym rozwiązaniu.
> Np. http://redis.io/topics/partitioning
>
> w.

Dziękuję za przypomnienie o Redisie. :)

Kiedyś trochę interesowałem się tym serwerem. Może nie
dotarłem do wszystkich szczegółów w dokumentacji, może
od tamtej pory coś nowego dodali. Z tego co pamiętam,
zniechęciły mnie dwie rzeczy:

1) Brak możliwości zdefiniowania tabel. Jeśli czegoś nie
pomyliłem, to autorzy zalecali przechowywanie w pamięci
każdego rekordu jako osobną hash-table. Może Redis
jest na tyle sprytnie zaimplementowany, że zachowuje
wydajność przy takim rozwiązaniu. Osobiście jednak myślę, że
gdy w jakiejś tabeli mamy 100mln rekordów (to się przekłada
na założenie 100mln maleńkich hash-table), to wydajnie
działał nie będzie.

2) Brak możliwość zakładania indeksów do sortowania, za wyjątkiem
sort-set. Niemniej sort-set działa tylko na floatach (właściwie
to na parze [dowolny typ, float], ale sortowanie jest wg floatów.
Jeśli dobrze zrozumiałem, to inne dane trzeba za każdym razem
sortować.

Pozdrawiam

do góry