W pracy ze strony
http://www.kaims.pl/~goluch/doc/mgr-two-sided.pdf
na stronie 53 wspomniana jest funkcja indeksująca. Pozwala ona na błyskawiczne wyszukiwanie spośród milionów rekordów z bazy danych. W bazie znajdują się rekordy z pozycjami z gry po kilku posunięciach. Każda ta pozycja w bazie jest inna. Chodzi o szybkie porównanie (tak jak przeszukiwanie połówkowe) czy szukana pozycja występuje w bazie danych. Niestety pozycje wymienione w bibliografii pod numerami 19 i 32 są niedostępne w bibliotece uniwersyteckiej. Może ktoś spotkał się dokładnie z tego typu problemem? Potrzebuję opis matematyczny tej funkcji indeksującej i zapis wykorzystującego ją algorytmu w postaci pseudoprogramu.
0
0
jeśli wyobrazisz sobie tabele jako tablicę rekordów od 1 do n, gdzie każdy rekord ma swój numer, to indeks w najprostszej postaci to tablica par pole_na_ktorym_jest_indeks<->rekord_w_tablicy posortowana wg pole_na_ktorym_jest_indeks. Wyszukiwanie w posortowanej liście jest dużo szybsze niż przeszukiwanie całej tabeli. Jeśli chcesz jeszcze bardziej przyśpieszyć wyszukiwanie to zamiast posortowanej tablicy możesz indeks zapisywać w postaci b-drzewa. Dlaczego tak to się robi. Bo przy dodawaniu rekordu dodaje się go na końcu pliku z danymi a wpis w pliku z indeksem musi zostać wstawiony w odpowiednie miejsce. Poza tym indeksy zazwyczaj zajmują znacznie mniej miejsca niż właściwe dane i o ile same właściwe dane mogą się nie mieścić w całości w pamięci o tyle indeksy zamiast odczytywać za każdym razem można wczytać do pamięci i tam na nich operować.
Poza tym to czy indeks przyśpieszy wyszukiwanie zależy też od tego jak bardzo zróżnicowane są dane w polu, które indeksujesz. Jeśli będziesz miał 1000000 rekordów ale w nich w polu indeksowanym będzie tylko 10 RÓŻNYCH wartości to taki indeks nie ma większego sensu.
To jest bardzo ogólne tłumaczenie ale myślę, że samą ideę powinieneś załapać