1. 
   Eu desencorajo fortemente o uso do Redis para isso. Você estará armazenando uma tonelada de dados extras de ponteiro e, se decidir que deseja fazer consultas mais complicadas, como SELECT WHERE first_name LIKE 'jon%' você vai ter problemas. Você também precisará criar índices extras e muito grandes que cruzem várias colunas, caso deseje pesquisar dois campos ao mesmo tempo. Basicamente, você precisará continuar hackeando e reengenhando uma estrutura de pesquisa. Seria muito melhor usar o Elastic Search ou Solr, ou qualquer uma das outras estruturas já criadas para fazer o que você está tentando fazer. Redis é incrível e tem muitos bons usos. Este não é um deles.
   
2. 
   Aviso à parte, para responder à sua pergunta real:acho que você seria melhor servido usando uma variante de sua primeira solução. Use um único conjunto classificado por índice, mas apenas converta suas letras em números. Converta suas letras para algum valor decimal. Você pode usar o valor ASCII ou apenas atribuir a cada letra um valor de 1 a 26 em ordem lexicográfica, supondo que esteja usando o inglês. Padronize, para que cada letra ocupe o mesmo comprimento numérico (assim, se 26 for seu maior número, 1 será escrito "01"). Em seguida, basta anexá-los com um ponto decimal na frente e usá-lo como sua pontuação por índice (ou seja, "chapéu" seria ".080120"). Isso permitirá que você tenha um mapeamento de 1 para 1 ordenado corretamente entre palavras e esses números. Ao pesquisar, converta de letras para números e, em seguida, você poderá usar todas as funções de conjunto classificado do Redis, como ZRANGEBYSCORE sem precisar reescrevê-los. As funções do Redis são escritas de maneira muito, muito otimizada, então é muito melhor usá-las sempre que possível em vez de escrever as suas próprias.