Eu tenho o problema muito comum de criar um índice para uma matriz de strings no disco. Em resumo, preciso armazenar a posição de cada string na representação em disco. Por exemplo, uma solução muito ingênua seria uma matriz de índice da seguinte maneira:

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

O que diz que a primeira cadeia está na posição 0, a segunda na posição 20, a terceira na posição 500 e a enésima na posição 103434.

As posições são sempre números inteiros não negativos de 64 bits em ordem seqüencial. Embora os números possam variar por qualquer diferença, na prática, espero que a diferença típica esteja dentro do intervalo de 2 ^ 8 a 2 ^ 20. Espero que esse índice seja mmap'ed na memória e as posições serão acessadas aleatoriamente (suponha distribuição uniforme).

Eu estava pensando em escrever meu próprio código para fazer algum tipo de codificação de delta de bloco ou outra codificação mais sofisticada, mas há muitos trade-offs diferentes entre velocidade de codificação / decodificação e espaço que eu prefiro obter uma biblioteca de trabalho como ponto de partida e talvez até se contentar com algo sem qualquer personalização.

Alguma dica? Uma biblioteca c seria ideal, mas um c ++ também me permitiria executar alguns benchmarks iniciais.

Mais alguns detalhes, se você ainda estiver seguindo. Isso será usado para construir uma biblioteca semelhante ao cdb (http://cr.yp.to/cdb/cdbmake.html) no topo da biblioteca cmph (http://cmph.sf.net). Em suma, é para um grande mapa associativo baseado em leitura de disco com um pequeno índice na memória.

Como é uma biblioteca, não tenho controle sobre entrada, mas o caso de uso típico que desejo otimizar tem milhões de centenas de valores, tamanho de valor médio nos poucos intervalos de kilobytes e valor máximo em 2 ^ 31.

Para o registro, se eu não encontrar uma biblioteca pronta para uso, pretendo implementar a codificação delta em blocos de 64 inteiros com os bytes iniciais especificando o deslocamento do bloco até o momento. Os blocos em si seriam indexados com uma árvore, dando-me o tempo de acesso O (log (n / 64)). Há muitas outras opções e eu preferiria não discuti-las. Estou realmente ansioso para usar o código em vez de ideias sobre como implementar a codificação. Eu ficarei feliz em compartilhar com todos o que eu fiz uma vez que eu tenho que trabalhar.

Agradeço sua ajuda e deixe-me saber se você tem alguma dúvida.