Mam bardzo częsty problem z tworzeniem indeksu dla tablicy łańcuchów wewnątrz dysku. Krótko mówiąc, muszę przechowywać pozycję każdego łańcucha w reprezentacji dysku. Na przykład bardzo naiwnym rozwiązaniem byłaby tablica indeksu w następujący sposób:

uint64 idx [] = {0, 20, 500, 1024, ..., 103434};

Który mówi, że pierwszy ciąg jest na pozycji 0, drugi na pozycji 20, trzeci na pozycji 500 i n-ty na pozycji 103434.

Pozycje są zawsze nieujemnymi 64 bitami liczb całkowitych w kolejności sekwencyjnej. Chociaż liczby mogą się różnić w zależności od różnicy, w praktyce oczekuję, że typowa różnica będzie mieściła się w przedziale od 2 ^ 8 do 2 ^ 20. Spodziewam się, że ten indeks zostanie zapisany w pamięci, a pozycje będą dostępne losowo (zakładając równomierny rozkład).

Zastanawiałem się nad napisaniem własnego kodu do wykonywania pewnego rodzaju blokowego kodowania delta lub innego bardziej zaawansowanego kodowania, ale istnieje tak wiele różnych kompromisów między szybkością kodowania / dekodowania a przestrzenią, że wolałbym, aby punktem wyjścia była biblioteka robocza a może nawet zadowolić się czymś bez żadnych dostosowań.

Jakieś wskazówki? Biblioteka c byłaby idealna, ale c ++ pozwoliłoby mi na uruchomienie niektórych początkowych testów.

Jeszcze kilka szczegółów, jeśli nadal śledzisz. Będzie to użyte do zbudowania biblioteki podobnej do cdb (http://cr.yp.to/cdb/cdbmake.html) na górze biblioteki cmph (http://cmph.sf.net). W skrócie, chodzi o dużą mapę asocjacyjną opartą tylko na dysku, z małym indeksem w pamięci.

Ponieważ jest to biblioteka, nie mam kontroli nad danymi wejściowymi, ale typowy przypadek użycia, który chcę zoptymalizować, ma miliony setek wartości, średni rozmiar wartości w zakresie kilku kilobajtów i maksymalną wartość 2 ^ 31.

Dla rekordu, jeśli nie znajdę biblioteki gotowej do użycia, zamierzam zaimplementować kodowanie delta w blokach 64 liczb całkowitych z początkowymi bajtami określającymi do tej pory przesunięcie bloku. Same bloki byłyby indeksowane drzewem, dając mi czas dostępu O (log (n / 64)). Jest zbyt wiele innych opcji i wolałbym ich nie omawiać. Naprawdę nie mogę się doczekać gotowego kodu, a nie pomysłów na implementację kodowania. Z przyjemnością podzielę się ze wszystkimi tym, co zrobiłem, kiedy już to działa.

Dziękuję za pomoc i daj mi znać, jeśli masz jakiekolwiek wątpliwości.